Towards Efficiently Solving Quantum Traveling Salesman Problem

Details Towards Efficiently Solving Quantum Traveling Salesman Problem Towards Efficiently Solving Quantum Traveling Salesman Problem

2004-11-02

arxiv.org/abs/quant-ph/0411013v1

Physics

Quantum Physics

4 pages, 3 tables, PRL (submitted)

Scientific paper

We present a framework for efficiently solving Approximate Traveling Salesman Problem (Approximate TSP) for Quantum Computing Models. Existing representations of TSP introduce extra states which do not correspond to any permutation. We present an efficient and intuitive encoding for TSP in quantum computing paradigm. Using this representation and assuming a Gaussian distribution on tour-lengths, we give an algorithm to solve Approximate TSP (Euclidean) within BQP resource bounds. Generalizing this strategy for any distribution, we present an oracle based Quantum Algorithm to solve Approximate TSP. We present a realization of the oracle in the quantum counterpart of PP.

Affiliated with

Also associated with

No associations

Rating

Towards Efficiently Solving Quantum Traveling Salesman Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards Efficiently Solving Quantum Traveling Salesman Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards Efficiently Solving Quantum Traveling Salesman Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-340503