Quantum Monte Carlo Integration
Estimating expectation values and integrals with a quadratic reduction in sample complexity using amplitude estimation.
The task
Many problems reduce to estimating an expectation E[f(X)] where X is a random variable with known distribution and f maps to [0,1]. Classical Monte Carlo draws N samples and averages, with error decreasing as 1/sqrt(N). Quantum Monte Carlo encodes the same expectation as an amplitude and estimates it with error decreasing as 1/M, where M is the number of quantum queries, a quadratic improvement.
Encoding the expectation
Two building blocks are needed. First, a state-preparation unitary P that loads the probability distribution: P|0> = sum_x sqrt(p_x) |x>. Second, a unitary R that rotates an ancilla by an angle whose sine squared equals f(x): R|x>|0> = |x>(sqrt(1-f(x))|0> + sqrt(f(x))|1>). Applying R after P yields an ancilla-1 probability exactly equal to E[f(X)] = sum_x p_x f(x).
With this amplitude in hand, quantum amplitude estimation reads it out at the Heisenberg limit.
Steps
- Load the distribution with P (often the hardest engineering step).
- Compute f(x) into an ancilla rotation with R.
- Estimate the resulting amplitude a = E[f(X)] via amplitude estimation.
- Report a with additive error epsilon using O(1/epsilon) queries.
Where the cost hides
The quadratic speedup counts queries to P and R, not their internal gate cost. Loading an arbitrary distribution can require deep circuits; efficient loading exists for log-concave and other structured distributions, and for distributions generated by an efficient quantum process. Computing f in-place may need arithmetic circuits and additional ancillas.
Applications
Risk-style expectation estimation, high-dimensional integrals, and averaged observables from stochastic models all fit this template. In simulation work supporting fusion design studies, averaged quantities over plasma parameter ensembles are expectation values of this form, computed on classical or quantum simulators rather than on any built machine.