Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- 11 August 2010
- journal article
- research article
- Published by The Royal Society in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 467 (2126), 459-472
- https://doi.org/10.1098/rspa.2010.0301
Abstract
We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.Keywords
This publication has 11 references indexed in Scilit:
- BQP and the polynomial hierarchyPublished by Association for Computing Machinery (ACM) ,2010
- Matchgate and space-bounded quantum computations are equivalentProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009
- Computational ComplexityPublished by Cambridge University Press (CUP) ,2009
- Temporally unstructured quantum computationProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009
- Fault-tolerant computing with biased-noise superconducting qubits: a case studyNew Journal of Physics, 2009
- Cluster-state quantum computationReports on Mathematical Physics, 2006
- Quantum computing, postselection, and probabilistic polynomial-timeProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2005
- Demonstrating the viability of universal quantum computation using teleportation and single-qubit operationsNature, 1999
- Threshold Computation and Cryptographic SecuritySIAM Journal on Computing, 1997
- PP is as Hard as the Polynomial-Time HierarchySIAM Journal on Computing, 1991