Scientific Reports · 2016 · 20 citations · 62 references
ComputingComputer SciencePhysicsAlgorithmsComputational BiologyQuantum ComputingCombinatorial OptimizationGraph AlgorithmsQuantum AlgorithmsQuantum AnnealingQuantum ComputationComputational Biology ModelsIsing Model FormulationQuantum Annealing SimulationSet CoverSet Cover ProblemSimulated AnnealingTime-independent Schrödinger Equation
Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology, and biochemistry. We show an explicit construction of Ising Hamiltonians whose ground states encode the solution of SCP instances. We numerically simulate the time-dependent Schrödinger equation in order to test the performance of quantum annealing for random instances and compare with that of simulated annealing. We also discuss explicit embedding strategies for realizing our Hamiltonian construction on the D-wave type restricted Ising Hamiltonian based on Chimera graphs. Our embedding on the Chimera graph preserves the structure of the original SCP instance and in particular, the embedding for general complete bipartite graphs and logical disjunctions may be of broader use than that the specific problem we deal with.
62
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Ising formulations of many NP problems
Andrew Lucas · Frontiers in Physics · 2014 · 2.5K citations · Full text
Computing, Computer Science, Physics +15
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et al. · Science · 2001 · 2.1K citations · Full text
Computing, Computer Science, Physics +15
Quantum annealing with manufactured spins
Mark W. Johnson, M. H. S. Amin, S. Gildert et al. · Nature · 2011 · 1.9K citations