A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
From MaRDI portal
Publication:6405335
DOI10.1137/1.9781611977554.CH46arXiv2207.08643OpenAlexW4316652405MaRDI QIDQ6405335
Author name not available (Why is that?)
Publication date: 18 July 2022
Abstract: We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first speed-up of this type to be obtained over the seminal nearly-linear time algorithm of v{S}tefankoviv{c}, Vempala and Vigoda [JACM, 2009]. Our result also preserves the quadratic speed-up in precision and spectral gap achieved in previous work by exploiting the properties of quantum Markov chains. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of -colorings, matchings or independent sets of a graph, and estimating the volume of a convex body. Our approach relies on developing new variants of the quantum phase and amplitude estimation algorithms that return nearly unbiased estimates with low variance and without destroying their initial quantum state. We extend these subroutines into a nearly unbiased quantum mean estimator that reduces the variance quadratically faster than the classical empirical mean. No such estimator was known to exist prior to our work. These properties, which are of general interest, lead to better convergence guarantees within the paradigm of simulated annealing for computing partition functions.
Full work available at URL: https://doi.org/10.1137/1.9781611977554.ch46
No records found.
This page was built for publication: A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405335)
