Empirical Quantum Advantage Achieved in Constrained Optimization with O(S N²) Time Complexity

Quantum computing promises to revolutionise optimisation problems, but demonstrating a clear advantage over classical algorithms remains a significant challenge. Chinonso Onah, Roman Firt, and Kristel Michielsen, from Volkswagen AG and RWTH Aachen University, now report a substantial step forward with their development of a new algorithm that achieves empirical quantum advantage in constrained optimisation. Their work introduces a constraint-enhanced approach, operating within a specifically designed quantum space, and delivers a significant reduction in the computational resources needed to find optimal solutions. Through simulations of travelling salesperson problems, the team demonstrates the ability to consistently recover the best possible solution at a shallow depth, showcasing a clear separation from classical methods and paving the way for practical applications of quantum optimisation.

Quantum Algorithms for Combinatorial Optimisation

This research comprehensively examines quantum optimization and combinatorial optimization problems, focusing on algorithms designed to solve computationally challenging tasks. The work acknowledges the inherent difficulty of many of these problems, specifically their NP-completeness, meaning no known classical algorithm can solve them efficiently. Consequently, the research explores heuristic and approximation algorithms that aim to find good solutions within a reasonable timeframe. The study also investigates the design and analysis of quantum algorithms, considering factors like operational parameters and quantum entanglement.

The research covers a wide range of optimization problems, including the Traveling Salesperson Problem, the Assignment Problem, the Knapsack Problem, the Quadratic Assignment Problem, various scheduling problems, the Maximum Cut Problem, and Max-3SAT. The study highlights the importance of theoretical concepts like QAOA, mixer designs, and warm-starting techniques, which aim to improve the performance of quantum algorithms. Advanced concepts like entanglement, quantum circuit complexity, and tensor networks provide tools for representing and simulating quantum states.

Constraint Enhancement and Wn State Preparation

Scientists developed a novel quantum algorithm, the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), which operates within a specifically designed computational space. This space utilizes one-hot product states, initialized with an n-qubit Wn state within each block. A key innovation is an ancilla-free, depth-optimal encoder that prepares the Wn state using a minimal number of two-qubit rotations per block, reducing the complexity of initial state preparation. This encoder employs a cascade-style circuit, applying controlled rotations to adjacent qubits to precisely construct the desired superposition.

The algorithm utilizes a two-local XY mixer, restricted to operate within the same block of n qubits, ensuring a constant spectral gap and promoting efficient exploration of the solution space. This design is provably optimal in gate count on a linear array, requiring a minimal number of two-qubit gates. The algorithm combines constant-depth sampling with a deterministic classical checker, resulting in a polynomial-time hybrid quantum-classical solver that efficiently identifies the best feasible solution. Simulations on Traveling Salesperson Problem instances demonstrated the algorithm’s ability to recover the global optimum at a shallow depth using polynomial shot budgets and coarse parameter grids, highlighting its potential for addressing complex optimization challenges.

Constraint-Enhanced Algorithm Solves Optimization Problems Exponentially Faster

Researchers developed the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), a novel approach to solving complex optimization problems. This work introduces a shallow, constraint-aware algorithm that operates within a specific computational space, utilizing a unique initial state preparation and mixing strategy. The team demonstrated a significant reduction in computational complexity, achieving a substantial decrease in required sampling complexity when fixing certain locations, compared to standard classical sampling methods. Furthermore, the algorithm exhibits an exponential performance advantage over raw bitstring sampling.

Experiments conducted on Traveling Salesperson Problem instances yielded optimal solutions at a shallow depth using polynomial shot budgets and coarse parameter grids, demonstrating the algorithm’s efficiency and scalability. The team’s approach exploits problem structures at both classical and quantum levels, leading to substantial improvements in performance. The Polynomial Hybrid Quantum-Classical solver recovered the optimal solution in all tested instances, dramatically reducing the computational cost. The core of this breakthrough lies in the algorithm’s ability to efficiently prepare an initial state, a block-wise W product, using an ancilla-free circuit requiring a minimal number of two-qubit rotations per block.

This initial state preparation is provably optimal in gate count on a linear array, minimizing the required quantum resources. The team also designed a two-local, ancilla-free block-XY mixer that preserves block-wise one-hot constraints, ensuring that the algorithm remains within the feasible solution space. This mixer is normalized to have a constant spectral gap, further enhancing its performance and stability. Through careful analysis and design, scientists demonstrated that the algorithm’s kernel is invariant under block permutations and symbol relabelings, leading to an exact unitary 1-design on the computational basis. This symmetry-driven design guarantees the existence of an optimal basis vector and provides instance-agnostic performance guarantees.

Constraint Enhanced Optimization Algorithm Achieves Speedup

Scientists have developed a novel quantum algorithm, the Constraint-Enhanced Quantum Approximate Optimization Algorithm, designed to efficiently tackle complex optimization problems. This algorithm utilizes a unique approach by operating within a specifically defined quantum space and employing a tailored encoding method that minimizes circuit complexity. The team demonstrated that this approach reduces the computational effort required, achieving a significant speedup compared to standard methods when solving problems with certain constraints. The algorithm’s effectiveness was confirmed through simulations on benchmark problems, where it successfully identified optimal solutions with a shallow circuit depth and manageable computational resources.

A key feature of this work is the development of a block-structured approach, dividing the problem into smaller, interconnected units, which further enhances efficiency and reduces the overall circuit complexity. The researchers also established theoretical limits on the block size, providing guidance for practical implementation and optimization. Future research will focus on exploring methods to overcome limitations in block size and extend the algorithm’s applicability to a wider range of optimization challenges.