Research map / Optimization / Nonconvex and smooth optimization
Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions
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.
Gives quantum simulated-annealing samplers for non-logconcave Gibbs distributions based on ULA (full and stochastic gradients) and a quantum partition-function estimator, using MALA as a reversible bridge for the analysis.
Problem
Quantum sampling from possibly non-logconcave Gibbs distributions exp(-beta f(x)) with finite-sum f, where ULA is non-reversible and existing quantum walk spectral-gap analyses do not apply; also estimating partition functions for such distributions.
Approach
Quantum simulated annealing over a sequence of Gaussian-tempered targets, with quantum walk operators built from unadjusted Langevin transitions (optionally with mini-batch stochastic gradients); the error from replacing the reversible MALA walk by the non-reversible ULA walk is bounded via Hellinger distance and a perturbation analysis, using MALA as a hypothetical reversible bridge.
Key results
- Quantum MALA samples with Õ(βd ρ^-1 c_LSI^-1) queries to full gradient and evaluation oracles.
- Quantum ULA needs Õ(β d^{3/2} ε^-1 ρ^-1 c_LSI^-1) full-gradient queries, versus classical ULA Õ(d/ε^2) per the paper's comparison table.
- Stochastic quantum ULA needs Õ(β^2 d^{3/2} ε^-2 ρ^-2 c_LSI^-1) mini-batch oracle queries, each with O(d) gradient calculations (total Õ(d^{5/2}/ε^2) gradient evaluations).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum simulated annealing with MALA walks instead of classical MALA sampling | Non-logconcave Gibbs sampling · Non-logconcave Gibbs sampling | dimension dependence of query complexity: \tilde{O}(d^{2}) -> \tilde{O}(d ) | Helped |
| Use quantum ULA instead of classical ULA | Non-logconcave Gibbs sampling · Non-logconcave Gibbs sampling | dimension dependence of query complexity: \tilde{O}(d/\epsilon^2) -> \tilde{O}(d^{3/2}/\epsilon) | Helped |
| Use stochastic-gradient quantum ULA rather than classical SGLD | Non-logconcave Gibbs sampling · Non-logconcave Gibbs sampling | dimension dependence of query complexity: \tilde{O}(d^4/\epsilon^2) -> \tilde{O}(d^{5/2}/\epsilon^2) | Helped |
| Replace the full-gradient oracle with a stochastic-gradient oracle | Quantum ULA · Non-logconcave Gibbs sampling | oracle access cost | Mixed |
Surprising findings
- The quantum walk for non-reversible ULA can be analyzed despite no detailed balance, by bounding its deviation from a reversible MALA bridge chain.
Limitations
- Results are theoretical query-complexity bounds with no implementation or experiments.
- Stochastic variant's gradient complexity scales as d^{5/2}/ε^2 and carries stronger dependence on ρ and β.
- Assumes smoothness and dissipativeness; relies on Cheeger and log-Sobolev constants that may be exponential in dimension for general f.
Experimental setup
Metrics: query complexity total variation distance
Baselines: classical ULA classical MALA SGLD quantum MALA
Builds on: Childs et al. quantum MALA via simulated annealing Szegedy quantum walk Metropolis-adjusted Langevin algorithm fixed-point amplitude amplification
Closest papers by meaning
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Gibbs Sampling of Continuous Potentials on a Quantum Computer (ICML 2024 · similarity 0.88)
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.87)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.86)
- Chain of Log-Concave Markov Chains (ICLR 2024 · similarity 0.86)
- Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.86)
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.