Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage

• URL: http://arxiv.org/abs/2609.03625v1
• Date: Thu, 03 Sep 2026 10:14:50 GMT
• Title: Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage
• Abstract summary: We introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation.<n>The proposed method does not yield an 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.
• Score: 5.419536837516965
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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 $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.

Related papers

• Faster Quantum Monte Carlo Simulation by Random Compilation [2.9903776166764984]
  Quantum Monte Carlo (QMC) algorithms are among the most powerful classical methods for simulating quantum systems.<n>We introduce randomly compiled quantum Monte Carlo (RC-QMC) as a general framework that suppresses systematic errors by averaging over a family of approximations.<n>Our framework achieves a computational advantage over standard QMC methods when estimating a target state to a desired level of accuracy.
  arXiv  Detail & Related papers  (2026-09-09T17:25:26Z)
• Scalable Lindblad Noise Learning via Stochastic Tensor-Network Simulation [48.887627688666974]
  Learning dissipation rates in large-scale open quantum systems is a major obstacle for near-term quantum technologies.<n>Here, we propose a scalable noise-learning framework for Lindblad dissipation rates that combines a simulation method, the Jump Method (TJM)<n>We demonstrate the approach on two noise models in the Ising model, in which independent dissipation rates are learned for each site up to $N_mathrmsite=16$.<n>This combination of scalable numerics and rigorous theoretical guarantees positions TJM-based noise learning as a practical foundation for characterizing dissipation in large quantum devices.
  arXiv  Detail & Related papers  (2026-08-25T15:07:11Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Quantum Machine Learning methods for Fourier-based distribution estimation with application in option pricing [42.79174867716636]
  We introduce two hybrid classical-quantum methods to address the option pricing problem.<n>We show that the proposed methods achieve remarkable accuracy, becoming a competitive quantum alternative for derivatives valuation.
  arXiv  Detail & Related papers  (2025-10-22T11:43:08Z)
• Calibration of Quantum Devices via Robust Statistical Methods [45.464983015777314]
  We numerically analyze advanced statistical methods for Bayesian inference against the state-of-the-art in quantum parameter learning.<n>We show advantages of these approaches over existing ones, namely under multi-modality and high dimensionality.<n>Our findings have applications in challenging quantumcharacterization tasks namely learning the dynamics of open quantum systems.
  arXiv  Detail & Related papers  (2025-07-09T15:22:17Z)
• Quantum speedup of non-linear Monte Carlo problems [3.534338813984755]
  We propose a quantum-inside-quantum Monte Carlo algorithm that achieves a speedup for a broad class of non-linear estimation problems.<n>A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing.
  arXiv  Detail & Related papers  (2025-02-07T17:13:27Z)
• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty.<n>We provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error.<n>Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
  arXiv  Detail & Related papers  (2024-06-05T14:16:47Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for Max-cut Approximation: QAOA is not optimal [0.0]
  We apply notions of emulation to Variational Quantum Annealing and the Quantum Approximate Algorithm Optimization (QAOA) Our Variational Quantum Annealing schedule is based on a novel parameterization that can be optimized in a similar gradient-free way as QAOA, using the same physical ingredients. In order to compare the performance of ans"atze types, we have developed statistical notions of Monte-Carlo methods.
  arXiv  Detail & Related papers  (2022-11-24T19:02:50Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum-assisted Monte Carlo algorithms for fermions [5.625946422295428]
  We propose a family of scalable quantum-assisted Monte Carlo algorithms where the quantum computer is used at its minimal cost. We show that the hybrid Monte Carlo framework is a general way to suppress errors in the ground state obtained from classical algorithms.
  arXiv  Detail & Related papers  (2022-05-30T07:49:22Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.