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

Michael J. Bremner, Richard Jozsa, Dan J. Shepherd · Proceedings of the Royal Society A · 2010

Summary

The class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection is introduced, and it is proved first that post- IQP equals the classical class PP, and that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level.

Type: article
Published: 2010-05-09
Cited by: 498
References: 22
Access: Open access
DOI: https://doi.org/10.1098/rspa.2010.0301
arXiv: https://arxiv.org/abs/1005.1407
OpenAlex: https://openalex.org/W2069280326
Semantic Scholar: https://api.semanticscholar.org/CorpusID:12301677

Keywords

Polynomial hierarchy, Multiplicative function, Bounded function, Complexity class, Polynomial

References

Permutational quantum computingStephen P. Jordan — 2009
Demonstrating the viability of universal quantum computation using teleportation and single-qubit operationsDaniel Gottesman, Isaac L. Chuang — 1999
Quantum Complexity: restrictions on algorithms and architecturesD. J. Shepherd — 2010
Binary Matroids and Quantum Probability DistributionsDan Shepherd — 2010
BQP and the polynomial hierarchyScott Aaronson — 2009
Cluster-state quantum computationMichael A. Nielsen — 2005
Temporally unstructured quantum computationDan Shepherd, Michael J. Bremner — 2008
Matchgate and space-bounded quantum computations are equivalentRichard Jozsa, Barbara Kraus, Akimasa Miyake — 2009
PP is as Hard as the Polynomial-Time HierarchySeinosuke Toda — 1991
Fault-tolerant computing with biased-noise superconducting qubits: a case studyPanos Aliferis, F Brito, David P. DiVincenzo — 2008
Quantum computing, postselection, and probabilistic polynomial-timeScott Aaronson — 2004
Quantum computingTetsuro Nishino — 2003
Adaptive quantum computation, constant depth quantum circuits and arthur-merlin gamesBarbara M. Terhal, David P. DiVincenzo — 2002
Computational Depth Complexity of Measurement-Based Quantum ComputationDan E. Browne, Elham Kashefi, Simon Perdrix — 2009
Simulating quantum computers with probabilistic methodsMaarten Van den Nest — 2009
Bounds on the Power of Constant-Depth Quantum CircuitsFenner, Stephen, Frederic Green, Steven Homer — 2003
Threshold Computation and Cryptographic SecurityYenjo Han, Lane A. Hemaspaandra, Thomas Thierauf — 1993
Simulating quantum computers with probabilistic methodsMaarten Van den Nest — 2016
Quantum Computation and Quantum Information: BibliographyNikolay Raychev, I. Chuang — 2010
I Computational ComplexityH. Nader — 2005

Cited by

Quantum Schur Sampling Circuits can be Strongly Simulated.Thanasit Praipong — 2018
Computational perspectives on Bell Inequalities and many-body quantum correlationsMatty J. Hoban — 2012
Unconditionally verifiable blind quantum computationJoseph F. Fitzsimons, Elham Kashefi — 2012
Computational quantum-classical boundary of noisy commuting quantum circuitsKeisuke Fujii, Shuhei Tamate — 2016
Contagious error sources would need time travel to prevent quantum computationGil Kalai, Greg Kuperberg — 2014
On the computational power of quantum computersMartin Schwarz — 2013
The computational power of matchgates and the XY interaction on arbitrary graphsDaniel J. Brod, Andrew M. Childs — 2013
Implementing Unitary 2-Designs Using Random Diagonal-unitary MatricesYoshifumi Nakata, Christoph Hirche, Ciara Morgan — 2015
Average-case complexity versus approximate simulation of commuting quantum computationsMichael J. Bremner, Ashley Montanaro, Dan Shepherd — 2015
Trading Inverses for an Irrep in the Solovay-Kitaev TheoremAharonov, Dorit, Arad, Itai, Eban, Elad — 2017
Binary Matroids and Quantum Probability DistributionsDan Shepherd — 2010
The computational power of normalizer circuits over black-box groupsJuan Bermejo-Vega, Cedric Yen-Yu Lin, Maarten Van den Nest — 2014
Classical simulation complexity of extended Clifford circuitsRichard Jozsa, M. Van den Nest — 2013
Commuting quantum circuits: efficient classical simulations versus hardness resultsXiaotong Ni, Maarten Van den Nest — 2012
Quantum computing by interrogationIvan Šupić — 2014
Gaussian Noise Sensitivity and BosonSamplingGil Kalai, Guy Kindler — 2014
Classical Simulation of Yang-Baxter GatesGorjan Alagic, Aniruddha Bapat, Stephen P. Jordan — 2014
Efficient quantum walk on a quantum processorXiaogang Qiang, T. Loke, Ashley Montanaro — 2015
Blindness and Verification of Quantum Computation with One Pure QubitTheodoros Kapourniotis, Elham Kashefi, Animesh Datta — 2014
Abelian Hypergroups and Quantum ComputationJuan Bermejo-Vega, Kevin C. Zatloukal — 2015

Related papers

No related papers recorded.