Travelling Salesperson Problem with Quantum Computing

Travelling Salesperson Problem with Quantum Computing

st

1 Bhanu Lalith Aakash Medury

Computer Science and Engineering-2/4 Vidya Jyothi Institute of Technology Hyderabad, Telanagana

nd

2 Vyoma Harshitha Podapati

Computer Science and Engineering-2/4

G. Narayanamma Institute of Technology and Sciences Hyderabad, Telanagana

AbstractCombinatorial optimization problems involve find- ing an optimal solution from a finite set of feasible solutions. Dynamic Programming attempts to solve a combinatorial prob- lem by performing an exhaustive search over the entire domain of the problem. In many such cases, this exhaustive search is not effective or tractable. Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin. Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance. The route can be optimal either by cost or by distance. The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity. For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially. However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes. A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.

1. Keywords

   Travelling Salesperson Problem, Combinatorial Optimiza- tion, Quantum Computing, Quantum Mechanics, Quantum Computer, Quantum Bits, Quantum Superposition, Quan- tum Entanglement, Quanutum Coupling, Quantum Tunnelling, Quantum Annealing.

2. Abbreviations and Acronyms

   Travelling Salesperson Problem(TSP), Dynamic Program- ming(DP), Quantum Computing(QC), Quantum Mechan- ics(QM), Quantum Bit(Qubit).

   1. INTRODUCTION

      Combinatorial Optimization problems, especially the problems that are categorized as NP-hard problems are often difficult to solve using classical computers. Travelling Salesperson Problem(TSP) is one such combinatorial optimization problem in which a salesperson is supposed to travel N cities with the constraints that he/she visits a city only once and come back to the origin city. There are several possible routes that the salesperson can travel along but he wishes to optimize the route in terms of cost/distance.

      There are several techniques using which one can tackle this problem. The most classical approach to solving this problem is by implementing Dynamic Programming(DP). DP is a technique usually employed

      to solve combinatorial optimization problems. Solving TSP using DP involves trying out all the combination of routes that are possible and storing them in a data structure, usually a 2×2 matrix. This matrix is also called the cost matrix. The entries in the cost matrix consists of the distance between any 2 cities. The diagonal elements of this matrix are 0 as the cost is 0 when the source and destination are the same. The computation is iteratively performed to calculate the distance between various cities and update the result in the cost matrix. Due to the principles of DP that involves trying out all the possible routes between various cities, the possible routes exponentially increase when the number of cities increase. To illustrate this exponential increase, observe the table below.

      No.of Cities	No.of Possible Routes
      5	24
      10	181000
      20	6.1 x 1016
      25	3.1 x 1023

      Table 1: No. of cities and corresponding possible routes

      We can observe that as the number of cities increase from 5 to 10, the number of possible routes increase from 24 to 181000. As we keep increasing the number of cities, the number of possible routes increase exponentially and implementing DP to compute the distance between cities for many such probable routes becomes increasingly difficult. Dynamic Programming and other algorithms like Branch-and-bound take exponential time to return the result. It is important to look for alternative solutions that require less time to solve such combinatorial optimization problems.

      Quantum Computing(QC) simplifies this computation and the result can be retrieved very quickly. Principles of QC are based on Quantum Mechanics. The classical computers use bits to store information. A bit is the smallest unit of information in a classical computer. A bit can either store a 0(low state) or a 1(high state). A Quantum Computer uses Quantum Bits(Qubit). A qubit is similar to bits in classical computer

      i.e it can either store a 0(low state) or a 1(high state) and it can also be in a superposition of these states(0 and 1). It is this property of superposition in combination with other properties in quantum mechanics that enables a quantum computer to perform complex mathematical operations in a very shorttime.

   2. METHODS

      The working of a Quantum Computer(QC) differs from the working of a Classical Computer. This is due to the science behind the working of a QC, i.e Quantum Mechanics. Quantum Mechanics operate at a quantum scale and the principles of classical mechanics no longer apply at a quantum scale. According to Heisenberg, The position and momentum of a particle at any instant of time cannot be determined precisely.. Considering an electron as a particle, the Heisen- bergs uncertainty principle holds valid and it is scientifically impossible to determine the exact position and momentum of that electron. However, if we consider the electron as a wave, we no longer deal with certainty that an electron can be found at a specific position, rather, we deal with the probability. It can be said that the probability of finding an electron is square of the amplitude. By considering a particle as a wave, we can explain some of the concepts of Quantum Mechanics.

      1. Quantum Superposition

         A fundamental principle of Quantum Mechanics is the principle of Quantum Superposition. Superposition arises due to the nature of the particle, as they behave like waves at a quantum scale. The atomic memory unit of a classical computer is a bit. A bit can store binary information, i.e 0 or 1. The information stored in a bit is always either a 0 or 1 and can not be any other value. In contrast, the atomic memory unit of a Quantum Computer is a Quantum Bit(qubit). A qubit can store either a 0 or 1 and can also be in a superposition of these states. The probability of a qubit measuring a 1 or a 0 in general is neither 1.0 or 0.0. A qubit is always in a superposition of these two states with a certain probability that its holding 1 and certain probability that its holding 0. The two superimposed quantum states result in another valid quantum state. Quantum Computers take advantage of the Quantum Superposition principle to explore various possible solutions for a given combinatorial optimization problem.

      2. Quantum Entanglement

         The state of particles in Classical Mechanics are inde- pendent of the state of other particles. The qualities of a particle(position, momentum, spin) can be independently de- termined without considering ny other particles. In Quantum Mechanics, this is not the case. Quantum State of any par- ticle cannot be described independently of the state of other particles, irrespective of how far the particles are separated by. This property is called the Quantum Entanglement. It is found that the position, momentum and spin performed on the quantum particles are perfectly correlated. The particles that were considered to exhibit Quantum Entanglement were as small as photons, neutrons, electrons and also large molecules like bucky balls. The effect of actions performed on one entangled particle can be noticed in another entangled particle even at large distances. This property differs from the Quan- tum Coupling as Quantum Coupling can only be observed in quantum scales. In contrast, Quantum Entanglement can be observed even when the particles are sepearted by large

         distances. The property of Quantum Entanglement is further explored and utlized in several fields of study like Quantum Communication, Quantum Computation. This is particularly helpful in tackling combinatorial optimization problems where a qubit can deduce the state of another qubit when they are entangled and perform related computation.

      3. Quantum Tunnelling

         According to classical mechanics, a particle needs to have a kinetic energy(KE) greater than the potential energy(PE) of the barrier in order to cross that barrier. If the particle does not possess the required kinetic energy to cross the barrier, the particle is certain of getting totally reflected. Since particles behave like waves in the field of Quantum Mechanics, there is a slight probability that the particle can cross the barrier even without the required Kinetic Energy to cross the potential barrier. This property cannot be justified by the laws of classical mechanics. It is the uncertainty in determining the exact location of the particles that allow them to break the rules of classical mechanics and pass the barrier without possessing the required kinetic energy. Quantum Computers can take advantage of this property to switch between various states while exploring solutions of combinatorial optimization problems.

      4. Quantum Annealing

      Quantum Annealing is a procedure of finding the global minimum of a given problem domain. This is achieved by the phenomenon of Quantum Fluctuations. It is defined as the temporary change in energy at a point in space. Quantum Annealing uses the concepts of Quantum Physics to find the lowest energy states and returns the optimal solution. Since Quantum Physics always deals with probability rather than certainty, the solution thus returned by the Quantum Annealer has a high probability of being the optimal solution over the entire set of feasible solutions. This process is often used in optimization and probability sampling problems.

      The classical computer explores various solutions of TSP by brute-force method. It looks for every possible combination of the cities and stores the result(adding distance between cities) in a matrix. This result computed is returned whenever desired, to avoid redundant computation. This is known as Dynamic Programming. DP is particularly helpful when there are several computations involved and some computations are performed over and over again. Even with a procedure like DP, solving combinatorial optimization problems are still extremely difficult and time consuming since the possibilities exponentially increase when the number of inputs are increased. In TSP, the possible routes exponentially increase even when the number of cities to visit increases by a small quantity. With the limited abilities of a classical computer, it takes exorbitantly long to solve TSP. A different approach to solve TSP is by using a Quantum Computer.

      Since a Quantum Computers fundamental unit is a

      Quantum Bit, its property of superposition gives a great advantage while looking for an optimal solution in a set of feasible solutions. We assume that the qubits used in our procedure are entangled so that the quantum state of one qubit affects the quantum state of another qubit. The qubits possess different quantity magnetic fields. Since Quantum Annealing looks for the lowest energy state, the distance between each city can be considered as an energy parameter in our design. The Quantum Computer applies the Quantum Annealing process to look for the optimal distance with the given constraints of the problem, i.e A city can be visited only once and the traveller must come back to the origin. The entangled qubits can directly affect the state of one another. For instance, a qubit can affect the quantum state of another qubit if it has found a local minima in that region. Since the qubits are in quantum scale, qubits can go through Quantum Tunnelling. With Quantum Tunnelling, the qubits need to travel along the path to reach a particular vertex or a point. The transition between state for these cubits can be instananeous. The Quantum Annealer can then calculate the lowest energy level between these states and return the optimal solution. Since the Quantum Bits are in a superposition of states, the Quantum Computer can look at various solutions at the same time. This whole process of finding an optimal solution can be performed by a Quantum Computer in a few microseconds.

   3. DISCUSSION

