Comparison

Monte Carlo or quantum amplitude estimation: when the quadratic speed-up is real

Quantum amplitude estimation, and its practical variant IQAE, reaches an additive error ε\varepsilon with about 1/ε1/\varepsilon oracle queries, where Monte Carlo needs about 1/ε21/\varepsilon^{2} samples. We measured that gap with IQAE on a noiseless simulator, on one tail probability of a 64-bin loss distribution: the error fell with oracle calls close to the theoretical rate, and the ratio of Monte Carlo samples to IQAE queries for the same error grew steadily as the target tightened. It is a gap in queries, not yet in time: once state loading, circuit depth and error correction are counted, Monte Carlo, quasi-Monte Carlo or an exact classical sum is faster on every problem published so far and every machine available today, and the published break-even points lie on fault-tolerant hardware that has not been built.

Updated

The comparison at a glance

Monte Carlo
Error falls as 1/N1/\sqrt{N} in the number of samples NN, whatever the dimension of the problem[8]
Quasi-Monte Carlo
Error close to (log⁡N)d/N(\log N)^d / N for smooth integrands in dimension dd, so it changes the rate in low dimension and loses ground as dd grows[8]
Amplitude estimation
Error falls as about 1/N in the number of oracle queries N, independent of dimension, for a circuit that encodes the quantity in an amplitude[1][2]
What a query costs
One coherent run of the state preparation and its inverse inside a Grover operator: loading the distribution, computing the payoff or loss, rotating an ancilla. A Monte Carlo sample is a few arithmetic operations
Faster in wall-clock today
Classical methods, on every problem published so far. In our run, Monte Carlo reached the simulated IQAE's accuracy sooner, and an exact sum took 0.0000032 s

What quantum amplitude estimation is, and its variants

Many Monte Carlo problems reduce to estimating one probability a: the share of paths that end in the money, or of scenarios whose loss passes a threshold. Amplitude estimation prepares a state in which an ancilla qubit reads 1 with probability a, and then repeats the Grover operator, the same rotation that drives Grover's search, so that the angle behind a grows with every repetition and can be read out more precisely than by counting shots[1]. Montanaro turned this into a general method for estimating the mean output of a randomised algorithm, with a near-quadratic speed-up over the best possible classical algorithm[2]. The mechanics, step by step, are in the IQAE chapter of the eigenkit docs.

The variants differ in what they ask of the hardware. Canonical amplitude estimation runs quantum phase estimation over the Grover operator, which needs controlled powers of it and an inverse quantum Fourier transform. Maximum-likelihood amplitude estimation (MLAE) drops phase estimation: it runs a few circuits with different numbers of Grover repetitions and fits a to all their counts[3]. Iterative amplitude estimation (IQAE), by Grinko, Gacon, Zoufal and Woerner, also avoids phase estimation and chooses each next Grover power adaptively, narrowing a confidence interval round by round. With Chernoff-Hoeffding intervals they prove that the total number of Grover applications stays below (50/ε)log⁡((2/α)log⁡2(π/(4ε)))(50/\varepsilon) \log((2/\alpha) \log_2(\pi/(4\varepsilon)))[4] for error ε\varepsilon with confidence 1−α1 - \alpha, a quadratic speed-up up to a double-logarithmic factor, and report that Clopper-Pearson intervals lower the constant by about a factor of 3[4]. None of the variants removes depth: the last rounds still apply the Grover operator about 1/ε1/\varepsilon times in one coherent circuit.

The quadratic gap, measured

Our run estimated one tail probability, P(loss≥VaR)P(\text{loss} \ge \text{VaR}) of a 64-bin portfolio loss distribution, with eigenkit's IQAE on its NumPy simulator and with Monte Carlo sampling from the same bins, over 20 seeds. The setup and the VaR and CVaR results are on the VaR and CVaR guide.

EstimatorError slope against queriesQueries for the RMSE IQAE reached at ε = 0.001Wall-clock for that RMSE
IQAE (theory −1)-0.9223070 oracle calls ± 7661 oracle calls0.23 s ± 0.08 s
Monte Carlo (theory −0.5)-0.502884013 samples0.09 s

Run var-cvar-iqae of 2026-11-03, mean and spread over 20 seeds, on Synthetic correlated Gaussian daily log-returns, 4 assets, 1000 days (seed 2026). IQAE queries are eigenkit's n_oracle_calls, mean and spread over seeds; Monte Carlo samples are what the exact binomial variance needs for the same RMSE. Wall-clock on one Apple Silicon CPU with other jobs running.

How the gap grows as the target tightens

The same run at every target precision: the oracle calls IQAE used, the Monte Carlo samples needed to reach the same error, their ratio, and the time each took on one laptop. The ratio grows as the target tightens, which is what a quadratic gap in queries means; the time does not follow it, because a simulated oracle call and a Monte Carlo sample cost very different amounts.

