PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Quantum Circuits for Arithmetic

Thomas Häner, Martin Roetteler, Krysta M. Svore

arXiv:1805.12445v1quant-phcs.ET

TL;DR

Quantum algorithms use function-evaluation oracles on superpositions, but missing reversible implementations leave runtime costs uncertain. The paper presents optimized circuits and a software-stack module for piecewise-smooth functions; the circuits span several functions, and a tuned inverse-square-root guess saves one Newton iteration. These circuits and resource estimates support more detailed cost analyses, while gate counts remain expensive.

  • Problem

    Quantum algorithms use classical-function oracles on superpositions, but absent reversible implementations make detailed runtime estimates difficult even when asymptotic behavior is favorable.

    Source: §I · p. 1

  • Method

    The authors combine classical high-performance-computing ideas with reversible arithmetic circuits and a Remez-based module for generating piecewise-polynomial evaluations.

    Source: §I · p. 1, §III · p. 2, §IV · p. 4

  • Results

    The circuits cover multiple mathematical functions; tuning the inverse-square-root initial guess reduces the required Newton iterations by 20-25%.

    Source: §I · p. 2, §VII · p. 5

  • Takeaways & Limitations

    The circuits and compiler module support more detailed resource analyses of quantum algorithms and automatic generation of piecewise-smooth-function oracles.

    Source: §IV · p. 4, §VII · p. 5

Abstract

from arXiv · show

Many quantum algorithms make use of oracles which evaluate classical functions on a superposition of inputs. In order to facilitate implementation, testing, and resource estimation of such algorithms, we present quantum circuits for evaluating functions that are often encountered in the quantum algorithm literature. This includes Gaussians, hyperbolic tangent, sine/cosine, inverse square root, arcsine, and exponentials. We use insights from classical high-performance computing in order to optimize our circuits and implement a quantum software stack module which allows to automatically generate circuits for evaluating piecewise smooth functions in the computational basis. Our circuits enable more detailed cost analyses of various quantum algorithms, allowing to identify concrete applications of future quantum computing devices. Furthermore, our resource estimates may guide future research aiming to reduce the costs or even the need for arithmetic in the computational basis altogether.

I. INTRODUCTION

Quantum algorithms need reversible arithmetic implementations to estimate realistic runtimes and crossover points, because function-implementation details affect constant overheads. The paper presents optimized circuits for smooth and application-specific functions, including piecewise-polynomial evaluation, and reports savings for arcsine and inverse square root.

I. INTRODUCTION

  • Quantum runtime estimates remain incomplete without reversible implementations, whose implementation details affect constant overheads and algorithm crossover points.The paper cites factoring and quantum-chemistry simulation as examples of tasks with favorable asymptotic behavior.Source: §I · p. 1
  • The paper presents quantum arithmetic circuits for integration into software stacks and discusses piecewise-polynomial implementations alongside application-specific functions.Its examples include inverse square root and arcsine.Source: §I · p. 1
  • Inverse square root and arcsine have roles in HHL and quantum rejection sampling, while tanh and inverse square root are relevant to quantum machine learning.The introduction also cites chemistry and finite-element applications involving Gaussians, sine, and cosine.Source: §I · p. 1
  • The piecewise-polynomial circuit evaluates piecewise-smooth functions accurately with low-degree polynomials, few additions and multiplications, and few intermediate registers.The paper also adapts classical high-performance-computing ideas, but notes that gate counts remain expensive despite reductions in Toffoli and qubit counts.Source: §I · pp. 1–2
  • One tuned inverse-square-root initial guess saves a Newton iteration, a 20-25% reduction, while arcsin on [−0.5, 0.5] costs about one sin invocation.For arcsin on [−1, 1], the implementation also requires a square-root evaluation.Source: §I · p. 2

II. LEARNING FROM CLASSICAL ARITHMETIC LIBRARIES

The paper adapts ideas from classical high-performance computing to reversible quantum arithmetic. It develops reversible implementations of selected classical functions and a parallel Horner approach for piecewise polynomial approximations.

