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

DOI10.1098/rspa.2010.0301zbMath1219.81071arXiv1005.1407OpenAlexW3100618339WikidataQ56689365 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 hierarchyquantum simulationquantum computational complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (27)

A linear-optical proof that the permanent is # P -hard ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable ⋮ The complexity of approximating complex-valued Ising and Tutte partition functions ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ Quantum extensive-form games ⋮ 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 ⋮ Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimised resource construction for verifiable quantum computation ⋮ 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 ⋮ Classically simulating quantum circuits with local depolarizing noise ⋮ Fault-tolerant conversion between adjacent Reed–Muller quantum codes based on gauge fixing ⋮ DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ Unnamed Item ⋮ Verification of quantum computation: an overview of existing approaches ⋮ Unnamed Item ⋮ Learning nonlinear input-output maps with dissipative quantum systems ⋮ Computation in a general physical setting

Cites Work

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

This page was built for publication: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy