Publications (24)
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer +1
Hamiltonian simulation with nearly optimal dependence on all parameters
Dominic W. Berry, Andrew M. Childs, Robin Kothari
Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve +2
An optimal quantum algorithm for the oracle identification problem
Robin Kothari
Separating quantum communication and approximate rank
Anurag Anshu, Shalev Ben-David, Ankit Garg +3
Dequantizing read-once quantum formulas
Alessandro Cosentino, Robin Kothari, Adam Paetznick
The quantum query complexity of read-many formulas
Andrew M. Childs, Shelby Kimmel, Robin Kothari
Dissipation in circuit quantum electrodynamics: lasing and cooling of a low-frequency oscillator
Julian Hauss, Arkady Fedorov, Stephan André +6
Randomized query complexity of sabotaged and composed functions
Shalev Ben-David, Robin Kothari
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
Stacey Jeffery, Robin Kothari, Frédéric Magniez
Nested Quantum Walks with Quantum Data Structures
Stacey Jeffery, Robin Kothari, Frederic Magniez
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5
Classical lower bounds from quantum upper bounds
Shalev Ben-David, Adam Bouland, Ankit Garg +1
A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
Andrew M. Childs, Stacey Jeffery, Robin Kothari +1
Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve +2
Easy and hard functions for the Boolean hidden shift problem
Andrew M. Childs, Robin Kothari, Maris Ozols +1
Quantum query complexity of minor-closed graph properties
Andrew M. Childs, Robin Kothari
Nearly optimal separations between communication (or query) complexity and partitions
Robin Kothari
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, Robin Kothari
Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, Rolando D. Somma
Simulating sparse Hamiltonians with star decompositions
Andrew M. Childs, Robin Kothari
Separating decision tree complexity from subcube partition complexity
Robin Kothari, David Racicot-Desloges, Miklos Santha
Limitations on the simulation of non-sparse Hamiltonians
Andrew M. Childs, Robin Kothari
Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
Shalev Ben-David, Robin Kothari