Quantum Speed-up for Approximating Partition Functions

Abstract

We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo Markov Chain method and use non-adaptive cooling schedules. The improvement in time complexity is twofold: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grover's fixed point search, quantum walks and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed-up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. Second, we generalize the method of quantum counting, showing how to estimate expected values of quantum observables. Using this method instead of classical sampling, we obtain the speed-up with respect to accuracy.

17 pages; v3: corrected typos, added a reference about efficient implementations of quantum walks

References in corpus (5)

• Quantum Simulations of Classical Annealing Processes
• Speed-up via Quantum Sampling
• Quantum speedup of classical mixing processes
• Quantum Simulated Annealing
• Efficient Circuits for Quantum Walks

Cited by in corpus (33)

• Quantum machine learning: a classical perspective
• Quantum speedup of Monte Carlo methods
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• From transistor to trapped-ion computers for quantum chemistry
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
• Necessary Condition for the Quantum Adiabatic Approximation
• Introduction to Quantum Algorithms for Physics and Chemistry
• Quantum Walks
• Quantum Computing for Fusion Energy Science Applications
• Quantum annealing with Jarzynski equality
• Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
• Quantum Enhanced Inference in Markov Logic Networks
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Quantum algorithm for credit valuation adjustments
• Quantum algorithms for scientific computing
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Quantum Algorithm for Preparing Thermal Gibbs States - Detailed Analysis
• Low Depth Quantum Circuits for Ising Models
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Quantum algorithm for estimating volumes of convex bodies
• Estimating Gibbs partition function with quantumClifford sampling
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Quantum algorithms for multivariate Monte Carlo estimation
• Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network
• Quantum algorithm for exact Monte Carlo sampling
• Quantum Phase Estimation with an Arbitrary Number of Qubits
• Efficient Circuits for Quantum Walks
• Use of Quantum Sampling to Calculate Mean Values of Observables and Partition Function of a Quantum System
• Ising models and topological codes: classical algorithms and quantum simulation
• Quantum Chebyshev's Inequality and Applications
• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Quantum Phase Estimation with Arbitrary Constant-precision Phase Shift Operators