A Sublinear-Time Quantum Algorithm for Approximating Partition Functions

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 Štefankovič, 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 $k$-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.

arXiv comment24 pages; v2: improved Theorem 3.3 and volume estimation

References in corpus (17)

• Quantum Amplitude Amplification and Estimation
• Quantum measurements and the Abelian Stabilizer Problem
• Quantum speedup of Monte Carlo methods
• Quantum Metropolis Sampling
• Search via Quantum Walk
• Fixed-point quantum search with an optimal number of queries
• Speed-up via Quantum Sampling
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Quantum Speed-up for Approximating Partition Functions
• Quantum Sub-Gaussian Mean Estimator
• Fast quantum algorithms for numerical integrals and stochastic processes
• Approximation algorithms for the normalizing constant of Gibbs distributions
• An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• A Faster Approximation Algorithm for the Gibbs Partition Function
• Quantum algorithm for estimating volumes of convex bodies

Cited by in corpus (5)

• Amplitude Estimation from Quantum Signal Processing
• Optimal quantum algorithm for Gibbs state preparation
• Quantum algorithm for copula-based risk aggregation using orthogonal series density estimation
• On Quantum Perceptron Learning via Quantum Search
• On the bias in iterative quantum amplitude estimation