scientific article; zbMATH DE number 7250161

DOI10.4230/LIPICS.CCC.2018.21MaRDI QIDQ5121909zbMATH OpenFDO

Authors Adam Bouland, Joseph Fitzsimons, Dax Enshan Koh

Publication date 22 September 2020

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

zbMATH Keywords

gate-set classificationpolynomial hierarchyquantum advantagesampling problems

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) 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)

Recommendations

• Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates
• Classical simulation and complexity of quantum computations (invited talk)
• Generalized Clifford groups and simulation of associated quantum circuits

Cites work

• Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
• Complexity classification of two-qubit commuting Hamiltonians
• How hard is it to approximate the Jones polynomial?
• scientific article; zbMATH DE number 1559533 (Why is no real title available?)
• Matchgates and classical simulation of quantum circuits
• Multiple-particle interference and quantum error correction
• On the power of quantum Fourier sampling
• On the Structure of Polynomial Time Reducibility
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• PP is as Hard as the Polynomial-Time Hierarchy
• Quantum computing, postselection, and probabilistic polynomial-time
• Self-dual codes and invariant theory
• The computational complexity of linear optics
• The Heisenberg representation of quantum computers
• The invariants of the Clifford groups
• The Solovay--Kitaev algorithm
• Universal quantum computation with ideal Clifford gates and noisy ancillas

Cited in

(8)

• Classically simulating quantum circuits with local depolarizing noise
• Generalized Clifford groups and simulation of associated quantum circuits
• scientific article; zbMATH DE number 7559454 (Why is no real title available?)
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Wasserstein complexity of quantum circuits
• Gaussianity and simulability of Cliffords and matchgates
• Discrete quantum gaussians and central limit theorem

Describes a project that uses

Uses Software

• QuaEC

This page was built for publication:

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