Research map / Learning theory and algorithms / Sample complexity
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
Andrew Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace gradient-oracle queries with quantum evaluation-oracle queries in ULD-RMM | ULD-RMM · Log-concave sampling (W2) | query complexity: classical: \widetilde O\mathopen{}\mathclose\bgroup\originalleft(\kappa^{7/6}d^{1/6}\epsilon^{-1/3}+\kappa d^{1/3}\epsil | Improved |
| Use quantum MALA instead of classical MALA | MALA · Log-concave sampling (TV) | query complexity: \widetilde O\mathopen{}\mathclose\bgroup\originalleft(\kappa d\aftergroup\egroup\originalright) -> \widetilde O\mathopen | Improved |
| Use quantum MALA with a warm-start distribution | MALA · Log-concave sampling (TV, warm start) | query complexity: \widetilde O\mathopen{}\mathclose\bgroup\originalleft(\kappa d^{1/2}\aftergroup\egroup\originalright) -> \widetilde O\ma | Improved |
| Apply quantum mean estimation in multilevel ULD-RMM annealing | Multilevel ULD-RMM · Normalizing constant estimation | query complexity: \widetilde O\mathopen{}\mathclose\bgroup\originalleft(\kappa^{7/6}d^{7/6}\epsilon^{-2}+\kappa d^{4/3}\epsilon^{-2}\after | Improved |
| Apply quantum mean estimation in multilevel ULD annealing | Multilevel ULD · Normalizing constant estimation | query complexity: \widetilde O\mathopen{}\mathclose\bgroup\originalleft(\kappa^2d^{3/2}\epsilon^{-2}\aftergroup\egroup\originalright) -> \ | Improved |
| Combine quantum MALA with quantum annealing and non-destructive mean estimation | MALA · Normalizing constant estimation | query complexity: \widetilde O\mathopen{}\mathclose\bgroup\originalleft(\kappa d^2\epsilon^{-2}\max\{1,\frac{\kappa}{d}\}\aftergroup\egrou | Improved |
Closest papers by meaning
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.93)
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.88)
- Quantum (Inspired) $D^2$-sampling with Applications (ICLR 2025 · similarity 0.88)
- 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.87)
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
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.
