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

Built on

S. Toda, PP is as hard as the polynomial-time hierarchy
1991
Earlier work this paper cites.
C. Papadimitriou, Computational complexity
1994
Earlier work this paper cites.
Y. Han, L. Hemaspaandra and T. Thierauf, Threshold computation and cryptographic security
1997
Earlier work this paper cites.
D. Gottesman and I. Chuang, Demonstrating the viability of universal quantum computation using teleporttation and single-qubit operations
1999
Earlier work this paper cites.
M. Nielsen and I. Chuang, Quantum computation and quantum information
2000
Earlier work this paper cites.

B. Terhal and D. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
2004
Cited alongside, same era.
S. Aaronson, Quantum computing, post-selection and probabilistic polynomial time
2005
Cited alongside, same era.
S. Fenner, F. Green, S. Homer and Y. Zhang, Bounds on the power of constant-depth quantum circuits
2005
Cited alongside, same era.
D. J. Shepherd, Quantum complexity: restrictions on algorithms and architectures
2009
Cited alongside, same era.
D. Shepherd and M. J. Bremner, Temporally unstructured quantum computation , Proc. R. Soc. A 465
Original
2009
Cited alongside, same era.
D. Browne, E. Kashefi and S. Perdrix, Computational depth complexity of measurement-based quantum computation
Original
Cited in the paper.
S. Jordan, Permutational quantum computing
Original
Cited in the paper.
S. Aaronson, BQP and the polynomial hierarchy
Original
Cited in the paper.
M. Van den Nest, Simulating Quantum Computers With Probabilistic Methods
Original
Cited in the paper.
G. Kuperberg, How hard is it to approximate the Jones polynomial?
Original
Cited in the paper.

P. Aliferis, F. Brito, D. P. DiVincenzo, J. Preskill, M. Steffen, and B. M. Terhal, Fault-Tolerant Computing With Biased-Noise Superconducting Qubits , New J. Phys. 11
Original
2009
Later among the works it cites.
S. Arora and B. Barak, Computational complexity: a modern approach
2009
Later among the works it cites.
R. Jozsa, B. Kraus, A. Miyake and J. Watrous, Matchgate and space-bounded quantum computations are equivalent
Original
2010
Closest in time.
D. Shepherd, Binary matroids and quantum probability distributions
2010
Closest in time.
S. Aaronson and A. Arkhipov, New evidence that quantum mechanics is hard to simulate on classical computers
2010
Closest in time.