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

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.

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.