Combinatorial Optimization problems, Probabilistic Sam- pling problems, often consume a lot of time and computer resources as there are several possible solutions and each one of them needs to be explored to return a definitive and optimal solution with certainty. TSP is one such combinatorial optimization problem in which the computer has to recursively find the distance between cities and compute the distance. Given N cities, there are (N-1)! factorial routes in which the traveller can travel each city once and return to the origin. For a small number of cities, the classical computer can return the solution in considerable time. However, as the number of cities increase, we observe an exponential increase in the time required to compute all the probable routes. This problem gets more complicated when other constraints(eg. no route between two particular cities) are imposed. The problem can ultimately be solved by a classical computer but it takes unreasonably high time to find an optimal solution. We need an effective method to solve such related Combinatorial Op- timization problems. Complex, resource-exhausting problems are a platform for Quantum Computer to show its dominance over Classical Computers. In this paper, we have presented a theoretical and a potential solution for the Travelling Sales- person Problem by using Quantum Computing. The properties of Quantum Bits(Superposition, Entanglement and Tunnelling) give an edge over the classical bits when computations that require resources for a very long time to solve a problem are involved. In our theoretical solution, we have considered the quantum bits with different magnetic

fields to record the distance between them as an energy parameter. The entangled quantum bits can affect one anothers state when encoutering a local minima. Various states can be instantaneously explored by qubits without traversing the actual path. This is known as Quantum Tunnelling which explains the property of quantum objects that pass through a potential barrier even when the object does not possess the required Kinetic Energy. These low energy states can be analyzed by the quantum annealer and can calculate the lowest energy level between these states. The scope of this paper is limited to the theoretical and a probable solution to find an optimal result to one of the combinatorial optimization and NP- hard problem, the Travelling Salesperson problem. The mathematics and the setup of the quantum computer to carry out the required tasks to return an optimal solution is beyond the scope of the paper. Finding a solution to such NP-hard problems using a quantum computer has several implications in other fields of study. Appliations of Quantum Computing extend even to find a solution to a real- time problem like drug development, material science and chemistry. The applications of quantum computing in these fields are an active area of research. There has been significant increase in funding research in quantum computing. There are indications of growth in this area, but due to the extremely convoluted nature of quantum mechanics, the research takes a long time to arrive at a discovery or an optimized solution.

