analiza aiqbench
This paper presents a significant advancement in quantum algorithms by establishing an unbiased framework for estimating Gibbs expectations, even for challenging non-log-concave and heavy-tailed distributions. By eliminating discretization biases through a change-of-measure approach, the proposed method achieves a quadratic speedup over classical multilevel Monte Carlo methods under relaxed convexity assumptions. These results expand the practical utility of quantum computing in statistics, machine learning, and finance by addressing previously difficult stochastic processes.
Quantum Algorithms for Gibbs Expectation of Non-log-concave and Heavy-tailed Distributions
arXiv:2604.00656v2 Announce Type: replace Abstract: We establish a systematic framework of unbiased quantum sampling and estimation protocols for the classical Gibbs expectation. This framework generalizes existing approaches to the partition function estimation and has broader applications in various fields. We consider sampling and estimation for a wide class of non-log-concave distributions, particularly heavy-tailed ones, under relaxed assumptions beyond strong convexity, such as dissipativity. We develop an unbiased extension of quantum-accelerated multilevel Monte Carlo (QA-MLMC) to eliminate all biases from discretization and time truncation, together with introducing a change-of-measure approach and the Girsanov theorem via Radon-Nikodym derivatives. As a result, our approach achieves quantum complexity $\widetilde{\mathcal{O}}(\epsilon^{-1})$ within error $\epsilon$, whereas the classical MLMC requires $\widetilde{\mathcal{O}}(\epsilon^{-2})$ and existing quantum algorithms yield biased estimators under stronger assumptions. Furthermore, our unified framework enables unbiased quantum sampling and estimation for certain heavy-tailed distributions after transformation. We provide several concrete applications of our approach in statistics, machine learning, and finance, towards more practical scenarios of the quantum acceleration of stochastic processes.
Abstract:We establish a systematic framework of unbiased quantum sampling and estimation protocols for the classical Gibbs expectation. This framework generalizes existing approaches to the partition function estimation and has broader applications in various fields. We consider sampling and estimation for a wide class of non-log-concave distributions, particularly heavy-tailed ones, under relaxed assumptions beyond strong convexity, such as dissipativity. We develop an unbiased extension of quantum-accelerated multilevel Monte Carlo (QA-MLMC) to eliminate all biases from discretization and time truncation, together with introducing a change-of-measure approach and the Girsanov theorem via Radon-Nikodym derivatives. As a result, our approach achieves quantum complexity $\widetilde{\mathcal{O}}(\epsilon^{-1})$ within error $\epsilon$, whereas the classical MLMC requires $\widetilde{\mathcal{O}}(\epsilon^{-2})$ and existing quantum algorithms yield biased estimators under stronger assumptions. Furthermore, our unified framework enables unbiased quantum sampling and estimation for certain heavy-tailed distributions after transformation. We provide several concrete applications of our approach in statistics, machine learning, and finance, towards more practical scenarios of the quantum acceleration of stochastic processes.
arXiv:2604.00656 [quant-ph]
(or arXiv:2604.00656v2 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2604.00656 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 249 cuvinte