II. LEARNING FROM CLASSICAL ARITHMETIC LIBRARIES

  • Classical high-performance libraries offer optimization ideas, but vectorized conditionals and loops can incur substantial overhead when adapted to quantum computation.The passage notes that quantum if-statements collapse the state vector, while vectorized classical code may require readout and case handling.Source: §II · p. 2
  • The authors adapt arcsine and fast inverse-square-root implementations to the quantum domain through reversible low-level implementations.They draw on implementations from the Cephes library and Quake III Arena.Source: §II · p. 2
  • A parallel version of the classical Horner scheme conditionally evaluates many polynomials, supporting efficient piecewise-polynomial approximation.The passage identifies the scheme as enabling polynomial evaluations in parallel.Source: §II · p. 2

III. EVALUATION OF PIECEWISE POLYNOMIAL APPROXIMATIONS

The paper evaluates polynomials reversibly and uses a label register to select among interval-specific polynomials. Parallel evaluation limits the depth cost of multiple intervals, while pebbling strategies trade registers against circuit depth.

III. EVALUATION OF PIECEWISE POLYNOMIAL APPROXIMATIONS

  • A reversible Horner evaluation stores intermediate results, multiplying the prior iterate by x and adding each classically known coefficient.Pebbling can optimize the resulting space/time trade-off.Source: §III · p. 2
  • When a high-degree minimax approximation is needed, partitioning the domain allows a different polynomial to be evaluated on each subdomain.The straightforward quantum case distinction would evaluate intervals serially, making cost grow linearly with the number of subdomains.Source: §III · p. 2
  • The LABEL gate initializes a ⌈log2(M)⌉-qubit register to encode x's subdomain, using a membership predicate and a conditional label assignment.The predicate is computed into an ancilla qubit.Source: Figure 1 · p. 3
  • With constant polynomial degree across the domain, parallel evaluation uses the label register to select interval coefficients and keeps circuit depth virtually unchanged.The parallel approach needs an extra ancilla register for the final iteration, while its small interval overhead permits low-degree approximations.Source: §III · p. 3
  • Pebbling strategies trade the number of registers, iterations, and circuit depth; dynamic programming finds optimal strategies for the sequential Horner dependency chain.Table I reports pebbling steps for fixed register and iteration counts, from which circuit width and depth can be obtained.Source: §III · p. 3, Table I · p. 3

IV. SOFTWARE STACK MODULE FOR PIECEWISE SMOOTH FUNCTIONS

The software-stack module uses the Remez algorithm to partition a user-specified interval into polynomial subdomains meeting a target accuracy. It then implements the resulting approximation with the parallel evaluation circuit.

IV. SOFTWARE STACK MODULE FOR PIECEWISE SMOOTH FUNCTIONS

  • The module uses Remez approximation within a subroutine to construct a piecewise-polynomial approximation for a piecewise-smooth function.The resulting approximation is implemented using the preceding parallel polynomial evaluation circuit.Source: §IV · p. 3
  • For a requested precision, accuracy, and register budget, the algorithm searches for subdomains whose degree-d polynomial meets the desired error.The interval is user-specified, and the degree may equivalently represent the register constraint when pebbling is not used.Source: §IV · pp. 3–4
  • It repeatedly halves and tests the interval, then binary-searches the right boundary to find the largest valid first subdomain before proceeding across the domain.The algorithm was run for various functions, target accuracies, and polynomial degrees to estimate resources.Source: §IV · p. 4

V. INVERSE SQUARE ROOT

The reversible inverse-square-root circuit adapts the fast-inverse-square-root initial-guess strategy to fixed-point arithmetic, then refines the estimate with Newton iterations. Tuning its initial-guess constants removes error peaks and can save an iteration for a target L∞ error.

V. INVERSE SQUARE ROOT

  • The classical fast-inverse-square-root strategy uses bit operations to form an initial guess, then improves it with Newton–Raphson iteration.Its bit operations shift the exponent and adjust the mantissa using a tunable magic number.Source: §V · p. 4
  • The fixed-point circuit uses a low-cost initial guess based on the first one in the input’s bit representation, followed by 2–4 Newton iterations.The approach adapts the classical fast inverse square root without relying on floating-point representation.Source: §V · p. 4
  • Tuning the initial-guess constants removes error peaks near powers of two and can save one Newton iteration for a given L∞ error.The untuned guess uses the input’s first nonzero bit but ignores its magnitude, so inputs in [1, 2) receive the same guess.Source: §V · p. 4