Target εIQAE oracle callsMonte Carlo samples for the same errorRatioIQAE timeMonte Carlo time
0.053856421.70.004 s0.00002 s
0.02152568114.50.015 s0.00022 s
0.011640156589.60.017 s0.00050 s
0.005461513472829.20.050 s0.00430 s
0.002928040247043.40.093 s0.01285 s
0.001230702884013125.00.229 s0.09205 s
0.0005393506857163174.30.379 s0.21886 s
0.000210585543235975408.41.040 s1.37994 s
0.0001247665155799927629.12.447 s4.97257 s

Run var-cvar-iqae of 2026-11-03, mean and spread over 20 seeds, on Synthetic correlated Gaussian daily log-returns, 4 assets, 1000 days (seed 2026).

Why fewer queries do not mean less time, and what would change that

On a simulator, a query is not a quantum operation. The simulated IQAE's time grew in proportion to its oracle calls (fitted: 0.99), at about 0.0000099 s per call, against 0.000000032 s per Monte Carlo sample. At the tightest targets the simulated IQAE did finish before Monte Carlo, but only because the simulator computes each round's state once, reads the exact ancilla probability and draws the shots from a binomial. A device has to run every shot, and a statevector simulator's cost grows exponentially with the qubits.

On hardware, a query is a deep circuit. For the 7-qubit toy above, the state preparation alone is 64 CX gates and the Grover reflection 122 CX gates, so the deepest circuit at ε=0.001\varepsilon = 0.001 needs at least 38564 CX gates, run without losing coherence. Loading a general distribution takes a number of gates that grows with the bin count.

State loading can eat the speed-up outright. Herbert proved that for analytically defined log-concave distributions, the Gaussian among them, preparing the state with the Grover-Rudolph method leaves no quantum speed-up for the mean and other moments[5]. The advantage needs a distribution that is cheap to load, or a model whose paths the circuit can compute rather than look up.

Error correction multiplies the cost of every gate. Babbush et al. conclude that quadratic speed-ups will not give a quantum advantage on early generations of fault-tolerant machines, because the overhead of error correction is larger than the gain[7]. The most complete estimate for a financial workload, derivative pricing by Chakrabarti et al., needs about 8k logical qubits[6] and a T-depth of 54 million[6], and the program would have to finish in about a second to beat a classical pricer. The option pricing page follows those estimates further.

What would flip it. Each obstacle above names a condition that would have to change: error-corrected hardware whose logical gates run fast enough that the deep final rounds finish inside a classical run time; a distribution that is cheap to load, or paths the circuit computes rather than looks up[5]; and a problem where classical sampling is truly expensive: high dimension, where quasi-Monte Carlo loses its edge[8], a tight precision and many repeats. Until such hardware exists, the parts you can measure are the ones this page measured: oracle calls and Grover depth on a simulator against your best classical method, and on a small circuit, how far gate noise lets the Grover power grow on a real QPU.

The classical side is stronger than plain Monte Carlo

The textbook comparison sets amplitude estimation against plain Monte Carlo. A production engine is rarely plain. Quasi-Monte Carlo replaces random points with low-discrepancy sequences and reaches an error close to 1/N for smooth integrands in moderate dimension[8]; importance sampling concentrates samples in the tail that VaR and expected shortfall depend on; control variates subtract what a cheap model already knows. When the distribution is known in closed form or on a small grid, the exact answer is a sum, which is what our 64-bin reference was.

What amplitude estimation keeps is a rate that does not depend on dimension, which quasi-Monte Carlo cannot promise, and that does not need a good sampling design. Its weak point is small amplitudes. Its error is additive, so a quantity encoded in a tiny amplitude needs a tight ε\varepsilon before the queries pay off: in our CVaR test, IQAE was less accurate than Monte Carlo with as many queries at loose targets, and ahead only at tight ones. The same habit of asking what a fair classical baseline would do runs through the guide to when quantum machine learning makes sense.

Which method for which problem

SituationUse todayWhere amplitude estimation stands
The distribution is known in closed form or on a small gridThe exact sum or formulaEstimates a number you can compute exactly
Smooth integrand, low to moderate dimensionQuasi-Monte CarloSame rate class in queries, each query far dearer
Rare events in the tailMonte Carlo with importance samplingSmall amplitudes need a tight ε\varepsilon before the query advantage appears
High dimension, high precision, many repeatsMonte Carlo with variance reduction, on GPUsThe case the quadratic speed-up is for, on fault-tolerant hardware that does not exist yet
Learning the method or checking a claimA simulator and an exact referenceeigenkit's IQAE, with oracle calls counted

