Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions

Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, Chunhao Wang
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:38953-38982, 2024.

Abstract

We present quantum algorithms for sampling from possibly non-logconcave probability distributions expressed as $\pi(x) \propto \exp(-\beta f(x))$ as well as quantum algorithms for estimating the partition function for such distributions. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients when $f$ can be written as a finite sum. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density matrix, making the quantum algorithms nontrivial to analyze. We overcame these challenges by first building a reference reversible Markov chain that converges to the target distribution, then controlling the discrepancy between our algorithm’s output and the target distribution by using the reference Markov chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of dimension or precision dependencies when compared to best-known classical algorithms under similar assumptions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-ozgul24a, title = {Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions}, author = {Ozgul, Guneykan and Li, Xiantao and Mahdavi, Mehrdad and Wang, Chunhao}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {38953--38982}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/ozgul24a/ozgul24a.pdf}, url = {https://proceedings.mlr.press/v235/ozgul24a.html}, abstract = {We present quantum algorithms for sampling from possibly non-logconcave probability distributions expressed as $\pi(x) \propto \exp(-\beta f(x))$ as well as quantum algorithms for estimating the partition function for such distributions. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients when $f$ can be written as a finite sum. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density matrix, making the quantum algorithms nontrivial to analyze. We overcame these challenges by first building a reference reversible Markov chain that converges to the target distribution, then controlling the discrepancy between our algorithm’s output and the target distribution by using the reference Markov chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of dimension or precision dependencies when compared to best-known classical algorithms under similar assumptions.} }
Endnote
%0 Conference Paper %T Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions %A Guneykan Ozgul %A Xiantao Li %A Mehrdad Mahdavi %A Chunhao Wang %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-ozgul24a %I PMLR %P 38953--38982 %U https://proceedings.mlr.press/v235/ozgul24a.html %V 235 %X We present quantum algorithms for sampling from possibly non-logconcave probability distributions expressed as $\pi(x) \propto \exp(-\beta f(x))$ as well as quantum algorithms for estimating the partition function for such distributions. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients when $f$ can be written as a finite sum. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density matrix, making the quantum algorithms nontrivial to analyze. We overcame these challenges by first building a reference reversible Markov chain that converges to the target distribution, then controlling the discrepancy between our algorithm’s output and the target distribution by using the reference Markov chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of dimension or precision dependencies when compared to best-known classical algorithms under similar assumptions.
APA
Ozgul, G., Li, X., Mahdavi, M. & Wang, C.. (2024). Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:38953-38982 Available from https://proceedings.mlr.press/v235/ozgul24a.html.

Related Material