A quantum algorithm to count weighted ground states of classical spin Hamiltonians

Abstract

Ground state counting plays an important role in several applications in science and engineering, from estimating residual entropy in physical systems, to bounding engineering reliability and solving combinatorial counting problems. While quantum algorithms such as adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) can minimize Hamiltonians, they are inadequate for counting ground states. We modify AQO and QAOA to count the ground states of arbitrary classical spin Hamiltonians, including counting ground states with arbitrary nonnegative weights attached to them. As a concrete example, we show how our method can be used to count the weighted fraction of edge covers on graphs, with user-specified confidence on the relative error of the weighted count, in the asymptotic limit of large graphs. We find the asymptotic computational time complexity of our algorithms, via analytical predictions for AQO and numerical calculations for QAOA, and compare with the classical optimal Monte Carlo algorithm (OMCS), as well as a modified Grover's algorithm. We show that for large problem instances with small weights on the ground states, AQO does not have a quantum speedup over OMCS for a fixed error and confidence, but QAOA has a sub-quadratic speedup on a broad class of numerically simulated problems. Our work is an important step in approaching general ground-state counting problems beyond those that can be solved with Grover's algorithm. It offers algorithms that can employ noisy intermediate-scale quantum devices for solving ground state counting problems on small instances, which can help in identifying more problem classes with quantum speedups.

arXiv comment25 pages including bibliography and appendices; 5 figures

References in corpus (17)

• A Quantum Approximate Optimization Algorithm
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Reachability Deficits in Quantum Approximate Optimization
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• Practical optimization for hybrid quantum-classical algorithms
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• A quantum algorithm to train neural networks using low-depth circuits
• Uncertain fate of fair sampling in quantum annealing
• Classical and Quantum Bounded Depth Approximation Algorithms
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
• A Jacobi Diagonalization and Anderson Acceleration Algorithm For Variational Quantum Algorithm Parameter Optimization
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• A Quantum Approximate Optimization Algorithm for continuous problems
• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Cited by in corpus (4)

• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Quantum Information Scrambling: From Holography to Quantum Simulators
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering