Quantum Computing Enables Discrete Exhaustive Search for Improved Traveling Salesman Solutions

The traveling salesman problem, a classic challenge in computer science, continues to drive innovation in computational methods, and researchers are now exploring quantum approaches to tackle its complexity. Omer Gurevich, Maor Matityahu, and Tal Mor from the Technion, Israel Institute of Technology, investigate how the problem can be effectively mapped onto quantum systems using the Ising formulation, a technique crucial for emerging quantum algorithms. This work clarifies the practical considerations of applying this formulation, particularly regarding qubit efficiency in current quantum computers, and introduces a novel method called Discrete Quantum Exhaustive Search. The team demonstrates how this approach enhances existing quantum optimisation techniques and, importantly, suggests a pathway to extend these solutions beyond the limitations of traditional computational complexity, potentially impacting fields like quantum chemistry and general spin problems.

Symmetry and Structure in Quantum Optimization

This research investigates methods for improving the performance of variational quantum algorithms (VQAs) when solving complex, NP-hard problems such as the Traveling Salesperson Problem and its variations. The team addresses the challenge of barren plateaus, where gradients vanish during training, by leveraging the inherent structure and symmetries within these problems to guide the search for optimal solutions. DQES involves breaking down the problem into a finite number of discrete states and then using quantum circuits to efficiently evaluate the cost function for each state.

This structured search, potentially guided by mutually unbiased bases, aims to overcome the limitations of traditional VQAs and avoid getting trapped in local optima. The method is applicable to problems formulated using Ising models, with potential applications in diverse fields like DNA sequencing, logistics, and quantum chemistry. The authors believe DQES offers several potential contributions, including improved VQA performance, mitigation of barren plateaus, and a means of incorporating problem-specific knowledge into quantum algorithms. This hybrid quantum-classical approach is designed to be feasible on near-term quantum computers and could unlock new solutions to challenging optimization problems.

VQE Solves Traveling Salesman Problem Efficiently

Researchers have applied the Variational Quantum Eigensolver (VQE) to the traveling salesman problem (TSP) and other NP-complete problems, analyzing the connection between the Ising model formulation and the practical constraints of the problem. This work establishes VQE as a novel SAT-solver within the quantum realm, emphasizing the importance of qubit efficiency for current quantum devices. DQES aims to overcome challenges posed by local minima and barren plateaus by systematically exploring discrete states and utilizing mutually unbiased bases to improve search capabilities. The team employed a Hamiltonian cycle framework, representing solutions as ordered node sequences and leveraging quantum superposition to explore multiple equivalent solutions simultaneously. DQES is designed to enhance quantum algorithms like the Quantum Approximate Optimization Algorithm and Variational Quantum Eigensolver, and was successfully applied to a four-city TSP instance, reducing the number of required computational variables. This reduction dramatically decreases processing time due to the exponential scaling of variables. Experiments involved calculating Ising Hamiltonian energies for unique qubit assignments and utilizing mutually unbiased bases.

Simulations of a four-node TSP instance identified two optimal solutions, confirming the method’s ability to find ideal routes. Integrating DQES with VQE demonstrated improved convergence, with VQE converging in more runs when initialized from the lowest-energy states identified by DQES, suggesting a potential advantage in bypassing local minima and barren plateaus. These results demonstrate a promising pathway for solving complex NP-complete problems and potentially extending these techniques to problems relevant to quantum chemistry and spin systems.

Traveling Salesman Problem via Hamiltonian Formulation

This research presents a new approach to formulating and solving the traveling salesman problem, building upon the Ising model and Hamiltonian cycle concepts. The team successfully demonstrated how to represent the problem using a compact variable assignment table, potentially improving computational efficiency for near-term quantum computing applications. This formulation ensures a complete cycle is found, avoiding invalid solutions. Researchers extended their method to directly address the TSP by incorporating cost minimization into the Hamiltonian, allowing for encoding the problem in a way suitable for quantum algorithms like the Quantum Approximate Optimization Algorithm and Variational Quantum Eigensolver. Future work will focus on extending this approach to more complex problems and exploring methods to further reduce computational demands.