Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929688386994176 |
|---|---|
| author | Dupont, Maxime Sundar, Bhuvanesh Evert, Bram Neira, David E. Bernal Peng, Zedong Jeffrey, Stephen Hodson, Mark J. |
| author_facet | Dupont, Maxime Sundar, Bhuvanesh Evert, Bram Neira, David E. Bernal Peng, Zedong Jeffrey, Stephen Hodson, Mark J. |
| contents | Achieving high-quality solutions faster than classical solvers on computationally hard problems is a challenge for quantum optimization to deliver utility. Using a superconducting quantum computer, we experimentally investigate the performance of a hybrid quantum-classical algorithm inspired by semidefinite programming approaches for solving the maximum-cut problem on 3-regular graphs up to several thousand variables. We leverage the structure of the input problems to address sizes beyond what current quantum machines can naively handle. We attain an average approximation ratio of 99% over a random ensemble of thousands of problem instances. We benchmark the quantum solver against similarly high-performing classical heuristics, including the Gurobi optimizer, simulated annealing, and the Burer-Monteiro algorithm. A run-time analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others on a projected 100-qubit quantum computer. We explore multiple leads to close the gap and discuss prospects for a practical quantum speedup. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17579 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer Dupont, Maxime Sundar, Bhuvanesh Evert, Bram Neira, David E. Bernal Peng, Zedong Jeffrey, Stephen Hodson, Mark J. Quantum Physics Achieving high-quality solutions faster than classical solvers on computationally hard problems is a challenge for quantum optimization to deliver utility. Using a superconducting quantum computer, we experimentally investigate the performance of a hybrid quantum-classical algorithm inspired by semidefinite programming approaches for solving the maximum-cut problem on 3-regular graphs up to several thousand variables. We leverage the structure of the input problems to address sizes beyond what current quantum machines can naively handle. We attain an average approximation ratio of 99% over a random ensemble of thousands of problem instances. We benchmark the quantum solver against similarly high-performing classical heuristics, including the Gurobi optimizer, simulated annealing, and the Burer-Monteiro algorithm. A run-time analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others on a projected 100-qubit quantum computer. We explore multiple leads to close the gap and discuss prospects for a practical quantum speedup. |
| title | Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2404.17579 |