Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments

Vrinda Mehta, Hans De Raedt, Kristel Michielsen, Fengping Jin · 2025

Read Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments by Vrinda Mehta, Hans De Raedt, Kristel Michielsen, Fengping Jin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-01423.txt.

Description

Vrinda Mehta and co-authors test how quantum annealing performs on hard 2-SAT problems that have several correct answers. Logic problems with multiple solutions stress samplers in special ways. Both simulated and physical annealers were put to work.

The team built a set of especially hard instances. Standard and reverse annealing protocols were tried on each. Ideal theory explains sampling through energy gap behavior. Time to solution depends on the smallest gap along the path. Real D-Wave hardware broke from that ideal picture. Its timing matched equilibrium probability predictions instead. The mismatch reveals noise effects in current machines. Results guide expectations for near-term quantum devices. It is a hard test for both routes.

Catalog record

CREATORVrinda Mehta, Hans De Raedt, Kristel Michielsen, Fengping Jin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-01423

Browse the full library · About the Tower of Babel