Kewen Wu

collaborators

2 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

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)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

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