Benchmarking QAOA on a Tensor-Based QUDO Formulation of a TSP Variant for Travel Search Engines- Results

The Travelling Salesman Problem (TSP) constitutes a fundamental Combinatorial Optimisation Problem (COP) with wide-ranging applications in logistics, transportation design and production scheduling. However, the best-known exact classical algorithms exhibit exponential time complexity, rendering large instances intractable in practice and motivating the exploration of alternative paradigms such as quantum computing. In this work, we implement the Quadratic Unconstrained Binary Optimisation (QUBO) formulation and its generalisation, Tensor Quadratic Unconstrained D-ary Optimisation (T-QUDO), which extends quantum circuit encoding from qubits to qudits, for a TSP variant. This variant seeks to determine a minimum-cost route while incorporating a time-dependent cost function and precedence constraints, and remains largely unexplored with T-QUDO despite its relevance to dynamic travel planning. The formulations are encoded within the Quantum Approximate Optimisation Algorithm (QAOA) framework and analysed under noiseless simulations with the Cirq and CUDA-Q libraries, aiming to assess the potential advantages of qudit-based representations over qubit-based ones, particularly in terms of expressivity, resource efficiency, and solution quality.