Beyond Quantum Advantage: Improved Classical Algorithms for the Binary Paint Shop Problem

Abstract:The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given $n$ car models that occur twice in a sequence of length $2n$, the objective is to find a colouring sequence such that each car model pair is painted differently while minimizing the number of times the paint is swapped along the sequence. A recent classical heuristic, known as the recursive star greedy (RSG) algorithm, is conjectured to achieve an expected paint swap ratio of $0.361$, thereby outperforming the Quantum Approximate Optimization Algorithm (QAOA) with circuit depth $p=7$. Since the performance of the QAOA with logarithmic circuit depth is instance independent, the average paint swap-ratio is upper-bounded by the QAOA. We provide an improved upper-bound of the BPSP by extending the QAOA to depth $p=17$, outputting an expected paint swap ratio of $0.334$ via an exact computation while numerical extrapolation suggests a further reduction to a value of $0.295$. To provide hardware-relevant comparisons, we additionally implement the BPSP on a D-Wave Quantum Annealer Advantage 2, obtaining a minimum paint swap ratio of $0.329$. Given that the QAOA with logarithmic circuit depth does not exhibit a quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm that outperforms both the RSG algorithm and logarithmic depth QAOA. We provide numerical evidence that the Mean-Field Approximate Optimization Algorithm (MF-AOA) is one such algorithm, yielding a paint swap ratio of approximately $0.280$ beating all known classical and quantum algorithms for the BPSP.

11 pages, 4 figures. Additional results for V3 including improved exact upper-bound rather than numerical upper-bound

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

arXiv:2604.00607 [quant-ph]

(or arXiv:2604.00607v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2604.00607 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.