Amplitude Estimation and the Monte-Carlo Speedup

Every other quantum-finance claim you will hear is either a maybe, a someday, or a polite lie. This one is neither. Quantum Amplitude Estimation (QAE) takes the single most stubborn law in all of computational finance — that Monte Carlo error shrinks like one over the square root of the sample count — and replaces it with one over the sample count. That is a quadratic speedup, and it is provable, not hand-wavy. It is the crown jewel of this whole course: the one place where the math unambiguously says the quantum machine asks fewer questions to get the same answer.

So we will spend this lesson earning the right to be excited — and then, at the very end, earning the right to be skeptical. Because “fewer queries in theory” and “fewer seconds on a real chip with real noise and a real data-loading bill” are very different claims, and the gap between them is the rest of this course.

If your memory of Monte Carlo for Finance is hazy, dust it off now. The entire payoff of QAE is felt only against the backdrop of why classical Monte Carlo is so frustratingly slow to converge.

The classical Monte-Carlo wall

Analogy. Classical Monte Carlo is a pollster. To estimate what fraction of voters favor a candidate, you call random people and average. Poll 100 people and your margin of error is some width; to halve that margin you do not call 200 people — you call 400. Each extra digit of precision costs you a hundredfold more phone calls. The pollster’s pain is the quant’s pain.

Definition. To estimate an expectation $\mu = \mathbb{E}[f(X)]$, classical Monte Carlo draws $N$ independent samples and averages them. By the Central Limit Theorem the standard error of that average is

$\text{SE} = \frac{\sigma}{\sqrt{N}},$

where $\sigma$ is the standard deviation of $f(X)$. The estimation error therefore shrinks like $1/\sqrt{N}$ — slope $-1/2$ on a log-log plot. Inverting it: to reach a target error $\varepsilon$ you need

$N \approx \frac{\sigma^2}{\varepsilon^2} \;\propto\; \frac{1}{\varepsilon^2}.$

The cost grows with the square of the precision you demand. This is the wall.

Worked example. Set $\sigma = 1$ for cleanliness. To reach an error of $\varepsilon = 10^{-2}$ (one percent) you need about $N = 1/(10^{-2})^2 = 1/10^{-4} = 10^{4}$ samples — ten thousand. Now you want one more digit, $\varepsilon = 10^{-3}$:

$N \approx \frac{1}{(10^{-3})^2} = \frac{1}{10^{-6}} = 10^{6}.$

A million. One extra digit of accuracy cost you a 100-fold increase in samples — from ten thousand to one million. That factor of 100 is not a coincidence; it is $(10^{-2}/10^{-3})^2 = 10^2$. Squaring the precision ratio is the whole story.

When to use it

Reach for classical Monte Carlo whenever an expectation has no closed form and the dimension is too high for a grid — pricing path-dependent options, aggregating portfolio risk, propagating uncertainty. It is the default workhorse precisely because it is general and embarrassingly parallel. Just budget honestly: every extra digit of precision is a four-fold (per half-digit) or hundred-fold (per full digit) sample bill, and that bill is the thing QAE promises to slash.

The core QAE result: 1/sqrt(N) becomes 1/N

Analogy. Imagine two referees timing how often a biased coin lands heads. The classical referee flips the coin many times and counts — and is stuck with the pollster’s square-root tax. The quantum referee does not flip and count; she puts the coin into a kind of resonant rotation whose angle encodes the bias directly, then reads the angle. Reading an angle precisely costs effort proportional to the precision you want, not its square. Same question, fundamentally cheaper measurement.

Definition. Suppose an operator $\mathcal{A}$ prepares a state in which the “good” outcome you care about has amplitude $\sqrt{a}$, so the probability of measuring it is exactly $a$. Classically you would estimate $a$ by sampling: prepare, measure, repeat $N$ times, count — error $\propto 1/\sqrt{N}$. Amplitude estimation instead uses amplitude amplification (the engine behind Grover’s algorithm) to estimate $a$ to additive error $\varepsilon$ using a number of applications of $\mathcal{A}$ (oracle “queries”) that scales as

$N_{\text{quantum}} = O\!\left(\frac{1}{\varepsilon}\right),$

against the classical

$N_{\text{classical}} = O\!\left(\frac{1}{\varepsilon^2}\right).$

