Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
From MaRDI portal
Publication:3088963
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
Related Items (28)
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 ⋮ Certified randomness from quantum supremacy ⋮ 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
This page was built for publication: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