VI. ARCSINE

The arcsine implementation combines polynomial evaluation with a square root to handle the function’s behavior near ±1. It uses a double-angle identity outside the interval where a polynomial alone gives a good approximation.

VI. ARCSINE

  • A polynomial alone approximates arcsin(x) well on [−0.5, 0.5], but not near ±1, where the function diverges.The implementation addresses the outer range with a case distinction using the double-angle identity for |x| ≥ 0.5.Source: §VI · p. 5
  • The Cephes-style arcsine implementation combines polynomial evaluation with a double-angle identity for |x| ≥ 0.5.The case distinction handles the region near ±1 where polynomial-only approximation is unsuitable.Source: §VI · p. 5
  • The square root needed by the identity can be computed from the inverse square root as x · 1/√x = √x.The passage also notes that a square-root circuit from Ref. [22] is an alternative.Source: §VI · p. 5

VII. SUMMARY AND OUTLOOK

The paper presents quantum circuits for evaluating several mathematical functions and a parallel polynomial-evaluation circuit for automatic code generation of piecewise smooth functions. Its fixed-point building blocks keep register sizes constant, with trade-offs involving overflow, truncation error, and qubit use.

VII. SUMMARY AND OUTLOOK

  • The circuits cover inverse and ordinary square roots, Gaussians, hyperbolic tangent, exponentials, sine/cosine, and arcsine.The parallel polynomial-evaluation circuit can be embedded in a quantum compilation framework to automatically generate circuits for piecewise smooth functions in the computational basis.Source: §VII · p. 5

Appendix A: Basic circuit building blocks for fixed-point arithmetic

  • Fixed-point arithmetic keeps the total bit size and point position constant, limiting register growth while introducing over- and underflow errors.Fixed-point addition likewise keeps register size constant by allowing over- and underflow.Source: Appendix A · p. 6
  • With pre-truncation, fixed-point multiplication can use at most n controlled additions on subsets of qubits, ignoring bits beyond the n-bit result; each addition introduces error at most 1/2^(n−p).Source: Appendix A · p. 6
  • Assuming a positive multiplicand avoids conditional inversions of the input and output on every multiplication, reducing the size of circuits with many multiplications.Negative multipliers are handled with controlled subtraction conditioned on the most significant bit.Source: Appendix A · p. 7
  • The fixed-point squaring method can save n − 1 qubits by copying out and resetting each conditioned-on bit in turn.The gate counts are stated to match those for multiplication.Source: Appendix A · p. 7

Appendix B: Resource estimates for polynomial evaluation

The appendix estimates resources for reversible polynomial evaluation and its parallel piecewise version, including Toffoli counts and register requirements. It also describes inverse-square-root computation by Newton’s method, which converges when the initial guess is sufficiently close.

Appendix B: Resource estimates for polynomial evaluation

  • Evaluating a degree-d polynomial by successive multiply-accumulate steps requires d + 1 intermediate and result registers if the final addition is not in-place.Without a non-trivial pebbling strategy, this stores the intermediate results; other strategies trade fewer ancillas for more gates.Source: Appendix B · p. 7
  • The Toffoli count for a degree-d polynomial is given as a function of n, d, and p, with each fused multiply-accumulate contributing to the total.The passage gives the expanded count as 2n^2d + 3npd + 7/2nd − 3p^2d + 3pd − d.Source: Appendix B · p. 7
  • The parallel scheme initializes a label register using a comparator for each subinterval, with the procedure repeated across the M intervals.The comparator output is uncomputed, and the label initialization uses one additional qubit.Source: Appendix B · p. 7
  • Parallel evaluation of M polynomials adds label-initialization overhead to the polynomial-evaluation cost and requires (d + 1)n + ⌈log2 M⌉ + 1 qubits.The total Toffoli count is expressed as Tpoly(n, d, p) + d · Textra(M).Source: Appendix B · p. 8

Appendix C: (Inverse) Square root

  • The inverse square root is computed using Newton’s method, whose iterates converge to 1/√a when the initial guess is sufficiently close to the true solution.The appendix identifies a as the input.Source: Appendix C · p. 8

