6 papers
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…
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…
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…
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 functi…