Verifying the output of quantum optimizers with ground-state energy lower bounds

Abstract

Solving optimisation problems encoded in the ground state of classical-spin systems is a focus area for quantum computing devices, providing upper bounds to the unknown solution. To certify these bounds, they are compared to those obtained by classical methods. However, even if the quantum bound beats them, this says little about how close it is to the unknown solution. We consider the use of relaxations to the ground-state problem as a benchmark for the output of quantum optimisers. These relaxations are radically more informative because they provide lower bounds to the ground-state energy. The chordal branch and bound algorithm we present provides a series of systematically improving confidence regions where the ground-state energy provably lies. Interestingly, each step in the process requires only an effort polynomial in the system size. Additionally, the algorithm exploits the locality and sparsity of relevant Ising spin models in a systematic way. This yields certified solutions for many of the problems that are currently addressed by heuristic optimisation algorithms more efficiently and for larger system sizes. We apply the method to verify the output of a D-Wave 2000Q device and identify instances where the annealer does not reach the ground-state energy and, more importantly, instances where it does, something impossible to do by means of standard variational approaches. Our work provides a flexible and scalable method for the verification of the outputs produced by quantum optimization devices.

Resubmitted to match the published version. 14 pages + 5 figures, comments and suggestions are welcome. In memoriam of Peter Wittek, who was a source of inspiration for all of us

References in corpus (11)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Architectural considerations in the design of a superconducting quantum annealing processor
• What is the Computational Value of Finite Range Tunneling?
• Probing for quantum speedup in spin glass problems with planted solutions
• Convergent relaxations of polynomial optimization problems with non-commuting variables
• Algorithm 950: Ncpol2sdpa---Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables
• A deceptive step towards quantum speedup detection
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)

Cited by in corpus (5)

• Lower Bounding Ground-State Energies of Local Hamiltonians Through the Renormalization Group
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Certificates of quantum many-body properties assisted by machine learning
• The Coming Decades of Quantum Simulation
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping