Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems

Abstract

Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state -- an equal superposition of all feasible solutions satisfying the problem's constraints -- is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher-order unconstrained binary optimization (HOBO) representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.

References in corpus (11)

• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Combinatorial optimisation via highly efficient quantum walks
• Implementation of efficient quantum search algorithms on NISQ computers
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with Advanced Decomposition of $n$-qudit Toffoli Gate
• Subdivided Phase Oracle for NISQ Search Algorithms
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Enhancing VQE Convergence for Optimization Problems with Problem-specific Parameterized Quantum Circuits

Cited by in corpus (1)

• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints