37 citations · 39 across the 6 of their papers we have counts for
6 papers · 1 filter
Classical algorithms for Forrelation
Sergey Bravyi, David Gosset, Daniel Grier +1
We study the forrelation problem: given a pair of -bit Boolean functions and , estimate the correlation between and the Fourier transform of . This problem is know…
Interactive quantum advantage with noisy, shallow Clifford circuits
Daniel Grier, Nathan Ju, Luke Schaeffer
Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC) can solve with near certainty (probability ), but that an…
Interactive shallow Clifford circuits: quantum advantage against NC and beyond
Daniel Grier, Luke Schaeffer
Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which…
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…
A Quantum Query Complexity Trichotomy for Regular Languages
Scott Aaronson, Daniel Grier, Luke Schaeffer
We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Theta(1), ~Theta(sqrt n), or Theta(n). Th…
The Classification of Reversible Bit Operations
Scott Aaronson, Daniel Grier, Luke Schaeffer
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps a…