On the classical hardness of spoofing linear cross-entropy benchmarking

DOI10.4086/TOC.2020.V016A011MaRDI QIDQ5140846zbMATH OpenOpenAlexFDO

Authors Scott Aaronson, Sam Gunn

Publication date 17 December 2020

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.12085

zbMATH Keywords

quantum complexityquantum supremacysampling complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68) Sampling theory in information and communication theory (94A20)

Recommendations

• Complexity-theoretic foundations of quantum supremacy experiments
• The classical complexity of boson sampling
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Commuting quantum circuits with few outputs are unlikely to be classically simulatable
• The computational complexity of linear optics

Cites work

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Complexity-theoretic foundations of quantum supremacy experiments
• The computational complexity of linear optics

Cited in

(6)

• Statistical aspects of the quantum supremacy demonstration
• Complexity-theoretic foundations of quantum supremacy experiments
• A polynomial-time classical algorithm for noisy random circuit sampling
• A qubit, a coin, and an advice string walk into a relational problem
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target
• The quantum supremacy Tsirelson inequality

This page was built for publication: On the classical hardness of spoofing linear cross-entropy benchmarking

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