Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer
Maxime Dupont, Bhuvanesh Sundar, Bram Evert, David E. Bernal Neira, Zedong Peng, Stephen Jeffrey, Mark J. Hodson
DOI 10.1103/PhysRevApplied.23.014045 · Physical Review Applied
Active bibliographic source — not scientific approval
Bibliographic access preserves source history; it does not approve extracted materials or validate reported claims. Review warnings on each occurrence separately.
Abstract
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.
Similar papers
Optimizing frequency allocation for fixed-frequency superconducting quantum processors
similarity 0.88Alexis Morvan et al.
Source status unknown — claims are unverified
Pulse-based variational quantum optimization and metalearning in superconducting circuits
similarity 0.88Yapeng Wang et al.
Source status unknown — claims are unverified
Efficient Algorithms for High-Dimensional Quantum Optimal Control of a Transmon Qubit
similarity 0.88Zhaoqi Leng et al.
Source status unknown — claims are unverified
Exploiting Dynamic Quantum Circuits in a Quantum Algorithm with Superconducting Qubits
similarity 0.87A. D. Córcoles et al.
Source status unknown — claims are unverified
Quantum optimal control of superconducting qubits based on machine-learning characterization
similarity 0.87Élie Genois et al.
Source status unknown — claims are unverified
Modeling of measurement-based quantum network coding on a superconducting quantum processor
similarity 0.87Poramet Pathumsoot et al.
Source status unknown — claims are unverified