Towards Efficiently Solving Quantum Traveling Salesman Problem

Simple item page
dc.creatorGoswami, Debabrata
dc.creatorKarnick, Harish
dc.creatorJain, Prateek
dc.creatorMaji, Hemanta K.
dc.date2004-11-02
dc.date.accessioned2026-07-07T06:11:24Z
dc.date.available2026-07-07T06:11:24Z
dc.descriptionWe 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.
dc.description4 pages, 3 tables, PRL (submitted)
dc.identifierhttps://arxiv.org/abs/quant-ph/0411013
dc.identifierhttp://arxiv.org/abs/quant-ph/0411013
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/92477
dc.subjectQuantum Physics
dc.titleTowards Efficiently Solving Quantum Traveling Salesman Problem
dc.typetext

Files

Collections

arXiv