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

arXiv:1808.01275 · Physical Review Research

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

Flavio Baccari, Christian Gogolin, Peter Wittek, Antonio Acín

Published Oct 30, 2020• 8 citations
arXivHTMLPDF

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.
DOI
10.1103/physrevresearch.2.043163

Related papers

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

Baccari, F., Gogolin, C., Wittek, P. +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.

•Jan 1, 2020•7 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

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

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

Low-Depth Mechanisms for Quantum Optimization

Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni +6 more

By gaining intuition about the mechanisms by which quantum optimization algorithms solve problems, approaches are identified that substantially improve the performance of quantum algorithms for this task.

arXiv:2008.08615•PRX Quantum•Jul 21, 2021•44 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.