© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2004.04197 · Nature Physics

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

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

Published Feb 4, 2021• 555 citations

DOI: 10.1038/s41567-020-01105-y

Related papers

Quantum approximate optimization on a gate-model superconducting processor

William J. Zeng, Nicholas C. Rubin, Michael J. Curtis +22 more

Bulletin of the American Physical Society•Mar 15, 2017•0 citations

QAOA with $N\cdot p\geq 200$

Ruslan Shaydulin, Marco Pistoia

One of the central goals of the DARPA Optimization with Noisy Intermediate-Scale Quantum (ONISQ) program is to implement a hybrid quantum/classical optimization algorithm with high $N\cdot p$, where $N$ is the number of qubits and $p$ is the number of alternating applications of parameterized quantum operators in the protocol. In this note, we demonstrate the execution of the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on non-planar 3-regular graphs with $N\cdot p$ of up to $320$ on the Quantinuum H1-1 and H2 trapped-ion quantum processors. To the best of our knowledge, this is the highest $N\cdot p$ demonstrated on hardware to date. Our demonstration highlights the rapid progress of quantum hardware.

arXiv:2303.02064•Mar 3, 2023•2 citations

QAOAwith $N\cdot p\geq 200$

Ruslan Shaydulin, Marco Pistoia

One of the central goals of the DARPA Optimization with Noisy Intermediate-Scale Quantum (ONISQ) program is to implement a hybrid quantum/classical optimization algorithm with high$N\cdot p$, where$N$is the number of qubits and$p$is the number of alternating applications of parameterized quantum operators in the protocol. In this note, we demonstrate the execution of the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on non-planar 3-regular graphs with$N\cdot p$of up to 300 on the Quantinuum 81–1 trapped-ion quantum processor. To the best of our knowledge, this is the highest$N\cdot p$demonstrated on hardware to date. Our demonstration highlights the rapid progress of quantum hardware.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•11 citations

Approaches to Constrained Quantum Approximate Optimization

Zain H. Saleem, Teague Tomesh, Bilal Tariq +1 more

arXiv:2010.06660•SN Computer Science•Jan 30, 2023•25 citations

Reachability Deficits Implicit in Google's Quantum Approximate Optimization of Graph Problems

V. Akshay, Hariphan Philathong, I. Zacharov +1 more

The quantum approximate optimisation algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the $density$ of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. We performed a detailed reanalysis of the data reproduced from Google's Sycamore superconducting qubit quantum processor executing QAOA applied to minimization problems on graphs. We found that Sycamore approaches a rapid fall-off in approximation quality experienced beyond intermediate-density instances. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.

•Jul 17, 2020•5 citations

Shape Design Optimization for 3D Integrated Superconducting Quantum Processors

Alireza Najafi-Yazdi, Guillaume Duclos-Cianci, Kevin Lalumière

Bulletin of the American Physical Society•Mar 8, 2018•0 citations

QAOA with

N\cdot p\geq 200

One of the central goals of the DARPA Optimization with Noisy Intermediate-Scale Quantum (ONISQ) program is to implement a hybrid quantum/classical optimization algorithm with high

N\cdot p

, where

N

is the number of qubits and

p

is the number of alternating applications of parameterized quantum operators in the protocol. In this note, we demonstrate the execution of the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on non-planar 3-regular graphs with

N\cdot p

of up to

320

on the Quantinuum H1-1 and H2 trapped-ion quantum processors. To the best of our knowledge, this is the highest

N

demonstrated on hardware to date. Our demonstration highlights the rapid progress of quantum hardware.

QAOAwith

N\cdot p

One of the central goals of the DARPA Optimization with Noisy Intermediate-Scale Quantum (ONISQ) program is to implement a hybrid quantum/classical optimization algorithm with high

N\cdot p

, where

N

is the number of qubits and

p

is the number of alternating applications of parameterized quantum operators in the protocol. In this note, we demonstrate the execution of the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on non-planar 3-regular graphs with

N\cdot p

of up to 300 on the Quantinuum 81–1 trapped-ion quantum processor. To the best of our knowledge, this is the highest

N\cdot p

demonstrated on hardware to date. Our demonstration highlights the rapid progress of quantum hardware.

The quantum approximate optimisation algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the

density

of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. We performed a detailed reanalysis of the data reproduced from Google's Sycamore superconducting qubit quantum processor executing QAOA applied to minimization problems on graphs. We found that Sycamore approaches a rapid fall-off in approximation quality experienced beyond intermediate-density instances. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.