Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
Creators: name: Harrigan, Matthew P.
name: Sung, Kevin J.
name: Neeley, Matthew
name: Satzinger, Kevin J.
name: Arute, Frank
name: Arya, Kunal
name: Atalaya, Juan
name: Bardin, Joseph C.
name: Barends, Rami
name: Boixo, Sergio
name: Broughton, Michael
name: Buckley, Bob B.
name: Buell, David A.
name: Burkett, Brian
name: Bushnell, Nicholas
name: Chen, Yu
name: Chen, Zijun
name: Chiaro, Ben
name: Collins, Roberto
name: Courtney, William
name: Demura, Sean
name: Dunsworth, Andrew
name: Eppens, Daniel
name: Fowler, Austin
name: Foxen, Brooks
name: Gidney, Craig
name: Giustina, Marissa
name: Graff, Rob
name: Habegger, Steve
name: Ho, Alan
name: Hong, Sabrina
name: Huang, Trent
name: Ioffe, L. B.
name: Isakov, Sergei V.
name: Jeffrey, Evan
name: Jiang, Zhang
name: Jones, Cody
name: Kafri, Dvir
name: Kechedzhi, Kostyantyn
name: Kelly, Julian
name: Kim, Seon
name: Klimov, Paul V.
name: Korotkov, Alexander N.
name: Kostritsa, Fedor
name: Landhuis, David
name: Laptev, Pavel
name: Lindmark, Mike
name: Leib, Martin
name: Martin, Orion
name: Martinis, John M.
name: McClean, Jarrod R.
name: McEwen, Matt
name: Megrant, Anthony
name: Mi, Xiao
name: Mohseni, Masoud
name: Mruczkiewicz, Wojciech
name: Mutus, Josh
name: Naaman, Ofer
name: Neill, Charles
name: Neukart, Florian
name: Niu, Murphy Yuezhen
name: O'Brien, Thomas E.
name: O'Gorman, Bryan
name: Ostby, Eric
name: Petukhov, Andre
name: Putterman, Harald
name: Quintana, Chris
name: Roushan, Pedram
name: Rubin, Nicholas C.
name: Sank, Daniel
name: Skolik, Andrea
name: Smelyanskiy, Vadim
name: Strain, Doug
name: Streif, Michael
name: Szalay, Marco
name: Vainsencher, Amit
name: White, Theodore
name: Yao, Z. Jamie
name: Yeh, Ping
name: Zalcman, Adam
name: Zhou, Leo
name: Neven, Hartmut
name: Bacon, Dave
name: Lucero, Erik
name: Farhi, Edward
name: Babbush, Ryan
Publisher: name: arXiv
Year: 2020
Subjects: subject: Quantum Physics (quant-ph)
subject: FOS: Physical sciences
subject: FOS: Physical sciences

description: 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 of our hardware; however, we also apply the QAOA to the Sherrington-Kirkpatrick model and MaxCut, both high dimensional graph problems for which the QAOA requires significant compilation. Experimental scans of the QAOA energy landscape show good agreement with theory across even the largest instances studied (23 qubits) and we are able to perform variational optimization successfully. For problems defined on our hardware graph we obtain an approximation ratio that is independent of problem size and observe, for the first time, that performance increases with circuit depth. For problems requiring compilation, performance decreases with problem size but still provides an advantage over random guessing for circuits involving several thousand gates. This behavior highlights the challenge of using near-term quantum computers to optimize problems on graphs differing from hardware connectivity. As these graphs are more representative of real world instances, our results advocate for more emphasis on such problems in the developing tradition of using the QAOA as a holistic, device-level benchmark of quantum processors.
description: 19 pages, 15 figures