Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
Physical Review A, vol. 104
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.
Authors 5
-
Volkswagen Group (Germany) · Friedrich-Alexander-Universität Erlangen-Nürnberg · Data:Lab Munich (Germany)
Affiliation as printed
Data:Lab, Volkswagen Group, Ungererstrasse 69, 80805 München, Germany
University Erlangen-Nürnberg (FAU), Institute of Theoretical Physics, Staudtstrasse 7, 91058 Erlangen, Germany
-
Sheir Yarkoni Aachen
Leiden University · Volkswagen Group (Germany) · Data:Lab Munich (Germany)
Affiliation as printed
Data:Lab, Volkswagen Group, Ungererstrasse 69, 80805 München, Germany
LIACS, Leiden University, Snellius Gebouw, Niels Bohrweg 1, 2333 CA Leiden, Netherlands
-
Andrea Skolik Aachen
Leiden University · Volkswagen Group (Germany) · Data:Lab Munich (Germany)
Affiliation as printed
Data:Lab, Volkswagen Group, Ungererstrasse 69, 80805 München, Germany
LIACS, Leiden University, Snellius Gebouw, Niels Bohrweg 1, 2333 CA Leiden, Netherlands
-
Florian Neukart Aachen
Leiden University · Volkswagen Group (Germany) · Data:Lab Munich (Germany)
Affiliation as printed
Data:Lab, Volkswagen Group, Ungererstrasse 69, 80805 München, Germany
LIACS, Leiden University, Snellius Gebouw, Niels Bohrweg 1, 2333 CA Leiden, Netherlands
-
Volkswagen Group (Germany) · Data:Lab Munich (Germany)
Affiliation as printed
Data:Lab, Volkswagen Group, Ungererstrasse 69, 80805 München, Germany
Cited by 40 stored of 40
No patents citing this paper on Lens.org (checked 2026-10-11).