Publications (53)
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…
No quantum speedup over gradient descent for non-smooth convex optimization
Ankit Garg, Robin Kothari, Praneeth Netrapalli +1
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function and its (sub)gradient. O…
Multi-qubit Toffoli with exponentially fewer T gates
David Gosset, Robin Kothari, Chenyi Zhang
Prior work of Beverland et al. has shown that any exact Clifford+ implementation of the -qubit Toffoli gate must use at least gates. Here we show how to get away with…
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 optim…
Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve +2
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous meth…
Quantum state preparation with optimal T-count
David Gosset, Robin Kothari, Kewen Wu
How many T gates are needed to approximate an arbitrary -qubit quantum state to within error ? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that…