Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
Streif M, Yarkoni S, Skolik A, Neukart F, Leib M (2021)
Publication Type: Journal article
Publication year: 2021
Journal
Book Volume: 104
Article Number: 012403
Journal Issue: 1
DOI: 10.1103/PhysRevA.104.012403
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→∞. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through Amazon Braket.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Streif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021). Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm. Physical Review A, 104(1). https://dx.doi.org/10.1103/PhysRevA.104.012403
MLA:
Streif, Michael, et al. "Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm." Physical Review A 104.1 (2021).
BibTeX: Download