Ryan Babbush

SODA Conference 2025 Conference Paper

Quartic quantum speedups for planted inference

• Alexander Schmidhuber
• Ryan O'Donnell
• Robin Kothari
• Ryan Babbush

SODA Conference 2025 Conference Paper

Triply efficient shadow tomography

• Robbie King
• David Gosset
• Robin Kothari
• Ryan Babbush

Given copies of a quantum state ρ, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision ε. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of ρ 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 singlecopy 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 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.

FOCS Conference 2023 Conference Paper

Exponential quantum speedup in simulating coupled classical oscillators *

• Ryan Babbush
• Dominic W. Berry
• Robin Kothari
• Rolando D. Somma
• Nathan Wiebe

We study the problem of simulating the time evolution of a system of 2 n classical coupled oscillators (e. g. , 2 n balls connected by springs) on a quantum computer. We map Newton’s equation for harmonic potentials to Schrödinger’s equation, such that the amplitudes of an $\mathcal{O}(n)$-qubit quantum state encode the momenta and displacements of the 2 n classical oscillators. Given oracle access to the masses and spring constants, we describe a quantum algorithm with query and time complexity poly (n) that solves this problem when certain parameters are polynomially bounded and the initial state is easy to prepare. As an example application, we apply our quantum algorithm to efficiently estimate the normalized kinetic energy of an oscillator at any time. We then show that any classical algorithm solving the same problem must make $2^{\Omega(n)}$ queries to the oracle and we also show that when the oracles are instantiated by poly (n)-size circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.

NeurIPS Conference 2014 Conference Paper

Bayesian Sampling Using Stochastic Gradient Thermostats

• Nan Ding
• Youhan Fang
• Ryan Babbush
• Changyou Chen
• Robert Skeel
• Hartmut Neven

Dynamics-based sampling methods, such as Hybrid Monte Carlo (HMC) and Langevin dynamics (LD), are commonly used to sample target distributions. Recently, such approaches have been combined with stochastic gradient techniques to increase sampling efficiency when dealing with large datasets. An outstanding problem with this approach is that the stochastic gradient introduces an unknown amount of noise which can prevent proper sampling after discretization. To remedy this problem, we show that one can leverage a small number of additional variables in order to stabilize momentum fluctuations induced by the unknown noise. Our method is inspired by the idea of a thermostat in statistical physics and is justified by a general theory.