Quantum threshold is powerful

DOI10.4230/LIPICS.CCC.2025.3MaRDI QIDQ7296749zbMATH OpenFDO

Authors Daniel Grier, Jackson Morris

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2025.3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A lower bound method for quantum circuits
• Bounds on the QAC^0 complexity of approximating parity
• Collapse of the hierarchy of constant-depth exact quantum circuits
• Constant depth circuits, Fourier transform, and learnability
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond
• Parity, circuits, and the polynomial-time hierarchy
• Quantum advantage with shallow circuits
• Quantum fan-out is powerful
• Quantum lower bounds for fanout

This page was built for publication: Quantum threshold is powerful

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296749)