1. Reversible implementation

The reversible inverse-square-root routine starts from a low-cost initial guess and applies Newton iterations, uncomputing intermediate results after each update. Tuning the guess by exponent can save an iteration, while retaining all iterates requires additional registers.

1. Reversible implementation

  • The initial guess uses the input’s first set bit to set its exponent-dependent value, with ancillas tracking the search and supporting register initialization.The construction scans bits from most to least significant and initializes the guess using shifted constants and input values.Source: §1 · p. 8
  • Tuning the initial-guess constant as a function of the exponent costs only a few extra CNOT gates and can save an entire Newton iteration.The proposed choice distinguishes three exponent cases.Source: §1 · p. 8
  • Each Newton update squares the current iterate, multiplies by the input, subtracts that intermediate from 1.5, and multiplies by the iterate to obtain the next value.The three intermediate results are then uncomputed.Source: §1 · p. 8
  • Without pebbling, m Newton iterations require m+3 n-qubit registers because all iterates are retained until the final iteration.Source: §1 · p. 8

2. Resource estimates

The resource estimates count the arithmetic and registers used by Newton iterations and arcsine evaluation. The arcsine implementation combines polynomial approximation with an inverse-square-root-based transformation to cover its wider input domain.

2. Resource estimates

  • Each Newton iteration uses five multiplications and two additions, including operations run in reverse to clear intermediate results.Source: §2 · p. 9
  • Newton iterations use n(m+4) qubits, and the stated qubit and Toffoli requirements are upper bounds when every iteration uses full-precision arithmetic.Because Newton converges quadratically, the fixed-point bit count should increase with the iteration.Source: §2 · p. 9

Appendix D: Arcsine

  • For arcsine on [0, 0.5], polynomial evaluation alone can be used; extending to [0, 1] uses the double-angle identity and an inverse-square-root computation.The arcsine cost also includes two conditional n-bit swaps and conditional copies.Source: Appendix D · p. 9, §2 · p. 10

1. Reversible implementation

  • The reversible arcsine procedure combines polynomial evaluation with the inverse square root to extend the approximation from [0, 0.5] to [0, 1].It uses a case distinction and computes either the transformed input’s square root or the squared input before combining the polynomial result.Source: §1 · pp. 9–10

2. Resource estimates

  • Figure 6 evaluates square-root absolute error over [0, 5] at 2,000 points for m=2, 3, or 4 iterations and n=25, 35, or 50 bits, with p=5.Source: Figure 6 · p. 10

Appendix E: Results of the Reversible Simulation

The reversible circuits were implemented and tested in a simulator, with resource costs reported for piecewise polynomial function evaluation. The inverse-square-root results show benefits from tuning the initial guess, while the arcsine implementation uses polynomial and square-root subroutines.

Appendix E: Results of the Reversible Simulation

  • The circuits were implemented at gate level and tested with a reversible simulator extension to LIQUi |⟩.Source: Appendix E · p. 10

2. (Inverse) Square root

  • Tuning the inverse-square-root initial guess yields almost uniform convergence and can save one Newton iteration for a given L∞ error.The untuned guess has large rounding effects near integer powers of two; 3–5 iterations should generally suffice.Source: §2 · p. 10
  • For small x, square root converges better than inverse square root because multiplication by x regularizes the error.The error after m Newton iterations is depicted for n-bit fixed-point representations; the initial guess could be tuned to minimize error after forming x · 1/√x.Source: §2 · pp. 10–11

3. Arcsine

  • The arcsine implementation evaluates an odd polynomial in x² and multiplies by x; for x > 0.5, reduced fractional resolution produces bit-noise.The minimax polynomial degrees are 7, 13, and 17 for 3, 4, and 5 iterations, respectively.Source: §3 · p. 11

1. Piecewise polynomial approximation

  • Table II reports compute-only Toffoli counts for Gaussian, hyperbolic tangent, sin(x), exp(−x) for x ≥ 0, and arcsin(x) on [−0.5, 0.5], with uncomputation adding a factor of 2.For even/odd functions, the given degree corresponds to evaluation cost; the implemented polynomial has degree 2d or 2d + 1, respectively.Source: Table II · p. 12
Loading 1805.12445v1…