The ratio is $N_{\text{classical}} / N_{\text{quantum}} \approx 1/\varepsilon$ — the quantum query count is the square root of the classical sample count. On a log-log error-vs-cost plot, classical has slope $-1/2$ and quantum has slope $-1$. The widening vertical gap between those two lines is the speedup.

Worked example. Demand a target error $\varepsilon = 10^{-3}$. Classical sampling needs

$N_{\text{classical}} \approx \frac{1}{(10^{-3})^2} = 10^{6} \;\text{samples},$

while QAE needs only

$N_{\text{quantum}} \approx \frac{1}{10^{-3}} = 10^{3} \;\text{queries}.$

A million versus a thousand. The speedup ratio is $10^{6}/10^{3} = 10^{3} = 1/\varepsilon$. Tighten the target to $\varepsilon = 10^{-4}$ and the gap explodes to $10^{8}$ vs $10^{4}$ — a ten-thousand-fold edge. The more precision you demand, the more lopsided the contest becomes, because you are racing slope $-1$ against slope $-1/2$.

When to use it

QAE is the tool whenever your quantity of interest is an expectation or a probability you would otherwise Monte-Carlo, and you need many digits of precision. The speedup ratio is $1/\varepsilon$, so the win is negligible at coarse precision ($\varepsilon = 0.1$ buys you only about 10x) and enormous at fine precision ($\varepsilon = 10^{-4}$ buys 10,000x). If you only ever need two-digit answers, the quadratic speedup barely matters; if you are chasing tight risk numbers or tail probabilities, it is exactly where the lever is longest.

How a payoff becomes an amplitude

Analogy. Think of building a custom dartboard whose geometry is rigged so that the probability a random dart lands in the bullseye equals exactly the number you want — the option’s expected payoff. Once the board is built, you do not throw thousands of darts and count (that is classical sampling). You hand the board to QAE, which estimates the bullseye probability directly and far more cheaply. The cleverness lives in building the board; the speedup lives in how you read it.

Definition. You construct, in two conceptual stages, an operator $\mathcal{A}$ acting on a register of qubits plus one ancilla:

1. Load the distribution. A sub-operator $\mathcal{P}$ prepares a superposition over the possible outcomes $x$ with amplitudes set so that measuring the register gives outcome $x$ with probability $p(x)$ — the distribution of your risk factor $X$. Formally it builds $\sum_x \sqrt{p(x)}\,\lvert x \rangle$.
2. Encode the payoff. A second sub-operator rotates the ancilla qubit by an angle that depends on the payoff $f(x)$, so that conditioned on outcome $x$ the ancilla is $\lvert 1 \rangle$ with probability proportional to $f(x)$.

Put together, the probability of measuring the ancilla in $\lvert 1 \rangle$ is

$a = \sum_x p(x)\, \tilde f(x) = \mathbb{E}\big[\tilde f(X)\big],$

where $\tilde f$ is $f$ rescaled into $[0,1]$. So $a$ — the amplitude QAE estimates — is the (normalized) expectation. Estimate $a$ to error $\varepsilon$ and you have estimated the expectation to error $\varepsilon$ (times the rescaling factor), in $O(1/\varepsilon)$ queries.

Worked example. Suppose a payoff takes just two values on a toy two-outcome model: $f = 0$ with probability $0.7$ and $f = 1$ with probability $0.3$. After loading, the ancilla is $\lvert 1 \rangle$ with probability $a = 0.7 \times 0 + 0.3 \times 1 = 0.3$. The true expected payoff is $0.3$. Classically you would prepare-and-measure $N$ times and your estimate of $0.3$ would carry error $\sqrt{0.3 \times 0.7}/\sqrt{N} \approx 0.458/\sqrt{N}$ — the familiar $1/\sqrt{N}$. QAE instead reads $a = 0.3$ to error $\varepsilon$ in $O(1/\varepsilon)$ queries. Same $0.3$; quadratically cheaper precision.

The canonical machinery, honestly. The original QAE wraps this in Quantum Phase Estimation (QPE): it treats the Grover-style amplitude-amplification operator as a rotation, and QPE reads its rotation angle — from which $a$ falls out. QPE is powerful but expensive: it needs many extra ancilla qubits and long, coherent circuits, which real noisy hardware hates. So a family of QPE-free / iterative amplitude estimation variants now exists (iterative QAE, maximum-likelihood QAE, and relatives) that recover the same $O(1/\varepsilon)$ scaling with far shallower circuits — at the cost of more, simpler measurement rounds. The headline speedup is the same; these variants are what make it remotely runnable on near-term (NISQ) machines.

