Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal 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, B. 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 R. 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, A. 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, D. Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, A. 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• 619 citations
arXivHTMLPDF
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

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.

arXiv:2303.02064•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•27 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

Feedback-Based Quantum Optimization

Alicia B Magann, Kenneth Rudinger, Matthew Grace +1 more

It is hoped that quantum computers will offer advantages over classical computers for combinatorial optimization. Here, we introduce a feedback-based strategy for quantum optimization, where the results of qubit measurements are used to constructively assign values to quantum circuit parameters. We show that this procedure results in an estimate of the combinatorial optimization problem solution that improves monotonically with the depth of the quantum circuit. Importantly, the measurement-based feedback enables approximate solutions to the combinatorial optimization problem without the need for any classical optimization effort, as would be required for the quantum approximate optimization algorithm. We demonstrate this feedback-based protocol on a superconducting quantum processor for the graph-partitioning problem MaxCut, and present a series of numerical analyses that further investigate the protocol's performance.

arXiv:2103.08619•Physical Review Letters•Dec 13, 2022•84 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•37 citations
QAOAwith N⋅p≥200N\cdot p\geq 200N⋅p≥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 highN⋅pN\cdot pN⋅p, whereNNNis the number of qubits andpppis 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 withN⋅pN\cdot pN⋅pof up to 300 on the Quantinuum 81–1 trapped-ion quantum processor. To the best of our knowledge, this is the highestN⋅pN\cdot pN⋅pdemonstrated 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 densitydensitydensity 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.
It is hoped that quantum computers will offer advantages over classical computers for combinatorial optimization. Here, we introduce a feedback-based strategy for quantum optimization, where the results of qubit measurements are used to constructively assign values to quantum circuit parameters. We show that this procedure results in an estimate of the combinatorial optimization problem solution that improves monotonically with the depth of the quantum circuit. Importantly, the measurement-based feedback enables approximate solutions to the combinatorial optimization problem without the need for any classical optimization effort, as would be required for the quantum approximate optimization algorithm. We demonstrate this feedback-based protocol on a superconducting quantum processor for the graph-partitioning problem MaxCut, and present a series of numerical analyses that further investigate the protocol's performance.