Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems
The ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same tim...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-05-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.7.023165 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849736924733898752 |
|---|---|
| author | Thorge Müller Ajainderpal Singh Frank K. Wilhelm Tim Bode |
| author_facet | Thorge Müller Ajainderpal Singh Frank K. Wilhelm Tim Bode |
| author_sort | Thorge Müller |
| collection | DOAJ |
| description | The ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put into doubt. Here we analyze the QAOA's performance on random Max-kXOR as a function of k and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large k and numbers of layers p, there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large p, which must be considered rather difficult both in the variational context and on near-term devices. |
| format | Article |
| id | doaj-art-d23fbc852cc34d9691e11bfeb2aa0c86 |
| institution | DOAJ |
| issn | 2643-1564 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj-art-d23fbc852cc34d9691e11bfeb2aa0c862025-08-20T03:07:06ZengAmerican Physical SocietyPhysical Review Research2643-15642025-05-017202316510.1103/PhysRevResearch.7.023165Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problemsThorge MüllerAjainderpal SinghFrank K. WilhelmTim BodeThe ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put into doubt. Here we analyze the QAOA's performance on random Max-kXOR as a function of k and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large k and numbers of layers p, there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large p, which must be considered rather difficult both in the variational context and on near-term devices.http://doi.org/10.1103/PhysRevResearch.7.023165 |
| spellingShingle | Thorge Müller Ajainderpal Singh Frank K. Wilhelm Tim Bode Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems Physical Review Research |
| title | Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems |
| title_full | Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems |
| title_fullStr | Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems |
| title_full_unstemmed | Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems |
| title_short | Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems |
| title_sort | limitations of quantum approximate optimization in solving generic higher order constraint satisfaction problems |
| url | http://doi.org/10.1103/PhysRevResearch.7.023165 |
| work_keys_str_mv | AT thorgemuller limitationsofquantumapproximateoptimizationinsolvinggenerichigherorderconstraintsatisfactionproblems AT ajainderpalsingh limitationsofquantumapproximateoptimizationinsolvinggenerichigherorderconstraintsatisfactionproblems AT frankkwilhelm limitationsofquantumapproximateoptimizationinsolvinggenerichigherorderconstraintsatisfactionproblems AT timbode limitationsofquantumapproximateoptimizationinsolvinggenerichigherorderconstraintsatisfactionproblems |