When to use it

This encoding step is exactly where QAE meets your specific problem: any quantity expressible as $\mathbb{E}[f(X)]$ for a distribution you can load and a payoff you can compute in-circuit is a candidate. Choose QAE when (a) you can write your target as such an expectation, (b) you can build a reasonably cheap loader $\mathcal{P}$, and (c) you need enough precision that the $1/\varepsilon$ vs $1/\varepsilon^2$ gap pays for the quantum overhead. If you cannot load the distribution cheaply, stop — the speedup may not survive, as the next-to-last section warns.

Pricing a European option with QAE

Analogy. A European option price is a weighted average of “what you get paid at expiry,” weighted by how likely each future price is (in the risk-neutral world) and shrunk by a discount factor. That is the pollster’s average again — and the pollster’s square-root tax again — which means it is precisely the kind of average QAE was built to estimate more cheaply.

Definition. A European call with strike $K$ on an underlying with terminal price $S_T$ has price

$C = e^{-rT}\, \mathbb{E}^{\mathbb{Q}}\!\big[\max(S_T - K,\, 0)\big],$

the discounted risk-neutral expectation of the payoff $\max(S_T - K, 0)$. To QAE this, you (1) load the risk-neutral distribution of $S_T$ into the register via $\mathcal{P}$, (2) encode the rescaled payoff $\max(S_T - K, 0)$ into the ancilla amplitude, and (3) run amplitude estimation to read $a = \mathbb{E}^{\mathbb{Q}}[\widetilde{\max(S_T - K,0)}]$ to error $\varepsilon$ in $O(1/\varepsilon)$ queries, then undo the rescaling and apply $e^{-rT}$.

Worked example. Say you want the option price to a relative precision of $\varepsilon = 10^{-3}$ (three digits, typical for a desk that cares about basis points on a book). Side by side:

At the desk’s $10^{-3}$ target, classical pricing burns a million payoff evaluations while QAE asks a thousand queries — a thousand-fold reduction in the number of times you must evaluate the payoff scenario. Push to four digits and the ratio is ten-thousand-fold. The table is just the two scaling laws made concrete; notice the speedup column is literally the inverse of the target error.

When to use it

QAE pricing is most attractive for instruments where classical Monte Carlo is already the chosen method and precision is expensive: path-dependent and exotic payoffs (Asian, barrier, basket) where no closed form exists, and where you need many digits. For a vanilla European with a Black–Scholes closed form you would not Monte-Carlo at all, let alone reach for a quantum computer — there is nothing to speed up. The rule of thumb: QAE helps exactly where classical MC hurts most.

Risk: VaR and CVaR as QAE targets

Analogy. Measuring tail risk is like estimating how often a river overtops a flood wall, and how bad it gets when it does. “How often” is a tail probability (VaR’s quantile); “how bad when it does” is a conditional expectation (CVaR). Both are averages over rare events — the worst kind for the pollster, because rare events demand huge samples to pin down. QAE’s quadratic edge is therefore widest exactly here, where classical sampling is most starved.

Definition. For a loss $L$ at confidence level $\alpha$ (say $99\%$):

$\text{VaR}_\alpha = \inf\{\,\ell : \mathbb{P}(L \le \ell) \ge \alpha\,\}, \qquad \text{CVaR}_\alpha = \mathbb{E}\big[\,L \mid L \ge \text{VaR}_\alpha\,\big].$

VaR is the loss threshold the probability mass $\alpha$ sits below; CVaR (Expected Shortfall) is the average loss given you are past that threshold. To find VaR with QAE you estimate the tail probability $\mathbb{P}(L \le \ell)$ — an amplitude — for candidate thresholds $\ell$ (a bisection search over thresholds, each evaluated by QAE). To get CVaR you estimate the conditional expectation of the loss in the tail — again an amplitude. Both inherit the $O(1/\varepsilon)$ query scaling against classical $O(1/\varepsilon^2)$.

Worked example. You want the $99\%$ tail probability of a portfolio loss to error $\varepsilon = 10^{-3}$. Classical Monte Carlo needs about $N_{\text{classical}} \approx 1/(10^{-3})^2 = 10^{6}$ scenario simulations to nail that probability — and rare-tail estimation is even hungrier in practice because few of those million scenarios land in the $1\%$ tail. QAE estimates the same tail amplitude in $N_{\text{quantum}} \approx 1/10^{-3} = 10^{3}$ queries — a thousand versus a million, the same $1/\varepsilon = 1000\times$ ratio. For CVaR, you run the same machinery on the conditional expectation; the quadratic speedup carries over unchanged because it, too, is just an amplitude.