REFERENCES

1. Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, and et al. 2018. Quantum Algorithm Implementations for Beginners. Technical Report. 76 pages. https: //arxiv.org/abs/1804.03719

2. Richard P. Feynman. 1982. Simulating Physics with Computers. Inter- national Journal of Theoretical Physics 21 (Jun 1982), 467488. Issue 67. https://doi.org/ 10.22331/q-2018-08-06-79

3. Philipp Gerbert and Frank Rueß. 2018. The Next Decade in Quantum Computing and How to Play. Technical Report.

   30 pages. https://www.bcg.com/en-ca/ publications/2018/next- decade- quantum-computing-how-play.aspx

4. Emily Grumbling and Mark Horowitz (Eds.). 2018. Quantum Com- puting: Progress and ProspectsConsensus Study Report. The Na- tional Academies of Science, Engineering and Medicine. 272 pages. https://doi.org/10.17226/25196

5. Travis S. Humble. 2019. Quantum Computing is Ideal for Quan- tum Problems. Oak Ridge National Laboratory (ORNL) Review. https://www.ornl.gov/blog/quantumcomputing-ideal- quantum-problems

6. Margaret Martonosi and Martin Roetteler. 2018. Next Steps in Quantum ComputingComputer Sciences Role. Technical Report.24 pages. https://cra.org/ccc/wp- content/uploads/sites/2/2018/11/Next-Steps-inQuantum-

   Computing.pdf

7. John Preskill. 2018. Quantum Computing in the NISQ Era and Beyond. Quantum The Open Journal for Quantum Science 2 (Jun 2018), 79. https://doi.org/10.22331/q- 2018-08-06-79

8. Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera, Prasanta K. Panigrahi (May 2018)- Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. 8 pages. https://arxiv.org/pdf/1805.10928.pdf