Quantum Mathematics Learning Guide 57: Quantum Amplitude Estimation, Approximate Counting, Monte Carlo and Quadratic Sampling Speedups

Quantum amplitude estimation turns the probability of a marked quantum event into a phase-estimation problem. Its promise is precise: under an appropriate oracle/query model, estimating a probability to additive error ε can require O(1/ε) coherent queries rather than the O(1/ε²) samples demanded by ordinary Monte Carlo averaging.

The algorithm sits directly above two earlier owners. Guide 10 introduced quantum phase estimation; Guide 11 introduced amplitude amplification and Grover rotations. Amplitude estimation combines those structures. A state-preparation unitary A encodes the unknown probability a as the squared length of a “good” component. A Grover-like iterate converts a into an eigenphase θ with a=sin²θ. Phase estimation, or a modern likelihood-based substitute, then estimates θ.

The speedup is a query-complexity statement. It does not automatically make every practical Monte Carlo workload quadratically faster after state preparation, arithmetic, fault tolerance, oracle construction and readout are counted. This guide keeps those assumptions explicit.

Encode probability as amplitude → build Grover rotation → convert amplitude to phase → estimate phase → map back to probability → account for query and implementation cost.

1. Encode a probability into a quantum state

Let A be a unitary state-preparation procedure acting on n+1 qubits such that

A|0⟩=√(1−a)|ψ_0⟩|0⟩+√a|ψ_1⟩|1⟩

with 0≤a≤1.

The final qubit marks “good” outcomes. Measuring it would return 1 with probability a.

If we simply repeat preparation and measurement M times, the empirical frequency estimates a with standard deviation of order 1/√M. Reaching additive error ε with constant confidence therefore costs O(1/ε²) independent samples.

2. Two-dimensional good/bad subspace

Define normalised states

|good⟩=|ψ_1⟩|1⟩

and

|bad⟩=|ψ_0⟩|0⟩.

Write

√a=sinθ, √(1−a)=cosθ

for θ∈[0,π/2]. Then

A|0⟩=cosθ|bad⟩+sinθ|good⟩.

The unknown probability has become an angle.

3. Grover iterate

Define a phase flip S_χ that changes the sign of good states and a reflection S₀ about |0…0⟩. A standard amplitude-amplification iterate is

Q=−A S_0 A† S_χ.

Inside the two-dimensional good/bad plane, Q acts as a rotation by 2θ.

Equivalently, Q has eigenvectors |ψ_±⟩ in that plane with eigenvalues

e^{±2iθ}.

This is the key conversion: a appears nonlinearly as the eigenphase of a unitary that can be queried coherently.

4. Recover amplitude from phase

If phase estimation returns an estimate θ̃ of θ, then

ã=sin²θ̃.

The map is symmetric under θ↔π−θ at the phase level, but restricting θ to [0,π/2] makes a unique.

The sensitivity is

d(sin²θ)/dθ=sin2θ.

Thus phase error δθ creates amplitude error approximately sin(2θ)δθ away from higher-order terms.

5. Canonical amplitude-estimation guarantee

Brassard, Høyer, Mosca and Tapp showed that an M-step amplitude-estimation procedure can return an estimate ã satisfying a bound of the form

|ã−a| ≤ 2π√(a(1−a))/M + π²/M²

with constant success probability in the canonical setting. [1]

The leading scaling is O(1/M), compared with O(1/√M) ordinary sampling error.

Constants, confidence amplification and the exact counting of A, A† and Q calls depend on implementation conventions.

6. Worked phase-to-amplitude example

Suppose the true good probability is a=1/4.

Then

sin²θ=1/4

so θ=π/6.

The Grover eigenphases are ±2θ=±π/3.

If a phase routine estimates θ̃=0.53 radians, then

ã=sin²(0.53)≈0.2555.

The amplitude error is about 0.0055.

7. Why ordinary Monte Carlo costs O(1/ε²)

Let X be a Bernoulli random variable with P(X=1)=a.

For M independent samples, the sample mean has variance

Var(X̄)=a(1−a)/M≤1/(4M).

Standard deviation therefore scales as 1/√M.

To make RMS error O(ε), set M=O(1/ε²).

This square-law sampling cost is exactly what quantum amplitude estimation attacks in the coherent-query model.

8. Quadratic query improvement

Quantum amplitude estimation uses coherent powers of Q to resolve θ to O(1/M), yielding amplitude error O(1/M).

Thus additive error ε requires

M=O(1/ε)

queries in the ideal model.

This is called a quadratic speedup in precision because 1/ε replaces 1/ε².

It is not an exponential speedup and does not remove logarithmic confidence factors or implementation overhead.

9. Approximate counting

Suppose f:{0,…,N−1}→{0,1} marks K solutions.

Prepare the uniform superposition

(1/√N)Σ_x|x⟩

and mark f(x)=1 as good.

Then

a=K/N.

Estimate a and return

K̃=Nã.

This is quantum approximate counting. It estimates how many marked inputs exist without enumerating them individually.

