Space-Efficient Quantum Optimization for the Traveling Salesman Problem via Binary Encoding of Feasible Solutions

Space-Efficient Quantum Optimization for the Traveling Salesman Problem via Binary Encoding of Feasible Solutions

Abstract:

The Traveling Salesperson Problem (TSP) is a classic combinatorial optimization problem with multiple applications in logistics, planning, and scheduling. Quantum algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA), have demonstrated potential for addressing such NP-hard problems and potentially can offer advantages over classical methods. Existing quantum approaches to the TSP typically rely on one-hot encoded states, requiring O(n^2) qubits for a TSP instance with n cities and using constraint-preserving mixers like the XY-mixer to navigate the feasible subspace. However, these methods are resource-intensive and face scalability issues due to the large number of qubits needed. This master thesis investigates a novel, space-efficient encoding scheme for solving the TSP using QAOA with a binary encoding of permutations, reducing the qubit requirement to O(n log2 n). The main challenge of binary encoding is the absence of an simple constraint-preserving mixer to maintain feasibility during optimization. To address this, an efficiently implementable unitary transformation was proposed to assign each binary-encoded tour a unique label. By adding O(log2 n!) ancillary qubits that represent each possible permutation of the TSP in factorial-base system, a canonical isomorphism between permutations and factorial-base numbers is established. The mixing operation is then performed on this ancillary space through a simpler X-mixer or a Grover mixer, automatically restricting the algorithm’s evolution to valid tours. This ensures that hard constraints remain satisfied throughout the optimization process, enabling faster convergence toward the optimal solution. Three variants of this encoding are explored in this master thesis: (1) a direct unitary transformation using a precomputed look-up table, (2) a quantum arithmetic–based method, and (3) an index-only approach that encodes both cost and mixer Hamiltonians in [log2(n!)] qubits, potentially introducing higher-order interactions. Numerical experiments with small problem instances demonstrate the feasibility of these approaches, highlighting the prospective benefits of this space-efficient encoding scheme in practical quantum optimization tasks.

Author:

Viktoria Patapovich

Advisors:

Jonas Stein, David Bucher, Claudia Linnhoff-Popien

Student Thesis | Published January 2025 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors