- 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
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
Learn more about how we do research
We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work