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
| CREATOR | Vrinda Mehta, Hans De Raedt, Kristel Michielsen, Fengping Jin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-01423