2000/12/20 by Steve Huntsman, Huntsman, Steve
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0012112
5 pages, pdf only [Finally deleted a blooper paragraph about expected runtimes that is only true for Euclidean TSP and has a bum eqn anyway. Does not affect anything that matters (temperature v precision etc)]
arxiv created 2002/12/09 · arxiv updated 2009/12/01
The question of whether or not quantum computers can efficiently solve NP-complete problems is open, although indications are that BQP does not contain NP. Still, many of these problems are natural candidates for solution on quantum computers. We outline a thermodynamical formalism for the traveling salesman problem which allows for its expected polytime solution on a quantum computer with probability arbitrarily close to unity, given sufficient energy resources and subject to a weak nondegeneracy constraint on the distances. Applications to other problems are also discussed.