3 citations · 3 across the 2 of their papers we have counts for
5 papers
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…
On the complexity of probabilistic trials for hidden satisfiability problems
Itai Arad, Adam Bouland, Daniel Grier +3
What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing…
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…