Jump to Content

Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

Matthew Harrigan
Kevin Jeffery Sung
Kevin Satzinger
Matthew Neeley
Frank Carlton Arute
Kunal Arya
Juan Atalaya
Joseph Bardin
Rami Barends
Sergio Boixo
Michael Blythe Broughton
Bob Benjamin Buckley
David A Buell
Brian Burkett
Nicholas Bushnell
Jimmy Chen
Yu Chen
Ben Chiaro
Roberto Collins
William Courtney
Sean Demura
Andrew Dunsworth
Austin Fowler
Brooks Riley Foxen
Craig Michael Gidney
Marissa Giustina
Rob Graff
Steve Habegger
Sabrina Hong
Lev Ioffe
Sergei Isakov
Evan Jeffrey
Zhang Jiang
Cody Jones
Dvir Kafri
Kostyantyn Kechedzhi
Julian Kelly
Seon Kim
Paul Klimov
Alexander Korotkov
Fedor Kostritsa
Dave Landhuis
Pavel Laptev
Martin Leib
Mike Lindmark
Orion Martin
John Martinis
Jarrod Ryan McClean
Matthew McEwen
Anthony Megrant
Xiao Mi
Masoud Mohseni
Wojtek Mruczkiewicz
Josh Mutus
Ofer Naaman
Charles Neill
Florian Neukart
Murphy Yuezhen Niu
Thomas E O'Brien
Bryan O'Gorman
A.G. Petukhov
Harry Putterman
Chris Quintana
Pedram Roushan
Nicholas Rubin
Daniel Sank
Andrea Skolik
Vadim Smelyanskiy
Doug Strain
Michael Streif
Marco Szalay
Amit Vainsencher
Ted White
Jamie Yao
Adam Zalcman
Leo Zhou
Hartmut Neven
Dave Bacon
Erik Lucero
Edward Farhi
Ryan Babbush
Nature Physics (2021)
Download Google Scholar

Abstract

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.

Research Areas