Improved separation between quantum and classical computers for sampling and functional tasks

DOI10.4230/LIPICS.CCC.2025.5MaRDI QIDQ7296753zbMATH OpenFDO

Authors Simon C. Marshall, Scott Aaronson, Vedran Dunjko

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.5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A polynomial-time classical algorithm for noisy random circuit sampling
• Designing programs that check their work
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• On Approximation Algorithms for # P
• PP is as Hard as the Polynomial-Time Hierarchy
• Quantum computing, postselection, and probabilistic polynomial-time
• The computational complexity of linear optics
• The equivalence of sampling and searching
• The weakness of CTC qubits and the power of approximate counting
• Threshold Computation and Cryptographic Security

This page was built for publication: Improved separation between quantum and classical computers for sampling and functional tasks

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