Average-case complexity versus approximate simulation of commuting quantum computations

L. Stockmeyer, “On approximation algorithms for #P,” SIAM J. Comput. 14

1985

Earlier work this paper cites.

A. Ehrenfeucht and M. Karpinski, “The computational complexity of (XOR, AND)-counting problems,” (1990), technical Report 8543-CS

1990

Earlier work this paper cites.

J. Feigenbaum and L. Fortnow, “Random-Self-Reducibility of Complete Sets,” SIAM Journal on Computing 22

1993

Earlier work this paper cites.

C. Papadimitriou, Computational Complexity (Addison-Wesley, 1994)

1994

Earlier work this paper cites.

S. Fenner, L. Fortnow, and S. Kurtz, “Gap-definable counting classes,” J. Comput. Syst. Sci. 48

1994

Earlier work this paper cites.

P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput. 26

1997

Earlier work this paper cites.

C. Dawson, H. Haselgrove, A. Hines, D. Mortimer, M. Nielsen, and T. Osborne, “Quantum computing and polynomial equations over the finite field Z 2 Z_{2} ,” Quantum Inf. Comput. 5

2005

Earlier work this paper cites.

J. Majer, J. M. Chow, J. M. Gambetta, Jens Koch, B. R. Johnson, J. A. Schreier, L. Frunzio, D. I. Schuster, A. A. Houck, A. Wallraff, A. Blais, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf, “Coupling superconducting qubits via a cavity bus,” Nature 449

Original

2007

Earlier work this paper cites.

D. Shepherd and M. J. Bremner, “Temporally unstructured quantum computation,” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 465

Original

2009

Earlier work this paper cites.

T. Rudolph, “A simple encoding of a quantum circuit amplitude as a matrix permanent,” Phys. Rev. A 80

Original

2009

Earlier work this paper cites.

D. Shepherd, “Binary Matroids and Quantum Probability Distributions,” (2010), arXiv:1005.1744

Original

2010

Cited alongside, same era.

M. Bremner, R. Jozsa, and D. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,” Proc. R. Soc. A 467

Original

2011

Cited alongside, same era.

B. P. Lanyon, C. Hempel, D. Nigg, M. Müller, R. Gerritsma, F. Zähringer, P. Schindler, J. T. Barreiro, M. Rambach, G. Kirchmair, M. Hennrich, P. Zoller, R. Blatt, and C. F. Roos, “Universal Digital Quantum Simulation with Trapped Ions,” Science 334

Original

2011

Cited alongside, same era.

D. Browne, E. Kashefi, and S. Perdrix, “Computational depth complexity of measurement-based quantum computation,” in Proc. 6 th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC’11) (2011) pp. 35–46, arXiv:0909.4673

Original

2011

Cited alongside, same era.

K. Fujii and T. Morimae, “Quantum commuting circuits and complexity of Ising partition functions,” (2013), arXiv:1311.2128

Original

2013

Later among the works it cites.

I. Georgescu, S. Ashhab, and F. Nori, “Quantum simulation,” Rev. Mod. Phys. 86

Original

2014

Later among the works it cites.

S. Iblisdir, M. Cirio, O. Boada, and G. K. Brennen, “Low depth quantum circuits for Ising models,” Annals of Physics 340

Original

2014

Later among the works it cites.

L. A. Goldberg and H. Guo, “The complexity of approximating complex-valued Ising and Tutte partition functions,” (2014), arXiv:1409.5627

Original

2014

Later among the works it cites.

A. Sinclair, P. Srivastava, and M. Thurley, “Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs,” Journal of Statistical Physics 155