Fetching the paper…
Reading the bibliography…
We show that the NP-hard quadratic unconstrained binary optimization (QUBO) problem on a graph $G$ can be solved using an adiabatic quantum computer that implements an Ising spin-1/2 Hamiltonian, by reduction through minor-embedding of $G$ in the quantum hardware graph $U$.
On the computational complexity of Ising spin glass models
F. Barahona · 1982
Earlier work this paper cites.
Introduction to parallel algorithms and architectures: arrays, trees, hypercubes
L. F. Thomson · 1992
Earlier work this paper cites.
Approximation algorithms for NP-complete problems on planar graphs
B. S. Baker · 1994
Earlier work this paper cites.
Graph minors. xiii: the disjoint paths problem
N. Robertson and P. D. Seymour · 1995
Earlier work this paper cites.
Short paths in expander graphs
J. M. Kleinberg and R. Rubinfeld · 1996
Earlier work this paper cites.
Quantum computation by adiabatic evolution
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 2000
Earlier work this paper cites.
A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda · 2001
Earlier work this paper cites.
How powerful is adiabatic quantum computation?
W. van Dam, M. Mosca, and U. Vazirani · 2001
Cited alongside, same era.
Limits on quantum adiabatic optimization
W. van Dam and U. Vazirani · 2001
Cited alongside, same era.
Pseudo-boolean optimization
E. Boros and P. Hammer · 2002
Cited alongside, same era.
Robustness of adiabatic quantum computation
A. Childs, E. Farhi, and J. Preskill · 2002
Cited alongside, same era.
Adiabatic quantum computation is equaivalent to standard quantum computation
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev · 2004
Cited alongside, same era.
Scalable architecture for adiabatic quantum computing of NP-hard problems
W. M. Kaminsky and S. Lloyd · 2004
Cited alongside, same era.
The quantum adiabatic optimization algorithm and local minima
B. W. Reichardt · 2004
Later among the works it cites.
Graph Theory
R. Diestel · 2005
Later among the works it cites.
Preprocessing of quadratic unconstrained binary optimization
E. Boros, P. L. Hammer, and G. Tavares · 2006
Later among the works it cites.
The complexity of the local hamiltonian problem
J. Kempe, A. Kitaev, and O. Regev · 2006
Later among the works it cites.
Limitations of some simple adiabatic quantum algorithms
L. M. Ioannou and M. Mosca · 2007
Later among the works it cites.
Work in progress
M. H. S. Amin and V. Choi · 2008
Closest in time.
Thermally assisted adiabatic quantum computation
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Scalable superconducting architecture for adiabatic quantum computation
W. M. Kaminsky, S. Lloyd, and T. P. Orlando · 2004
Cited alongside, same era.
The role of single qubit decoherence time in adiabatic quantum computation
M. H. S. Amin, C. J. S. Truncik, and D. V. Averin
Cited in the paper.
A classical approximation scheme for the ground-state energy of Ising spin hamiltonians on planar graphs
N. Bansal, S. Bravyi, and B. M. Terhal
Cited in the paper.
Simulation of many-body hamiltonians using perturbation theory with bounded-strength interactions
S. Bravyi, D. P. DiVincenzo, D. Loss, and B. M. Terhal
Cited in the paper.
The complexity of quantum spin systems on a two-dimensional square lattice
R. Oliveira and B. M. Terhal
Cited in the paper.
M. H. S. Amin, P. J. Love, and C. J. S. Truncik · 2008
Closest in time.