Quantum Travel Planner Gets Closer to Solving Impossible Delivery Routes

Quantum search represents a fundamental component within the field of quantum computation. Successfully applying it to complex combinatorial optimisation problems, however, remains a significant challenge. Maximilian Hess, Lilly Palackal, and Abhishek Awasthi, from Infineon Technologies AG and BASF Digital Solutions GmbH, alongside Peter J. Eder et al., present novel research constructing heuristic state preparation routines for the Traveling Salesperson Problem (TSP). Their approach mimics the classical Lin-Kernighan heuristic, aiming to achieve a practical approximation ratio with a polynomial number of iterations. This work is significant as it addresses the limitations of naive quantum search by integrating problem-specific state preparation, potentially unlocking more efficient solutions for intractable optimisation tasks.

This work addresses a fundamental limitation of quantum search, the need to efficiently explore exponentially large solution spaces, by integrating a problem-specific state preparation routine.

The innovation lies in a heuristic that mimics the classical Lin-Kernighan heuristic, effectively focusing the quantum search on promising routes and significantly reducing the computational burden. By strategically preparing the initial quantum state, the algorithm prioritizes states representing Hamiltonian cycles, thereby circumventing the limitations of starting with a uniform superposition across all possible solutions.

This study builds upon previous research to construct a state preparation routine tailored for the TSP, a problem with a fundamentally different constraint structure than previously tackled with similar methods like the knapsack problem. The researchers combine this routine with Grover’s algorithm, aiming to achieve a reasonable approximation ratio with a polynomial number of Grover iterations.

Central to the advancement is the ability to navigate scenarios where the number of potential “good” solutions is unknown, employing algorithmic settings that compare different termination criteria and iteration choices. This addresses a key subtlety in applying Grover’s algorithm to optimisation tasks, where randomization is often used to account for an undefined number of optimal states.

The team’s benchmarking scheme allows analysis of instances exceeding 100 binary variables, a scale inaccessible to other quantum algorithms such as the Quantum Approximate Optimisation Algorithm. This hybrid approach demonstrates a significant step towards practical quantum solutions for complex optimisation problems.

By intelligently biasing the initial quantum state towards likely candidates, the algorithm avoids the exponential runtime typically associated with searching vast, unstructured spaces. The methodology builds upon prior work by Baertschi and Eidenbenz, constructing heuristic state preparation routines that mimic the classical Lin-Kernighan heuristic to approximate solutions with a polynomial number of iterations.

This approach aims to increase the amplitudes of promising states by exploiting the inherent structure of the TSP, thereby complementing the search process. The core of the work involves preparing a superposition of routes that differ only slightly from the current best solution, focusing improvement steps on a limited number of positions within the incumbent solution.

This state preparation routine relies on the efficient creation of Dicke states, a technique previously developed by the same authors, and introduces a biasing factor to skew the initial superposition towards reference states. Inspiration for this biasing factor comes from successful quantum algorithms applied to the knapsack problem, where skewing the initial state significantly improved performance.

The research employs a benchmarking scheme, similar to those used in previous studies, to evaluate the algorithm’s performance on instances exceeding 100 binary variables. This hybrid scheme allows for analysis beyond the capabilities of other quantum algorithms, such as the Quantum Approximate Optimisation Algorithm.

The Grover Adaptive Search algorithm itself iteratively refines a solution candidate, beginning with a heuristically generated initial solution and employing a while loop that continues until a defined termination condition is met. Within the loop, the number of Grover iterations is randomly selected from a range determined by a scaling factor, λ, and applied to an oracle and diffusion operator.

Measurements are then taken to identify a new candidate solution, and if this solution improves upon the current best, the incumbent solution is updated and the iteration counter reset. Otherwise, the iteration counter is multiplied by λ, increasing the search intensity. Initial objective values were computed using a greedy procedure, subsequently refined with the OR-Tools CP-SAT solver to establish a set of feasible tours.

This allowed for classical simulation of Grover-based protocols without requiring quantum circuit execution. The simulation computed measurement probabilities, pj(x), using the formula pj(x) = p0(x) sin2((2j + 1) arcsin √ P ) P, where M represents the number of good states and P is the sum of all measurement probabilities belonging to those states.

This evaluation method remained viable for instance sizes exceeding 100 variables, surpassing the scope of benchmarks for algorithms like QAOA. The work limited the number of rounds within each improvement step to R = 5, R = logλ(n2), or R = logλ(n4), where λ equals 5/4. The expected and maximum number of iterations was O(λR) given the highest R value of logλ(n4), indicating a polynomial runtime for the algorithm.

Deviation from the optimal solution was measured as d(x) −d(x∗) d(x∗), where x is the detected solution and x∗ is the optimal solution, averaged across multiple trial runs. The number of Grover iterations required to reach these results also served as a key performance metric. Benchmarking of a quantum search algorithm with a locally-inspired state preparation routine revealed limited ability to move away from the initial greedy solution for the considered instances.

The algorithm was run with an iteration limit of 5n3, where n represents the number of vertices in the graph. Examination of a quantum search algorithm starting from a superposition of feasible states highlighted differences between three variants of Grover adaptive search. The fixed interval and incremental strategies achieved a higher approximation ratio for a given number of rounds, but at the cost of a significantly increased total number of iterations. This routine mimics the classical Lin-Kernighan heuristic, aiming for a reasonable approximation ratio with a polynomial number of iterations.

The study involved comparing different algorithmic settings, specifically concerning termination criteria and iteration choices when the number of optimal solutions is unknown. Analysis of various settings revealed that a fixed interval strategy for determining the number of Grover iterations is only suitable when the number of marked states is expected to be very low.

The incremental strategy, while potentially faster, requires the amplitude of good states to be an integer multiple of a value related to the total number of solutions, a condition not always met in complex scenarios. The standard Grover adaptive search strategy offers more control over the number of iterations, particularly when the algorithm parameter is kept relatively small.

Determining whether this fixed-point quantum search can outperform classical methods by trading randomness for algorithmic overhead requires further numerical investigation. The authors acknowledge limitations in their benchmarking scheme, which was restricted to smaller instances than those where the proposed neighborhood search is expected to be most effective.

Additionally, the quantum circuits needed to implement the oracles were not fully addressed, although general implementations exist and problem-specific improvements may be possible. Future research should focus on evaluating the performance of this quantum search algorithm on larger instances and exploring more efficient oracle implementations to assess its competitiveness with classical heuristics.