7 papers
The Robustness of QAC0
Daniel Grier, Jackson Morris, Kewen Wu
In this work we study the robustness of with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typical…
On the Advantage of Adaptivity for Sampling with Cell Probes
Farzan Byramji, Daniel M. Kane, Jackson Morris +1
We construct an explicit distribution over that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distr…
Immersions of -projective spaces via -theory
Manyi Guo, Jackson Morris, Alex Waugh +1
We compute the Atiyah Real -theory of -equivariant projective spaces and construct immersions of such spaces into multiples of the regular representation. These computation…
Hard-to-Sample Distributions from Robust Extractors
Farzan Byramji, Daniel M. Kane, Jackson Morris +1
We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notio…
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 …
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…