Source-linked AI summary
Quantum Approximate Counting, Simplified
Scott Aaronson, Patrick Rall
TL;DR
Approximate counting raises whether the QFT is necessary for its quadratic quantum speedup. The paper answers with a rigorous Grover-iteration-only algorithm matching BHMT’s query complexity, then generalizes it to amplitude estimation. Its guarantees include a QFT-free amplitude-estimation result under stated state and amplitude assumptions.
Problem
The paper asks whether approximate counting’s quadratic quantum speedup requires the QFT or can be obtained using purely Grover-like means.
Method
The paper replaces the QFT with Grover iterations and estimation techniques, using an adaptive approach based on narrowing the Grover-angle range.
Results
The algorithm matches BHMT’s tight approximate-counting query complexity, while its analysis is fully rigorous.
Takeaways & Limitations
The QFT-free approach also yields a generalization to amplitude estimation, a subroutine used for several quantum estimation problems.
Takeaways & Limitations
The amplitude-estimation statement assumes arbitrary n-qubit states with a real amplitude satisfying 0 < a < 1.
Abstract
from arXiv · showhide
In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of $N$ items, $K$ of them marked, their algorithm estimates $K$ to within relative error $\varepsilon$ by making only $O\left( \frac{1}{\varepsilon}\sqrt{\frac{N}{K}}\right) $ queries. Although this speedup is of "Grover" type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shor's algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.
1 Introduction
The paper asks whether approximate counting’s quadratic quantum speedup requires the QFT and presents a rigorous Grover-iteration-only alternative. It matches BHMT’s query complexity, simplifies the analysis, and extends the approach to amplitude estimation.
- Motivation: Approximate counting estimates the number K of marked items among N using the fewest possible marking queries while achieving multiplicative error ε.The query model returns whether a queried item is marked.
- Motivation: BHMT achieved a tight quadratic quantum speedup for approximate counting but relied essentially on the QFT, unlike Grover’s algorithm.Their algorithm was presented as a hybrid of Grover’s and Shor’s algorithms.
- Contribution: The paper gives the first rigorous approximate-counting algorithm based entirely on Grover iterations, with no QFT or other quantum-mechanical ingredients.Its query complexity matches BHMT’s bound.
- Contribution: The algorithm’s computational complexity exceeds its query complexity by only an O(log N) multiplicative factor.The authors suggest its simplicity may make it more amenable to near-term quantum implementation.
- Extensions: Amplitude estimation generalizes approximate counting and can provide quadratic accuracy-runtime improvements for Monte-Carlo-type estimation algorithms.The paper extends its QFT-free approach to amplitude estimation.
- Main Ideas: The approach mirrors classical biased-coin estimation: obtain a constant-factor rough estimate, then refine it to the target multiplicative accuracy.Quantumly, Grover iterations provide a “Grover coin” whose measurement probability depends on the Grover angle.
- Main Ideas: The algorithm adaptively varies Grover iterations like binary search, using the Rotation Lemma to distinguish angle ranges and converge on K.An initial preprocessing step ensures θmax/θmin ≤ 1.65, enabling the lemma’s guarantee.
2 Approximate Counting
The approximate-counting algorithm uses repeated Grover-state measurements in two stages: a rough constant-factor estimate followed by multiplicative refinement. Its analysis bounds failure probabilities and query complexity while returning an estimate with controlled relative error.
- Algorithm: The algorithm estimates K by setting θ := arcsin√(K/N), applying odd-length Grover iterations, and measuring marked-item outcomes.The measured marked-item probability is sin^2(rθ), and each circuit uses O(r) queries with O(log N) qubits.
- Algorithm: Step 1 produces bounds θmin and θmax with ratio at most 1.65, providing a constant-factor estimate of θ.When ideal behavior occurs, the bounds contain θ and satisfy θmax/θmin = 1.65.
- Correctness: The first step has ideal behavior with probability at least 1−δ/2 because early termination is bounded by δ/4 and late termination by δ/5.The proof separately analyzes insufficient and excessive observed marked-item frequencies using concentration bounds.
- Complexity and extensions: The total query complexity is O(√(N/K) log(δ^−1)) for the rough stage, with the refined stage contributing the stated Q(N,K,ε,δ) bound.The algorithm uses O(log N) qubits of space and can also identify K = 0 with high probability.
- Algorithm: Step 2 reduces the interval ratio γ by a factor of 0.9 per iteration until θmax/θmin ≤ 1 + ε/5.The resulting estimate satisfies (1−ε)K ≤ K̂ ≤ (1+ε)K.
- Correctness: Step 2 preserves θmin ≤ θ ≤ θmax with high probability and reaches the target interval after a logarithmic number of refinements.Its per-iteration failure probabilities are allocated as δt := (δε/65)·(0.9)^−t, and the union bound controls total failure.
3 Amplitude Estimation
The paper extends its QFT-free approximate-counting approach to amplitude estimation by estimating the magnitude of an inner product through Grover-based procedures. The resulting algorithm reuses the approximate-counting analysis and achieves multiplicative-error estimation.
- Amplitude Estimation: Amplitude estimation targets the magnitude a = |⟨ψ|φ⟩| for two quantum states supplied through a unitary U.The unitary prepares |ψ⟩ and marks the component orthogonal to |φ⟩.
- Reduction: The construction redefines the Grover angle as θ := arcsin a, allowing the approximate-counting argument to be reused.The paper presents this as the central reduction from amplitude estimation to approximate counting.
- Algorithm: The algorithm marks outcomes in which the final two qubits are measured as |00⟩ and returns â := 1001 · sin(θmax).These are the amplitude-estimation algorithm's marked-event rule and estimator.
- Grover-based procedure: Grover iterations rotate within a two-dimensional subspace, making the relevant measurement probability equal to sin^2(rθ).The probability of observing the designated basis state is the quantity bounded in the analysis.
- Guarantee: The analysis guarantees that θmax estimates θ within a 1+ε/5 multiplicative factor, yielding an estimate of a within a 1+ε multiplicative factor.The paper states that the final guarantee follows by a simple calculation.
4 Open Problems
The paper identifies quantum-depth-limited approximate counting as an open problem and asks whether tight bounds can be obtained when the state is measured and destroyed periodically. It also raises parallel Grover invocations as a possible direction.
- Quantum depth: A central open question is whether approximate counting has tight quantum query-complexity bounds when the state is measured and destroyed after every T queries.The question is posed as a function of the allowed quantum depth T.
- Quantum depth: The quantum-depth question is motivated by near-term quantum computers' expected limitations in sustained quantum depth and by theoretical challenges in adapting polynomial methods.The passage describes both practical and theoretical motivation.
- Parallelization: Another open direction asks whether approximate counting can retain optimal query complexity with parallel rather than sequential Grover invocations.The passage connects this direction to the algorithm of Suzuki et al.