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

被引：348

作者：

Harrigan, Matthew P. ^{[1
]}

Sung, Kevin J. ^{[1
,2
]}

Neeley, Matthew ^{[1
]}

Satzinger, Kevin J. ^{[1
]}

Arute, Frank ^{[1
]}

Arya, Kunal ^{[1
]}

Atalaya, Juan ^{[1
]}

Bardin, Joseph C. ^{[1
,3
]}

Barends, Rami ^{[1
]}

Boixo, Sergio ^{[1
]}

Broughton, Michael ^{[1
]}

Buckley, Bob B. ^{[1
]}

Buell, David A. ^{[1
]}

Burkett, Brian ^{[1
]}

Bushnell, Nicholas ^{[1
]}

Chen, Yu ^{[1
]}

Chen, Zijun ^{[1
]}

Chiaro, Ben ^{[1
,4
]}

Collins, Roberto ^{[1
]}

Courtney, William ^{[1
]}

Demura, Sean ^{[1
]}

Dunsworth, Andrew ^{[1
]}

Eppens, Daniel ^{[1
]}

Fowler, Austin ^{[1
]}

Foxen, Brooks ^{[1
]}

Gidney, Craig ^{[1
]}

Giustina, Marissa ^{[1
]}

Graff, Rob ^{[1
]}

Habegger, Steve ^{[1
]}

Ho, Alan ^{[1
]}

Hong, Sabrina ^{[1
]}

Huang, Trent ^{[1
]}

Ioffe, L. B. ^{[1
]}

Isakov, Sergei, V ^{[1
]}

Jeffrey, Evan ^{[1
]}

Jiang, Zhang ^{[1
]}

Jones, Cody ^{[1
]}

Kafri, Dvir ^{[1
]}

Kechedzhi, Kostyantyn ^{[1
]}

Kelly, Julian ^{[1
]}

Kim, Seon ^{[1
]}

Klimov, Paul, V ^{[1
]}

Korotkov, Alexander N. ^{[1
,5
]}

Kostritsa, Fedor ^{[1
]}

Landhuis, David ^{[1
]}

Laptev, Pavel ^{[1
]}

Lindmark, Mike ^{[1
]}

Leib, Martin ^{[6
]}

Martin, Orion ^{[1
]}

Martinis, John M. ^{[1
,4
]}

机构：

[1] Google Res, Mountain View, CA 94043 USA

[2] Univ Michigan, Dept Elect Engn & Comp Sci, Ann Arbor, MI 48109 USA

[3] Univ Massachusetts, Dept Elect & Comp Engn, Amherst, MA 01003 USA

[4] Univ Calif Santa Barbara, Dept Phys, Santa Barbara, CA 93106 USA

[5] Univ Calif Riverside, Dept Elect & Comp Engn, Riverside, CA 92521 USA

[6] Volkswagen Data Lab, Munich, Germany

[7] NASA, Ames Res Ctr, Moffett Field, CA 94035 USA

[8] Univ Calif Berkeley, Dept Elect Engn & Comp Sci, Berkeley, CA 94720 USA

[9] Leiden Univ, Leiden, Netherlands

[10] Friedrich Alexander Univ Erlangen Nurnberg, Dept Phys, Erlangen, Germany

[11] Harvard Univ, Dept Phys, Cambridge, MA 02138 USA

来源：

NATURE PHYSICS | 2021年 / 17卷 / 03期

基金：

欧盟地平线“2020”;

关键词：

MODEL; CUT;

D O I：

10.1038/s41567-020-01105-y

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页码：332 / +

页数：6

共 38 条

[1] Implementation of XY entangling gates with a single calibrated pulse [J].

Abrams, Deanna M. ;

Didier, Nicolas ;

Johnson, Blake R. ;

da Silva, Marcus P. ;

Ryan, Colm A. .

NATURE ELECTRONICS, 2020, 3 (12) :744-+

[2]

[Anonymous], 2020, CIRQ DEV CIRQ PYTH F

[3] Quantum supremacy using a programmable superconducting processor [J].

Arute, Frank ;

Arya, Kunal ;

Babbush, Ryan ;

Bacon, Dave ;

Bardin, Joseph C. ;

Barends, Rami ;

Biswas, Rupak ;

Boixo, Sergio ;

Brandao, Fernando G. S. L. ;

Buell, David A. ;

Burkett, Brian ;

Chen, Yu ;

Chen, Zijun ;

Chiaro, Ben ;

Collins, Roberto ;

Courtney, William ;

Dunsworth, Andrew ;

Farhi, Edward ;

Foxen, Brooks ;

Fowler, Austin ;

Gidney, Craig ;

Giustina, Marissa ;

Graff, Rob ;

Guerin, Keith ;

Habegger, Steve ;

Harrigan, Matthew P. ;

Hartmann, Michael J. ;

Ho, Alan ;

Hoffmann, Markus ;

Huang, Trent ;

Humble, Travis S. ;

Isakov, Sergei V. ;

Jeffrey, Evan ;

Jiang, Zhang ;

Kafri, Dvir ;

Kechedzhi, Kostyantyn ;

Kelly, Julian ;

Klimov, Paul V. ;

Knysh, Sergey ;

Korotkov, Alexander ;

Kostritsa, Fedor ;

Landhuis, David ;

Lindmark, Mike ;

Lucero, Erik ;

Lyakh, Dmitry ;

Mandra, Salvatore ;

McClean, Jarrod R. ;

McEwen, Matthew ;

Megrant, Anthony ;

Mi, Xiao .

NATURE, 2019, 574 (7779) :505-+

[4] ON THE COMPUTATIONAL-COMPLEXITY OF ISING SPIN-GLASS MODELS [J].

BARAHONA, F .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1982, 15 (10) :3241-3253

[5] Improved Success Probability with Greater Circuit Depth for the Quantum Approximate Optimization Algorithm [J].

Bengtsson, Andreas ;

Vikstal, Pontus ;

Warren, Christopher ;

Svensson, Marika ;

Gu, Xiu ;

Kockum, Anton Frisk ;

Krantz, Philip ;

Krizan, Christian ;

Shiri, Daryoush ;

Svensson, Ida-Maria ;

Tancredi, Giovanna ;

Johansson, Goran ;

Delsing, Per ;

Ferrini, Giulia ;

Bylander, Jonas .

PHYSICAL REVIEW APPLIED, 2020, 14 (03)

[6]

Berman P., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P200

[7] A NASA perspective on quantum computing: Opportunities and challenges [J].