Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Baccari, F., Gogolin, C., Wittek, P., Acin, A.

Published Jan 1, 2020• 7 citations
OpenAlex

Abstract

The authors show how to benchmark the output of quantum devices designed to solve optimization problems encoded in the ground-state configuration of classical spin systems by means of lower bounds to the ground-state energy obtained by semi-definite programming.

Related papers

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

Flavio Baccari, Christian Gogolin, Peter Wittek +1 more

The authors show how to benchmark the output of quantum devices designed to solve optimization problems encoded in the ground-state configuration of classical spin systems by means of lower bounds to the ground-state energy obtained by semi-definite programming.

arXiv:1808.01275•Physical Review Research•Oct 30, 2020•8 citations

A device-oriented optimizer for solving ground state problems on an approximate quantum computer, Part II: Experiments for interacting spin and molecular systems

Abhinav Kandala, Antonio Mezzacapo, Kristan Temme +7 more

Bulletin of the American Physical Society•Mar 14, 2017•0 citations

Chordal branch and bound algortihms for spin glasses

García Hernández, Álvaro

In the era of quantum technology, benchmarking classical algorithms is necessary for certifying the results given by the quantum device to the optimization problem that is wanted to solve. Here we analyse a new algorithm that gives an upper and a lower bound to the ground state solution of Ising type optimization problems. We test its performance in solution planted problems and compare it with simulated annealing, a common algorithm to solve optimization problems, getting in general more reliable results in the same amount of time. Additionally, we verify the tunable hardness of the planting schemes used to generate the optimization problems.

•Jul 7, 2022•0 citations

Lower bounds for ground states of condensed matter systems

Tillmann Baumgratz, Martin Bodo Plenio

Standard variational methods tend to obtain upper bounds on the ground state energy of quantum many-body systems. Here we study a complementary method that determines lower bounds on the ground state energy in a systematic fashion, scales polynomially in the system size and gives direct access to correlation functions. This is achieved by relaxing the positivity constraint on the density matrix and replacing it by positivity constraints on moment matrices, thus yielding a semi-definite programme. Further, the number of free parameters in the optimization problem can be reduced dramatically under the assumption of translational invariance. A novel numerical approach, principally a combination of a projected gradient algorithm with Dykstra's algorithm, for solving the optimization problem in a memory-efficient manner is presented and a proof of convergence for this iterative method is given. Numerical experiments that determine lower bounds on the ground state energies for the Ising and Heisenberg Hamiltonians confirm that the approach can be applied to large systems, especially under the assumption of translational invariance.

arXiv:1106.5275•New Journal of Physics•Feb 13, 2012•44 citations

A device-oriented optimizer for solving ground state problems on an approximate quantum computer, Part I: Theory

Antonio Mezzacapo, Abhinav Kandala, Kristan Temme +7 more

Bulletin of the American Physical Society•Mar 14, 2017•0 citations

Bootstrapping Lattice Vacua

Scott Lawrence

This paper demonstrates the application of semidefinite programming to lattice field theories, showcasing spin chains and lattice scalar field theory. Requiring expectation values of manifestly positive semi-definite operators to be non-negative results in a lower bound on the ground-state energy of any quantum mechanical system, which can be made arbitrarily tight for systems described by finite-dimensional Hilbert spaces. Such bounds can be obtained directly in the infinite-volume limit. The process of optimizing these lower bounds also yields estimates for a chosen set of expectation values in the ground state.

arXiv:2111.13007•Nov 25, 2021•2 citations
In the era of quantum technology, benchmarking classical algorithms is necessary for certifying the results given by the quantum device to the optimization problem that is wanted to solve. Here we analyse a new algorithm that gives an upper and a lower bound to the ground state solution of Ising type optimization problems. We test its performance in solution planted problems and compare it with simulated annealing, a common algorithm to solve optimization problems, getting in general more reliable results in the same amount of time. Additionally, we verify the tunable hardness of the planting schemes used to generate the optimization problems.
Standard variational methods tend to obtain upper bounds on the ground state energy of quantum many-body systems. Here we study a complementary method that determines lower bounds on the ground state energy in a systematic fashion, scales polynomially in the system size and gives direct access to correlation functions. This is achieved by relaxing the positivity constraint on the density matrix and replacing it by positivity constraints on moment matrices, thus yielding a semi-definite programme. Further, the number of free parameters in the optimization problem can be reduced dramatically under the assumption of translational invariance. A novel numerical approach, principally a combination of a projected gradient algorithm with Dykstra's algorithm, for solving the optimization problem in a memory-efficient manner is presented and a proof of convergence for this iterative method is given. Numerical experiments that determine lower bounds on the ground state energies for the Ising and Heisenberg Hamiltonians confirm that the approach can be applied to large systems, especially under the assumption of translational invariance.
This paper demonstrates the application of semidefinite programming to lattice field theories, showcasing spin chains and lattice scalar field theory. Requiring expectation values of manifestly positive semi-definite operators to be non-negative results in a lower bound on the ground-state energy of any quantum mechanical system, which can be made arbitrarily tight for systems described by finite-dimensional Hilbert spaces. Such bounds can be obtained directly in the infinite-volume limit. The process of optimizing these lower bounds also yields estimates for a chosen set of expectation values in the ground state.