Ryan Babbush

Ryan Babbush

Ryan is the director of the Quantum Algorithm & Applications Team at Google. The mandate of this research team is to develop new and more efficient quantum algorithms, discovery and analyze new applications of quantum computers, build and open source tools for accelerating quantum algorithms research, and to design algorithms experiments to demonstrate on existing quantum devices.
Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    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, 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
    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
    Quartic Quantum Speedups for Planted Inference Problems
    Alexander Schmidhuber
    Ryan O'Donnell
    arXiv:2406.19378(2024)
    Preview abstract We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings, by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks. 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
    Austin Fowler
    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
    Zhang Jiang
    Cody Jones
    Pavol Juhas
    Kostyantyn Kechedzhi
    Mostafa Khezri
    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
    Benjamin Villalonga
    Cheng Xing
    Jamie Yao
    Ping Yeh
    Juhwan Yoo
    Grayson Young
    Yaxing Zhang
    Ningfeng Zhu
    Jeremy Hilton
    Anthony Megrant
    Yu Chen
    Vadim Smelyanskiy
    Dmitry Abanin
    Science, 383(2024), pp. 1332-1337
    Preview abstract Engineered dissipative reservoirs have the potential to steer many-body quantum systems toward correlated steady states useful for quantum simulation of high-temperature superconductivity or quantum magnetism. Using up to 49 superconducting qubits, we prepared low-energy states of the transverse-field Ising model through coupling to dissipative auxiliary qubits. In one dimension, we observed long-range quantum correlations and a ground-state fidelity of 0.86 for 18 qubits at the critical point. In two dimensions, we found mutual information that extends beyond nearest neighbors. Lastly, by coupling the system to auxiliaries emulating reservoirs with different chemical potentials, we explored transport in the quantum Heisenberg model. Our results establish engineered dissipation as a scalable alternative to unitary evolution for preparing entangled many-body states on noisy quantum processors. View details
    Triply efficient shadow tomography
    Robbie King
    David Gosset
    arXiv:2404.19211(2024)
    Preview abstract Given copies of a quantum state $\rho$, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision $\epsilon$. We say that a shadow tomography protocol is \textit{triply efficient} if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of $\rho$ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph $G$ that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of $G$ with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as \textit{chi-boundedness}. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all $n$-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an $n$-qubit quantum state into a $\poly(n)$-sized classical representation, from which one can extract the expected value of any of the $4^n$ Pauli observables in $\poly(n)$ time, up to a small constant error. 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
    Austin Fowler
    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
    Zhang Jiang
    Cody Jones
    Pavol Juhas
    Mostafa Khezri
    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
    Benjamin Villalonga
    Cheng Xing
    Jamie Yao
    Ping Yeh
    Juhwan Yoo
    Grayson Young
    Yaxing Zhang
    Ningfeng Zhu
    Jeremy Hilton
    Anthony Megrant
    Yu Chen
    Vadim Smelyanskiy
    Vedika Khemani
    Sarang Gopalakrishnan
    Tomaž Prosen
    Science, 384(2024), pp. 48-53
    Preview abstract Understanding universal aspects of quantum dynamics is an unresolved problem in statistical mechanics. In particular, the spin dynamics of the one-dimensional Heisenberg model were conjectured as to belong to the Kardar-Parisi-Zhang (KPZ) universality class based on the scaling of the infinite-temperature spin-spin correlation function. In a chain of 46 superconducting qubits, we studied the probability distribution of the magnetization transferred across the chain’s center, P(M). The first two moments of P(M) show superdiffusive behavior, a hallmark of KPZ universality. However, the third and fourth moments ruled out the KPZ conjecture and allow for evaluating other theories. Our results highlight the importance of studying higher moments in determining dynamic universality classes and provide insights into universal behavior in quantum systems. View details
    Quantum Computation of Stopping power for Inertial Fusion Target Design
    Dominic Berry
    Alina Kononov
    Alec White
    Joonho Lee
    Andrew Baczewski
    Proceedings of the National Academy of Sciences, 121(2024), e2317772121
    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
    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, 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
    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, 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
    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
    Austin Fowler
    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
    Mostafa Khezri
    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
    Benjamin Villalonga
    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