Complexity-theoretic foundations of quantum supremacy experiments

DOI10.4230/LIPICS.CCC.2017.22MaRDI QIDQ5111152zbMATH OpenFDO

Authors Scott Aaronson, Lijie Chen

Publication date 26 May 2020

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

zbMATH Keywords

computational complexityquantum computingquantum supremacy

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Other Turing degree structures (03D28) Classical models of computation (Turing machines, etc.) (68Q04)

Recommendations

• The argument against quantum computers
• On the classical hardness of spoofing linear cross-entropy benchmarking
• The classical complexity of boson sampling
• Towards quantum supremacy with lossy scattershot boson sampling
• The road to quantum computational supremacy

Cited in

(30)

• Quantum circuit design for objective function maximization in gate-model quantum computers
• On the need for large quantum depth
• Efficient algorithm for full-state quantum circuit simulation with DD compression while maintaining accuracy
• The classical complexity of boson sampling
• Verification of quantum computation: an overview of existing approaches
• BQP and the polynomial hierarchy
• Post-processing optimization for continuous-variable quantum key distribution
• Quantum science and quantum technology
• Entanglement accessibility measures for the quantum Internet
• The argument against quantum computers
• State stabilization for gate-model quantum computers
• scientific article; zbMATH DE number 7559371 (Why is no real title available?)
• On the classical hardness of spoofing linear cross-entropy benchmarking
• Fast and scalable quantum computing simulation on multi-core and many-core platforms
• Trading locality for time: certifiable randomness from low-depth circuits
• Forrelation: a problem that optimally separates quantum from classical computing
• The equivalence of sampling and searching
• The equivalence of sampling and searching
• Random quantum circuits transform local noise into global white noise
• On the power of quantum Fourier sampling
• scientific article; zbMATH DE number 7564421 (Why is no real title available?)
• Approximate unitary \(t\)-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Entanglement concentration service for the quantum Internet
• Quantum advantage from one-way functions
• Performance analysis and modeling for quantum computing simulation on distributed GPU platforms
• A polynomial-time classical algorithm for noisy random circuit sampling
• Certified randomness from quantum supremacy
• Decoherence dynamics estimation for superconducting gate-model quantum computers
• The road to quantum computational supremacy
• Quantum computational complexity with photons and linear optics

This page was built for publication: Complexity-theoretic foundations of quantum supremacy experiments

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