Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
Michael Streif, Sheir Yarkoni, Andrea Skolik, Florian Neukart, Martin Leib
Abstract
The binary paint shop problem (BPSP) is an APX-hard optimization problem of the automotive industry. In this work, we show how to use the quantum approximate optimization algorithm (QAOA) to find solutions of the BPSP. We demonstrate that QAOA with constant depth is able to beat all known heuristics for the binary paint shop problem on average in the infinite size limit $n\ensuremath{\rightarrow}\ensuremath{\infty}$. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through Amazon Braket.
Topics & Concepts
HeuristicsBinary numberQuantumComputer scienceAlgorithmMathematical optimizationMathematicsPhysicsArithmeticQuantum mechanicsQuantum Computing Algorithms and ArchitectureOptimization and Search ProblemsQuantum Information and Cryptography