Jump to Content
Ryan Babbush

Ryan Babbush

Ryan leads the Quantum Algorithm & Applications Team at Google. The mandate of this team is to develop new and more efficient quantum algorithms, research potential applications of quantum computing, build and open source tools for accelerating quantum algorithms research, and to execute experiments on existing quantum devices. Ryan's individual contributor research focuses on developing algorithms for fault-tolerant quantum computers, especially with applications in chemistry, physics, and machine learning.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Drug Design on Quantum Computers
    Raffaele Santagati
    Alán Aspuru-Guzik
    Matthias Degroote
    Leticia Gonzalez
    Elica Kyoseva
    Nikolaj Moll
    Markus Oppel
    Robert Parrish
    Michael Streif
    Christofer Tautermann
    Horst Weiss
    Nathan Wiebe
    Clemens Utschig-Utschig
    Nature Physics (2024)
    Preview abstract The promised industrial applications of quantum computers often rest on their anticipated ability to perform accurate, efficient quantum chemical calculations. Computational drug discovery relies on accurate predictions of how candidate drugs interact with their targets in a cellular environment involving several thousands of atoms at finite temperatures. Although quantum computers are still far from being used as daily tools in the pharmaceutical industry, here we explore the challenges and opportunities of applying quantum computers to drug design. We discuss where these could transform industrial research and identify the substantial further developments needed to reach this goal. View details
    Analyzing Prospects for Quantum Advantage in Topological Data Analysis
    Dominic W. Berry
    Yuan Su
    Casper Gyurik
    Robbie King
    Joao Basso
    Abhishek Rajput
    Nathan Wiebe
    Vedran Djunko
    PRX Quantum, vol. 5 (2024), pp. 010319
    Preview abstract Lloyd et al. were first to demonstrate the promise of quantum algorithms for computing Betti numbers in persistent homology (a way of characterizing topological features of data sets). Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that super-quadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for super-polynomial advantage. We then introduce and analyze specific problem examples for which super-polynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve some seemingly classically intractable instances. 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
    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, vol. 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
    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, vol. 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
    Preview abstract The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number κ and the allowable error ϵ [PRX Quantum 3, 0403003 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,500 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is over an order of magnitude more efficient than using a randomized approach from [arXiv:2305.11352] that claimed to be more efficient. 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
    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
    Fault-Tolerant Quantum Simulation of Materials Using Bloch Orbitals
    Dominic Berry
    Alec White
    Eugene DePrince III
    Sabrina Sicolo
    Michael Kuehn
    Michael Kaicher
    Joonho Lee
    PRX Quantum, vol. 4 (2023), pp. 040303
    Preview abstract The simulation of chemistry is among the most promising applications of quantum computing. However, most prior work exploring algorithms for block encoding, time evolving, and sampling in the eigenbasis of electronic structure Hamiltonians has either focused on modeling finite-sized systems, or has required a large number of plane-wave basis functions. In this work, we extend methods for quantum simulation with Bloch orbitals constructed from symmetry-adapted atom-centered orbitals so that one can model periodic ab initio Hamiltonians using only a modest number of basis functions. We focus on adapting existing algorithms based on combining qubitization with tensor factorizations of the Coulomb operator. Significant modifications of those algorithms are required to obtain an asymptotic speedup leveraging translational (or, more broadly, Abelian) symmetries. We implement block encodings using known tensor factorizations and a new Bloch orbital form of tensor hypercontraction. Finally, we estimate the resources required to deploy our algorithms to classically challenging model materials relevant to the chemistry of lithium nickel oxide battery cathodes within the surface code. We find that even with these improvements, the quantum runtime of these algorithms is on the order of thousands of days and further algorithmic improvements are required to make realistic quantum simulation of materials practical. View details
    Evaluating the Evidence for Exponential Quantum Advantage in Ground-State Quantum Chemistry
    Seunghoon Lee
    Joonho Lee
    Huanchen Zhai
    Yu Tong
    Alexander Dalzell
    Ashutosh Kumar
    Phillip Helms
    Johnnie Gray
    Zhi-Hao Cui
    Michael Kastoryano
    John Preskill
    David Reichman
    Earl Campbell
    Edward Valeev
    Lin Lin
    Garnet Chan
    Nature Communications, vol. 14 (2023)
    Preview abstract Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for ground-state quantum chemistry through polynomial speedups, it may be prudent to assume exponential speedups are not generically available for this problem. View details
    Quantum Simulation of Exact Electron Dynamics can be more Efficient than Classical Mean-Field Methods
    William J. Huggins
    Dominic W. Berry
    Shu Fay Ung
    Andrew Zhao
    David Reichman
    Andrew Baczewski
    Joonho Lee
    Nature Communications, vol. 14 (2023), pp. 4058
    Preview abstract Quantum algorithms for simulating electronic ground states are slower than popular classical mean-field algorithms such as Hartree-Fock and density functional theory, but offer higher accuracy. Accordingly, quantum computers have been predominantly regarded as competitors to only the most accurate and costly classical methods for treating electron correlation. However, here we tighten bounds showing that certain first quantized quantum algorithms enable exact time evolution of electronic systems with exponentially less space and polynomially fewer operations in basis set size than conventional real-time time-dependent Hartree-Fock and density functional theory. Although the need to sample observables in the quantum algorithm reduces the speedup, we show that one can estimate all elements of the k-particle reduced density matrix with a number of samples scaling only polylogarithmically in basis set size. We also introduce a more efficient quantum algorithm for first quantized mean-field state preparation that is likely cheaper than the cost of time evolution. We conclude that quantum speedup is most pronounced for finite temperature simulations and suggest several practically important electron dynamics problems with potential quantum advantage. View details
    Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
    Dominic Berry
    Ahmed Elnabawy
    Gabriele Ahlers
    Albert Eugene DePrince III
    Joonho Lee
    Christian Gogolin
    arXiv:2312.07654 (2023)
    Preview abstract This paper improves and demonstrates the usefulness of the first quantized plane-wave algorithms for the quantum simulation of electronic structure, developed by Babbush et al. and Su et al. We describe the first quantum algorithm for first quantized simulation that accurately includes pseudopotentials. We focus on the Goedecker-Tetter-Hutter (GTH) pseudopotential, which is among the most accurate and widely used norm-conserving pseudopotentials enabling the removal of core electrons from the simulation. The resultant screened nuclear potential regularizes cusps in the electronic wavefunction so that orders of magnitude fewer plane waves are required for a chemically accurate basis. Despite the complicated form of the GTH pseudopotential, we are able to block encode the associated operator without significantly increasing the overall cost of quantum simulation. This is surprising since simulating the nuclear potential is much simpler without pseudopotentials, yet is still the bottleneck. We also generalize prior methods to enable the simulation of materials with non-cubic unit cells, which requires nontrivial modifications. Finally, we combine these techniques to estimate the block-encoding costs for commercially relevant instances of heterogeneous catalysis (e.g. carbon monoxide adsorption on transition metals) and compare to the quantum resources needed to simulate materials in second quantization. We conclude that for computational cells with many particles, first quantization often requires meaningfully less spacetime volume. View details
    Preview abstract Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it - one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoCo or P450. View details
    Matchgate Shadows for Fermionic Quantum Simulation
    Kianna Wan
    Bill Huggins
    Joonho Lee
    Communications in Mathematical Physics (2023)
    Preview abstract "Classical shadows" are estimators of an unknown quantum state, constructed from suitably distributed random measurements on copies of that state [Nature Physics 16, 1050-1057]. Here, we analyze classical shadows obtained using random matchgate circuits, which correspond to fermionic Gaussian unitaries. We prove that the first three moments of the Haar distribution over the continuous group of matchgate circuits are equal to those of the discrete uniform distribution over only the matchgate circuits that are also Clifford unitaries; thus, the latter forms a "matchgate 3-design." This implies that the classical shadows resulting from the two ensembles are functionally equivalent. We show how one can use these matchgate shadows to efficiently estimate inner products between an arbitrary quantum state and fermionic Gaussian states, as well as the expectation values of local fermionic operators and various other quantities, thus surpassing the capabilities of prior work. As a concrete application, this enables us to apply wavefunction constraints that control the fermion sign problem in the quantum-classical auxiliary-field quantum Monte Carlo algorithm (QC-AFQMC) [Nature 603, 416-420], without the exponential post-processing cost incurred by the original approach. View details
    Quantum Error Mitigation
    Zhenyu Cai
    Simon Benjamin
    Suguru Endo
    William J. Huggins
    Ying Li
    Thomas E O'Brien
    Reviews of Modern Physics, vol. 95 (2023), pp. 045005
    Preview abstract For quantum computers to successfully solve real-world problems, it is necessary to tackle the challenge of noise: the errors that occur in elementary physical components due to unwanted or imperfect interactions. The theory of quantum fault tolerance can provide an answer in the long term, but in the coming era of noisy intermediate-scale quantum machines one must seek to mitigate errors rather than completely eliminate them. This review surveys the diverse methods that have been proposed for quantum error mitigation, assesses their in-principle efficacy, and describes the hardware demonstrations achieved to date. Commonalities and limitations among the methods are identified, while mention is made of how mitigation methods can be chosen according to the primary type of noise present, including algorithmic errors. Open problems in the field are identified, and the prospects for realizing mitigation-based devices that can deliver a quantum advantage with an impact on science and business are discussed. View details
    Exponential Quantum Speedup in Simulating Coupled Classical Oscillators
    Dominic Berry
    Rolando Somma
    Nathan Wiebe
    Physical Review X, vol. 13 (2023), pp. 041041
    Preview abstract We present a quantum algorithm for simulating the classical dynamics of 2^n coupled oscillators (e.g., 2^n masses coupled by springs). Our approach leverages a mapping between the Schrodinger equation and Newton's equations for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time, for a specification of the problem that we prove is \BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2^n modes. 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
    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, vol. 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
    Efficient Quantum Computation of Molecular Forces and Other Energy Gradients
    Thomas E O'Brien
    Michael Streif
    Raffaele Santagati
    Yuan Su
    William J. Huggins
    Joshua Goings
    Nikolaj Moll
    Elica Kyoseva
    Matthias Degroote
    Christofer Tautermann
    Joonho Lee
    Dominic Berry
    Nathan Wiebe
    Physical Review Research, vol. 4 (2022), pp. 043210
    Preview abstract While most work on the quantum simulation of chemistry has focused on computing energy surfaces, a similarly important application requiring subtly different algorithms is the computation of energy derivatives. Almost all molecular properties can be expressed an energy derivative, including molecular forces, which are essential for applications such as molecular dynamics simulations. Here, we introduce new quantum algorithms for computing molecular energy derivatives with significantly lower complexity than prior methods. Under cost models appropriate for noisy-intermediate scale quantum devices we demonstrate how low rank factorizations and other tomography schemes can be optimized for energy derivative calculations. We perform numerics revealing that our techniques reduce the number of circuit repetitions required by many orders of magnitude for even modest systems. In the context of fault-tolerant algorithms, we develop new methods of estimating energy derivatives with Heisenberg limited scaling incorporating state-of-the-art techniques for block encoding fermionic operators. Our results suggest that the calculation of forces on a single nuclei may be of similar cost to estimating energies of chemical systems, but that further developments are needed for quantum computers to meaningfully assist with molecular dynamics simulations. View details
    Preview abstract We propose a quantum algorithm for inferring the molecular nuclear spin Hamiltonian from time-resolved measurements of spin-spin correlators, which can be obtained via nuclear magnetic resonance (NMR). We focus on learning the anisotropic dipolar term of the Hamiltonian, which generates dynamics that are challenging to classically simulate in some contexts. We demonstrate the ability to directly estimate the Jacobian and Hessian of the corresponding learning problem on a quantum computer, allowing us to learn the Hamiltonian parameters. We develop algorithms for performing this computation on both noisy near-term and future fault-tolerant quantum computers. We argue that the former is promising as an early beyond-classical quantum application since it only requires evolution of a local spin Hamiltonian. We investigate the example of a protein (ubiquitin) confined on a membrane as a benchmark of our method. We isolate small spin clusters, demonstrate the convergence of our learning algorithm on one such example, and then investigate the learnability of these clusters as we cross the ergodic to nonergodic phase transition by suppressing the dipolar interaction. We see a clear correspondence between a drop in the multifractal dimension measured across many-body eigenstates of these clusters, and a transition in the structure of the Hessian of the learning cost function (from degenerate to learnable). Our hope is that such quantum computations might enable the interpretation and development of new NMR techniques for analyzing molecular structure. View details
    Preview abstract The most efficient known quantum circuits for preparing unitary coupled cluster states and applying Trotter steps of the arbitrary basis electronic structure Hamiltonian involve interleaved sequences of fermionic Gaussian circuits and Ising interaction type circuits. These circuits arise from factorizing the two-body operators generating those unitaries as a sum of squared one-body operators that are simulated using product formulas. We introduce a numerical algorithm for performing this factorization that has an iteration complexity no worse than single particle basis transformations of the two-body operators and often results in many times fewer squared one-body operators in the sum of squares compared to the analytical decompositions. As an application of this numerical procedure, we demonstrate that our protocol can be used to approximate generic unitary coupled cluster operators and prepare the necessary high-quality initial states for techniques (like ADAPT-VQE) that iteratively construct approximations to the ground state. View details
    Simulating Challenging Correlated Molecules and Materials on the Sycamore Quantum Processor
    Ruslan Tazhigulov
    Shi-Ning Sun
    Reza Haghshenas
    Huanchen Zhai
    Adrian Tan
    Austin Minnich
    Garnet Kin-Lic Chan
    PRX Quantum, vol. 3 (2022), pp. 040318
    Preview abstract Simulating complex molecules and materials is an anticipated application of quantum devices. With strong quantum advantage demonstrated in artificial tasks, we examine how such advantage translates into modeling physical problems, and in particular, strongly correlated electronic structure. We simulate static and dynamical electronic structure on a superconducting quantum processor derived from Google’s Sycamore architecture for two representative correlated electron problems: the nitrogenase iron-sulfur molecular clusters, and α-ruthenium trichloride, a proximate spin-liquid material. To do so, we simplify the electronic structure into low-energy spin models that fit on the device. With extensive error mitigation and assistance from classically simulated data, we achieve quantitatively meaningful results deploying about 1/5 of the gate resources used in artificial quantum advantage experiments on a similar architecture. This increases to over 1/2 of the gate resources when choosing a model that suits the hardware. Our work serves to convert artificial measures of quantum advantage into a physically relevant setting. View details
    Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
    William J. Huggins
    Kianna Wan
    Thomas E O'Brien
    Nathan Wiebe
    Physical Review Letters, vol. 129 (2022), pp. 240501
    Preview abstract Many quantum algorithms involve the evaluation of expectation values. Optimal strategies for estimating a single expectation value are known, requiring a number of iterations that scales with the target error $\epsilon$ as $\mathcal{O}(\epsilon^{-1})$. In this paper we address the task of estimating the expectation values of \(M\) different observables, each to within an error \(\epsilon\), with the same \(\epsilon^{-1}\) dependence. We describe an approach that leverages Gily\'{e}n \emph{et al.}'s~quantum gradient estimation algorithm to achieve $\mathcal{O}\sqrt{M}\epsilon^{-1})$ scaling up to logarithmic factors, regardless of the commutation properties of the $M$ observables. We prove that this scaling is optimal in the worst case, even when the operators are mutually commuting. We highlight the flexibility of our approach by presenting several generalizations, including a strategy for accelerating the estimation of a collection of dynamic correlation functions. View details
    Optimal Scaling Quantum Linear Systems Solver via Discrete Adiabatic Theorem
    Pedro C. S. Costa
    Dong An
    Yuval Sanders
    Yuan Su
    Dominic W. Berry
    PRX Quantum, vol. 3 (2022), pp. 040303
    Preview abstract Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number $\kappa$ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of $\log(\kappa)$. Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in $\kappa$, matching a known lower bound on the complexity. Our $\mathcal{O}(\kappa\log(1/\epsilon))$ complexity is also optimal in terms of the combined scaling in $\kappa$ and the precision $\epsilon$. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications. View details
    Preview abstract An accurate assessment of how quantum computers can be used for chemical simulation, especially their potential computational advantages, provides important context on how to deploy these future devices. To perform this assessment reliably, quantum resource estimates must be coupled with classical computations attempting to answer relevant chemical questions and to define the classical algorithms simulation frontier. Herein, we explore the quantum computation and classical computation resources required to assess the electronic structure of cytochrome P450 enzymes (CYPs) and thus define a classical–quantum advantage boundary. This is accomplished by analyzing the convergence of density matrix renormalization group plus n-electron valence state perturbation theory (DMRG+NEVPT2) and coupled-cluster singles doubles with noniterative triples [CCSD(T)] calculations for spin gaps in models of the CYP catalytic cycle that indicate multireference character. The quantum resources required to perform phase estimation using qubitized quantum walks are calculated for the same systems. Compilation into the surface code provides runtime estimates to compare directly to DMRG runtimes and to evaluate potential quantum advantage. Both classical and quantum resource estimates suggest that simulation of CYP models at scales large enough to balance dynamic and multiconfigurational electron correlation has the potential to be a quantum advantage problem and emphasizes the important interplay between classical computations and quantum algorithms development for chemical simulation. 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
    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
    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
    Power of data in quantum machine learning
    Hsin-Yuan (Robert) Huang
    Michael Blythe Broughton
    Masoud Mohseni
    Nature Communications, vol. 12 (2021), pp. 2631
    Preview abstract The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime. For near-term implementations, we demonstrate a significant prediction advantage over some classical models on engineered data sets designed to demonstrate a maximal quantum advantage in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits. 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
    Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
    Yuan Su
    Dominic W. Berry
    Nathan Wiebe
    PRX Quantum, vol. 2 (2021), pp. 040332
    Preview abstract Quantum simulations of chemistry in first quantization offer important advantages over approaches in second quantization including faster convergence to the continuum limit and the opportunity for practical simulations outside the Born-Oppenheimer approximation. However, as all prior work on quantum simulation in first quantization has been limited to asymptotic analysis, it has been impossible to compare the resources required for these approaches to those for more commonly studied algorithms in second quantization. Here, we analyze and optimize the resources required to implement two first quantized quantum algorithms for chemistry from Babbush et al that realize block encodings for the qubitization and interaction picture frameworks of Low et al. The two algorithms we study enable simulation with gate complexities O(η^{8/3} N^{1/3} t+η^{4/3} N^{2/3} t) and O(η^{8/3} N^{1/3} t) where η is the number of electrons, N is the number of plane wave basis functions, and t is the duration of time-evolution (t is inverse to target precision when the goal is to estimate energies). In addition to providing the first explicit circuits and constant factors for any first quantized simulation and introducing improvements which reduce circuit complexity by about a thousandfold over naive implementations for modest sized systems, we also describe new algorithms that asymptotically achieve the same scaling in a real space representation. We assess the resources required to simulate various molecules and materials and conclude that the qubitized algorithm will often be more practical than the interaction picture algorithm. We demonstrate that our qubitized algorithm often requires much less surface code spacetime volume for simulating millions of plane waves than the best second quantized algorithms require for simulating hundreds of Gaussian orbitals. 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, vol. 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
    Variational Quantum Algorithms
    Marco Cerezo
    Andrew Arrasmith
    Simon Benjamin
    Suguro Endo
    Keisuke Fujii
    Kosuke Mitarai
    Xiao Yuan
    Lukasz Cincio
    Patrick Coles
    Nature Reviews Physics (2021)
    Preview abstract Applications such as simulating large quantum systems or solving large-scale linear algebra problems are immensely challenging for classical computers due their extremely high computational cost. Quantum computers promise to unlock these applications, although fault-tolerant quantum computers will likely not be available for several years. Currently available quantum devices have serious constraints, including limited qubit numbers and noise processes that limit circuit depth. Variational Quantum Algorithms (VQAs), which employ a classical optimizer to train a parametrized quantum circuit, have emerged as a leading strategy to address these constraints. VQAs have now been proposed for essentially all applications that researchers have envisioned for quantum computers, and they appear to the best hope for obtaining quantum advantage. Nevertheless, challenges remain including the trainability, accuracy, and efficiency of VQAs. In this review article we present an overview of the field of VQAs. Furthermore, we discuss strategies to overcome their challenges as well as the exciting prospects for using them as a means to obtain quantum advantage. View details
    Quantum advantage in learning from experiments
    Hsin-Yuan (Robert) Huang
    Michael Blythe Broughton
    Jordan Cotler
    Sitan Chen
    Jerry Li
    Masoud Mohseni
    Richard Kueng
    John Preskill
    Science, vol. 376 (2021), pp. 1182 - 1186
    Preview abstract Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. An experimental setup that transduces data from a physical system to a stable quantum memory, and processes that data using a quantum computer, could have significant advantages over conventional experiments in which the physical system is measured and the outcomes are processed using a classical computer. We prove that, in various tasks, quantum machines can learn from exponentially fewer experiments than those required in conventional experiments. The exponential advantage holds in predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics. In some tasks, the quantum processing needed to achieve the exponential advantage can be modest; for example, one can simultaneously learn about many noncommuting observables by processing only two copies of the system. Conducting experiments with up to 40 superconducting qubits and 1300 quantum gates, we demonstrate that a substantial quantum advantage can be realized using today's relatively noisy quantum processors. Our results highlight how quantum technology can enable powerful new strategies to learn about nature. View details
    Preview abstract In this perspective we discuss conditions under which it would be possible for a modest fault-tolerant quantum computer to realize a runtime advantage by executing a quantum algorithm with only a small polynomial speedup over the best classical alternative. The challenge is that the computation must finish within a reasonable amount of time while being difficult enough that the small quantum scaling advantage would compensate for the large constant factor overheads associated with error correction. We compute several examples of such runtimes using state-of-the-art surface code constructions under a variety of assumptions. We conclude that quadratic speedups will not enable quantum advantage on early generations of such fault-tolerant devices unless there is a significant improvement in how we realize quantum error correction. While this conclusion persists even if we were to increase the rate of logical gates in the surface code by more than an order of magnitude, we also repeat this analysis for speedups by other polynomial degrees and find that quartic speedups look significantly more practical. 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, vol. 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
    Low Rank Representations for Quantum Simulations of Electronic Structure
    Mario Motta
    Erika Ye
    Zhendong Li
    Austin Minnich
    Garnet Kin-Lic Chan
    NPJ Quantum Information, vol. 7 (2021)
    Preview abstract The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for N molecular orbitals, the O(N^4) gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy, we are able to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with O(N^3) gate complexity in small simulations, which reduces to O(N^2 log N) gate complexity in the asymptotic regime, while our unitary Coupled Cluster Trotter step has O(N^3) gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have O(N^2) depth on a linearly connected array, an improvement over the O(N^3) scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4,000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 100,000 non-Clifford rotations. We also apply our algorithm to iron-sulfur clusters relevant for elucidating the mode of action of metalloenzymes. View details
    Tuning Quantum Information Scrambling on a 53-Qubit Processor
    Alan Derk
    Alan Ho
    Alex Opremcak
    Alexander Korotkov
    Alexandre Bourassa
    Andre Gregory Petukhov
    Andrew Dunsworth
    Anthony Megrant
    Bálint Pató
    Benjamin Chiaro
    Brooks Riley Foxen
    Charles Neill
    Cody Jones
    Daniel Eppens
    Dave Landhuis
    Doug Strain
    Edward Farhi
    Eric Ostby
    Fedor Kostritsa
    Frank Carlton Arute
    Igor Aleiner
    Jamie Yao
    Jeffrey Marshall
    Jeremy Patterson Hilton
    Jimmy Chen
    Josh Mutus
    Juan Atalaya
    Kostyantyn Kechedzhi
    Kunal Arya
    Marco Szalay
    Masoud Mohseni
    Matt Trevithick
    Michael Blythe Broughton
    Michael Newman
    Nicholas Bushnell
    Nicholas Redd
    Orion Martin
    Pavel Laptev
    Ping Yeh
    Rami Barends
    Roberto Collins
    Salvatore Mandra
    Sean Harrington
    Sergei Isakov
    Thomas E O'Brien
    Trent Huang
    Trevor Mccourt
    Vadim Smelyanskiy
    Vladimir Shvarts
    William Courtney
    Wojtek Mruczkiewicz
    Xiao Mi
    Yu Chen
    arXiv (2021)
    Preview abstract As entanglement in a quantum system grows, initially localized quantum information is spread into the exponentially many degrees of freedom of the entire system. This process, known as quantum scrambling, is computationally intensive to study classically and lies at the heart of several modern physics conundrums. Here, we characterize scrambling of different quantum circuits on a 53-qubit programmable quantum processor by measuring their out-of-time-order correlators (OTOCs). We observe that the spatiotemporal spread of OTOCs, as well as their circuit-to-circuit fluctuation, unravel in detail the time-scale and extent of quantum scrambling. Comparison with numerical results indicates a high OTOC measurement accuracy despite the large size of the quantum system. Our work establishes OTOC as an experimental tool to diagnose quantum scrambling at the threshold of being classically inaccessible. View details
    Error Mitigation via Verified Phase Estimation
    Thomas E O'Brien
    Stefano Polla
    Bill Huggins
    Sam Connor McArdle
    PRX Quantum, vol. 2 (2021)
    Preview abstract We present a novel error mitigation technique for quantum phase estimation. By post-selecting the system register to be in the starting state, we convert all single errors prior to final measurement to a time-dependent decay (up to on average exponentially small corrections), which may be accurately corrected for at the cost of additional measurement. This error migitation can be built into phase estimation techniques that do not require control qubits. By separating the observable of interest into a linear combination of fast-forwardable Hamiltonians and measuring those components individually, we can convert this decay into a constant offset. Using this technique, we demonstrate the estimation of expectation values on numerical simulations of moderately-sized quantum circuits with multiple orders of magnitude improvement over unmitigated estimation at near-term error rates. We further combine verified phase estimation with the optimization step in a variational algorithm to provide additional mitigation of control error. In many cases, our results demonstrate a clear signature that the verification technique can mitigate against any single error occurring in an instance of a quantum computation: the error $\epsilon$ in the expectation value estimation scales with $p^2$, where $p$ is the probability of an error occurring at any point in the circuit. Further numerics indicate that our scheme remains robust in the presence of sampling noise, though different classical post-processing methods may lead to up to an order of magnitude error increase in the final energy estimates. View details
    The Fermionic Quantum Emulator
    Klaas Gunst
    Alec White
    Leon Freitag
    Kyle Throssell
    Garnet Kin-Lic Chan
    Toru Shiozaki
    Quantum, vol. 5 (2021), pp. 568
    Preview abstract The fermionic quantum emulator (FQE) is a collection of protocols for emulating quantum dynamics of fermions efficiently taking advantage of common symmetries present in chemical, materials, and condensed-matter systems. The library is fully integrated with the OpenFermion software package and serves as the simulation backend. The FQE reduces memory footprint by exploiting number and spin symmetry along with custom evolution routines for sparse and dense Hamiltonians, allowing us to study significantly larger quantum circuits at modest computational cost when compared against qubit state vector simulators. This release paper outlines the technical details of the simulation methods and key advantages. View details
    Virtual Distillation for Quantum Error Mitigation
    William J. Huggins
    Sam Connor McArdle
    Thomas E O'Brien
    Joonho Lee
    Birgitta Whaley
    Physical Review X, vol. 11 (2021), pp. 041036
    Preview abstract Contemporary quantum computers have relatively high levels of noise, making it difficult to use them to perform useful calculations, even with a large number of qubits. Quantum error correction is expected to eventually enable fault-tolerant quantum computation at large scales, but until then it will be necessary to use alternative strategies to mitigate the impact of errors. We propose a near-term friendly strategy to mitigate errors by entangling and measuring \(M\) copies of a noisy state \(\rho\). This enables us to estimate expectation values with respect to a state with dramatically reduced error, \(\rho^M/ \tr(\rho^M)\), without explicitly preparing it, hence the name ``virtual distillation''. As \(M\) increases, this state approaches the closest pure state to \(\rho\), exponentially quickly. We analyze the effectiveness of virtual distillation and find that it is governed in many regimes by the behaviour of this pure state (corresponding to the dominant eigenvector of \(\rho\)). We numerically demonstrate that virtual distillation is capable of suppressing errors by multiple orders of magnitude and explain how this effect is enhanced as the system size grows. Finally, we show that this technique can improve the convergence of randomized quantum algorithms, even in the absence of device noise. View details
    Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer
    William J. Huggins
    Bryan O'Gorman
    David Reichman
    Joonho Lee
    Nature (2021)
    Preview abstract Interacting many-electron problems pose some of the greatest computational challenges in science, with essential applications across many fields. The solutions to these problems will offer accurate predictions of chemical reactivity and kinetics, and other properties of quantum systems. Fermionic quantum Monte Carlo (QMC) methods which use a statistical sampling of the ground state, are among the most powerful approaches to these problems. Controlling the fermionic sign problem with constraints ensures the efficiency of QMC at the expense of potentially significant biases owing to the limited flexibility of classical computation. Here we propose an approach that combines constrained QMC with quantum computation to reduce such biases. We implement our scheme experimentally using up to 16 qubits to unbias constrained QMC calculations performed on chemical systems with as many as 120 orbitals. These experiments represent the largest chemistry simulations performed with the help of quantum computers, while achieving accuracy that is competitive with state-of-the-art classical methods without burdensome error mitigation. Compared with the popular variational quantum eigensolver our hybrid quantum-classical computational model offers an alternative path towards achieving a practical quantum advantage for the electronic structure problem without demanding exceedingly accurate preparation and measurement of the ground-state wavefunction. View details
    Exponential suppression of bit or phase flip errors with repetitive quantum error correction
    Alan Derk
    Alan Ho
    Alex Opremcak
    Alexander Korotkov
    Alexandre Bourassa
    Andre Gregory Petukhov
    Andrew Dunsworth
    Anthony Megrant
    Bálint Pató
    Benjamin Chiaro
    Brooks Riley Foxen
    Charles Neill
    Cody Jones
    Daniel Eppens
    Dave Landhuis
    Doug Strain
    Edward Farhi
    Eric Ostby
    Fedor Kostritsa
    Frank Carlton Arute
    Igor Aleiner
    Jamie Yao
    Jeremy Patterson Hilton
    Jimmy Chen
    Josh Mutus
    Juan Atalaya
    Kostyantyn Kechedzhi
    Kunal Arya
    Marco Szalay
    Masoud Mohseni
    Matt Trevithick
    Michael Broughton
    Michael Newman
    Nicholas Bushnell
    Nicholas Redd
    Orion Martin
    Pavel Laptev
    Ping Yeh
    Rami Barends
    Roberto Collins
    Sean Harrington
    Sergei Isakov
    Thomas E O'Brien
    Trent Huang
    Trevor Mccourt
    Vadim Smelyanskiy
    Vladimir Shvarts
    William Courtney
    Wojtek Mruczkiewicz
    Xiao Mi
    Yu Chen
    Nature (2021)
    Preview abstract Realizing the potential of quantum computing will require achieving sufficiently low logical error rates. Many applications call for error rates below 10^-15, but state-of-the-art quantum platforms typically have physical error rates near 10^-3. Quantum error correction (QEC) promises to bridge this divide by distributing quantum logical information across many physical qubits so that errors can be corrected. Logical errors are then exponentially suppressed as the number of physical qubits grows, provided that the physical error rates are below a certain threshold. QEC also requires that the errors are local, and that performance is maintained over many rounds of error correction, a major outstanding experimental challenge. Here, we implement 1D repetition codes embedded in a 2D grid of superconducting qubits which demonstrate exponential suppression of bit or phase-flip errors, reducing logical error per round by more than 100x when increasing the number of qubits from 5 to 21. Crucially, this error suppression is stable over 50 rounds of error correction. We also introduce a method for analyzing error correlations with high precision, and characterize the locality of errors in a device performing QEC for the first time. Finally, we perform error detection using a small 2D surface code logical qubit on the same device, and show that the results from both 1D and 2D codes agree with numerical simulations using a simple depolarizing error model. These findings demonstrate that superconducting qubits are on a viable path towards fault tolerant quantum computing. View details
    Preview abstract Variational algorithms are a promising paradigm for utilizing near-term quantum devices for modeling electronic states of molecular systems. However, previous bounds on the measurement time required have suggested that the application of these techniques to larger molecules might be infeasible. We present a measurement strategy based on a low-rank factorization of the two-electron integral tensor. Our approach provides a cubic reduction in term groupings over prior state-of-the-art and enables measurement times three orders of magnitude smaller than those suggested by commonly referenced bounds for the largest systems we consider. Although our technique requires execution of a linear-depth circuit prior to measurement, this is compensated for by eliminating challenges associated with sampling nonlocal Jordan–Wigner transformed operators in the presence of measurement error, while enabling a powerful form of error mitigation based on efficient postselection. We numerically characterize these benefits with noisy quantum circuit simulations for ground-state energies of strongly correlated electronic systems. View details
    Preview abstract We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. With ${\cal O}(\lambda / \epsilon)$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $\lambda$ is the 1-norm of Hamiltonian coefficients and $\epsilon$ is the target precision. This is the lowest complexity that has been shown for quantum computations of chemistry within an arbitrary basis. Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis). Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a non-orthogonal basis defined by the THC factors. We then use qubitization to simulate the non-orthogonal THC Hamiltonian, in a fashion that avoids most complications of the non-orthogonal basis. We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work. In addition to having lower asymptotic scaling spacetime volume, compilation of our algorithm for challenging finite-sized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach. By laying out and optimizing the surface code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, assuming $1 \, \mu {\rm s}$ cycle times and physical gate error rates no worse than $0.1\%$. View details
    Preview abstract Recent work has deployed linear combinations of unitaries techniques to significantly reduce the cost of performing fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve over those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to compute relative precision quantities (e.g. energy per unit cell), as is often the goal for condensed-phase (e.g. solid-state) systems. In this context, simulations of the Hubbard model and plane wave electronic structure models with $N < 10^5$ fermionic modes can be performed with roughly O(1) and O(N^2) T complexities. We also perform numerics that reveal tradeoffs between the error of a Trotter step and Trotter step gate complexity across various implementations; e.g., we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates using lattice surgery and assuming error rates of one part in a thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with only a few hundred thousand physical qubits. View details
    Preview abstract Proposals for near-term experiments in quantum chemistry on quantum computers leverage the ability to target a subset of degrees of freedom containing the essential quantum behavior, sometimes called the active space. This approximation allows one to treat more difficult problems using fewer qubits and lower gate depths than would otherwise be possible. However, while this approximation captures many important qualitative features, it may leave the results wanting in terms of absolute accuracy (basis error) of the representation. In traditional approaches, increasing this accuracy requires increasing the number of qubits and an appropriate increase in circuit depth as well. Here we introduce a technique requiring no additional qubits or circuit depth that is able to remove much of this approximation in favor of additional measurements. The technique is constructed and analyzed theoretically, and some numerical proof of concept calculations are shown. As an example, we show how to achieve the accuracy of a 20 qubit representation using only 4 qubits and a modest number of additional measurements for a simple hydrogen molecule. We close with an outlook on the impact this technique may have on both near-term and fault-tolerant quantum simulations. View details
    Preview abstract Variational quantum algorithms are a leading candidate for early applications on noisy intermediate-scale quantum computers. These algorithms depend on a classical optimization outer-loop that minimizes some function of a parameterized quantum circuit. In practice, finite sampling error and gate errors make this a stochastic optimization with unique challenges that must be addressed at the level of the optimizer. The sharp trade-off between precision and sampling time in conjunction with experimental constraints necessitates the development of new optimization strategies to minimize overall wall clock time in this setting. We introduce an optimization method and numerically compare its performance with common methods in use today. The method is a simple surrogate model-based algorithm designed to improve reuse of collected data. It does so by estimating the gradient using a least-squares quadratic fit of sampled function values within a moving trusted region. To make fair comparisons between optimization methods, we develop experimentally relevant cost models designed to balance efficiency in testing and accuracy with respect to cloud quantum computing systems. The results here underscore the need to both use relevant cost models and optimize hyperparameters of existing optimization methods for competitive performance. We compare tuned methods using cost models presented by superconducting devices accessed through cloud computing platforms. The method introduced here has several practical advantages in realistic experimental settings, and has been used successfully in a separately published experiment on Google's Sycamore device. View details
    Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
    Yuval Sanders
    Dominic W. Berry
    Pedro C. S. Costa
    Louis W. Tessler
    Nathan Wiebe
    PRX Quantum, vol. 1 (2020), pp. 020312
    Preview abstract Here we explore which heuristic quantum algorithms for combinatorial optimization might be most practical to try out on a small fault-tolerant quantum computer. We compile circuits for several variants of quantum-accelerated simulated annealing including those using qubitization or Szegedy walks to quantize classical Markov chains and those simulating spectral-gap-amplified Hamiltonians encoding a Gibbs state. We also optimize fault-tolerant realizations of the adiabatic algorithm, quantum-enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. Many of these methods are bottlenecked by calls to the same subroutines; thus, optimized circuits for those primitives should be of interest regardless of which heuristic is most effective in practice. We compile these bottlenecks for several families of optimization problems and report for how long and for what size systems one can perform these heuristics in the surface code given a range of resource budgets. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup achieves an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions (e.g., that the quantum algorithm requires exactly quadratically fewer steps), our analysis suggests that quantum-accelerated simulated annealing requires roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about 4 CPU-minutes. View details
    Preview abstract With the rapid developments in quantum hardware comes a push towards the first practical applications on these devices. While fully fault-tolerant quantum computers may still be years away, one may ask if there exist intermediate forms of error correction or mitigation that might enable practical applications before then. In this work, we consider the idea of post-processing error decoders using existing quantum codes, which are capable of mitigating errors on encoded logical qubits using classical post-processing with no complicated syndrome measurements or additional qubits beyond those used for the logical qubits. This greatly simplifies the experimental exploration of quantum codes on near-term devices, removing the need for locality of syndromes or fast feed-forward, allowing one to study performance aspects of codes on real devices. We provide a general construction equipped with a simple stochastic sampling scheme that does not depend explicitly on a number of terms that we extend to approximate projectors within a subspace. This theory then allows one to generalize to the correction of some logical errors in the code space, correction of some physical unencoded Hamiltonians without engineered symmetries, and corrections derived from approximate symmetries. In this work, we develop the theory of the method and demonstrate it on a simple example with the perfect [[5,1,3]] code, which exhibits a pseudo-threshold of p≈0.50 under a single qubit depolarizing channel applied to all qubits. We also provide a demonstration under the application of a logical operation and performance on an unencoded hydrogen molecule, which exhibits a significant improvement over the entire range of possible errors incurred under a depolarizing channel. View details
    Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
    Xavier Bonet
    Thomas O'Brien
    Physical Review X, vol. 10 (2020), pp. 031064
    Preview abstract Many applications of quantum simulation require to prepare and then characterize quantum states by performing an efficient partial tomography to estimate observables corresponding to k-body reduced density matrices (k-RDMs). For instance, variational algorithms for the quantum simulation of chemistry usually require that one measure the fermionic 2-RDM. While such marginals provide a tractable description of quantum states from which many important properties can be computed, their determination often requires a prohibitively large number of circuit repetitions. Here we describe a method by which all elements of k-RDMs acting on N qubits can be sampled with a number of circuits scaling as O(3^k log^{k-1} N), an exponential improvement in N over prior art. Next, we show that if one is able to implement a linear depth circuit on a linear array prior to measurement, then one can sample all elements of the fermionic 2-RDM using only O(N^2) circuits. We prove that this result is asymptotically optimal. Finally, we demonstrate that one can estimate the expectation value of any linear combination of fermionic 2-RDM elements using O(N^4 / w) circuits, each with only O(w) gates on a linear array where w < N is a free parameter. We expect these results will improve the viability of many proposals for near-term quantum simulation. View details
    Discontinuous Galerkin Discretization for Quantum Simulation of Chemistry
    Fabian M. Faulstich
    Qinyi Zhu
    Bryan O'Gorman
    Yiheng Qiu
    Steven White
    Lin Lin
    New Journal of Physics, vol. 22 (2020)
    Preview abstract Methods for electronic structure based on Gaussian and molecular orbital discretizations offer a well established, compact representation that forms much of the foundation of correlated quantum chemistry calculations on both classical and quantum computers. Despite their ability to describe essential physics with relatively few basis functions, these representations can suffer from a quartic growth of the number of integrals. Recent results have shown that, for some quantum and classical algorithms, moving to representations with diagonal two-body operators can result in dramatically lower asymptotic costs, even if the number of functions required increases significantly. We introduce a way to interpolate between the two regimes in a systematic and controllable manner, such that the number of functions is minimized while maintaining a block diagonal structure of the two-body operator and desirable properties of an original, primitive basis. Techniques are analyzed for leveraging the structure of this new representation on quantum computers. Empirical results for hydrogen chains suggest a scaling improvement from O(N^4.5) in molecular orbital representations to O(N^2.6) in our representation for quantum evolution in a fault-tolerant setting, and exhibit a constant factor crossover at 15 to 20 atoms. Moreover, we test these methods using modern density matrix renormalization group methods classically, and achieve excellent accuracy with respect to the complete basis set limit with a speedup of 1-2 orders of magnitude with respect to using the primitive or Gaussian basis sets alone. These results suggest our representation provides significant cost reductions while maintaining accuracy relative to molecular orbital or strictly diagonal approaches for modest-sized systems in both classical and quantum computation for correlated systems. View details
    Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
    Brooks Riley Foxen
    Charles Neill
    Andrew Dunsworth
    Ben Chiaro
    Anthony Megrant
    Jimmy Chen
    Rami Barends
    Frank Carlton Arute
    Kunal Arya
    Yu Chen
    Roberto Collins
    Edward Farhi
    Rob Graff
    Trent Huang
    Sergei Isakov
    Kostyantyn Kechedzhi
    Alexander Korotkov
    Fedor Kostritsa
    Dave Landhuis
    Xiao Mi
    Masoud Mohseni
    Josh Mutus
    Vadim Smelyanskiy
    Amit Vainsencher
    Jamie Yao
    John Martinis
    arXiv:2001.08343 (2020)
    Preview abstract Quantum algorithms offer a dramatic speedup for computational problems in machine learning, material science, and chemistry. However, any near-term realizations of these algorithms will need to be heavily optimized to fit within the finite resources offered by existing noisy quantum hardware. Here, taking advantage of the strong adjustable coupling of gmon qubits, we demonstrate a continuous two qubit gate set that can provide a 5x reduction in circuit depth. We implement two gate families: an iSWAP-like gate to attain an arbitrary swap angle, $\theta$, and a CPHASE gate that generates an arbitrary conditional phase, $\phi$. Using one of each of these gates, we can perform an arbitrary two qubit gate within the excitation-preserving subspace allowing for a complete implementation of the so-called Fermionic Simulation, or fSim, gate set. We benchmark the fidelity of the iSWAP-like and CPHASE gate families as well as 525 other fSim gates spread evenly across the entire fSim($\theta$, $\phi$) parameter space achieving purity-limited average two qubit Pauli error of $3.8 \times 10^{-3}$ per fSim gate. View details
    TensorFlow Quantum: A Software Framework for Quantum Machine Learning
    Michael Broughton
    Guillaume Verdon
    Trevor McCourt
    Antonio J. Martinez
    Jae Hyeon Yoo
    Sergei V. Isakov
    Philip Massey
    Ramin Halavati
    Alexander Zlokapa
    Evan Peters
    Owen Lockwood
    Andrea Skolik
    Sofiene Jerbi
    Vedran Djunko
    Martin Leib
    Michael Streif
    David Von Dollen
    Hongxiang Chen
    Chuxiang Cao
    Roeland Wiersema
    Hsin-Yuan Huang
    Alan K. Ho
    Masoud Mohseni
    (2020)
    Preview abstract We introduce TensorFlow Quantum (TFQ), an open source library for the rapid prototyping of hybrid quantum-classical models for classical or quantum data. This framework offers high-level abstractions for the design and training of both discriminative and generative quantum models under TensorFlow and supports high-performance quantum circuit simulators. We provide an overview of the software architecture and building blocks through several examples and review the theory of hybrid quantum-classical neural networks. We illustrate TFQ functionalities via several basic applications including supervised learning for quantum classification, quantum control, simulating noisy quantum circuits, and quantum approximate optimization. Moreover, we demonstrate how one can apply TFQ to tackle advanced quantum learning tasks including meta-learning, layerwise learning, Hamiltonian learning, sampling thermal states, variational quantum eigensolvers, classification of quantum phase transitions, generative adversarial networks, and reinforcement learning. We hope this framework provides the necessary tools for the quantum computing and machine learning research communities to explore models of both natural and artificial quantum systems, and ultimately discover new quantum algorithms which could potentially yield a quantum advantage. View details
    Hartree-Fock on a Superconducting Qubit Quantum Computer
    Frank Carlton Arute
    Kunal Arya
    Rami Barends
    Michael Blythe Broughton
    Bob Benjamin Buckley
    Nicholas Bushnell
    Yu Chen
    Jimmy Chen
    Benjamin Chiaro
    Roberto Collins
    William Courtney
    Andrew Dunsworth
    Edward Farhi
    Brooks Riley Foxen
    Rob Graff
    Steve Habegger
    Alan Ho
    Trent Huang
    William J. Huggins
    Sergei Isakov
    Cody Jones
    Kostyantyn Kechedzhi
    Alexander Korotkov
    Fedor Kostritsa
    Dave Landhuis
    Pavel Laptev
    Mike Lindmark
    Orion Martin
    John Martinis
    Anthony Megrant
    Xiao Mi
    Masoud Mohseni
    Wojtek Mruczkiewicz
    Josh Mutus
    Charles Neill
    Thomas E O'Brien
    Eric Ostby
    Andre Gregory Petukhov
    Harry Putterman
    Vadim Smelyanskiy
    Doug Strain
    Kevin Jeffery Sung
    Marco Szalay
    Tyler Y. Takeshita
    Amit Vainsencher
    Nathan Wiebe
    Jamie Yao
    Ping Yeh
    Science, vol. 369 (2020), pp. 6507
    Preview abstract As the search continues for useful applications of noisy intermediate scale quantum devices, variational simulations of fermionic systems remain one of the most promising directions. Here, we perform a series of quantum simulations of chemistry which involve twice the number of qubits and more than ten times the number of gates as the largest prior experiments. We model the binding energy of ${\rm H}_6$, ${\rm H}_8$, ${\rm H}_{10}$ and ${\rm H}_{12}$ chains as well as the isomerization of diazene. We also demonstrate error-mitigation strategies based on $N$-representability which dramatically improve the effective fidelity of our experiments. Our parameterized ansatz circuits realize the Givens rotation approach to free fermion evolution, which we variationally optimize to prepare the Hartree-Fock wavefunction. This ubiquitous algorithmic primitive corresponds to a rotation of the orbital basis and is required by many proposals for correlated simulations of molecules and Hubbard models. Because free fermion evolutions are classically tractable to simulate, yet still generate highly entangled states over the computational basis, we use these experiments to benchmark the performance of our hardware while establishing a foundation for scaling up more complex correlated quantum simulations of chemistry. View details
    Accurately computing electronic properties of materials using eigenenergies
    Alan Derk
    Alan Ho
    Alex Opremcak
    Alexander Korotkov
    Andre Gregory Petukhov
    Andrew Dunsworth
    Anthony Megrant
    Bálint Pató
    Benjamin Chiaro
    Bob Benjamin Buckley
    Brooks Riley Foxen
    Charles Neill
    Cody Jones
    Daniel Eppens
    Dave Landhuis
    Doug Strain
    Edward Farhi
    Eric Ostby
    Fedor Kostritsa
    Frank Carlton Arute
    Igor Aleiner
    Jamie Yao
    Jeremy Patterson Hilton
    Jimmy Chen
    Josh Mutus
    Juan Atalaya
    Juan Campero
    Kostyantyn Kechedzhi
    Kunal Arya
    Marco Szalay
    Masoud Mohseni
    Matt Jacob-Mitos
    Matt Trevithick
    Michael Blythe Broughton
    Michael Newman
    Nicholas Bushnell
    Nicholas Redd
    Orion Martin
    Pavel Laptev
    Ping Yeh
    Rami Barends
    Roberto Collins
    Sean Harrington
    Sergei Isakov
    Thomas E O'Brien
    Trent Huang
    Trevor Mccourt
    Vadim Smelyanskiy
    Vladimir Shvarts
    William Courtney
    William J. Huggins
    Wojtek Mruczkiewicz
    Xiao Mi
    Yu Chen
    arXiv preprint arXiv:2012.00921 (2020)
    Preview abstract A promising approach to study quantum materials is to simulate them on an engineered quantum platform. However, achieving the accuracy needed to outperform classical methods has been an outstanding challenge. Here, using superconducting qubits, we provide an experimental blueprint for a programmable and accurate quantum matter simulator and demonstrate how to probe fundamental electronic properties. We illustrate the underlying method by reconstructing the single-particle band-structure of a one-dimensional wire. We demonstrate nearly complete mitigation of decoherence and readout errors and arrive at an accuracy in measuring energy eigenvalues of this wire with an error of ~0.01 radians, whereas typical energy scales are of order 1 radian. Insight into this unprecedented algorithm fidelity is gained by highlighting robust properties of a Fourier transform, including the ability to resolve eigenenergies with a statistical uncertainty of 1e-4 radians. Furthermore, we synthesize magnetic flux and disordered local potentials, two key tenets of a condensed-matter system. When sweeping the magnetic flux, we observe avoided level crossings in the spectrum, a detailed fingerprint of the spatial distribution of local disorder. Combining these methods, we reconstruct electronic properties of the eigenstates where we observe persistent currents and a strong suppression of conductance with added disorder. Our work describes an accurate method for quantum simulation and paves the way to study novel quantum materials with superconducting qubits. View details
    Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
    Dominic W. Berry
    Physical Review A Rapid Communication, vol. 99 (2019), 040301(R)
    Preview abstract We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with $N$ Majorana modes for time $t$ to precision $\epsilon$ with gate complexity ${\cal O}(N^{7/2} t + N^{5/2} \log(1 / \epsilon) / \log\log(1/\epsilon))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/\epsilon$ and large polynomial improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale as ${\cal O}(N^{10} t^2 / \epsilon)$. Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian $H$ as an asymmetric projection of a signal oracle $U$ onto two different signal states prepared by distinct state oracles, $A\ket{0} \mapsto \ket{A}$ and $B\ket{0} \mapsto \ket{B}$, such that $H = \bra{B} U \ket{A}$. Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing $B$ using only Hadamard gates and realizing $A$ as a random quantum circuit. View details
    Preview abstract Fermion-to-qubit mappings that preserve geometric locality are especially useful for simulating lattice fermion models (e.g., the Hubbard model) on a quantum computer. They avoid the overhead associated with geometric nonlocal parity terms in mappings such as the Jordan-Wigner transformation and the Bravyi-Kitaev transformation. As a result, they often provide quantum circuits with lower depth and gate complexity. In such encodings, fermionic states are encoded in the common +1 eigenspace of a set of stabilizers, akin to stabilizer quantum error-correcting codes. Here, we discuss several known geometric locality-preserving mappings and their abilities to correct and detect single-qubit errors. We introduce a geometric locality-preserving map, whose stabilizers correspond to products of Majorana operators on closed paths of the fermionic hopping graph. We show that our code, which we refer to as the Majorana loop stabilizer code (MLSC) can correct all single-qubit errors on a two-dimensional square lattice, while previous geometric locality-preserving codes can only detect single-qubit errors on the same lattice. Compared to existing codes, the MLSC maps the relevant fermionic operators to lower-weight qubit operators despite having higher code distance. Going beyond lattice models, we demonstrate that the MLSC is compatible with state-of-the-art algorithms for simulating quantum chemistry, and can offer those simulations the same error-correction properties without additional asymptotic overhead. These properties make the MLSC a promising candidate for error-mitigated quantum simulations of fermions on near-term devices View details
    Preview abstract Quantum Neural Networks (QNNs) are a promising variational learning paradigm with applications to near-term quantum processors, however they still face some significant challenges. One such challenge is finding good parameter initialization heuristics that ensure rapid and consistent convergence to local minima of the parameterized quantum circuit landscape. In this work, we train classical neural networks to assist in the quantum learning process, also know as meta-learning, to rapidly find approximate optima in the parameter landscape for several classes of quantum variational algorithms. Specifically, we train classical recurrent neural networks to find approximately optimal parameters within a small number of queries of the cost function for the Quantum Approximate Optimization Algorithm (QAOA) for MaxCut, QAOA for Sherrington-Kirkpatrick Ising model, and for a Variational Quantum Eigensolver for the Hubbard model. By initializing other optimizers at parameter values suggested by the classical neural network, we demonstrate a significant improvement in the total number of optimization iterations required to reach a given accuracy. We further demonstrate that the optimization strategies learned by the neural network generalize well across a range of problem instance sizes. This opens up the possibility of training on small, classically simulatable problem instances, in order to initialize larger, classically intractably simulatable problem instances on quantum devices, thereby significantly reducing the number of required quantum-classical optimization iterations. View details
    Preview abstract We present a quantum algorithm for simulating quantum chemistry with gate complexity Õ(η^{8/3}N^{1/3}),where η is the number of electrons and N is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity Õ(η^{2/3}N^{8/3}). We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when N ≫ η, as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation. View details
    Quantum Supremacy using a Programmable Superconducting Processor
    Frank Arute
    Kunal Arya
    Rami Barends
    Rupak Biswas
    Fernando Brandao
    David Buell
    Yu Chen
    Jimmy Chen
    Ben Chiaro
    Roberto Collins
    William Courtney
    Andrew Dunsworth
    Edward Farhi
    Brooks Foxen
    Austin Fowler
    Rob Graff
    Keith Guerin
    Steve Habegger
    Michael Hartmann
    Alan Ho
    Trent Huang
    Travis Humble
    Sergei Isakov
    Kostyantyn Kechedzhi
    Sergey Knysh
    Alexander Korotkov
    Fedor Kostritsa
    Dave Landhuis
    Mike Lindmark
    Dmitry Lyakh
    Salvatore Mandrà
    Anthony Megrant
    Xiao Mi
    Kristel Michielsen
    Masoud Mohseni
    Josh Mutus
    Charles Neill
    Eric Ostby
    Andre Petukhov
    Eleanor G. Rieffel
    Vadim Smelyanskiy
    Kevin Jeffery Sung
    Matt Trevithick
    Amit Vainsencher
    Benjamin Villalonga
    Z. Jamie Yao
    Ping Yeh
    John Martinis
    Nature, vol. 574 (2019), 505–510
    Preview abstract The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor. A fundamental challenge is to build a high-fidelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 2^53 (about 10^16). Measurements from repeated experiments sample the resulting probability distribution, which we verify using classical simulations. Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times-our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years. This dramatic increase in speed compared to all known classical algorithms is an experimental realization of quantum supremacy for this specific computational task, heralding a much-anticipated computing paradigm. View details
    Preview abstract Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with O(N^{3/2} λ) T complexity, where N is number of orbitals and λ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring almost one thousand times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space. View details
    Postponing the Orthogonality Catastrophe: Efficient State Preparation for Electronic Structure Simulations on Quantum Devices
    Norman Tubman
    Carlos Mejuto Zaera
    Jeffrey Epstein
    Diptarka Hait
    Daniel Levine
    William Huggins
    Martin Head-Gordon
    K. Birgitta Whaley
    arXiv:1809.05523 (2018)
    Preview abstract Despite significant work on resource estimation for quantum simulation of electronic systems, the challenge of preparing states with sufficient ground state support has so far been largely neglected. In this work we investigate this issue in several systems of interest, including organic molecules, transition metal complexes, the uniform electron gas, Hubbard models, and quantum impurity models arising from embedding formalisms such as dynamical mean-field theory. Our approach uses a state-of-the-art classical technique for high-fidelity ground state approximation. We find that easy-to-prepare single Slater determinants such as the Hartree-Fock state often have surprisingly robust support on the ground state for many applications of interest. For the most difficult systems, single-determinant reference states may be insufficient, but low-complexity reference states may suffice. For this we introduce a method for preparation of multi-determinant states on quantum computers. View details
    Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
    Ian D. Kivlichan
    Nathan Wiebe
    Alán Aspuru-Guzik
    Garnet Kin-Lic Chan
    Physical Review Letters, vol. 120 (2018), pp. 110501
    Preview abstract As physical implementations of quantum architectures emerge, it is increasingly important to consider the cost of algorithms for practical connectivities between qubits. We show that by using an arrangement of gates that we term the fermionic swap network, we can simulate a Trotter step of the electronic structure Hamiltonian in exactly N depth and with N^2/2 two-qubit entangling gates, and prepare arbitrary Slater determinants in at most N/2 depth, all assuming only a minimal, linearly connected architecture. We conjecture that no explicit Trotter step of the electronic structure Hamiltonian is possible with fewer entangling gates, even with arbitrary connectivities. These results represent significant practical improvements on the cost of all current proposed algorithms for both variational and phase estimation based simulation of quantum chemistry. View details
    Strategies for Quantum Computing Molecular Energies Using the Unitary Coupled Cluster Ansatz
    Jhonathan Romero Fontalvo
    Cornelius Hempel
    Peter J. Love
    Alán Aspuru-Guzik
    Quantum Science and Technology, vol. 4 (2018), pp. 14008
    Preview abstract The variational quantum eigensolver (VQE) algorithm combines the ability of quantum computers to efficiently compute expectations values with a classical optimization routine in order to approximate ground state energies of quantum systems. In this paper, we study the application of VQE to the simulation of molecular energies using the unitary coupled cluster (UCC) ansatz. We introduce new strategies to reduce the circuit depth for the implementation of UCC and improve the optimization of the wavefunction based on efficient classical approximations of the cluster amplitudes. Additionally, we propose a method to compute the energy gradient within the VQE approach. We illustrate our methodology with numerical simulations for a system of four hydrogen atoms that exhibit strong correlation and show that the cost of the circuit depth and execution time of VQE using a UCC ansatz can be reduced without introducing significant loss of accuracy in the final wavefunctions and energies. View details
    Preview abstract Many quantum algorithms, including recently proposed hybrid classical/quantum algorithms, make use of restricted tomography of the quantum state that measures the reduced density matrices, or marginals, of the full state. The most straightforward approach to this algorithmic step estimates each component of the marginal independently without making use of the algebraic and geometric structure of the marginals. Within the field of quantum chemistry, this structure is termed the fermionic $n$-representability conditions, and is supported by a vast amount of literature on both theoretical and practical results related to their approximations. In this work, we introduce these conditions in the language of quantum computation, and utilize them to develop several techniques to accelerate and improve practical applications for quantum chemistry on quantum computers. As a general result, we demonstrate how these marginals concentrate to diagonal quantities when measured on random quantum states. We also show that one can use fermionic $n$-representability conditions to reduce the total number of measurements required by more than an order of magnitude for medium sized systems in chemistry. As a practical demonstration, we simulate an efficient restoration of the physicality of energy curves for the dilation of a four qubit diatomic hydrogen system in the presence of three distinct one qubit error channels, providing evidence these techniques are useful for pre-fault tolerant quantum chemistry experiments. View details
    Preview abstract Many experimental proposals for noisy intermediate scale quantum devices involve training a parameterized quantum circuit with a classical optimization loop. Such hybrid quantum-classical algorithms are popular for applications in quantum simulation, optimization, and machine learning. Due to its simplicity and hardware efficiency, random circuits are often proposed as initial guesses for exploring the space of quantum states. We show that the exponential dimension of Hilbert space and the gradient estimation complexity make this choice unsuitable for hybrid quantum-classical algorithms run on more than a few qubits. Specifically, we show that for a wide class of reasonable parameterized quantum circuits, the probability that the gradient along any reasonable direction is non-zero to some fixed precision is exponentially small as a function of the number of qubits. We argue that this is related to the 2-design characteristic of random circuits, and that solutions to this problem must be studied. View details
    Preview abstract We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity O(lambda / epsilon) where lambda is an absolute sum of Hamiltonian coefficients and epsilon is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity O(N + \log (1/epsilon)) where N is number of orbitals in the basis. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error-correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only a few times more qubits than would be required for magic state distillation. View details
    Low-Depth Quantum Simulation of Materials
    Nathan Wiebe
    James McClain
    Garnet Chan
    Physical Review X, vol. 8 (2018), pp. 011044
    Preview abstract Quantum simulation of the electronic structure problem is one of the most researched applications of quantum computing. The majority of quantum algorithms for this problem encode the wavefunction using $N$ molecular orbitals, leading to Hamiltonians with ${\cal O}(N^4)$ second-quantized terms. To avoid this overhead, we introduce basis functions which diagonalize the periodized Coulomb operator, providing Hamiltonians for condensed phase systems with $N^2$ second-quantized terms. Using this representation we can implement single Trotter steps of the Hamiltonians with gate depth of ${\cal O}(N)$ on a planar lattice of qubits -- a quartic improvement over prior methods. Special properties of our basis allow us to apply Trotter based simulations with planar circuit depth in $\widetilde{\cal O}(N^{7/2} / \epsilon^{1/2})$ and Taylor series methods with circuit size $\widetilde{\cal O}(N^{11/3})$, where $\epsilon$ is target precision. Variational algorithms also require significantly fewer measurements to find the mean energy using our representation, ameliorating a primary challenge of that approach. We conclude with a proposal to simulate the uniform electron gas (jellium) using a linear depth variational ansatz realizable on near-term quantum devices with planar connectivity. From these results we identify simulation of low-density jellium as an ideal first target for demonstrating quantum supremacy in electronic structure. View details