Quantum gates or universal quantum gates have been used a common concept of quantum computer. There is another type of quantum computing algorithm, which is recently implemented as an effective concept of quantum computer. This is the quantum annealing computer. The quantum annealing machine is shown recently a very powerful tool to solve combinatory optimization problems such as traveling salesman problem (TSP). A Canadian venture company D-Wave Systems has commercialized this type of quantum computer with 2000 Q-bits on the market.
Quantum gates or universal quantum gates have been used a common concept of quantum computer. There is another type of quantum computing algorithm, which is recently implemented as an effective concept of quantum computer. This is the quantum annealing computer. The quantum annealing machine is shown recently a very powerful tool to solve combinatory optimization problems such as traveling salesman problem (TSP). A Canadian venture company D-Wave Systems has commercialized this type of quantum computer with 2000 Q-bits on the market.
Quantum annealing (QA) algorithm is a new quantum optimization algorithm based on the classical simulated annealing (SA) algorithm. Unlike classical SA algorithm, which uses the thermal waves to search for the optimal solution, the QA algorithm uses the quantum tunneling effect to allow a quantum to penetrate a potential barrier with a higher energy than itself. Therefore, the algorithm can get rid of the local extreme values and is more likely to approach the global optimal with higher probability. In the literature, the QA algorithm has shown perfect optimization effects on combinatorial optimization problems. In this paper, the basic concepts and application fields of QA algorithm, which is the core principle of D-Wave quantum computer, are systematically reviewed. The applications of QA algorithm in cryptography, traveling salesman problem, graph coloring problem, and traffic path are discussed in detail. In addition, the direction of future research for QA algorithm is explored.
This paper describes the logic and creativity needed in order to have high probability of solving discrete optimization problems on a quantum annealing computer.Current features of quantum computing via annealing are discussed.We illustrate the logic at the forefront of this new era of computing, describe some of the work done in this field, and indicate the distinct mindset that is used when programming this type of machine.The traveling salesman problem is formulated for solving on a quantum annealing computer, which illustrates the methods for this computer.
At land, sea and in the air mobility and traffic management offer a vast amount of problems with a large potential of optimization with quantum computers, e.g. service scheduling, route planning, or path optimization. Many of these problems can be described at a fundamental level by the traveling salesman problem (TSP), in which the shortest route while visiting each point exactly once is to be found [1]. The TSP has already received a lot of attention in the quantum computing community, for example, implementations for adiabatic quantum annealers exist and have been tested [2,3]. We investigate the TSP with a focus on going beyond qubits by employing continuous quantum systems. Using bosonic Qiskit we simulate potential algorithms for solving the TSP and compare their performance. [1] Flood, M. M., The traveling-salesman problem. Operations research, 4(1), 61-75, (1956). [2] Martoňák, Roman, Giuseppe E. Santoro, and Erio Tosatti., Quantum annealing of the traveling-salesman problem. Physical Review E 70.5: 057701, (2004). [3] Jain, S., Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics, 646, (2021).
This paper illustrates fundamental principles about small traveling salesman problems (TSPs) which are a current application for quantum annealing computers.The 2048 qubit, quantum annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8 cities, which advances a recent 4-city result on a quantum simulator.Additionally, the D-Wave quantum computer is expected to find all optimal tours for each TSP.To prepare for this, we show the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities.The examples in the TSPLIB have 14 or more cities.These are too large for the current quantum annealing processors.We have included an annotated bibliography about solving the TSP on a quantum computer.
In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.
Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000Qquantum hardware demonstrate that the optimal solutions for several instances can be attained.