Research map / Learning theory and algorithms / Sample complexity
Quantum speedup of non-linear Monte Carlo problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Q-NestExpect, a quantum-inside-quantum multilevel Monte Carlo algorithm that estimates nested expectations with cost Õ(1/ε), matching a quantum lower bound up to polylog factors and removing the loss of quadratic speedup in direct QA-MLMC.
Problem
Estimating nested expectations (non-linear functionals of distributions) with quantum algorithms; direct quantum-accelerated MLMC only achieves Õ(1/ε²) cost, no quadratic speedup over classical MLMC.
Approach
Designs a new sequence of MLMC approximations in which the inner conditional expectation is estimated by quantum-accelerated Monte Carlo at progressively higher precision, and then applies quantum-accelerated Monte Carlo again to each level's coupled difference, giving parameters α=1, β=2, γ≈1 and cost Õ(1/ε).
Key results
- Q-NestExpect achieves cost Õ(K√(SV)/ε) for nested expectations, versus Õ(ε^-2) for direct QA-MLMC and classical MLMC under standard Lipschitz assumptions.
- The paper proves a matching Ω(1/ε) lower bound for quantum algorithms, so the algorithm is optimal up to polylogarithmic factors.
- Applications to Bayesian experiment design, EVPPI, call-on-call option pricing, and conditional stochastic optimization are analyzed with Õ(1/ε) costs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the quantum-inside-quantum MLMC sequence instead of direct QA-MLMC | Nested expectation estimation · Nested expectations | cost: \widetilde{O}\pt{\epsilon^{-2}} -> \widetilde{O}\pt{\epsilon^{-1}} | Helped |
| Use classical MLMC instead of the nested estimator | Nested expectation estimation · Nested expectations | cost: O\pt{\epsilon^{-4}} -> \widetilde{O}\pt{\epsilon^{-2}} | Helped |
| Use Q-NestExpect instead of the nested estimator | Nested expectation estimation · Nested expectations | cost: O\pt{\epsilon^{-4}} -> \widetilde{O}\pt{\epsilon^{-1}} | Helped |
Surprising findings
- Direct application of QA-MLMC to nested expectations yields no improvement over classical MLMC, losing the quadratic speedup because the highest-level cost is poly(1/ε).
Limitations
- Results assume fault-tolerant quantum computing and are not realizable on current NISQ hardware.
- Requires Assumption 5 that users have full access to the sampling procedure as code, not just black-box samples.
- Dependence on Lipschitz constant, variance, and dimension is not shown to be optimal.
Experimental setup
Metrics: query complexity / cost scaling in epsilon
Baselines: nested Monte Carlo estimator classical MLMC QA-MLMC (Kaneko et al.)
Builds on: multilevel Monte Carlo (Giles 2008) quantum-accelerated MLMC (Kaneko et al.) quantum Monte Carlo speedup (Montanaro 2015)
Closest papers by meaning
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.86)
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.85)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.85)
- Differentiable Quantum Computing for Large-scale Linear Control (NeurIPS 2024 · similarity 0.84)
- Characterizing Trainability of Instantaneous Quantum Polynomial Circuit Born Machine (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.