How to read a quadratic speed-up claim

Most claims about quantum Monte Carlo are true in one unit and read in another. Five questions recover the unit.

  1. Queries or seconds?

    A ratio of oracle queries to samples is not a speed. It also depends on the target: in our run the ratio was small at loose ε\varepsilon and grew steadily as ε\varepsilon tightened, so an "N times faster" figure holds at one precision only.

  2. What is inside one query?

    Check whether the count includes loading the distribution and computing the payoff, or treats them as a free gate. On a simulator the oracle is often one matrix; on hardware it is most of the circuit.

  3. Against which classical method?

    Plain Monte Carlo is the weakest baseline. Ask for quasi-Monte Carlo, importance sampling or an exact method where one exists.

  4. Simulated or run?

    A statevector simulator reads exact probabilities and adds shot noise afterwards. Its times, and its interval guarantees, assume noiseless circuits.

  5. Logical or physical qubits, and at what clock rate?

    Resource estimates count error-corrected logical qubits and T-gates. A break-even needs both the qubits and a logical gate rate fast enough to finish within the classical run time.

Run it on a real QPU with EigenOrbit RouterWhat would run: a small IQAE circuit at a loose ε, to measure how far gate noise lets the Grover power grow. eigenkit documents no QPU run of IQAE yet, and a device of today shows noise, not a speed-up.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).

Questions

What is quantum amplitude estimation?

A quantum algorithm that estimates the probability that a circuit leaves a marked qubit in state 1. It repeats the Grover operator to amplify the angle behind that probability, so its error falls as about one over the number of oracle queries, against one over the square root of the number of samples for Monte Carlo. Many Monte Carlo problems, such as option prices or tail probabilities, can be written as such a probability.

What is IQAE?

Iterative quantum amplitude estimation, by Grinko, Gacon, Zoufal and Woerner (2021). It avoids quantum phase estimation: it runs rounds of the Grover operator with adaptively chosen powers and narrows a confidence interval after each round. It keeps the quadratic query advantage up to a double-logarithmic factor and needs fewer qubits and gates than the canonical algorithm, but its last rounds are still circuits of depth about one over epsilon.

Is quantum amplitude estimation faster than Monte Carlo?

In the number of queries, yes, and the gap grows as the target precision tightens. In time, not on any machine that exists: each query is a coherent circuit that loads the distribution and computes the payoff, error correction multiplies its cost, and published break-even estimates need thousands of logical qubits running far faster than projected logical clock rates. On a CPU simulator, Monte Carlo reaches the same accuracy sooner.

Does amplitude estimation beat quasi-Monte Carlo?

Not in practice today. Quasi-Monte Carlo already reaches an error close to one over N for smooth, low-dimensional problems, the same class of rate as amplitude estimation, with classical samples that cost almost nothing. Amplitude estimation's edge is that its rate does not depend on dimension, which matters only for high-dimensional problems on fault-tolerant hardware.

When will quantum Monte Carlo give a real advantage?

Nobody can give a date. The published resource estimates put the break-even on fault-tolerant machines with thousands of logical qubits and fast logical gates, and Babbush et al. argue that quadratic speed-ups will not be enough on the first generations of such machines. Treat any timeline as a vendor target, not a result.

Can I run IQAE on a real quantum computer?

Small instances, yes in principle: the early rounds use only a few Grover repetitions. But gate noise grows with depth, the interval guarantee assumes noiseless circuits, and a target precision useful for finance needs circuits far deeper than current devices run. eigenkit documents IQAE on simulators only.

Sources

  1. G. Brassard, P. Høyer, M. Mosca, A. Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics 305, 53–74 (AMS), 2002. arXiv:quant-ph/0005055.
  2. A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A 471, 20150301, 2015. arXiv:1504.06987.
  3. Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, N. Yamamoto. Amplitude estimation without phase estimation. Quantum Information Processing 19, 75, 2020. arXiv:1904.10246.
  4. D. Grinko, J. Gacon, C. Zoufal, S. Woerner. Iterative quantum amplitude estimation. npj Quantum Information 7, 52, 2021. arXiv:1912.05559.
  5. S. Herbert. The problem with Grover-Rudolph state preparation for quantum Monte Carlo. Physical Review E 103, 063302, 2021. arXiv:2101.02240.
  6. S. Chakrabarti, R. Krishnakumar, G. Mazzola, N. Stamatopoulos, S. Woerner, W. J. Zeng. A threshold for quantum advantage in derivative pricing. Quantum 5, 463, 2021. arXiv:2012.03819.
  7. R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, H. Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103, 2021. arXiv:2011.04149.
  8. R. E. Caflisch. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica 7, 1–49, 1998.

Run it yourself with eigenkit

eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.

$ pip install eigenkit