Robin Kothari

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.

SODA Conference 2023 Conference Paper

Mean estimation when you have the source code; or, quantum Monte Carlo methods

• Robin Kothari
• Ryan O'Donnell

Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y ). We give a quantum procedure that runs the code O ( n ) times and returns an estimate for μ = E [ y ] that with high probability satisfies, where σ = stddev[ y ]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse. Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https: //arxiv. org/abs/2208. 07544

FOCS Conference 2023 Conference Paper

Query-optimal estimation of unitary channels in diamond distance

• Jeongwan Haah
• Robin Kothari
• Ryan O'Donnell
• Ewin Tang

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O\left(\mathrm{~d}^{2} / \varepsilon\right)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)$ [via standard process tomography] or $O\left(\mathrm{~d}^{2. 5} / \varepsilon\right)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega\left(\mathrm{d}^{2} / \varepsilon\right)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

FOCS Conference 2022 Conference Paper

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

• Jeongwan Haah
• Robin Kothari
• Ewin Tang

We study the problem of learning a Hamiltonian H to precision $\varepsilon$, supposing we are given copies of its Gibbs state $\rho =\exp(-\beta H)/\mathrm{Tr}(\exp(-\beta H))$ at a known inverse temperature $\beta$. Anshu, Arunachalam, Kuwahara, and Soleimanifar [AAKS21] recently studied the sample complexity (number of copies of $\rho$ needed) of this problem for geometrically local N-qubit Hamiltonians. In the high-temperature (low $\beta$) regime, their algorithm has sample complexity poly (N, 1/$\beta$, 1/$\varepsilon$) and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S=O(\log N/(\beta\varepsilon)^{2}$) and time complexity linear in the sample size, O(SN). Furthermore, we prove a matching lower bound showing that our algorithm’s sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn H from a real-time evolution unitary $e^{-i t H}$ in a small t regime with similar sample and time complexity.

STOC Conference 2021 Conference Paper

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem

• Scott Aaronson
• Shalev Ben-David
• Robin Kothari
• Shravas Rao
• Avishay Tal

NeurIPS Conference 2021 Conference Paper

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

• Ankit Garg
• Robin Kothari
• Praneeth Netrapalli
• Suhail Sherif

We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an $\epsilon$-approximate minimum of a convex function $f$, given oracle access to the function and its first $p$ derivatives, assuming that the $p$th derivative of $f$ is Lipschitz. Recently, three independent research groups (Jiang et al. , PLMR 2019; Gasnikov et al. , PLMR 2019; Bubeck et al. , PLMR 2019) developed a new algorithm that solves this problem with $\widetilde{O}\left(1/\epsilon^{\frac{2}{3p+1}}\right)$ oracle calls for constant $p$. This is known to be optimal (up to log factors) for deterministic algorithms, but known lower bounds for randomized algorithms do not match this bound. We prove a new lower bound that matches this bound (up to log factors), and holds not only for randomized algorithms, but also for quantum algorithms.

ICML Conference 2021 Conference Paper

Quantum algorithms for reinforcement learning with a generative model

• Daochen Wang
• Aarthi Sundaram
• Robin Kothari
• Ashish Kapoor
• Martin Rötteler

Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a $\gamma$-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy ($\pi^*$), the optimal value function ($v^*$), and the optimal $Q$-function ($q^*$), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy ($\epsilon$) and two main parameters of the MDP: the effective time horizon ($\frac{1}{1-\gamma}$) and the size of the action space ($A$). Moreover, we show that our quantum algorithm for computing $q^*$ is optimal by proving a matching quantum lower bound.

FOCS Conference 2021 Conference Paper

Unambiguous DNFs and Alon-Saks-Seymour

• Kaspars Balodis
• Shalev Ben-David
• Mika Göös
• Siddhartha Jain 0002
• Robin Kothari

We exhibit an unambiguous $k$ -DNF formula that requires CNF width $\tilde\Omega(k^{2})$, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon–Saks–Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.

STOC Conference 2019 Conference Paper

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

• Adam Bene Watts
• Robin Kothari
• Luke Schaeffer
• Avishay Tal

SODA Conference 2019 Conference Paper

Quantum algorithms and approximating polynomials for composed functions with shared inputs

• Mark Bun
• Robin Kothari
• Justin Thaler

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let f be a Boolean function and consider a function F obtained by applying f to conjunctions of possibly overlapping subsets of n variables. If f has quantum query complexity Q ( f ), we give an algorithm for evaluating F using quantum queries. This improves on the bound of that follows by treating each conjunction independently, and is tight for worst-case choices of f. Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of f. By recursively applying our composition theorems, we obtain a nearly optimal Õ ( n 1–2– d ) upper bound on the quantum query complexity and approximate degree of linear-size depth- d AC 0 circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC 0 circuits. We also show that any substantially faster learning algorithm will require fundamentally new techniques.

FOCS Conference 2018 Conference Paper

Classical Lower Bounds from Quantum Upper Bounds

• Shalev Ben-David
• Adam Bouland
• Ankit Garg 0001
• Robin Kothari

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0, 1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

FOCS Conference 2018 Conference Paper

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians

• Jeongwan Haah
• Matthew B. Hastings
• Robin Kothari
• Guang Hao Low

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i. e. , a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and encompasses all physically reasonable Hamiltonians. Our algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error ε using O(T polylog(nT/ε)) gates with depth O(T polylog(nT/ε)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/ε. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires (nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

STOC Conference 2018 Conference Paper

The polynomial method strikes back: tight quantum query bounds via dual polynomials

• Mark Bun
• Robin Kothari
• Justin Thaler

FOCS Conference 2016 Conference Paper

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

• Anurag Anshu
• Aleksandrs Belovs
• Shalev Ben-David
• Mika Göös
• Rahul Jain 0001
• Robin Kothari
• Troy Lee
• Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2. 5 gap. We further present a 1. 5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1. 15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1. 5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.

STOC Conference 2016 Conference Paper

Separations in query complexity using cheat sheets

• Scott Aaronson
• Shalev Ben-David
• Robin Kothari

FOCS Conference 2015 Conference Paper

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

• Dominic W. Berry
• Andrew M. Childs
• Robin Kothari

We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product tau of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sub linear dependence on tau.

STOC Conference 2014 Conference Paper

Exponential improvement in precision for simulating sparse Hamiltonians

• Dominic W. Berry
• Andrew M. Childs
• Richard Cleve
• Robin Kothari
• Rolando D. Somma

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d -sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O ( τ log( τ / ε )/log log( τ/ε )) queries and O ( τn log 2 ( τ/ε )/log log( τ/ε )) additional 2-qubit gates, where τ=d 2 ||H|| max t . Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

SODA Conference 2013 Conference Paper

Nested Quantum Walks with Quantum Data Structures

• Stacey Jeffery
• Robin Kothari
• Frédéric Magniez

We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the O ( n 35/27 ) and O ( n 9/7 ) learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.