Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917019878686720 |
|---|---|
| author | Streif, Michael Yarkoni, Sheir Skolik, Andrea Neukart, Florian Leib, Martin |
| author_facet | Streif, Michael Yarkoni, Sheir Skolik, Andrea Neukart, Florian Leib, Martin |
| contents | 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 and demonstrate that QAOA with constant depth is able to beat classical heuristics on average in the infinite size limit $n\rightarrow\infty$. For the BPSP, it is known that no classical algorithm can exist which approximates the problem in polynomial runtime. We introduce a BPSP instance which is hard to solve with QAOA, and numerically investigate its performance and discuss QAOA's ability to generate approximate solutions. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through AWS Braket. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_03403 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm Streif, Michael Yarkoni, Sheir Skolik, Andrea Neukart, Florian Leib, Martin Quantum Physics 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 and demonstrate that QAOA with constant depth is able to beat classical heuristics on average in the infinite size limit $n\rightarrow\infty$. For the BPSP, it is known that no classical algorithm can exist which approximates the problem in polynomial runtime. We introduce a BPSP instance which is hard to solve with QAOA, and numerically investigate its performance and discuss QAOA's ability to generate approximate solutions. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through AWS Braket. |
| title | Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2011.03403 |