Evaluating quantum computing circuits in view of the resource costs of a quantum algorithm

1. A processor-implemented method for compiling a quantum circuit for performing an evaluation of a polynomial, the method comprising:

receiving an input comprising a polynomial function and a set of sub-intervals;

partitioning the polynomial function into the set of sub-intervals by determining whether an input value of the polynomial function falls into any of the set of sub-intervals;

computing a label register having at least one label indicative of at least one of the set of sub-intervals;

determining a polynomial interpolation for the set of sub-intervals corresponding to the input; and

using the processor generating an output including the quantum circuit to a quantum processor for execution,

wherein the quantum circuit comprises a label gate for initializing the label register and quantum gates for performing, in parallel, polynomial evaluation corresponding to each of the set of sub-intervals.

2. The processor-implemented method of claim 1 further comprising determining an overall achievable precision for any input value that falls into any of the set of intervals.

3. The processor-implemented method of claim 1 , wherein the set of sub-intervals is chosen by pre-processing the input.

4. The processor-implemented method of claim 1 , wherein the polynomial evaluation is performed in a nested fashion.

5. The processor-implemented method of claim 1 , wherein the polynomial evaluation is performed by applying a gate to load a next set of coefficients into a quantum register, while multiplying a previous set of coefficients by a variable to produce an output, and then adding the next set of coefficients to the output.

6. The processor-implemented method of claim 1 , wherein the input is divided into the set of sub-intervals to reduce an approximation error associated with the polynomial evaluation.

7. The processor-implemented method of claim 6 , wherein at least a subset of the set of intervals is fused together to reduce a quantum cost associated with the polynomial evaluation.

8. A processor-implemented method for compiling a quantum circuit for performing an evaluation of a polynomial corresponding to an input, the method comprising:

receiving by the processor an input comprising a polynomial function and an initial set of sub-intervals;

partitioning the polynomial function into the initial set of sub-intervals by determining whether an input value of the polynomial function falls into any of the initial set of sub-intervals;

computing a label register having at least one label indicative of at least one of the initial set of sub-intervals;

determining a polynomial interpolation of an initial degree d for the initial set of sub-intervals corresponding to the input;

determining whether a required target precision is achievable based on the initial degree d and the initial set of sub-intervals;

if the target precision is achievable, then generating an output including a quantum circuit to a quantum processor for execution; and

if the target precision is not achievable, then either incrementing the initial degree d or subdividing the initial set of subintervals into additional intervals until the target precision is achievable and then generating the output including the quantum circuit to the quantum processor for execution,

wherein the quantum circuit comprises a label gate for initializing the label register and quantum gates for performing, in parallel, polynomial evaluation corresponding to each of the set of sub-intervals.

9. The processor-implemented method of claim 8 , wherein the initial set of sub-intervals is chosen by pre-processing the input.

10. The processor-implemented method of claim 8 , wherein the polynomial evaluation is performed in a nested fashion.

11. The processor-implemented method of claim 8 , wherein the polynomial evaluation is performed by applying a gate to load a next set of coefficients into a quantum register, while multiplying a previous set of coefficients by a variable to produce an output, and then adding the next set of coefficients to the output.

12. The processor-implemented method of claim 8 , wherein the input is divided into the initial set of sub-intervals to reduce an approximation error associated with the polynomial evaluation.

13. The processor-implemented method of claim 8 , wherein at least a subset of the initial set of intervals is fused together to reduce a quantum cost associated with the polynomial evaluation.

14. A processor-implemented method for performing an evaluation of a polynomial, the method comprising:

receiving an input comprising a polynomial function and a set of sub-intervals;

partitioning the polynomial function into the set of sub-intervals by determining whether an input value of the polynomial function falls into any of the set of sub-intervals;

determining a polynomial interpolation for the set of sub-intervals corresponding to the input; and

using the processor generating an output including a quantum circuit for performing, in parallel, polynomial evaluation corresponding to each of the set of sub-intervals, wherein the polynomial evaluation is performed by applying a gate to load a next set of coefficients into a quantum register, while multiplying a previous set of coefficients by a variable to produce an output, and then adding the next set of coefficients to the output.

15. The processor-implemented method of claim 14 , further comprising determining an overall achievable precision for any input value that falls into any of the set of intervals.

16. The processor-implemented method of claim 14 , wherein the set of sub-intervals is chosen by pre-processing the input.

17. The processor-implemented method of claim 14 , wherein the polynomial evaluation is performed in a nested fashion.

18. The processor-implemented method of claim 14 , further comprising labeling the input value using a label indicative of one of the set of sub-intervals.

19. The processor-implemented method of claim 14 , wherein the previous set of coefficients are multiplied by a variable into a new register and the previous set of coefficients are stored as intermediate results.

20. The processor-implemented method of claim 14 , wherein the input is divided into the set of sub-intervals to reduce an approximation error associated with the polynomial evaluation, and wherein at least a subset of the set of intervals is fused together to reduce a quantum cost associated with the polynomial evaluation.