Quantum approximate optimization of non-planar graph problems on a planar superconducting processor

By F. Arute, K. Arya, Ryan Babbush, D. Bacon, J. Bardin, R. Barends, Sergio Boixo, M. Broughton, B. Buckley, D. Buell and 74 more. Nature Physics, 2020

622 citations recorded by the source corpus.

Faster algorithms for combinatorial optimization could prove transformative for diverse areas such as logistics, finance and machine learning. Accordingly, the possibility of quantum enhanced optimization has driven much interest in quantum technologies. Here we demonstrate the application of the Google Sycamore superconducting qubit quantum processor to combinatorial optimization problems with the quantum approximate optimization algorithm (QAOA). Like past QAOA experiments, we study performance for problems defined on the planar connectivity graph native to our hardware; however, we also apply the QAOA to the Sherrington–Kirkpatrick model and MaxCut, non-native problems that require extensive compilation to implement. For hardware-native problems, which are classically efficient to solve on average, we obtain an approximation ratio that is independent of problem size and observe that performance increases with circuit depth. For problems requiring compilation, performance decreases with problem size. Circuits involving several thousand gates still present an advantage over random guessing but not over some efficient classical algorithms. Our results suggest that it will be challenging to scale near-term implementations of the QAOA for problems on non-native graphs. As these graphs are closer to real-world instances, we suggest more emphasis should be placed on such problems when using the QAOA to benchmark quantum processors. It is hoped that quantum computers may be faster than classical ones at solving optimization problems. Here the authors implement a quantum optimization algorithm over 23 qubits but find more limited performance when an optimization problem structure does not match the underlying hardware.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/91c10ab4c59843ecb405018b13f792719ce7009c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Demonstration of quantum volume 64 on a superconducting quantum computing system (2020, background): “This demonstrates the benefit of removing simplifying abstraction barriers in the exposed gate set to gain efficiency in compiling [22], [23], [24].”
Noise-induced barren plateaus in variational quantum algorithms (2020, methodology): “For combinatorial optimization problems, such as MaxCut on 3-regular graphs, the compilation of a single instance of the problem unitary e−iγHP can require an Ω(n)-depth circuit [54].”
General parameter-shift rules for quantum gradients (2021, background): “Since then, it has been investigated analytically [60, 61, 62], numerically [63, 64], and on quantum computers [65, 66].”
Quantum computing with neutral atoms (2020, background): “A recent preprint from the Google group supported this statement, by finding that the best performance of a variational algorithm for optimization was achieved on a problem that maps directly to the native hardware layout of the device [73].”
Ising machines as hardware solvers of combinatorial optimization problems (2022, methodology): “QAOA has been demonstrated at the small-scale on platforms such as superconducting qubits 167 , photonics 168 to trapped ions 165 .”
Cost function dependent barren plateaus in shallow parametrized quantum circuits (2021, background): “As recent large-scale implementations for chemistry 7 and optimization 8 applications have shown, this ansatz leads to smaller errors due to hardware noise.”
Warm-starting quantum optimization (2020, background): “The circuits become especially deep when large p is required or when the native hardware connectivity does not match the problem structure, thence requiring SWAP gates [40].”