4 papers
Contains (with Many Copies of the Input)
Daniel Grier, Jackson Morris, Kewen Wu
is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the sma…
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
Daniel Grier, Daniel M. Kane, Jackson Morris +2
We construct a family of distributions with over and a family of depth- quantum circuits such that …
Tight bounds on depth-2 QAC-circuits computing parity
Stephen Fenner, Daniel Grier, Daniel Padé +1
We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This…
Quantum Threshold is Powerful
Daniel Grier, Jackson Morris
In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean function…