TLDR: A new quantum algorithm called ‘Freeze and Conquer’ tackles the Traveling Salesman Problem (TSP) by optimizing a quantum circuit’s structure (Ansatz) once, then ‘freezing’ and reusing it for new problem instances. This approach, which also uses a compact permutation encoding to reduce qubit requirements, significantly speeds up solution times for moderate problem sizes (4-6 cities) by eliminating repeated structural optimization. While highly effective for smaller instances, its success rate drops for 7-city problems, indicating current scalability limits.
Researchers Fabrizio Fagiolo and Nicolò Vescera have introduced a novel approach to tackle the Traveling Salesman Problem (TSP) using variational quantum algorithms. Their method, dubbed “Freeze and Conquer,” focuses on making quantum solutions for complex optimization problems more practical and efficient, especially for current-generation quantum hardware.
The Traveling Salesman Problem is a classic challenge in computer science where a salesman must visit a set of cities and return to the starting city, minimizing the total distance traveled. Finding the shortest route becomes incredibly difficult as the number of cities increases, making it an NP-hard problem. Quantum computing offers promising avenues for such problems, particularly through Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA).
However, current quantum computers, often referred to as Noisy Intermediate-Scale Quantum (NISQ) devices, face limitations. Two major hurdles are the high number of qubits required for standard problem encodings and the need for deep, complex quantum circuits. The “Freeze and Conquer” method addresses these by using a compact way to represent permutations, which significantly reduces the number of qubits needed. For instance, it requires only O(n log n) qubits, where ‘n’ is the number of cities, compared to the more common O(n^2) encodings.
The Optimize-Freeze-Reuse Strategy
The core innovation lies in its “optimize-freeze-reuse” strategy, inspired by machine learning principles. It involves two main phases:
- Training Phase: The quantum circuit’s structure, known as the “Ansatz,” is optimized using a classical algorithm called Simulated Annealing (SA). This optimization happens on a single training instance of the TSP. SA helps explore different circuit layouts and parameters to find the most effective one.
- Reuse Phase: Once the optimal Ansatz structure is found, it is “frozen.” This means its topology is fixed and will not change. For any new TSP instance, only the circuit’s parameters are quickly re-optimized. This eliminates the time-consuming process of finding a new optimal circuit structure for every new problem, making the solution much faster and more suitable for NISQ hardware.
The researchers implemented their algorithm using the Qiskit library in Python and tested it on 40 randomly generated symmetric TSP instances ranging from 4 to 7 cities. For each city count, one instance was used for training the Ansatz, and ten were used for testing its generalization ability.
Performance and Scalability
The results demonstrated remarkable efficiency for smaller problems:
- For 4-city problems, the Ansatz achieved a 100% success rate in finding the optimal tour.
- For 5-city problems, it maintained a high success rate of 90%.
- For 6-city problems, the success rate was around 80%.
However, the scalability limitations became apparent with 7-city problems, where the success rate dropped significantly to an average of approximately 20%. This indicates that while the method shows robust generalization for moderate problem sizes, larger instances still pose a challenge for the current approach.
The study highlights that freezing the Ansatz dramatically reduces the time needed to find a solution without compromising the quality of the results for smaller to moderate problem sizes. This makes the procedure immediately implementable on existing NISQ devices, as it avoids the costly structural search during testing.
Also Read:
- Navigating Complex Tasks with Tree-Guided Diffusion
- AI Travel Assistants: Bridging the Gap Between Efficiency and the Human Touch in Vacation Planning
Future Directions
Looking ahead, the researchers plan to test their method on real quantum hardware, such as superconducting or ion trap-based systems, and incorporate error mitigation techniques to account for noise. Algorithmic improvements include exploring gradient-based optimizers like Adam or SPSA for faster convergence and using “warm-start” strategies to initialize parameters closer to optimal solutions. The team also aims to extend this optimize-freeze-reuse paradigm to other complex permutation problems, such as the Vehicle Routing Problem (VRP) and Job-Shop Scheduling (JSS), which are crucial for industrial applications.
For more in-depth information, you can read the full research paper here.
