779 citations · 2.6k across the 35 of their papers we have counts for
3 papers · 2 filters
Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, Rolando D. Somma
Harrow, Hassidim, and Lloyd showed that for a suitably specified matrix and -dimensional vector , there is a quantum algorithm that outputs a quantum s…
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, Robin Kothari
We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best suc…
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…