Combinatorial optimization enhanced by shallow quantum circuits with 104 superconducting qubits

Area of Science:

• Quantum Computing
• Combinatorial Optimization
• Computational Physics

Background:

• Quantum computing aims to solve classically intractable problems.
• Combinatorial optimization problems are widely applicable and map to Ising Hamiltonians.
• Nondeterministic Polynomial time (NP)-hard problems, such as finding ground states of the Ising model, are key targets.

Purpose of the Study:

• To propose a quantum-sampling strategy for accelerating solutions to Ising model ground states.
• To design and experimentally demonstrate a quantum algorithm for NP-hard combinatorial optimization problems.
• To assess the potential for quantum speedup compared to classical algorithms.

Main Methods:

• Developed a quantum-sampling algorithm utilizing a shallow-circuit subroutine.
• Navigated the energy landscape of the Ising model.
• Experimentally tested the algorithm on up to 104 superconducting qubits.

Main Results:

• The quantum algorithm produced favorable solutions compared to a highly optimized classical simulated-annealing algorithm.
• Demonstrated a path toward quantum speedup using the time-to-solution metric.
• Showcased competitive performance against classical heuristics on near-term superconducting processors.

Conclusions:

• The proposed quantum-sampling strategy offers a promising alternative for combinatorial optimization.
• Quantum advantage for these problems may be achievable on current superconducting quantum processors.
• The study highlights the potential of quantum computing for tackling valuable, complex optimization tasks.