37 citations · 47 across the 4 of their papers we have counts for
3 papers · 1 filter
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer +1
Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth…
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
Scott Aaronson, Robin Kothari, William Kretschmer +1
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Lauren…
Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
Shalev Ben-David, Robin Kothari
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close t…