Impossibility of Classically Simulating One-Clean-Qubit Computation

Toda, S.: 𝖯𝖯 \mathsf{PP} is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991)

1991

Earlier work this paper cites.

Toda, S., Ogiwara, M.: Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput. 21(2), 316–328 (1992)

Original

1992

Earlier work this paper cites.

Tarui, J.: Probabilistic polynomials, 𝖠𝖢 0 \mathsf{AC}^{0} functions and the polynomial-time hierarchy. Theor. Comput. Sci. 113(1), 167–183 (1993)

1993

Earlier work this paper cites.

Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)

1995

Earlier work this paper cites.

Adleman, L.M., DeMarrais, J., Huang, M.D.A.: Quantum computability. SIAM J. Comput. 26(5), 1524–1540 (1997)

1997

Earlier work this paper cites.

Knill, E., Laflamme, R.: Power of one bit of quantum information. Phys. Rev. Lett. 81(25), 5672–5675 (1998)

1998

Earlier work this paper cites.

Fenner, S., Green, F., Homer, S., Pruim, R.: Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proc. R. Soc. A 455(1991), 3953–3966 (1999)

1999

Earlier work this paper cites.

Poulin, D., Laflamme, R., Milburn, G.J., Paz, J.P.: Testing integrability with a single bit of quantum information. Phys. Rev. A 68(2), article 022302 (2003)

2003

Earlier work this paper cites.

Poulin, D., Blume-Kohout, R., Laflamme, R., Ollivier, H.: Exponential speedup with a single bit of quantum information: Measuring the average fidelity decay. Phys. Rev. Lett. 92(17), article 177906 (2004)

2004

Earlier work this paper cites.

Terhal, B.M., DiVincenzo, D.P.: Adptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Inf. Comput. 4(2), 134–145 (2004)

2004

Earlier work this paper cites.

Aaronson, S.: Quantum computing, postselection, and probabilistic polynomial-time. Proc. R. Soc. A 461(2063), 3473–3482 (2005)

2005

Cited alongside, same era.

Datta, A., Flammia, S.T., Caves, C.M.: Entanglement and the power of one qubit. Phys. Rev. A 72(4), article 042316 (2005)

2005

Cited alongside, same era.

Fenner, S., Green, F., Homer, S., Zhang, Y.: Bounds on the power of constant-depth quantum circuits. In: Fundamentals of Computation Theory, 15th International Symposium, FCT 2005. Lecture Notes in Comput. Sci., vol. 3623, pp. 44–55 (2005)

2005

Cited alongside, same era.

Ambainis, A., Schulman, L.J., Vazirani, U.: Computing with highly mixed states. J. ACM 53(3), 507–531 (2006)

2006

Cited alongside, same era.

Böhler, E., Glaßer, C., Meister, D.: Error-bounded probabilistic computations between 𝖬𝖠 \mathsf{MA} and 𝖠𝖬 \mathsf{AM} . J. Comput. Syst. Sci. 72(6), 1043–1076 (2006)

Bremner, M.J., Jozsa, R., Shepherd, D.J.: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467(2126), 459–472 (2011)

2011

Later among the works it cites.

Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. Theory Comput. 9, 143–252 (article 4) (2013)

2013

Later among the works it cites.

Ni, X., Van den Nest, M.: Commuting quantum circuits: Efficient classical simulations versus hardness results. Quantum Inf. Comput. 13(1–2), 0054–0072 (2013)

2013

Later among the works it cites.

Brod, D.J.: The complexity of simulating constant-depth BosonSampling (2014), arXiv.org e-Print archive, arXiv:1412.6788 [quant-ph]

Original

2014

Closest in time.