Quantum heuristic algorithm for traveling salesman problem
arXiv:1004.4124 · doi:10.3938/jkps.61.1944
Abstract
We propose a quantum heuristic algorithm to solve a traveling salesman problem by generalizing Grover search. Sufficient conditions are derived to greatly enhance the probability of finding the tours with extremal costs, reaching almost to unity and they are shown characterized by statistical properties of tour costs. In particular for a Gaussian distribution of the tours along the cost we show that the quantum algorithm exhibits the quadratic speedup of its classical counterpart, similarly to Grover search.
arXiv commentPublished version
References in corpus (15)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum algorithm for solving linear systems of equations
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Noiseless Quantum Codes
- Quantum computers can search rapidly by using almost any transformation
- Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
- Quantum annealing of the Traveling Salesman Problem
- Manipulating biphotonic qutrits
- Phase matching in quantum searching
- Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Programmable networks for quantum algorithms
- Quantum search on structured problems
- Quantum Optimization for Combinatorial Searches