Classical Algorithm Beats Quantum Approach to Optimisation Challenge

Mark Goh and colleagues at University of Cologne investigated the binary paint shop problem, a computationally difficult optimisation task with implications for logistical sequencing. The team’s work, involving implementation on a D-Wave Quantum Annealer Advantage 2, shows that current quantum algorithms, specifically the Quantum Approximate Optimisation Algorithm (QAOA), do not offer a performance advantage over existing classical methods for this problem. The Mean-Field Approximate Optimisation Algorithm (MF-AOA) achieves a superior paint swap ratio of approximately 0.2799, surpassing both the recursive star greedy algorithm and logarithmic depth QAOA. These findings suggest the potential for developing improved classical algorithms for sparse optimisation problems and provide a new benchmark for performance in the field.

Classical algorithm exceeds quantum performance on binary paint shop optimisation

The Mean-Field Approximate Optimisation Algorithm (MF-AOA) now achieves a paint swap ratio of approximately 0.2799, a substantial improvement over the previously conjectured 0.361 for the recursive star greedy algorithm. The binary paint shop problem (BPSP) is an APX-hard combinatorial optimisation problem, meaning it is unlikely to be solvable in polynomial time, and finding even approximate solutions is computationally expensive as the problem size (n, representing the number of car models) increases. In the BPSP, a sequence of 2n car models must be painted, with each model appearing exactly twice. The objective is to minimise the number of times the paint colour needs to be switched during the painting process, ensuring that the two occurrences of each car model are painted different colours. This is analogous to scheduling tasks with constraints, where minimising switching costs is crucial. The MF-AOA’s result crosses a critical threshold, demonstrating for the first time that a classical algorithm can surpass both established classical heuristics and leading quantum approaches for the binary paint shop problem. Confirmed by benchmarking against other algorithms on this complex optimisation challenge, the MF-AOA’s superiority is now evident.

Establishing a new benchmark, the MF-AOA’s performance prompts a reassessment of classical optimisation strategies for sparse problems and challenges expectations surrounding quantum supremacy in this domain. The D-Wave Quantum Annealer Advantage 2 achieved a paint swap ratio of 0.320, while the recursive star greedy (RSG) algorithm also underperforms the new classical approach. The RSG algorithm is a classical heuristic that builds a solution incrementally, prioritising models that are most constrained. Theoretical limits suggest the Quantum Approximate Optimisation Algorithm (QAOA), utilising logarithmic circuit depth, is capped between approximately 0.265 and 0.282. QAOA is a hybrid quantum-classical algorithm that uses a quantum computer to explore the solution space and a classical computer to optimise the parameters of the quantum circuit. Logarithmic circuit depth refers to the number of layers in the quantum circuit, with lower depths generally being easier to implement on current quantum hardware. Scaling the MF-AOA to handle substantially larger, real-world optimisation problems remains a significant hurdle, despite these promising results. The MF-AOA operates by approximating the complex cost function of the BPSP with a simpler, mean-field representation, allowing for efficient optimisation using classical techniques. Optimisation problems underpin many logistical challenges, from scheduling deliveries to efficiently sequencing manufacturing processes like painting cars, and further research will focus on extending this approach to more complex scenarios.

Classical optimisation excels on a constrained binary paint shop scheduling task

These results demonstrate a surprising durability in classical approaches, despite the widespread anticipation of a revolution in the field through quantum computing. The BPSP serves as a valuable test case for evaluating the performance of different optimisation algorithms, particularly those designed for sparse problems where the number of constraints is relatively low compared to the number of variables. It is important to acknowledge that this improved performance currently applies only to the specific, artificially constructed “binary paint shop problem”, and does not immediately invalidate concerns about the broader applicability of classical algorithms versus quantum approaches. The Mean-Field Approximate Optimisation Algorithm, simplifying complex calculations to make them manageable, achieved a new best result, minimising paint swaps with remarkable efficiency. The algorithm’s effectiveness stems from its ability to efficiently explore the solution space and identify near-optimal solutions without being trapped in local minima.

A classical approach now outperforms both established classical heuristics and quantum computation on the binary paint shop problem, a challenging optimisation task involving efficient colour sequencing. The significance of achieving a paint swap ratio of 0.2799 lies in its proximity to the theoretical lower bound for this problem, suggesting that the MF-AOA is approaching the optimal solution. With a paint swap ratio of approximately 0.2799, the MF-AOA demonstrates a clear advantage over the recursive star greedy algorithm and the Quantum Approximate Optimisation Algorithm, even with logarithmic circuit depth. The D-Wave Advantage 2, a superconducting quantum annealer, attempts to solve the BPSP by leveraging quantum phenomena such as superposition and entanglement to explore the solution space. However, the performance of quantum annealers is often limited by factors such as qubit connectivity and noise. This result is significant because it challenges the assumption of inevitable quantum supremacy for all optimisation challenges, particularly those exhibiting sparse characteristics, and opens avenues for further investigation into classical optimisation techniques. Future work will explore the potential of combining the MF-AOA with other classical algorithms and techniques to further improve its performance and scalability, and to investigate its applicability to a wider range of optimisation problems.

The Mean-Field Approximate Optimisation Algorithm (MF-AOA) achieved a new best result in solving the binary paint shop problem, minimising paint swaps to a ratio of approximately 0.2799. This is important because it demonstrates a classical algorithm can outperform both existing classical methods and quantum computation for this specific optimisation task. The MF-AOA’s success stems from its efficient exploration of potential solutions, avoiding limitations seen in other algorithms. Researchers intend to explore combining this algorithm with other classical techniques to improve performance and broaden its application to other optimisation problems.