Quantum Adiabatic Computation and the Travelling Salesman Problem
arXiv:quant-ph/0601151
Abstract
The NP-complete problem of the travelling salesman (TSP) is considered in the framework of quantum adiabatic computation (QAC). We first derive a remarkable lower bound for the computation time for adiabatic algorithms in general as a function of the energy involved in the computation. Energy, and not just time and space, must thus be considered in the evaluation of algorithm complexity, in perfect accordance with the understanding that all computation is physical. We then propose, with oracular Hamiltonians, new quantum adiabatic algorithms of which not only the lower bound in time but also the energy requirement do not increase exponentially in the size of the input. Such an improvement in both time and energy complexity, as compared to all other existing algorithms for TSP, is apparently due to quantum entanglement. We also appeal to the general theory of Diophantine equations in a speculation on physical implementation of those oracular Hamiltonians.
7 pages. Explanation added for the derivation of the lower bound on computation time
References in corpus (15)
- Quantum Mechanics helps in searching for a needle in a haystack
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum Search by Local Adiabatic Evolution
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Quantum Adiabatic Evolution Algorithms with Different Paths
- A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
- A reformulation of Hilbert's tenth problem through Quantum Mechanics
- Energy and Efficiency of Adiabatic Quantum Search Algorithms
- Quantum adiabatic algorithm for Hilbert's tenth problem: I. The algorithm
- Quantum Register Physics
- A Random Matrix Model of Adiabatic Quantum Computing
- Quantum Adiabatic Algorithm and Large Spin Tunnelling
- Local adiabatic quantum search with different paths
- Quantum search algorithm by adiabatic evolution under a priori probability
- Eigenlevel statistics of the quantum adiabatic algorithm