Source-linked AI summary
Quantum speedup of Monte Carlo methods
Ashley Montanaro
TL;DR
Classical estimation of a bounded-variance mean has an asymptotically optimal dependence on variance and error, motivating a quantum improvement. The paper gives a black-box quantum estimator with near-quadratic savings and combines it with quantum walks for faster partition-function algorithms, while leaving cooling-schedule construction as an open efficiency question.
Problem
Classical mean estimation has asymptotically optimal sample complexity in its dependence on σ and ϵ, despite requiring over 100 million runs when σ = 1 and estimating µ to four decimal places.
Method
The paper presents a black-box quantum algorithm that estimates the mean of a randomized or quantum subroutine with bounded variance and uses quantum walks to accelerate Markov-chain Monte Carlo.
Results
The estimator uses eO(σ/ϵ) calls to the subroutine with 99% success probability, while quantum-walk partition-function algorithms achieve near-quadratic improvements in ϵ and τ dependence over the fastest known classical algorithm.
Takeaways & Limitations
Quantum speedups obtained by the underlying subroutine can be incorporated into the general estimation framework, including quantum-walk improvements for partition-function computation.
Takeaways & Limitations
The overall partition-function complexity includes a classical eO((log A)τ) cooling-schedule computation, and the paper leaves a more efficient quantum schedule-finding algorithm open.
Abstract
from arXiv · showhide
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomised or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
1 Introduction
The paper develops a quantum mean-estimation algorithm that nearly quadratically improves the optimal classical sampling dependence, then applies it to partition functions and distribution-distance estimation.
- Monte Carlo estimates expected outputs by averaging independent samples, requiring k = O(σ2/ϵ2) samples for additive error ϵ with 99% success.
- Without further information about A, this classical sample complexity is asymptotically optimal in its dependence on σ and ϵ.
- Using only a variance upper bound, the quantum algorithm estimates µ with 99% success using A eO(σ/ϵ) times, optimal up to polylogarithmic factors.The result applies when A is an arbitrary black-box randomized or quantum algorithm.
- Applications: The framework applies to quantum subroutines and combines with quantum walks to accelerate rigorous partition-function algorithms based on multiple-stage Markov-chain sampling.For partition functions, the algorithm uses eO((log A)√τ/ϵ) quantum-walk steps, with quadratically worse classical dependence on τ and ϵ.
- Applications: For partition functions with |Ω| = A, a Chebyshev cooling schedule has ℓ = eO(√log A), yielding eO((log A)/ϵ) samples for relative error ϵ.Computing the schedule itself adds an overall complexity of eO((log A)√τ(√τ + 1/ϵ)).
- Applications: Applications include improved approximate counting of colourings and matchings, and improved accuracy for total variation distance estimation.The colouring runtime is eO(n3/2/ϵ + n2), matching uses eO(n3/2m1/2/ϵ + n2m), and total variation distance builds on an existing quantum algorithm.
2 Algorithms
The algorithms use amplitude estimation to estimate mean outputs, extending from values bounded in [0,1] to nonnegative outputs with bounded ℓ2 norm and then bounded variance. Their query complexity is near-linear in the inverse additive accuracy, with explicit success-probability amplification.
- Bounded output values: The bounded-output algorithm assumes a measurement-free quantum circuit, computational-basis measurement at the end, and an efficiently computable output map φ(x)∈[0,1].Classical randomized algorithms and circuits with intermediate measurements can be converted to this form.
- Bounded ℓ2 norm: When E[v(A)^2]=O(1), Algorithm 2 requires O((1/ϵ) log3/2(1/ϵ) log log(1/ϵ)) uses of A for additive error ϵ.The powering lemma increases success probability to 1−δ with an O(log 1/δ) repetition factor.
- Optimality: The quantum mean-estimation complexity is optimal up to polylogarithmic factors because arbitrary-mean estimation has an Ω(1/ϵ) quantum lower bound.The lower bound follows from the quantum query complexity of estimating the fraction of ones of an arbitrary Boolean function.
3 Partition function problems
The paper develops quantum methods for estimating partition functions through multiple temperature stages, replacing classical sampling and estimation components with quantum procedures. Under cooling-schedule and Markov-chain assumptions, the resulting algorithms achieve near-quadratic improvements in relevant complexity parameters.
- Partition-function framework: A partition function is approximated by estimating ratios between successive inverse temperatures and combining them in a telescoping product.The schedule runs from β0 = 0 to βℓ = ∞, with Z(β0) assumed easy to compute.
- Quantum ratio estimation: O(Bℓ2/ϵ2) samples suffice classically, whereas the quantum construction estimates the stages using the bounded-variance mean-estimation algorithm.The theorem assumes exact sampling from the intermediate distributions; the quantum proof applies the estimator separately to each stage.
- Partition-function framework: A B-Chebyshev cooling schedule bounds the relative second moments of the stage-wise random variables used to estimate these ratios.This variance control allows the quantum mean-estimation algorithm to be applied at each temperature stage.
- Quantum ratio estimation: 3/4 success probability follows when every ratio estimate has relative error at most ϵ/(2ℓ), yielding a final relative error at most ϵ.The error is controlled by a union bound and the product inequalities for the ℓ estimated ratios.
- Quantum-walk implementation: Quantum walks reduce the Markov-chain mixing dependence from τ to O(√τ), but general efficient dependence on πmin,i remains unknown.The limitation concerns approximate preparation from Markov chains, not the mean-estimation speedup itself.
- Quantum-walk implementation: The best comparable classical bound is eO((log A)τ/ϵ2), while the quantum approach gives a near-quadratic reduction in τ and ϵ when ϵ ≤ 1/√τ.Outside that regime, the stated near-quadratic reduction with respect to ϵ still applies.
4 Estimating the total variation distance
The paper improves quantum estimation of total variation distance between two distributions, retaining quadratic dependence on n while substantially improving dependence on accuracy and failure probability.
- The task is to estimate ||p − q|| up to additive error ϵ from samples of distributions p and q on n elements.
- The previous quantum algorithm used O(√n/(ϵ8δ5)) samples to achieve success probability 1 − δ.
- The subroutine samples x from r = (p + q)/2, estimates p(x) and q(x) with amplitude estimation, and outputs |ep(x) − eq(x)|/(ep(x) + eq(x)).
- The analysis splits elements into small and large parts and bounds the estimated ratio's deviation from the exact ratio using a stability proposition.
- O(√nϵ^-3/2 log(1/ϵ)) samples suffice to estimate the subroutine mean within ϵ/2, and repetition yields overall complexity O((√n/ϵ5/2) log(1/ϵ) log(1/δ)).This improves on the earlier O(√n/(ϵ8δ5)) complexity for small ϵ and δ.
A Stability of Algorithm 3
The paper shows that Algorithm 3 remains accurate when its input algorithm is replaced by another algorithm with a close output distribution. The proof uses amplitude-estimation output distributions and bounds the accumulated effect across all uses of the algorithm.
- The stability question concerns using samples from an approximate distribution eπ instead of π when estimating a quantity defined from samples.
- The comparison uses an arcsin addition formula and inequalities involving shortest arcs between phases on the unit circle.
- Lemma 18 states that if the output distributions DA and DB are within total variation distance γ, Algorithm 3 applied to A estimates E[v(B)] up to additive error ϵ with a bounded failure probability.
- The result is more general than an earlier approximate-rotation result because it assumes closeness of measured output distributions rather than closeness of the underlying states.
- The proof compares amplitude-estimation measurement distributions MA and MB associated with the mean values µA and µB.
- A hybrid-style argument bounds the discrepancy for each use of A and then applies a union bound over all uses in Algorithm 3.