Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

DOI10.1098/rspa.2010.0301zbMath1219.81071arXiv1005.1407WikidataQ56689365 ScholiaQ56689365MaRDI QIDQ3088963

Richard Jozsa, D. J. Shepherd, Michael J. Bremner

Publication date: 21 August 2011

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

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

zbMATH Keywords

polynomial hierarchy; quantum simulation; quantum computational complexity

Mathematics Subject Classification ID

81P68: Quantum computation

68Q12: Quantum algorithms and complexity in the theory of computing

Related Items

Fault-tolerant conversion between adjacent Reed–Muller quantum codes based on gauge fixing, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Compact Gaussian quantum computation by multi-pixel homodyne detection, A framework for phase and interference in generalized probabilistic theories, Generating a statet-design by diagonal quantum circuits, Exact and efficient simulation of concordant computation, DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS, Unnamed Item, Computation in a general physical setting, Commuting quantum circuits and complexity of Ising partition functions, Approximate unitary \(t\)-designs by short random quantum circuits using nearest-neighbor and long-range gates, Random quantum circuits transform local noise into global white noise, The complexity of approximating complex-valued Ising and Tutte partition functions, Learning nonlinear input-output maps with dissipative quantum systems, Classically simulating quantum circuits with local depolarizing noise, Verification of quantum computation: an overview of existing approaches, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Quantum extensive-form games, Complexity Classification of Local Hamiltonian Problems, A linear-optical proof that the permanent is # P -hard, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Optimised resource construction for verifiable quantum computation, Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable, Unnamed Item

Cites Work

• Temporally unstructured quantum computation
• Matchgate and space-bounded quantum computations are equivalent
• Quantum computing, postselection, and probabilistic polynomial-time