Research map / Learning theory and algorithms / Sample complexity
Gibbs Sampling of Continuous Potentials on a Quantum Computer
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.
Builds a quantum algorithm that prepares Gibbs states of periodic continuous potentials by solving the Fokker–Planck equation with quantum linear-ODE solvers and Fourier-based encoding, with theory on semi-analytic functions bounding discretization and sampling errors.
Problem
Gibbs sampling from continuous real-valued (periodic) potential functions on a quantum computer, where discretization of the continuum must be controlled.
Approach
Introduces semi-analytic functions (a Fourier-decay condition weaker than analyticity) to bound Fourier interpolation and derivative-estimation errors, then uses quantum Fourier transforms and quantum linear-ODE solvers on the Fokker–Planck equation to prepare a state encoding the Gibbs distribution, enabling continuous sampling.
Key results
- Interpolation/sampling error for semi-analytic periodic functions decays as exp(-0.6 N/a) in the number of grid points N, giving gate complexity O(dN/a polylog(NdLl/C)) for sampling within total variation distance epsilon.
- For Chebyshev-grid Gibbs sampling, a query complexity of O~(d^3 ... ) to the energy oracle is stated for Lipschitz potentials with analytic Fokker–Planck trajectories.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase N beyond the stated upper bound on a and use upsampling with M=200 | Fourier interpolation · Function families (a) and (b) | sampling error: less than 0.1 | Helped |
Limitations
- Results are stated for periodic functions; the extension to non-periodic functions is only sketched via infinite lattices.
- Lower bound shows that Omega(a) grid points are necessary for arbitrarily accurate sampling, so cost grows with semi-analyticity parameter.
Experimental setup
Metrics: total variation distance gate complexity query complexity
Builds on: quantum linear ODE solvers Fourier pseudo-spectral differentiation Chebyshev interpolation
Closest papers by meaning
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.88)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.84)
- Quantum speedup of non-linear Monte Carlo problems (NeurIPS 2025 · similarity 0.84)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.84)
- Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.84)
- One More Time: Revisiting Neural Quantum States from a Reinforcement Learning Perspective (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.