10. Worked counting example

Let N=4096 and suppose K=320.

The marked fraction is

a=320/4096=0.078125.

If amplitude estimation returns ã=0.0790, then

K̃=4096×0.0790≈323.6.

A sensible integer estimate would be about 324, with uncertainty derived from the amplitude-estimation confidence interval rather than from rounding alone.

11. Expectation values as amplitudes

Monte Carlo problems often ask for

μ=E[f(X)]

with f scaled into [0,1].

Prepare a quantum state encoding the distribution P(x), then rotate an ancilla so that conditional good probability equals f(x):

|x⟩|0⟩→|x⟩[√(1−f(x))|0⟩+√f(x)|1⟩].

After superposing x with amplitudes √P(x), the ancilla-1 probability is

a=Σ_x P(x)f(x)=E[f(X)].

Amplitude estimation can therefore estimate an expectation.

12. Monte Carlo integration

For an integral

I=∫ p(x)f(x)dx

interpret p(x) as a probability density and discretise/encode it quantumly.

The quantum algorithmic core is attractive when:

• the distribution can be prepared efficiently;
• f(x) can be computed reversibly;
• the ancilla rotation can encode f accurately;
• coherent depth survives long enough for repeated Grover powers.

If those operations are expensive, the query advantage can be consumed by state-preparation and arithmetic overhead.

13. Montanaro’s Monte Carlo speedup

Montanaro formalised broad conditions under which quantum algorithms provide near-quadratic speedups for Monte Carlo methods, including bounded-variance settings and mean estimation with quantum subroutines. [2]

The theorem is algorithmic, not automatic hardware acceleration. A classical random variable must be represented by a coherent quantum procedure that can be queried and, in many constructions, inverted.

14. Confidence amplification

One run of canonical amplitude estimation succeeds only with a constant probability.

Repeat independently and take a median to boost success probability from a constant to 1−δ.

The repetition overhead is logarithmic:

O(log(1/δ)).

Thus a common complexity form is O((1/ε)log(1/δ)) queries for additive error ε and failure probability δ, up to method-specific constants.

15. Canonical QAE needs deep coherent control

Textbook QAE uses quantum phase estimation on Q and therefore controlled powers

Q, Q², Q⁴, ….

The largest power can be O(1/ε).

This creates long coherent circuits, controlled operations and an inverse quantum Fourier transform.

Near-term amplitude-estimation research therefore asks how much of the quadratic scaling can be retained with shallower, control-friendlier circuits.

16. Maximum-likelihood amplitude estimation

Instead of phase estimation, run circuits with several Grover powers Q^mA|0⟩ and measure the good/bad ancilla.

The good probability after m Grover iterations is

p_m=sin²[(2m+1)θ].

Collect binomial counts for several m values and maximise the likelihood over θ.

This removes the phase-estimation register and inverse QFT, trading quantum depth/width against a classical nonlinear estimation problem.

17. Aliasing in Grover powers

The function sin²[(2m+1)θ] is periodic and non-injective.

A high power can make many different θ values produce the same measured probability.

Modern methods therefore use a schedule of increasing powers and confidence intervals to resolve the correct branch.

Using only the largest possible m is not enough; coarse-to-fine disambiguation matters.

18. Iterative amplitude estimation

Iterative amplitude-estimation methods maintain a confidence interval for θ or a and choose Grover powers adaptively so the transformed interval remains inside a region where the sine-squared map can be inverted unambiguously.

Grinko and collaborators developed an iterative QAE method that avoids quantum phase estimation while retaining a rigorous quadratic-type query advantage in the relevant oracle model. [3]

Different iterative/maximum-likelihood algorithms have different confidence proofs and asymptotic constants; “QAE without QPE” is a family, not one unique algorithm.

19. Maximum depth versus total queries

Two resource counts should be separated:

• total oracle queries: total number of A/Q uses across all shots;
• maximum coherent depth: largest Grover power within one circuit.

Reducing maximum depth often requires more circuit repetitions.

A hardware-limited design may prefer a larger total query count if it keeps each coherent circuit below the error-correction or decoherence budget.

20. Noise breaks perfect Grover oscillations

Under depolarisation, dephasing or coherent gate error, the ideal sinusoid

p_m=sin²[(2m+1)θ]

is damped or distorted as m grows.

Very large Grover powers can therefore carry less useful information than moderate powers on noisy hardware.

Noise-aware QAE jointly fits amplitude and noise parameters or limits the depth schedule. Error mitigation from Guide 55 may assist, but it introduces its own sampling overhead.

21. Lower bounds

The O(1/ε) scaling is not merely one clever algorithm. Quantum query lower bounds show that, in standard amplitude/mean-estimation black-box settings, one cannot generally improve the dependence on ε beyond constant factors while retaining the same oracle model.

Thus amplitude estimation is essentially precision-optimal as a query primitive.

Real applications can still be dominated by a different bottleneck—state loading, arithmetic precision, memory or fault-tolerant logical gates.

22. Option-pricing example as an encoding problem

