779 citations · 2.6k across the 35 of their papers we have counts for
41 papers
An Optimal Quantum Linear Systems Algorithm
Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari
In the quantum linear systems problem (QLSP), we are given query access to a -sparse matrix with condition number , and the ability to prepare a quantum state…
Randomized query complexity can beat certificate complexity
Shalev Ben-David, Robin Kothari
A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query…
Exponential quantum speedup in simulating coupled classical oscillators
Ryan Babbush, Dominic W. Berry, Robin Kothari +2
We present a quantum algorithm for simulating the classical dynamics of coupled oscillators (e.g., masses coupled by springs). Our approach leverages a mapping between…
Query-optimal estimation of unitary channels in diamond distance
Jeongwan Haah, Robin Kothari, Ryan O'Donnell +1
We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a -dimensional qudit, we aim to output a classical des…
Quantum divide and conquer
Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak +2
The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size into smaller subproblems (say, copies of size e…
Mean estimation when you have the source code; or, quantum Monte Carlo methods
Robin Kothari, Ryan O'Donnell
Suppose 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 $\boldsy…