Kewen Wu

collaborators

3 papers

cs.CC2026

$QAC^{0}$ Contains $TC^{0}$ (with Many Copies of the Input)

Daniel Grier, Jackson Morris, Kewen Wu

$QAC^{0}$ 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…

cs.CC2025

Symmetric Distributions from Shallow Circuits

Daniel M. Kane, Anthony Ostuni, Kewen Wu

We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let $f : {0, 1}^{m} \to {0, 1}^{n}$ be a Boolean fu…

cs.CC2025

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Daniel Grier, Daniel M. Kane, Jackson Morris +2

We construct a family of distributions ${D_{n}}_{n}$ with $D_{n}$ over ${0, 1}^{n}$ and a family of depth- $7$ quantum circuits ${C_{n}}_{n}$ such that $D_{n}$ …

QAC0 Contains TC0 (with Many Copies of the Input)

Symmetric Distributions from Shallow Circuits

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

$QAC^{0}$ Contains $TC^{0}$ (with Many Copies of the Input)