Warm-starting Pauli Correlation Encoding Improves Traveling Salesman Problem Performance with Polynomial Qubit Reduction

The Traveling Salesman Problem, a classic challenge in computer science, continues to drive innovation in optimisation techniques, and researchers are now exploring quantum approaches to tackle its complexity. Rafael S. do Carmo, Renato Gomes dos Reis, and Samuel Fernando F. Silva, alongside colleagues including Luiz Gustavo E. Arruda and Felipe F. Fanchini, have developed a new method that significantly improves the performance of Pauli Correlation Encoding (PCE), a promising quantum strategy. Their work introduces a ‘warm-start’ technique, incorporating insights from established classical algorithms into the quantum optimisation process, effectively guiding the search for better solutions. The team demonstrates that this warm-start PCE consistently outperforms standard PCE on the Traveling Salesman Problem, achieving optimal results in a substantially higher percentage of cases and delivering improved approximation ratios, representing a valuable step towards practical quantum solutions for complex optimisation challenges on near-term quantum hardware.

These algorithms aim to outperform classical methods, but require adaptation for current quantum computers with limited capabilities. This research builds upon the Probabilistic Combinatorial Optimisation (PCO) framework, a quantum algorithm designed for these types of problems. A key advancement involves using warm-starting techniques, which leverage classical heuristics to find a good initial solution that guides the quantum algorithm, improving its performance and speed of convergence.

Different classical methods are explored to generate these starting points. This approach also reduces the number of qubits required, making it more suitable for near-term quantum devices. The algorithm shows promise for practical applications and achieves competitive results with state-of-the-art classical algorithms for certain problem instances. Scientists also plan to develop more effective classical heuristics for warm-starting and investigate error mitigation techniques to improve the accuracy of the quantum algorithm. This advancement incorporates a classical bias derived from the Goemans-Williamson randomised rounding algorithm into the PCE loss function, guiding the optimisation process towards improved solutions. These findings highlight the practical benefits of employing a warm-start strategy within the PCE framework, offering a means to improve performance on near-term quantum hardware.

While experiments focused on relatively small instances, the researchers emphasise the problem-agnostic nature of the warm bias, suggesting broad applicability to other QUBO or MaxCut problems. This work addresses a key limitation of many quantum algorithms, namely the large number of qubits required for complex problems. PCE itself offers a reduction in qubit count compared to traditional encoding methods, and the new Warm-PCE further enhances performance by incorporating a classical bias derived from the Goemans-Williamson randomised rounding technique. Results show that Warm-PCE consistently outperforms standard PCE, achieving an optimal solution in 28% to 64% of instances, compared to 4% to 26% for PCE. The mean approximation ratio of Warm-PCE also demonstrates a clear advantage. This metric increases monotonically with circuit depth, exceeding the performance of the PCE baseline from a depth of 3. In contrast, the approximation ratio for standard PCE remained relatively flat across all tested depths. These findings confirm the benefit of incorporating a classical warm-start strategy within the PCE framework, paving the way for more efficient quantum solvers on near-term hardware. This research establishes a promising pathway for tackling computationally challenging problems with reduced qubit requirements and improved solution quality.