Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage
Abstract
Numerical integration with Monte Carlo methods is a central computational task in many scientific and industrial applications, including financial derivative pricing and risk management. Classical Monte Carlo algorithms are computationally demanding: achieving an accuracy ε typically requires a number of function evaluations scaling as O(1/ε2). Quantum-accelerated Monte Carlo methods based on quantum amplitude estimation can in principle quadratically improve this dependence. However, \textit{quasi}-Monte Carlo methods have not been explored in the quantum context. In this work, we introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation. The proposed method prepares the quasi-random point set coherently in superposition. The method does not yield an asymptotic improvement over classical quasi-Monte Carlo, since the total error separates into a discretization error, determined by the finite net, and a quantum estimation error. Instead, we explore a pre-asymptotic advantage window: for a target accuracy that would classically require 2q low discrepancy points, one can prepare a higher-resolution net of size 2Q, with Q>q, in superposition and reach the same accuracy using significantly fewer function queries. This window can be controlled by tuning the circuit resolution and amplitude-estimation parameters, making the approach relevant for practical regimes where the number of queries is finite rather than asymptotically large.
Related
- Asymptotic advantage of quantum one-way and SMP communication for total functions
- Numerical simulation of D-Wave's quantum advantage experiment with time-dependent variational Monte Carlo
- Asymptotic expansion of cavity Quasi-Normal Modes in Schwarzschild de-Sitter black hole
- Quasi-isotropic Asymptotic Expansions in Varying Speed of Light Cosmologies
- Exponential advantage in continuous-variable quantum state learning
BibTeX
@misc{recchia2026quantum,
title = {{Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage}},
author = {Paolo Recchia and Zhan Yu and Kelvin Koor and Patrick Rebentrost},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03625},
eprint = {2609.03625},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03625},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage
AU - Paolo Recchia
AU - Zhan Yu
AU - Kelvin Koor
AU - Patrick Rebentrost
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03625
UR - https://arxiv.org/abs/2609.03625
AB - Numerical integration with Monte Carlo methods is a central computational task in many scientific and industrial applications, including financial derivative pricing and risk management. Classical Monte Carlo algorithms are computationally demanding: achieving an accuracy ε typically requires a number of function evaluations scaling as O(1/ε^2). Quantum-accelerated Monte Carlo methods based on quantum amplitude estimation can in principle quadratically improve this dependence. However, \textit{quasi}-Monte Carlo methods have not been explored in the quantum context. In this work, we introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation. The proposed method prepares the quasi-random point set coherently in superposition. The method does not yield an asymptotic improvement over classical quasi-Monte Carlo, since the total error separates into a discretization error, determined by the finite net, and a quantum estimation error. Instead, we explore a pre-asymptotic advantage window: for a target accuracy that would classically require 2^q low discrepancy points, one can prepare a higher-resolution net of size 2^Q, with Q>q, in superposition and reach the same accuracy using significantly fewer function queries. This window can be controlled by tuning the circuit resolution and amplitude-estimation parameters, making the approach relevant for practical regimes where the number of queries is finite rather than asymptotically large.
ER -