3 citations · 3 across the 2 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…
Depth-2 QAC circuits cannot simulate quantum parity
Daniel Padé, Stephen Fenner, Daniel Grier +1
We show that the quantum parity gate on qubits cannot be cleanly simulated by a quantum circuit with two layers of arbitrary C-SIGN gates of any arity and arbitrary 1-qubit…
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…
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…