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

Harrigan MP, Sung KJ, Neeley M, Satzinger KJ, Arute F, Arya K, Atalaya J, Bardin JC, Barends R, Boixo S, Broughton M, Buckley BB, Buell DA, Burkett B, Bushnell N, Chen Y, Chen Z, Chiaro B, Collins R, Courtney W, Demura S, Dunsworth A, Eppens D, Fowler A, Foxen B, Gidney C, Giustina M, Graff R, Habegger S, Ho A, Hong S, Huang T, Ioffe LB, Isakov S, Jeffrey E, Jiang Z, Jones C, Kafri D, Kechedzhi K, Kelly J, Kim S, Klimov P, Korotkov AN, Kostritsa F, Landhuis D, Laptev P, Lindmark M, Leib M, Martin O, Martinis JM, Mcclean JR, Mcewen M, Megrant A, Mi X, Mohseni M, Mruczkiewicz W, Mutus J, Naaman O, Neill C, Neukart F, Niu MY, O'Brien TE, O'Gorman B, Ostby E, Petukhov A, Putterman H, Quintana C, Roushan P, Rubin NC, Sank D, Skolik A, Smelyanskiy V, Strain D, Streif M, Szalay M, Vainsencher A, White T, Yao ZJ, Yeh P, Zalcman A, Zhou L, Neven H, Bacon D, Lucero E, Farhi E, Babbush R (2021)

Publication Type: Journal article

Publication year: 2021

Journal

Nature Physics Nature Research

DOI: 10.1038/s41567-020-01105-y

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.

Authors with CRIS profile

Michael Streif Lehrstuhl für Theoretische Physik

Involved external institutions

Google Inc. US United States (USA) (US) Volkswagen Data Lab DE Germany (DE) National Aeronautics and Space Administration (NASA) US United States (USA) (US)

How to cite

APA:

Harrigan, M.P., Sung, K.J., Neeley, M., Satzinger, K.J., Arute, F., Arya, K.,... Babbush, R. (2021). Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics. https://dx.doi.org/10.1038/s41567-020-01105-y

MLA:

Harrigan, Matthew P., et al. "Quantum approximate optimization of non-planar graph problems on a planar superconducting processor." Nature Physics (2021).

BibTeX: Download