When to use it

Target QAE at risk numbers when you need tight tail estimates and classical MC is straining — deep-tail VaR/CVaR, large netting sets, regulatory capital calculations rerun constantly. As with pricing, the lever is precision: a back-of-envelope $95\%$ VaR to two digits will not justify a quantum machine, but a $99.9\%$ Expected Shortfall to four digits, computed nightly across a huge book, is precisely the shape of problem where slope $-1$ crushes slope $-1/2$. Just remember the loader still has to exist and be cheap.

The asterisk: quadratic, not magic

Analogy. A quadratic speedup is like upgrading from walking to cycling — genuinely faster, you will arrive much sooner, and over long distances the gap is large. But it is not teleportation. An exponential speedup (the thing quantum hype constantly implies) would be teleportation: it would turn a problem that takes the age of the universe into one that takes a second. QAE does not do that. It cannot turn a classically intractable expectation into a trivial one; it can make a classically expensive-but-doable one cheaper — if every other cost cooperates.

Definition and the catch. The clean statement is about query count: QAE uses $O(1/\varepsilon)$ applications of $\mathcal{A}$ versus classical $O(1/\varepsilon^2)$ samples. But the wall-clock (or dollar) cost is

$\text{total cost} \approx (\text{number of queries}) \times (\text{cost per query}) \;+\; (\text{loading} + \text{readout} + \text{error-handling overhead}).$

The quadratic win lives entirely in the first factor. It can be devoured by the rest:

• Loading is the silent killer. Building $\mathcal{A}$ requires loading the distribution $\mathcal{P}$ into the quantum state. If that loading costs $O(2^n)$ or $O(N)$ gates — as a naive general loader can — then every query pays a cost comparable to the classical sampling you were trying to avoid, and the $1/\varepsilon$ vs $1/\varepsilon^2$ advantage evaporates. The speedup assumes a cheap loader, which is not free for arbitrary distributions.
• Noise. On real NISQ hardware, the deep, coherent circuits canonical QAE wants accumulate errors fast; you may need so many repetitions or so much error mitigation that the practical scaling looks nothing like the textbook $O(1/\varepsilon)$.
• Readout and constants. The big-O hides constant factors and the comparatively glacial clock speed of today’s quantum gates versus a classical FLOP.

Worked example. Recall at $\varepsilon = 10^{-3}$ the query-count win is $10^{6}$ vs $10^{3}$ — a $1000\times$ edge in queries. Now suppose each quantum query, including loading, is $10^{4}\times$ slower (in wall-clock) than drawing one classical sample — entirely plausible on near-term hardware. Then wall-clock cost is roughly $10^{3} \times 10^{4} = 10^{7}$ “time units” for QAE against $10^{6} \times 1 = 10^{6}$ for classical. The quantum machine is now 10x slower in wall-clock despite asking 1000x fewer questions. The query speedup was real; it just did not survive contact with the cost-per-query. That arithmetic — query advantage versus per-query and loading penalty — is the entire fight, and it is what the rest of this course adjudicates.

When to use it

Invoke the quadratic speedup as a real but conditional argument: it is the strongest quantum-finance case precisely because the algorithmic win is proven, but you must always pair it with the loading-and-noise caveat. Use it to justify research interest and long-horizon bets; do not use it to claim a present-day production advantage. The honest one-liner: “QAE provably needs quadratically fewer queries — and whether that becomes fewer seconds depends on the loader, the readout, and the hardware noise, which today usually say no.”

Recap

You came in wanting one honest quantum win, and here it is: amplitude estimation reads an unknown probability $a$ to error $\varepsilon$ in $O(1/\varepsilon)$ queries, demolishing classical Monte Carlo’s $O(1/\varepsilon^2)$ — a quadratic speedup, slope $-1$ against slope $-1/2$. Map any expectation onto an ancilla amplitude and QAE prices options (discounted expected payoffs) and measures risk (VaR tail probabilities, CVaR conditional expectations) with that same square-root reduction in queries. Then the asterisk: it is quadratic, not exponential; it presumes a cheap distribution loader; and a query-count theorem only becomes a wall-clock or PnL win once loading, readout, and noise are paid for — the subject of the lessons ahead.