Abstract
Sampling is a fundamental operation in statistical physics, chemistry, and machine learning, yet it remains computationally expensive for classical systems due to the curse of dimensionality. This paper surveys how quantum computers leverage high-dimensional state spaces and inherent probabilistic nature to solve complex sampling problems. We explore methodologies such as Gaussian Boson Sampling and Quantum-Enhanced MCMC, which offer potential exponential speedups over classical algorithms.
Introduction
Sampling—the act of drawing representative data points from a distribution—is a cornerstone of modern science. It is used to estimate the value of $\pi$, simulate molecular behavior, and train generative AI models. However, classical computers struggle with high-dimensional distributions because the state space grows exponentially with the number of variables. Quantum computers naturally operate in this exponential space ($2^n$ dimensions for $n$ qubits), providing a promising roadmap for achieving quantum advantage in sampling tasks.
Methodologies in Quantum Sampling
The authors categorize quantum sampling into five primary methodologies:
- Gaussian Boson Sampling (GBS): A non-universal photonic approach where squeezed light is sent through an interferometer. The resulting photon-counting statistics are related to the "hafnian" of a matrix, a calculation that is #P-hard for classical computers.
- Quantum-Enhanced Markov Chain Monte Carlo (MCMC): Traditional MCMC often gets trapped in local energy minima. This method uses a quantum routine to propose new states, allowing the chain to "jump" across the energy landscape more efficiently than classical local updates.
- Variational Monte Carlo (VMC): Used for many-body quantum systems, where a quantum computer prepares a parameterized wave function (ansatz) and measurements provide samples to calculate energy gradients classically.
- Quantum Boltzmann Machines (QBM): A quantum version of generative neural networks that uses quantum effects, like transverse fields, to create more expressive probability distributions than classical Ising models.
- Quantum Bayesian Networks: These map directed acyclic graphs (DAGs) directly to quantum circuits, where nodes become qubits and parental relationships are represented by $k$-controlled unitary gates.
Key Insights and Structural Advantages
A major insight of this survey is the "Quantum Jump" advantage. In rugged energy landscapes, classical "local spin flips" often fail to explore the state space effectively. Quantum proposals can sample states that are far away in the state space but have comparable energy, drastically speeding up convergence.
Furthermore, there is a direct mapping between the logic of Bayesian networks and quantum control wires. This structural mapping suggests that quantum computers are uniquely suited for modeling sequential or hierarchical causal structures, such as those found in Natural Language Processing (NLP).
Results and Performance
- Computational Speedup: The Jiuzhang GBS experiment demonstrated a calculation that would take 600 million years on a classical supercomputer, completed in just a few minutes.
- Molecular Simulations: VMC results for small molecules like $H_2$ and $H_2O$ showed that quantum-inspired Restricted Boltzmann Machines (RBMs) outperformed standard Hartree-Fock methods.
- Convergence: Quantum-enhanced MCMC showed significant improvements in convergence speed compared to local and uniform updating, even on noisy current-generation hardware.
Limitations and Future Directions
Despite the promise, several barriers remain. Many methods, especially QBMs and VMC, require deep circuits that are difficult for Noisy Intermediate-Scale Quantum (NISQ) devices. Additionally, while experimental speedups are observed, the exact complexity classes for some problems remain unproven. Future work must focus on automating hyperparameter tuning for quantum mixing and designing hardware-efficient yet expressive wave function ansätze.
Summary updated