Financial option pricing is often cited because the target is an expectation of a payoff under a risk-neutral distribution.

The quantum core would need to:

• prepare a distribution over asset paths or terminal prices;
• compute payoff reversibly;
• scale payoff into [0,1];
• encode it as an ancilla rotation;
• run QAE.

The quadratic sampling advantage applies only after those data-loading and arithmetic costs are honestly included. This guide is mathematical/algorithmic education, not financial advice.

23. Risk estimation and tail probabilities

Threshold probabilities can also be encoded directly:

a=P(X≥L).

A reversible comparator marks samples exceeding threshold L, and QAE estimates the marked probability.

Estimating a rare tail accurately in relative error can be harder than additive-error estimation because the required additive tolerance itself scales with a.

Complexity claims should therefore state whether error is additive or relative.

24. Common misconception: QAE measures an amplitude directly

The algorithm does not perform an observable measurement whose outcome equals a. It encodes a into a Grover eigenphase, then infers the probability statistically from phase-sensitive quantum experiments.

25. Common misconception: quadratic query speedup means quadratic wall-clock speedup

Oracle construction, state preparation, reversible arithmetic, error correction, circuit depth and classical post-processing can dominate. Query complexity isolates one resource.

26. Common misconception: amplitude estimation replaces every classical Monte Carlo simulation

It helps when the random process can be coherently implemented and inverted at acceptable cost. Classical Monte Carlo remains preferable when data are already classical, state preparation is expensive or coherent depth is unavailable.

27. Worked synthesis problem

A quantum procedure encodes an expected value μ=0.36 into a good amplitude.

Step 1: Angle. θ=arcsin√0.36=arcsin0.6≈0.643501.

Step 2: Grover eigenphase. 2θ≈1.287002 radians.

Step 3: Suppose θ̃=0.65. Then μ̃=sin²0.65≈0.3663.

Step 4: Additive error. Approximately 0.0063.

Step 5: Resource interpretation. If ε≈0.006 is required, classical Bernoulli sampling needs on the order of 1/ε²≈27,800 samples before constants/confidence, whereas ideal QAE’s precision scaling is on the order of 1/ε≈167 coherent-query units. That comparison is asymptotic and does not include the very different implementation cost of each quantum query.

28. Practice set

1. How is unknown probability a encoded by A?
2. Why introduce θ with a=sin²θ?
3. What are the Grover eigenvalues in the good/bad plane?
4. How is a recovered from θ?
5. What precision scaling does classical independent sampling have?
6. What ideal query scaling does QAE achieve?
7. How does approximate counting encode K?
8. How can E[f(X)] be encoded as an ancilla probability?
9. Why does canonical QAE require deep coherent circuits?
10. What probability is measured after m Grover iterations in likelihood-based QAE?
11. Why do large Grover powers create aliasing?
12. Why should query complexity not be confused with total runtime?

Answers

1. A|0⟩=√(1−a)|bad⟩+√a|good⟩.
2. It turns amplitude estimation into eigenphase estimation for a planar rotation.
3. e^{±2iθ}.
4. a=sin²θ.
5. O(1/ε²) samples for additive RMS/constant-confidence error ε.
6. O(1/ε) coherent queries up to method/confidence factors.
7. a=K/N for a uniform superposition over N inputs with K marked.
8. Prepare √P(x) amplitudes and rotate an ancilla so its conditional success probability is f(x).
9. It uses controlled high powers of the Grover iterate and a phase-estimation circuit.
10. sin²[(2m+1)θ].
11. The sine-squared function is periodic, so several θ values can match one high-power observation.
12. A quantum query may itself require expensive state preparation, arithmetic, logical gates and fault-tolerant depth.

Sources and further study

[1] Gilles Brassard, Peter Høyer, Michele Mosca and Alain Tapp, Quantum Amplitude Amplification and Estimation. The foundational amplitude-estimation and approximate-counting framework.

[2] Ashley Montanaro, Quantum speedup of Monte Carlo methods, Proceedings of the Royal Society A 471, 20150301 (2015). A broad treatment of quantum mean-estimation and Monte Carlo speedups.

[3] Dmitry Grinko, Julien Gacon, Christa Zoufal and Stefan Woerner, Iterative Quantum Amplitude Estimation. An amplitude-estimation algorithm avoiding quantum phase estimation.

[4] Yohichi Suzuki and colleagues, Amplitude Estimation without Phase Estimation. Likelihood-based amplitude estimation using circuits with different Grover powers.

Continue through Quantum Mathematics

Guide 58: Quantum Chemistry Mathematics, Electronic Structure, Fermionic Hamiltonians and Qubit Mappings gives one important application family for quantum simulation and energy estimation. Guide 59: Measurement-Based Quantum Computation, Qubit Graph States, Cluster States and Feed-Forward develops a different computational architecture. Guide 60: Quantum Causal Models, Process Matrices, Causal Inequalities and Indefinite Causal Order examines causal structure beyond fixed circuit order.

Return to the BTT Mathematics Learning Hub.