Matthew P Harrigan

Matthew P Harrigan

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Preview abstract Quantum computing's transition from theory to reality has spurred the need for novel software tools to manage the increasing complexity, sophistication, toil, and chance for error of quantum algorithm development. We present Qualtran, an open-source library for representing and analyzing quantum algorithms. Using carefully chosen abstractions and data structures, we can simulate and test algorithms, automatically generate information-rich diagrams, and tabulate resource requirements. Qualtran offers a \emph{standard library} of algorithmic building blocks that are essential for modern cost-minimizing compilations. Its capabilities are showcased through the re-analysis of key algorithms in Hamiltonian simulation, chemistry, and cryptography. The resulting architecture-independent resource counts can be forwarded to our implementation of cost models to estimate physical costs like wall-clock time and number of physical qubits assuming a surface-code architecture. Qualtran provides a foundation for explicit constructions and reproducible analysis, fostering greater collaboration within the quantum algorithm development community. We believe tools like Qualtran will accelerate progress in the field. View details
    Stable quantum-correlated many-body states through engineered dissipation
    Xiao Mi
    Alexios Michailidis
    Sara Shabani
    Jerome Lloyd
    Rajeev Acharya
    Igor Aleiner
    Trond Andersen
    Markus Ansmann
    Frank Arute
    Kunal Arya
    Juan Atalaya
    Gina Bortoli
    Alexandre Bourassa
    Leon Brill
    Michael Broughton
    Bob Buckley
    Tim Burger
    Nicholas Bushnell
    Jimmy Chen
    Benjamin Chiaro
    Desmond Chik
    Charina Chou
    Josh Cogan
    Roberto Collins
    Paul Conner
    William Courtney
    Alex Crook
    Ben Curtin
    Alejo Grajales Dau
    Dripto Debroy
    Agustin Di Paolo
    ILYA Drozdov
    Andrew Dunsworth
    Lara Faoro
    Edward Farhi
    Reza Fatemi
    Vinicius Ferreira
    Ebrahim Forati
    Brooks Foxen
    Élie Genois
    William Giang
    Dar Gilboa
    Raja Gosula
    Steve Habegger
    Michael Hamilton
    Monica Hansen
    Sean Harrington
    Paula Heu
    Markus Hoffmann
    Trent Huang
    Ashley Huff
    Bill Huggins
    Sergei Isakov
    Justin Iveland
    Cody Jones
    Pavol Juhas
    Kostyantyn Kechedzhi
    Marika Kieferova
    Alexei Kitaev
    Andrey Klots
    Alexander Korotkov
    Fedor Kostritsa
    John Mark Kreikebaum
    Dave Landhuis
    Pavel Laptev
    Kim Ming Lau
    Lily Laws
    Joonho Lee
    Kenny Lee
    Yuri Lensky
    Alexander Lill
    Wayne Liu
    Orion Martin
    Amanda Mieszala
    Shirin Montazeri
    Alexis Morvan
    Ramis Movassagh
    Wojtek Mruczkiewicz
    Charles Neill
    Ani Nersisyan
    Michael Newman
    JiunHow Ng
    Murray Ich Nguyen
    Tom O'Brien
    Alex Opremcak
    Andre Petukhov
    Rebecca Potter
    Leonid Pryadko
    Charles Rocque
    Negar Saei
    Kannan Sankaragomathi
    Henry Schurkus
    Christopher Schuster
    Mike Shearn
    Aaron Shorter
    Noah Shutty
    Vladimir Shvarts
    Jindra Skruzny
    Clarke Smith
    Rolando Somma
    George Sterling
    Doug Strain
    Marco Szalay
    Alfredo Torres
    Guifre Vidal
    Cheng Xing
    Jamie Yao
    Ping Yeh
    Juhwan Yoo
    Grayson Young
    Yaxing Zhang
    Ningfeng Zhu
    Jeremy Hilton
    Anthony Megrant
    Yu Chen
    Vadim Smelyanskiy
    Dmitry Abanin
    Science, 383 (2024), pp. 1332-1337
    Preview abstract Engineered dissipative reservoirs have the potential to steer many-body quantum systems toward correlated steady states useful for quantum simulation of high-temperature superconductivity or quantum magnetism. Using up to 49 superconducting qubits, we prepared low-energy states of the transverse-field Ising model through coupling to dissipative auxiliary qubits. In one dimension, we observed long-range quantum correlations and a ground-state fidelity of 0.86 for 18 qubits at the critical point. In two dimensions, we found mutual information that extends beyond nearest neighbors. Lastly, by coupling the system to auxiliaries emulating reservoirs with different chemical potentials, we explored transport in the quantum Heisenberg model. Our results establish engineered dissipation as a scalable alternative to unitary evolution for preparing entangled many-body states on noisy quantum processors. View details
    Dynamics of magnetization at infinite temperature in a Heisenberg spin chain
    Trond Andersen
    Rhine Samajdar
    Andre Petukhov
    Jesse Hoke
    Dmitry Abanin
    ILYA Drozdov
    Xiao Mi
    Alexis Morvan
    Charles Neill
    Rajeev Acharya
    Richard Ross Allen
    Kyle Anderson
    Markus Ansmann
    Frank Arute
    Kunal Arya
    Juan Atalaya
    Gina Bortoli
    Alexandre Bourassa
    Leon Brill
    Michael Broughton
    Bob Buckley
    Tim Burger
    Nicholas Bushnell
    Juan Campero
    Hung-Shen Chang
    Jimmy Chen
    Benjamin Chiaro
    Desmond Chik
    Josh Cogan
    Roberto Collins
    Paul Conner
    William Courtney
    Alex Crook
    Ben Curtin
    Agustin Di Paolo
    Andrew Dunsworth
    Clint Earle
    Lara Faoro
    Edward Farhi
    Reza Fatemi
    Vinicius Ferreira
    Ebrahim Forati
    Brooks Foxen
    Gonzalo Garcia
    Élie Genois
    William Giang
    Dar Gilboa
    Raja Gosula
    Alejo Grajales Dau
    Steve Habegger
    Michael Hamilton
    Monica Hansen
    Sean Harrington
    Paula Heu
    Gordon Hill
    Markus Hoffmann
    Trent Huang
    Ashley Huff
    Bill Huggins
    Sergei Isakov
    Justin Iveland
    Cody Jones
    Pavol Juhas
    Marika Kieferova
    Alexei Kitaev
    Andrey Klots
    Alexander Korotkov
    Fedor Kostritsa
    John Mark Kreikebaum
    Dave Landhuis
    Pavel Laptev
    Kim Ming Lau
    Lily Laws
    Joonho Lee
    Kenny Lee
    Yuri Lensky
    Alexander Lill
    Wayne Liu
    Salvatore Mandra
    Orion Martin
    Steven Martin
    Seneca Meeks
    Amanda Mieszala
    Shirin Montazeri
    Ramis Movassagh
    Wojtek Mruczkiewicz
    Ani Nersisyan
    Michael Newman
    JiunHow Ng
    Murray Ich Nguyen
    Tom O'Brien
    Seun Omonije
    Alex Opremcak
    Rebecca Potter
    Leonid Pryadko
    David Rhodes
    Charles Rocque
    Negar Saei
    Kannan Sankaragomathi
    Henry Schurkus
    Christopher Schuster
    Mike Shearn
    Aaron Shorter
    Noah Shutty
    Vladimir Shvarts
    Vlad Sivak
    Jindra Skruzny
    Clarke Smith
    Rolando Somma
    George Sterling
    Doug Strain
    Marco Szalay
    Doug Thor
    Alfredo Torres
    Guifre Vidal
    Cheng Xing
    Jamie Yao
    Ping Yeh
    Juhwan Yoo
    Grayson Young
    Yaxing Zhang
    Ningfeng Zhu
    Jeremy Hilton
    Anthony Megrant
    Yu Chen
    Vadim Smelyanskiy
    Vedika Khemani
    Sarang Gopalakrishnan
    Tomaž Prosen
    Science, 384 (2024), pp. 48-53
    Preview abstract Understanding universal aspects of quantum dynamics is an unresolved problem in statistical mechanics. In particular, the spin dynamics of the one-dimensional Heisenberg model were conjectured as to belong to the Kardar-Parisi-Zhang (KPZ) universality class based on the scaling of the infinite-temperature spin-spin correlation function. In a chain of 46 superconducting qubits, we studied the probability distribution of the magnetization transferred across the chain’s center, P(M). The first two moments of P(M) show superdiffusive behavior, a hallmark of KPZ universality. However, the third and fourth moments ruled out the KPZ conjecture and allow for evaluating other theories. Our results highlight the importance of studying higher moments in determining dynamic universality classes and provide insights into universal behavior in quantum systems. View details
    Purification-Based Quantum Error Mitigation of Pair-Correlated Electron Simulations
    Thomas E O'Brien
    Gian-Luca R. Anselmetti
    Fotios Gkritsis
    Vincent Elfving
    Stefano Polla
    William J. Huggins
    Oumarou Oumarou
    Kostyantyn Kechedzhi
    Dmitry Abanin
    Rajeev Acharya
    Igor Aleiner
    Richard Ross Allen
    Trond Ikdahl Andersen
    Kyle Anderson
    Markus Ansmann
    Frank Carlton Arute
    Kunal Arya
    Juan Atalaya
    Michael Blythe Broughton
    Bob Benjamin Buckley
    Alexandre Bourassa
    Leon Brill
    Tim Burger
    Nicholas Bushnell
    Jimmy Chen
    Yu Chen
    Benjamin Chiaro
    Desmond Chun Fung Chik
    Josh Godfrey Cogan
    Roberto Collins
    Paul Conner
    William Courtney
    Alex Crook
    Ben Curtin
    Ilya Drozdov
    Andrew Dunsworth
    Daniel Eppens
    Lara Faoro
    Edward Farhi
    Reza Fatemi
    Ebrahim Forati
    Brooks Riley Foxen
    William Giang
    Dar Gilboa
    Alejandro Grajales Dau
    Steve Habegger
    Michael C. Hamilton
    Sean Harrington
    Jeremy Patterson Hilton
    Markus Rudolf Hoffmann
    Trent Huang
    Ashley Anne Huff
    Sergei Isakov
    Justin Thomas Iveland
    Cody Jones
    Pavol Juhas
    Marika Kieferova
    Andrey Klots
    Alexander Korotkov
    Fedor Kostritsa
    John Mark Kreikebaum
    Dave Landhuis
    Pavel Laptev
    Kim Ming Lau
    Lily MeeKit Laws
    Joonho Lee
    Kenny Lee
    Alexander T. Lill
    Wayne Liu
    Orion Martin
    Trevor Johnathan Mccourt
    Anthony Megrant
    Xiao Mi
    Masoud Mohseni
    Shirin Montazeri
    Alexis Morvan
    Ramis Movassagh
    Wojtek Mruczkiewicz
    Charles Neill
    Ani Nersisyan
    Michael Newman
    Jiun How Ng
    Murray Nguyen
    Alex Opremcak
    Andre Gregory Petukhov
    Rebecca Potter
    Kannan Aryaperumal Sankaragomathi
    Christopher Schuster
    Mike Shearn
    Aaron Shorter
    Vladimir Shvarts
    Jindra Skruzny
    Vadim Smelyanskiy
    Clarke Smith
    Rolando Diego Somma
    Doug Strain
    Marco Szalay
    Alfredo Torres
    Guifre Vidal
    Jamie Yao
    Ping Yeh
    Juhwan Yoo
    Grayson Robert Young
    Yaxing Zhang
    Ningfeng Zhu
    Christian Gogolin
    Nature Physics (2023)
    Preview abstract An important measure of the development of quantum computing platforms has been the simulation of increasingly complex physical systems. Prior to fault-tolerant quantum computing, robust error mitigation strategies are necessary to continue this growth. Here, we study physical simulation within the seniority-zero electron pairing subspace, which affords both a computational stepping stone to a fully correlated model, and an opportunity to validate recently introduced ``purification-based'' error-mitigation strategies. We compare the performance of error mitigation based on doubling quantum resources in time (echo verification) or in space (virtual distillation), on up to 20 qubits of a superconducting qubit quantum processor. We observe a reduction of error by one to two orders of magnitude below less sophisticated techniques (e.g. post-selection); the gain from error mitigation is seen to increase with the system size. Employing these error mitigation strategies enables the implementation of the largest variational algorithm for a correlated chemistry system to-date. Extrapolating performance from these results allows us to estimate minimum requirements for a beyond-classical simulation of electronic structure. We find that, despite the impressive gains from purification-based error mitigation, significant hardware improvements will be required for classically intractable variational chemistry simulations. View details
    Measurement-induced entanglement and teleportation on a noisy quantum processor
    Jesse Hoke
    Matteo Ippoliti
    Dmitry Abanin
    Rajeev Acharya
    Trond Andersen
    Markus Ansmann
    Frank Arute
    Kunal Arya
    Juan Atalaya
    Gina Bortoli
    Alexandre Bourassa
    Leon Brill
    Michael Broughton
    Bob Buckley
    Tim Burger
    Nicholas Bushnell
    Jimmy Chen
    Benjamin Chiaro
    Desmond Chik
    Josh Cogan
    Roberto Collins
    Paul Conner
    William Courtney
    Alex Crook
    Ben Curtin
    Alejo Grajales Dau
    Agustin Di Paolo
    ILYA Drozdov
    Andrew Dunsworth
    Daniel Eppens
    Edward Farhi
    Reza Fatemi
    Vinicius Ferreira
    Ebrahim Forati
    Brooks Foxen
    William Giang
    Dar Gilboa
    Raja Gosula
    Steve Habegger
    Michael Hamilton
    Monica Hansen
    Paula Heu
    Markus Hoffmann
    Trent Huang
    Ashley Huff
    Bill Huggins
    Sergei Isakov
    Justin Iveland
    Cody Jones
    Pavol Juhas
    Kostyantyn Kechedzhi
    Marika Kieferova
    Alexei Kitaev
    Andrey Klots
    Alexander Korotkov
    Fedor Kostritsa
    John Mark Kreikebaum
    Dave Landhuis
    Pavel Laptev
    Kim Ming Lau
    Lily Laws
    Joonho Lee
    Kenny Lee
    Yuri Lensky
    Alexander Lill
    Wayne Liu
    Orion Martin
    Amanda Mieszala
    Shirin Montazeri
    Alexis Morvan
    Ramis Movassagh
    Wojtek Mruczkiewicz
    Charles Neill
    Ani Nersisyan
    Michael Newman
    JiunHow Ng
    Murray Ich Nguyen
    Tom O'Brien
    Seun Omonije
    Alex Opremcak
    Andre Petukhov
    Rebecca Potter
    Leonid Pryadko
    Charles Rocque
    Negar Saei
    Kannan Sankaragomathi
    Henry Schurkus
    Christopher Schuster
    Mike Shearn
    Aaron Shorter
    Noah Shutty
    Vladimir Shvarts
    Jindra Skruzny
    Clarke Smith
    Rolando Somma
    George Sterling
    Doug Strain
    Marco Szalay
    Alfredo Torres
    Guifre Vidal
    Cheng Xing
    Jamie Yao
    Ping Yeh
    Juhwan Yoo
    Grayson Young
    Yaxing Zhang
    Ningfeng Zhu
    Jeremy Hilton
    Anthony Megrant
    Yu Chen
    Vadim Smelyanskiy
    Xiao Mi
    Vedika Khemani
    Nature, 622 (2023), 481–486
    Preview abstract Measurement has a special role in quantum theory: by collapsing the wavefunction, it can enable phenomena such as teleportation and thereby alter the ‘arrow of time’ that constrains unitary evolution. When integrated in many-body dynamics, measurements can lead to emergent patterns of quantum information in space–time that go beyond the established paradigms for characterizing phases, either in or out of equilibrium. For present-day noisy intermediate-scale quantum (NISQ) processors, the experimental realization of such physics can be problematic because of hardware limitations and the stochastic nature of quantum measurement. Here we address these experimental challenges and study measurement-induced quantum information phases on up to 70 superconducting qubits. By leveraging the interchangeability of space and time, we use a duality mapping to avoid mid-circuit measurement and access different manifestations of the underlying phases, from entanglement scaling to measurement-induced teleportation. We obtain finite-sized signatures of a phase transition with a decoding protocol that correlates the experimental measurement with classical simulation data. The phases display remarkably different sensitivity to noise, and we use this disparity to turn an inherent hardware limitation into a useful diagnostic. Our work demonstrates an approach to realizing measurement-induced physics at scales that are at the limits of current NISQ processors. View details
    Noise-resilient Majorana Edge Modes on a Chain of Superconducting Qubits
    Alejandro Grajales Dau
    Alex Crook
    Alex Opremcak
    Alexa Rubinov
    Alexander Korotkov
    Alexandre Bourassa
    Alexei Kitaev
    Alexis Morvan
    Andre Gregory Petukhov
    Andrew Dunsworth
    Andrey Klots
    Anthony Megrant
    Ashley Anne Huff
    Benjamin Chiaro
    Bernardo Meurer Costa
    Bob Benjamin Buckley
    Brooks Foxen
    Charles Neill
    Christopher Schuster
    Cody Jones
    Daniel Eppens
    Dar Gilboa
    Dave Landhuis
    Dmitry Abanin
    Doug Strain
    Ebrahim Forati
    Edward Farhi
    Emily Mount
    Fedor Kostritsa
    Frank Carlton Arute
    Guifre Vidal
    Igor Aleiner
    Jamie Yao
    Jeremy Patterson Hilton
    Joao Basso
    John Mark Kreikebaum
    Joonho Lee
    Juan Atalaya
    Juhwan Yoo
    Justin Thomas Iveland
    Kannan Aryaperumal Sankaragomathi
    Kenny Lee
    Kim Ming Lau
    Kostyantyn Kechedzhi
    Kunal Arya
    Lara Faoro
    Leon Brill
    Marco Szalay
    Markus Rudolf Hoffmann
    Masoud Mohseni
    Michael Blythe Broughton
    Michael Newman
    Michel Henri Devoret
    Mike Shearn
    Nicholas Bushnell
    Orion Martin
    Paul Conner
    Pavel Laptev
    Ping Yeh
    Rajeev Acharya
    Rebecca Potter
    Reza Fatemi
    Roberto Collins
    Sergei Isakov
    Shirin Montazeri
    Steve Habegger
    Thomas E O'Brien
    Trent Huang
    Trond Ikdahl Andersen
    Vadim Smelyanskiy
    Vladimir Shvarts
    Wayne Liu
    William Courtney
    William Giang
    William J. Huggins
    Wojtek Mruczkiewicz
    Xiao Mi
    Yaxing Zhang
    Yu Chen
    Yuan Su
    Zijun Chen
    Science (2022) (to appear)
    Preview abstract Inherent symmetry of a quantum system may protect its otherwise fragile states. Leveraging such protection requires testing its robustness against uncontrolled environmental interactions. Using 47 superconducting qubits, we implement the kicked Ising model which exhibits Majorana edge modes (MEMs) protected by a $\mathbb{Z}_2$-symmetry. Remarkably, we find that any multi-qubit Pauli operator overlapping with the MEMs exhibits a uniform decay rate comparable to single-qubit relaxation rates, irrespective of its size or composition. This finding allows us to accurately reconstruct the exponentially localized spatial profiles of the MEMs. Spectroscopic measurements further indicate exponentially suppressed hybridization between the MEMs over larger system sizes, which manifests as a strong resilience against low-frequency noise. Our work elucidates the noise sensitivity of symmetry-protected edge modes in a solid-state environment. View details
    Realizing topologically ordered states on a quantum processor
    Y.-J. Liu
    A. Smith
    C. Knapp
    M. Newman
    N. C. Jones
    Z. Chen
    X. Mi
    A. Dunsworth
    I. Aleiner
    F. Arute
    K. Arya
    J. Atalaya
    R. Barends
    J. Basso
    M. Broughton
    B. B. Buckley
    N. Bushnell
    B. Chiaro
    R. Collins
    W. Courtney
    A. R Derk
    D. Eppens
    L. Faoro
    E. Farhi
    B. Foxen
    A. Greene
    S. D. Harrington
    J. Hilton
    T. Huang
    W. J. Huggins
    S. V. Isakov
    K. Kechedzhi
    A. N. Korotkov
    F. Kostritsa
    D. Landhuis
    P. Laptev
    O. Martin
    M. Mohseni
    S. Montazeri
    W. Mruczkiewicz
    J. Mutus
    C. Neill
    T. E. O'Brien
    A. Opremcak
    B. Pato
    A. Petukhov
    V. Shvarts
    D. Strain
    M. Szalay
    Z. Yao
    P. Yeh
    J. Yoo
    A. Megrant
    Y. Chen
    V. Smelyanskiy
    A. Kitaev
    M. Knap
    F. Pollmann
    Science, 374 (2021), pp. 1237-1241
    Preview abstract The discovery of topological order has revolutionized the understanding of quantum matter in modern physics and provided the theoretical foundation for many quantum error correcting codes. Realizing topologically ordered states has proven to be extremely challenging in both condensed matter and synthetic quantum systems. Here, we prepare the ground state of the emblematic toric code Hamiltonian using an efficient quantum circuit on a superconducting quantum processor. We measure a topological entanglement entropy of Stopo ≈ −0.95 × ln 2 and simulate anyon interferometry to extract the braiding statistics of the emergent excitations. Furthermore, we investigate key aspects of the surface code, including logical state injection and the decay of the non-local order parameter. Our results illustrate the topological nature of these states and demonstrate their potential for implementing the surface code. View details
    What the foundations of quantum computer science teach us about chemistry
    Joonho Lee
    Thomas E O'Brien
    William J. Huggins
    Hsin-Yuan Huang
    Journal of Chemical Physics, 155 (2021), pp. 150901
    Preview abstract With the rapid development of quantum technology, one of the leading applications that has been identified is the simulation of chemistry. Interestingly, even before full scale quantum computers are available, quantum computer science has exhibited a remarkable string of results that directly impact what is possible in chemical simulation, even with a quantum computer. Some of these results even impact our understanding of chemistry in the real world. In this perspective, we take the position that direct chemical simulation is best understood as a digital experiment. While on one hand this clarifies the power of quantum computers to extend our reach, it also shows us the limitations of taking such an approach too directly. Leveraging results that quantum computers cannot outpace the physical world, we build to the controversial stance that some chemical problems are best viewed as problems for which no algorithm can deliver their solution in general, known in computer science as undecidable problems. This has implications for the predictive power of thermodynamic models and topics like the ergodic hypothesis. However, we argue that this perspective is not defeatist, but rather helps shed light on the success of existing chemical models like transition state theory, molecular orbital theory, and thermodynamics as models that benefit from data. We contextualize recent results showing that data-augmented models are more powerful rote simulation. These results help us appreciate the success of traditional chemical theory and anticipate new models learned from experimental data. Not only can quantum computers provide data for such models, but they can extend the class and power of models that utilize data in fundamental ways. These discussions culminate in speculation on new ways for quantum computing and chemistry to interact and our perspective on the eventual roles of quantum computers in the future of chemistry. View details
    Preview abstract One of the major application areas of interest for both near-term and fault-tolerant quantum computers is the optimization of classical objective functions. In this work, we develop intuitive constructions for a large class of these algorithms based on connections to simple dynamics of quantum systems, quantum walks, and classical continuous relaxations. We focus on developing a language and tools connected with kinetic energy on a graph for understanding the physical mechanisms of success and failure to guide algorithmic improvement. This physical language, in combination with uniqueness results related to unitarity, allow us to identify some potential pitfalls from kinetic energy fundamentally opposing the goal of optimization. This is connected to effects from wavefunction confinement, phase randomization, and shadow defects lurking in the objective far away from the ideal solution. As an example, we explore the surprising deficiency of many quantum methods in solving uncoupled spin problems and how this is both predictive of performance on some more complex systems while immediately suggesting simple resolutions. Further examination of canonical problems like the Hamming ramp or bush of implications show that entanglement can be strictly detrimental to performance results from the underlying mechanism of solution in approaches like QAOA. Kinetic energy and graph Laplacian perspectives provide new insights to common initialization and optimal solutions in QAOA as well as new methods for more effective layerwise training. Connections to classical methods of continuous extensions, homotopy methods, and iterated rounding suggest new directions for research in quantum optimization. Throughout, we unveil many pitfalls and mechanisms in quantum optimization using a physical perspective, which aim to spur the development of novel quantum optimization algorithms and refinements. View details
    Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
    Kevin Jeffery Sung
    Frank Carlton Arute
    Kunal Arya
    Juan Atalaya
    Rami Barends
    Michael Blythe Broughton
    Bob Benjamin Buckley
    Nicholas Bushnell
    Jimmy Chen
    Yu Chen
    Ben Chiaro
    Roberto Collins
    William Courtney
    Andrew Dunsworth
    Brooks Riley Foxen
    Rob Graff
    Steve Habegger
    Sergei Isakov
    Cody Jones
    Kostyantyn Kechedzhi
    Alexander Korotkov
    Fedor Kostritsa
    Dave Landhuis
    Pavel Laptev
    Martin Leib
    Mike Lindmark
    Orion Martin
    John Martinis
    Anthony Megrant
    Xiao Mi
    Masoud Mohseni
    Wojtek Mruczkiewicz
    Josh Mutus
    Charles Neill
    Florian Neukart
    Thomas E O'Brien
    Bryan O'Gorman
    A.G. Petukhov
    Harry Putterman
    Andrea Skolik
    Vadim Smelyanskiy
    Doug Strain
    Michael Streif
    Marco Szalay
    Amit Vainsencher
    Jamie Yao
    Leo Zhou
    Edward Farhi
    Nature Physics (2021)
    Preview 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. View details