National Journal of System and Information Technology

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Quantum Computer and Quantum Algorithm for Travelling Salesman Problem


     

   Subscribe/Renew Journal


Depending upon the extraordinary power of Quantum Computing Algorithms various branches like Quantum Cryptography, Quantum Information Technology, Quantum Teleportation have emerged [1-4]. It is thought that this power of Quantum Computing Algorithms can also be successfully applied to many combinatorial optimization problems. In this article, a class of combinatorial optimization problem is chosen as case study under Quantum Computing. These problems are widely believed to be unsolvable in polynomial time. Mostly it provides suboptimal solutions in finite time using best known classical algorithms. Travelling Salesman Problem (TSP) is one such problem to be studied here. A great deal of effort has already been devoted towards devising efficient algorithms that can solve the problem [5-18]. Moreover, the methods of finding solutions for the TSP with Artificial Neural Network and Genetic Algorithms [5-8] do not provide the exact solution to the problems for all the cases, excepting a few. A successful attempt has been made to have a deterministic solution for TSP by applying the power of Quantum Computing Algorithm.

Keywords

Quantum Computing, Travelling Salesman Problem, Quantum Algorithms
Subscription Login to verify subscription
User
Notifications
Font Size


  • P.W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,",Proc. Of the 35th Annual Symposium on the Foundation of Computer Science, IEEE Computer Society Press, Los Alamitos, California, 1994), pp.124-134.

  • R. Rivest, A. Shamir and L. Adelman, Communication ACM 21, 120(1978).

  • D. Deutsch, ``Quantum Theory is a universal physical theory," Int. J. Theor. Phys. 24, 1-41(1985); ``Quantum Theory the Crunch turning Principle and the universal quantum computer,” Proc. Roy. Soc. Lond. A 400 97-117(1985)

  • R.P. Feynman, ``Simulating physics with computers," Int. J. Theor. Phys. 21, 467- 488(1982);``Quantum Mechanical Computers," 507-531.

  • S. Haykin, 1999, Neural Networks-a Comprehensive foundation, Prentice Hall.

  • The TSP home page, Mathematics Department, university Princeton, http://www.math.princeton.edu/tsp/index.html.

  • J.J.Hopfield, D.W.Tank, 1985. Neural Computation of decisions in Optimization Problem, Biological cybernetics, vol.52, pp.141-152”.

  • G.V.Wilson, G.S.Pawley, 1988. On the Stability of the Travelling Salesman problem Algorithm of Hopfield and Tank, Biological Cybernetics, vol.58, pp.63-70.

  • Gee, S.V.B.Aiyer, R.Prager, 1993. An Analytical framework for Optimizing Neural Networks, vol.6, pp.79-97.

  • S.V.B.Aiyer, M.Niranjan, F.Fallside, 1990. A theoretical investigation into the performance of the Hopfield model, IEEE Transactions on Neural Networks, vol.1, pp.204-215.

  • N.Ansari, E.Hou, 1997. Computational Intelligence For Optimization, Norwell, MA:Kluwer Academic publishing Group.

  • H. Crowder and M. Padberg, ``Solving large-scale symmetric Travelling salesman problems to optimality," Mgmt. Sci. 26 (1980),495-509.

  • M.Padberg and G.Rinaldi, ``Optimization of a 532-city symmetric Travelling salesman problem by branch and cut," Operations Res. Lett. 6 (1987), 1-7.

  • D.L.Applegate and W. Cook, ``Solving large-scale matching problems," in {it Network Flows and Matching: First DIMACS Implementation Challenge}, American mathematical Society,Providence,RI,1993,557-576.

  • M.Padberg and G.Rinaldi, ``A branch-and-cut algorithm for the resolution of largescale symmetric Travelling salesman problems," {it SIAM Review} 33 (1991),60-100.

  • M.Gr"otschel and O. Holland, ``Solution of large-scale symmetric Travelling salesman problems," Math. Programming 141-202 (1991).

  • D.Applegate, R.Bixby, V.Chv'atal, and W. Cook, private communication(1994).

  • E.L.Lawler,J.K.Lenstra, A.H.G.Rinnooy Kan, and D.B.Shmoys,{it The Travelling Salesman Problem}, John Wiley & Sons,Chichester, 1985.

  • M.R.Garey, and D.S.Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness}, W.H.Freeman, San Francisco, 1979.

  • M.A. Nielson and I.L. Chang; Quantum Computation and Quantum Information, Cambridge, U.K. Cambridge Univ. Press, 2000

  • Josef Gruska; Quantum Computing, The McGraw-Hill Companies, 1999.

  • http://cam.qubit.org//links.php

  • B.Oemer(2003), http://tph.tuwien.ac.at/~oemer/qcl.html.

  • Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi and H. J. Kimble, “ Measurement of Conditional phase shifts for quantum logic”, Phys. Rev. Lett. 75, 4710-4713.

  • C. Monroe, D.M. Meekkhof, B.E. King, W.M. Itano and D.J. Wineland, “ demonstration of Fundamental of logic gates”.

  • N. Gershenfeld and I. Chuang, “ Bulk spin-resonance quantum computation”, Science 275, 350-356(1997).

  • P.W. Shor, “Scheme for reducing decoherence in quantum computer memory”, Phys. Rev. A52, R2493-R2496(1995).

  • P. Benoiff, “ The computer as a physical system: microscopic quantum mechanical Hamiltonian model of Computers as rpresented by Turing Mechines”, J. Stat. Physics, 22 563-591(1980); “Quantum Mechanical Hamiltonian models of discrete processes”, J. Math. Phys. 22, 495-507(1981); “ Quantum Mechanical Model for Turing Machines that dissipate no energy,” Phys. Rev. Lett. 48, 1581-1585(1982); “Quantum Mechanical Hamiltonian models of Turing machines,” J. Stat. Phys. 29, 515-546(1982).

  • D. Deutsch, “ Quantum Theory as a Universal Physical Theory”, Int. J. Theor. Phys. 24, 1-41(1985); “Quantum theory, the Church-Turing principle and the Universal Quantum Computer,” Proc. Roy. Soc. London. A 400, 97-117(1985).

  • M.R. Garey and D.S. Johnson(1979). Computer and Intractability. A Guide to the NP-Completeness. Ney York, NY:W.H Freeman and Company.

  • D. Applegate, R. Bixby, V. Chavatal and W. Cook [1988] on the solution of the Travelling Salesman Problem, Documenta Mathematica 3, 645-756.

  • Held and R. M. Karp[1962]. A Dynamic programming Approach to sequencing Problem.

  • R.Z. Hwang, R.C. Chang and R.C.T. Lee[1993]. The searching over separator strategy to solve some NP-Hard problems in sub exponential time. Algorithemica 9, 398-423.


Abstract Views: 405

PDF Views: 2




  • Quantum Computer and Quantum Algorithm for Travelling Salesman Problem

Abstract Views: 405  |  PDF Views: 2

Authors

Abstract


Depending upon the extraordinary power of Quantum Computing Algorithms various branches like Quantum Cryptography, Quantum Information Technology, Quantum Teleportation have emerged [1-4]. It is thought that this power of Quantum Computing Algorithms can also be successfully applied to many combinatorial optimization problems. In this article, a class of combinatorial optimization problem is chosen as case study under Quantum Computing. These problems are widely believed to be unsolvable in polynomial time. Mostly it provides suboptimal solutions in finite time using best known classical algorithms. Travelling Salesman Problem (TSP) is one such problem to be studied here. A great deal of effort has already been devoted towards devising efficient algorithms that can solve the problem [5-18]. Moreover, the methods of finding solutions for the TSP with Artificial Neural Network and Genetic Algorithms [5-8] do not provide the exact solution to the problems for all the cases, excepting a few. A successful attempt has been made to have a deterministic solution for TSP by applying the power of Quantum Computing Algorithm.

Keywords


Quantum Computing, Travelling Salesman Problem, Quantum Algorithms

References