Complexity-theoretic foundations of quantum supremacy experiments

DOI10.4230/LIPICS.CCC.2017.22zbMATH Open1451.81157arXiv1612.05903MaRDI QIDQ5111152FDOQ5111152

Authors: Scott Aaronson, Lijie Chen 

Publication date: 26 May 2020

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

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

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)

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
• Entanglement accessibility measures for the quantum Internet
• Quantum science and quantum technology
• The argument against quantum computers
• State stabilization for gate-model quantum computers
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)