Source-linked AI summary
Iterative Quantum Amplitude Estimation
Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner
TL;DR
The paper addresses how to obtain QAE’s quadratic Monte Carlo speedup without the resource demands of QPE. It introduces IQAE, based solely on Grover iterations, and rigorously analyzes its convergence. IQAE achieves the speedup up to a double-logarithmic factor and outperforms tested QPE-free variants empirically, with QAES requiring about 108 times more oracle queries in the reported comparison.
Problem
Removing QPE could reduce QAE’s qubit and circuit-depth requirements, but prior QPE-free variants lacked rigorous correctness proofs or had impractically large constants.
Method
IQAE replaces QPE with iterative Grover queries and uses interval-based power selection to improve amplitude estimates with high confidence.
Results
IQAE empirically outperforms the tested alternatives; in the reported comparison, QAES requires about 108 times more oracle queries than IQAE.
Takeaways & Limitations
IQAE provides a QPE-free route to quadratic speedup with rigorous error and convergence bounds and substantially smaller constants than QAES.
Abstract
from arXiv · showhide
We introduce a new variant of Quantum Amplitude Estimation (QAE), called Iterative QAE (IQAE), which does not rely on Quantum Phase Estimation (QPE) but is only based on Grover's Algorithm, which reduces the required number of qubits and gates. We provide a rigorous analysis of IQAE and prove that it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation. Furthermore, we show with an empirical study that our algorithm outperforms other known QAE variants without QPE, some even by orders of magnitude, i.e., our algorithm requires significantly fewer samples to achieve the same estimation accuracy and confidence level.
I. INTRODUCTION
QAE aims to improve Monte Carlo amplitude estimation by replacing classical sampling with quantum procedures. The introduction motivates removing QPE, reviews existing QPE-free variants, and presents IQAE as a rigorously analyzed algorithm with strong empirical performance.
- Classical Monte Carlo estimation scales as O(1/√M), whereas QAE achieves O(1/M) using M quantum samples.
- Removing QPE from canonical QAE could reduce qubit and circuit-depth requirements, lowering resource demands for practical applications.
- MLAE replaces QPE with Grover iterations and MLE, while another approach replaces QPE with the Hadamard test.
- Prior QPE-free approaches lacked rigorous correctness proofs, making their potential quantum advantage difficult to compare.
- QAES rigorously achieves quadratic speedup without logarithmic factors, but its very large constants may make it impractical.
- IQAE is proposed as a QPE-free variant that empirically outperforms tested alternatives and achieves the desired asymptotic behavior up to a multiplicative logarithmic factor.
- IQAE requires iterative quantum queries and cannot be parallelized, whereas MLAE permits parallel queries but has a potential speedup limited to at most a factor of two.
II. QUANTUM AMPLITUDE ESTIMATION
QAE estimates an unknown amplitude through Grover-based quantum samples, with canonical QAE using QPE and ancilla-controlled powers of the Grover operator. QPE-free variants differ in how they select powers and combine measurements, trading rigorous guarantees, asymptotic scaling, and practical constants.
- QAE estimates an unknown amplitude a from an operator A by applying the Grover-related operator Q, whose applications are counted as quantum samples or oracle queries.
- Canonical QAE uses m ancilla qubits, sets M = 2^m quantum samples, applies geometrically increasing controlled powers of Q, and then performs a QFT.
- With probability at least 8/π^2 ≈81%, canonical QAE attains estimation error O(1/M), implying a quadratic speedup over classical Monte Carlo simulation.
- MLE can remove canonical QAE’s grid restriction by estimating θa from ancilla observations and can provide confidence intervals through a likelihood ratio.
- QPE-free QAE variants differ mainly in how they choose powers k of Q and combine the resulting measurements into an estimate of a.
- MLAE uses powers k = 2^j and MLE, with Fisher information O(Nshots M^2) and a lower error-scaling bound Ω(1/(√Nshots M)), but no upper error bound is provided.
- QAES iteratively adapts Q powers, provides a rigorous relative-error upper bound, and achieves query complexity O(log(1/α)/ϵ), but with very large constants.
- IQAE provides rigorous performance analysis while accepting a multiplicative log(2/α log2(π/4ϵ)) factor, whose constants are described as much smaller than QAES’s.
III. ITERATIVE QUANTUM AMPLITUDE ESTIMATION
IQAE iteratively estimates the amplitude by selecting progressively larger Grover powers whose scaled confidence interval remains within one cosine half-plane. This design supports rigorous accuracy and query-complexity guarantees while avoiding QPE.
- Algorithmic rationale: IQAE estimates sin^2((2k+1)θa) for successive Grover powers and updates the confidence interval for the unknown amplitude.The last-qubit measurement probability is used to refine the interval around θa.
- FindNextK: FindNextK selects the largest feasible K = 4k + 2 at least twice the previous factor while keeping [Kθl, Kθu] modulo 2π within one half-plane.Restricting the interval to either [0, π] or [π, 2π] makes cosine inversion unambiguous.
- Confidence control: The algorithm combines estimates across rounds using confidence intervals and a union bound to control the total failure probability.IQAE supports Chernoff-Hoeffding or Clopper-Pearson confidence intervals.
- Guarantees: IQAE terminates after at most ⌈log2(π/8ϵ)⌉ rounds, with each round containing at most Nmax(ϵ, α)/Nshots iterations.The resulting interval satisfies θu − θl ≤ 2ϵ.
- Guarantees: The midpoint estimate ã = (al + au)/2 satisfies |a − ã| ≤ ϵ with confidence 1 − α.The theorem provides a corresponding upper bound on total oracle applications.
- Complexity and refinements: The theorem’s oracle bound is loose because it uses Chernoff-Hoeffding intervals, while Clopper-Pearson intervals can reduce the constant overhead by a factor of 3.The overall computational complexity, including classical processing, scales in the same way as the query complexity.
IV. RESULTS
The experiments compare IQAE with MLAE, QAES, canonical QAE, and classical Monte Carlo under matched estimation settings. IQAE performs best overall, while QAES is worst in practice despite its asymptotic behavior.
- Comparative results: IQAE outperforms MLAE, QAES, canonical QAE, and classical Monte Carlo in the tested 95% confidence comparisons.The experiments estimate a = 1/2 using absolute-error confidence intervals.
- Comparative results: QAES requires about 10^8 times more oracle queries than IQAE on average and performs worse than classical Monte Carlo at the tested target accuracies.This occurs despite QAES having the best asymptotic behavior among the compared methods.
- Comparative results: MLAE performs comparably to IQAE, but exact maximum-likelihood estimation becomes numerically challenging as m increases.Canonical QAE with MLE postprocessing performs slightly worse than IQAE and MLAE.
- Comparative results: Applying QPE in the QAE setting provides no observed advantage in these experiments and increases complexity relative to IQAE.IQAE therefore reduces required qubits and gates while improving the measured performance.
- Experimental design: The empirical study evaluates all a ∈ {i/100 | i = 0, ..., 100}, ϵ ∈ {10^-i | i = 3, ..., 6}, and α ∈ {1%, 5%, 10%} with Nshots = 100.Average and worst-case oracle complexity are evaluated over the considered amplitude values.
- Schedule analysis: For the first round, Nshots = 100 can be too small to achieve as large a Ki+1/Ki ratio as desired, sometimes requiring another iteration with the same Ki.The k-schedule analysis reports average, standard deviation, minimum, and maximum ratios over 1,000 repetitions.
V. CONCLUSION AND OUTLOOK
IQAE provides a rigorous, QPE-free approach based solely on Grover iterations, with empirical performance advantages and several open questions concerning bounds, parallelization, and parameter choices.
- IQAE uses only Grover iterations, does not require QPE, and supports rigorous error and convergence bounds.
- IQAE empirically outperforms the other tested QAE variants, with QAES requiring about 108 times more oracle queries on average.
- IQAE achieves quadratic speedup up to a log(2/α log2(π/4ϵ))-factor, while QAES has optimal asymptotic complexity with very large constants.
- IQAE provides an absolute error bound, leaving a relative error bound for future research.
- Parallel QAE implementations and the optimal IQAE parameter settings remain open research directions.
- The proof’s upper bound nearly matches actual performance, although whether a tighter analytic bound exists remains open.
Appendix A: Canonical QAE with MLE
Canonical QAE models measurement outcomes with a parameterized distribution and improves amplitude estimates through maximum-likelihood postprocessing. Likelihood-ratio intervals provide the preferred confidence-interval construction in the reported tests.
- MLE formulation: MLE estimates the unknown amplitude parameter by maximizing the likelihood of the observed QAE samples.The likelihood is often maximized in log form for numerical convenience.
- MLE formulation: QAE samples correspond to grid points generated by the measurement distribution, with grid values xi = sin2(iπ/M).The distribution assigns probabilities to sampled grid points and is fitted to the QAE data.
- Postprocessing behavior: The QAE output is the median of the samples, whereas the MLE is the distribution peak and lies very close to the true amplitude.In the illustrated setting, the MLE is shown as the global maximum of the log-likelihood.
- Postprocessing behavior: The MLE search uses bisection over the neighboring grid-point intervals identified by the QAE estimate.As N approaches infinity, this search returns the exact amplitude independently of the number of qubits m.
- Confidence intervals: Likelihood-ratio confidence intervals were more reliable in the tests than intervals based on observed Fisher information.The likelihood-ratio statistic is approximately chi-squared distributed for large sample numbers and supports a two-sided hypothesis test.
Appendix B: Proof of Theorem 1
Theorem 1’s proof combines round-wise Chernoff-Hoeffding guarantees with a union bound and derives sufficient bounds on rounds, shots, and oracle calls. The analysis also establishes the interval transformation and the schedule conditions needed for progress.
- Proof strategy: The proof uses a union bound to combine per-round Chernoff-Hoeffding estimates and control the total error probability by α.An upper bound T on the number of rounds is then used to bound total query complexity.
- Interval transformation: IQAE converts amplitude intervals into angle intervals, so achieving |θu − θl|/2 ≤ ϵ suffices for amplitude accuracy ϵ.The functions gL(θi) encode the resulting angle error as a function of the current estimate and parameter L.
- Round progression: Applying Qki scales the angle θa by Ki = 4ki + 2, and the next Grover power is chosen so the scaled confidence interval remains usable.The construction exploits cosine invertibility on a selected half-plane.
- Complexity bounds: The proof defines T = ⌈logr(rLmax/2ϵ)⌉ and shows T ≥ t, making T an upper bound on the required number of rounds.The no-overshooting condition also yields a stronger bound involving the shots in the final round.
- Complexity bounds: Lemma 1 supplies a sufficient Nmax condition ensuring that the growth factor qi reaches at least r, with the analysis using r = 2 and an optimized L∗.The resulting bound is converted into a numerical form after substituting Lmax = L∗.
- Practical qualification: In practice, IQAE may use fewer than Nmax shots per iteration, so one round can contain several while-loop iterations before the algorithm progresses.Nmax is an upper bound chosen to support the proof’s sufficient growth condition, not necessarily the practical measurement count.
Appendix C: A variant of the theorem 1 for Clopper-Pearson interval method
The Clopper-Pearson variant proves correctness at confidence level 0.95 over a stated accuracy range and permits bounded shot allocations. Its proof requires numerical treatment because the interval depends on observed outcomes.
- Proof qualification: Clopper-Pearson intervals depend on the sampled Binomial value, preventing an analytic Nmax parameterization independent of the observations.The smallest sufficient Nmax is therefore found numerically for the required conditions at confidence level 0.95.
- Theorem conditions: The theorem assumes confidence level 1 − α = 0.95, target accuracy ϵ ≥ 2^-200, and Nshots between 1 and Nmax(ϵ, α).These are the stated conditions for the Clopper-Pearson correctness result.
- Termination and accuracy: IQAE terminates after at most ⌈log2(π/8ϵ)⌉ rounds, with each round containing at most Nmax(ϵ, α)/Nshots iterations.A round is defined as a set of iterations using the same ki.
- Termination and accuracy: The midpoint estimate ã = (al + au)/2 satisfies |a − ã| ≤ ϵ with confidence 1 − α.The guarantee follows after IQAE constructs an angle interval whose width is at most 2ϵ.