The authors convert classical software bug detection into quantum optimization instances and test QAOA, Grover, and QSVT on small examples for potential polynomial speedup.
Ising formulations of many NP prob- lems
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We provide Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems. This collects and extends mappings to the Ising model from partitioning, covering and satisfiability. In each case, the required number of spins is at most cubic in the size of the problem. This work may be useful in designing adiabatic quantum optimization algorithms.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 2verdicts
UNVERDICTED 2roles
background 1polarities
background 1representative citing papers
Quantum annealing is described as a heuristic for discrete optimization and sampling that also serves as a platform for studying non-equilibrium many-body quantum dynamics with programmable spin systems.
citing papers explorer
-
Towards Classical Software Verification using Quantum Computers
The authors convert classical software bug detection into quantum optimization instances and test QAOA, Grover, and QSVT on small examples for potential polynomial speedup.
-
Quantum Annealing: Optimisation, Sampling, and Many-Body Dynamics
Quantum annealing is described as a heuristic for discrete optimization and sampling that also serves as a platform for studying non-equilibrium many-body quantum dynamics with programmable spin systems.