Natural proofs for quantum state preparation lower bounds
quant-ph, cs.CC
Submitted: 2026-10-05
Updated: 2026-10-05
Sources
- Quantum circuit lower bounds in the magic hierarchy
- On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
- Random Unitaries in Constant (Quantum) Time
- $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
- Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries
- Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
- The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians