Jump to Content

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

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