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 with about oracle queries, where Monte Carlo needs about 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 in the number of samples , whatever the dimension of the problem[8]
- Quasi-Monte Carlo
- Error close to for smooth integrands in dimension , so it changes the rate in low dimension and loses ground as 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 [4] for error with confidence , 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 times in one coherent circuit.
The quadratic gap, measured
Our run estimated one tail probability, 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.
| Estimator | Error slope against queries | Queries for the RMSE IQAE reached at ε = 0.001 | Wall-clock for that RMSE |
|---|---|---|---|
| IQAE (theory −1) | -0.92 | 23070 oracle calls ± 7661 oracle calls | 0.23 s ± 0.08 s |
| Monte Carlo (theory −0.5) | -0.50 | 2884013 samples | 0.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 calls | Monte Carlo samples for the same error | Ratio | IQAE time | Monte Carlo time |
|---|---|---|---|---|---|
| 0.05 | 385 | 642 | 1.7 | 0.004 s | 0.00002 s |
| 0.02 | 1525 | 6811 | 4.5 | 0.015 s | 0.00022 s |
| 0.01 | 1640 | 15658 | 9.6 | 0.017 s | 0.00050 s |
| 0.005 | 4615 | 134728 | 29.2 | 0.050 s | 0.00430 s |
| 0.002 | 9280 | 402470 | 43.4 | 0.093 s | 0.01285 s |
| 0.001 | 23070 | 2884013 | 125.0 | 0.229 s | 0.09205 s |
| 0.0005 | 39350 | 6857163 | 174.3 | 0.379 s | 0.21886 s |
| 0.0002 | 105855 | 43235975 | 408.4 | 1.040 s | 1.37994 s |
| 0.0001 | 247665 | 155799927 | 629.1 | 2.447 s | 4.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 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 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
| Situation | Use today | Where amplitude estimation stands |
|---|---|---|
| The distribution is known in closed form or on a small grid | The exact sum or formula | Estimates a number you can compute exactly |
| Smooth integrand, low to moderate dimension | Quasi-Monte Carlo | Same rate class in queries, each query far dearer |
| Rare events in the tail | Monte Carlo with importance sampling | Small amplitudes need a tight before the query advantage appears |
| High dimension, high precision, many repeats | Monte Carlo with variance reduction, on GPUs | The case the quadratic speed-up is for, on fault-tolerant hardware that does not exist yet |
| Learning the method or checking a claim | A simulator and an exact reference | eigenkit'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.
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 and grew steadily as tightened, so an "N times faster" figure holds at one precision only.
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.
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.
Simulated or run?
A statevector simulator reads exact probabilities and adds shot noise afterwards. Its times, and its interval guarantees, assume noiseless circuits.
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
- 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.
- A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A 471, 20150301, 2015. arXiv:1504.06987.
- 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.
- D. Grinko, J. Gacon, C. Zoufal, S. Woerner. Iterative quantum amplitude estimation. npj Quantum Information 7, 52, 2021. arXiv:1912.05559.
- S. Herbert. The problem with Grover-Rudolph state preparation for quantum Monte Carlo. Physical Review E 103, 063302, 2021. arXiv:2101.02240.
- 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.
- 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.
- 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