[1]    Scott Aaronson: Algorithms for Boolean function query properties. SIAM J. Comput., 32(5):1140–1157, 2003. [doi:10.1137/S0097539700379644]

[2]   Scott Aaronson: Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. A, 461(2063):3473–3482, 2005. Preprint at arXiv. [doi:10.1098/rspa.2005.1546]

[3]   Scott Aaronson: BQP and the polynomial hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. Preprint at arXiv. [doi:10.1145/1806689.1806711]

[4]   Scott Aaronson: The equivalence of sampling and searching. In 6th Internat. Comp. Sci. Symp. in Russia (CSR’11), pp. 1–14. Springer, 2011. Available at ECCC. Preprint at arXiv. [doi:10.1007/978-3-642-20712-9_1]

[5]   Scott Aaronson and Daniel Gottesman: Improved simulation of stabilizer circuits. Phys. Rev. A, 70(5):052328, 2004. Preprint at arXiv. [doi:10.1103/PhysRevA.70.052328]

[6]   Daniel S. Abrams and Seth Lloyd: Simulation of many-body Fermi systems on a universal quantum computer. Phys. Rev. Lett., 79(13):2586–2589, 1997. Preprint at arXiv. [doi:10.1103/PhysRevLett.79.2586]

[7]   Dorit Aharonov and Michael Ben-Or: Fault-tolerant quantum computation with constant error rate. SIAM J. Comput., 38(4):1207–1282, 2008. Preliminary version in STOC’97. Preprint at arXiv. [doi:10.1137/S0097539799359385]

[8]   Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, and Sushant Sachdeva: Testing permanent oracles - revisited. In Proc. 16th Internat. Workshop on Randomization and Computation (RANDOM’12), pp. 362–373, 2012. Available at ECCC. Preprint at arXiv. [doi:10.1007/978-3-642-32512-0_31]

[9]   Stephen D. Bartlett and Barry C. Sanders: Requirement for quantum computation. J. Modern Optics, 50(15-17):2331–2340, 2003. Preprint at arXiv. [doi:10.1080/09500340308233564]

[10]   Carlo W. J. Beenakker, David P. DiVincenzo, Clive Emary, and Marco Kindermann: Charge detection enables free-electron quantum computation. Phys. Rev. Lett., 93(2):020501, 2004. Preprint at arXiv. [doi:10.1103/PhysRevLett.93.020501]

[11]   Ethan Bernstein and Umesh Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]

[12]   Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. A, 467(2126):459–472, 2011. Preprint at arXiv. [doi:10.1098/rspa.2010.0301]

[13]   Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy C. Ralph, and Andrew G. White: Photonic boson sampling in a tunable circuit. Science, 2012 (online). Preprint at arXiv. [doi:10.1126/science.1231440]

[14]   Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358–368. IEEE Comp. Soc. Press, 1999. Preprint at arXiv. [doi:10.1109/SFFCS.1999.814607]

[15]   Eduardo R. Caianiello: On quantum field theory, I: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs. Nuovo Cimento, 10(12):1634–1652, 1953. [doi:10.1007/BF02781659]

[16]   David M. Ceperley: An overview of quantum Monte Carlo methods. Reviews in Mineralogy and Geochemistry, 71(1):129–135, 2010. [doi:10.2138/rmg.2010.71.6]

[17]   Richard Cleve and John Watrous: Fast parallel circuits for the quantum Fourier transform. In Proc. 41st FOCS, pp. 526–536. IEEE Comp. Soc. Press, 2000. Preprint at arXiv. [doi:10.1109/SFCS.2000.892140]

[18]   Kevin P. Costello and Van H. Vu: Concentration of random determinants and permanent estimators. SIAM J. Discrete Math., 23(3):1356–1371, 2009. Preprint at arXiv. [doi:10.1137/080733784]

[19]   Andrea Crespi, Roberto Osellame, Roberta Ramponi, Daniel J. Brod, Ernesto F. Galvão, Nicolò Spagnolo, Chiara Vitelli, Enrico Maiorino, Paolo Mataloni, and Fabio Sciarrino: Experimental boson sampling in arbitrary integrated photonic circuits. 2012. [arXiv:1212.2783]

[20]   Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. Commun. ACM, 52(2):89–97, 2009. [doi:10.1145/1461928.1461951]

[21]   Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195–259, 2009. Preliminary version in STOC’06. [doi:10.1137/070699652]

[22]   Georgy P. Egorychev: Proof of the van der Waerden conjecture for permanents. Sibirsk. Mat. Zh., 22(6):65–71, 1981. English translation in Siberian Math. J. 22 (6), pp. 854-859, 1981. [doi:10.1007/BF00968054]

[23]   Dmitry I. Falikman: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix. Mat. Zametki, 29(6):931–938, 1981. English translation in Math. Notes 29 (6), pp. 475-479, 1981. [doi:10.1007/BF01163285]

[24]   Bill Fefferman and Chris Umans: Pseudorandom generators and the BQP vs. PH problem. 2010. [arXiv:1007.0305]

[25]   Stephen Fenner, Frederic Green, Steven Homer, and Randall Pruim: Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proc. Roy. Soc. A, 455(1991):3953–3966, 1999. Preprint at arXiv. [doi:10.1098/rspa.1999.0485]

[26]   Richard P. Feynman: Simulating physics with computers. Int. J. Theoretical Physics, 21(6-7):467–488, 1982. [doi:10.1007/BF02650179]

[27]    Lance Fortnow and John D. Rogers: Complexity limitations on quantum computation. J. Comput. System Sci., 59(2):240–252, 1999. Preliminary version in CCC’98. Preprint at arXiv. [doi:10.1006/jcss.1999.1651]

[28]   Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson: Self-testing/correcting for polynomials and for approximate functions. In Proc. 23rd STOC, pp. 33–42. ACM Press, 1991. [doi:10.1145/103418.103429]

[29]   Peter Gemmell and Madhu Sudan: Highly resilient correctors for polynomials. Inform. Process. Lett., 43(4):169–174, 1992. [doi:10.1016/0020-0190(92)90195-2]

[30]   Viacheslav L. Girko: A refinement of the Central Limit Theorem for random determinants. Teor. Veroyatnost. i Primenen, 42(1):63–73, 1997. Translation in Theory Probab. Appl 42 (1) (1998), 121-129. [doi:10.1137/S0040585X97975939]

[31]   Chris D. Godsil and Ivan Gutman: On the matching polynomial of a graph. In Algebraic Methods in Graph Theory I, pp. 241–249. North Holland, 1981.

[32]   Daniel Gottesman, Alexei Kitaev, and John Preskill: Encoding a qubit in an oscillator. Phys. Rev. A, 64(1):012310, 2001. Preprint at arXiv. [doi:10.1103/PhysRevA.64.012310]

[33]   Leonid Gurvits: On the complexity of mixed discriminants and related problems. In 30th Internat. Symp. Mathematical Foundations of Computer Science (MFCS’05), pp. 447–458. Springer, 2005. [doi:10.1007/11549345_39]

[34]   Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf: Threshold computation and cryptographic security. SIAM J. Comput., 26(1):59–78, 1997. Preliminary version in ISAAC’93. [doi:10.1137/S0097539792240467]

[35]   Johan Håstad: Computational Limitations for Small Depth Circuits. MIT Press, 1987.

[36]   C. K. Hong, Zhe-Yu Ou, and Leonard Mandel: Measurement of subpicosecond time intervals between two photons by interference. Phys. Rev. Lett., 59(18):2044–2046, 1987. [doi:10.1103/PhysRevLett.59.2044]

[37]   Mark Jerrum, Alistair Sinclair, and Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671–697, 2004. Preliminary version in STOC’01. [doi:10.1145/1008731.1008738]

[38]   Tiefeng Jiang: How many entries of a typical orthogonal matrix can be approximated by independent normals? Ann. Probab., 34(4):1497–1529, 2006. [doi:10.1214/009117906000000205]

[39]   Stephen P. Jordan: Permutational quantum computing. Quantum Information & Computation, 10(5):470–497, 2010. Preprint at arXiv. [ACM:2011369]

[40]   Subhash Khot: On the Unique Games Conjecture. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 99–121. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.19]

[41]   Emanuel Knill: Fermionic linear optics and matchgates. 2001. [arXiv:quant-ph/0108033]

[42]   Emanuel Knill and Raymond Laflamme: Power of one bit of quantum information. Phys. Rev. Lett., 81(25):5672–5675, 1998. Preprint at arXiv. [doi:10.1103/PhysRevLett.81.5672]

[43]   Emanuel Knill, Raymond Laflamme, and Gerard J. Milburn: A scheme for efficient quantum computation with linear optics. Nature, 409(6816):46–52, 2001. See also arXiv:quant-ph/0006088. [doi:10.1038/35051009]

[44]   Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek: Resilient quantum computation. Science, 279(5349):342–345, 1998. Preprint at arXiv. [doi:10.1126/science.279.5349.342]

[45]   Kenneth Lange: Applied Probability. Springer, 2003.

[46]   Yuan Liang Lim and Almut Beige: Generalized Hong-Ou-Mandel experiments with bosons and fermions. New J. Phys., 7(155):1–10, 2005. Preprint at arXiv. [doi:10.1088/1367-2630/7/1/155]

[47]   Richard J. Lipton: New directions in testing. In Distributed Computing and Cryptography, pp. 191–202. AMS, 1991.

[48]   Brahim Lounis and Michel Orrit: Single-photon sources. Reports on Progress in Physics, 68(5):1129–1179, 2005. [doi:10.1088/0034-4885/68/5/R04]

[49]   Christian Mastrodonato and Roderich Tumulka: Elementary proof for asymptotics of large Haar-distributed unitary matrices. Letters in Mathematical Physics, 82(1):51–59, 2007. Preprint at arXiv. [doi:10.1007/s11005-007-0194-7]

[50]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[51]   Ramamohan Paturi: On the degree of polynomials that approximate symmetric Boolean functions. In Proc. 24th STOC, pp. 468–474. ACM Press, 1992. [doi:10.1145/129712.129758]

[52]   Dénes Petz and Júlia Réffy: On asymptotics of large Haar distributed unitary matrices. Periodica Mathematica Hungarica, 49(1):103–117, 2004. Preprint at arXiv. [doi:10.1023/B:MAHU.0000040542.56072.ab]

[53]   Dénés Petz and Júlia Réffy: Large deviation theorem for the empirical eigenvalue distribution of truncated Haar unitary matrices. Prob. Theory and Related Fields, 133(2):175–189, 2005. Preprint at arXiv. [doi:10.1007/s00440-004-0420-5]

[54]   Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani: Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73(1):58–61, 1994. [doi:10.1103/PhysRevLett.73.58]

[55]   Júlia Réffy: Asymptotics of random unitaries. Ph. D. thesis, Budapest University of Technology and Economics, 2005. http://www.math.bme.hu/~reffyj/disszer.pdf.

[56]   Terry Rudolph: A simple encoding of a quantum circuit amplitude as a matrix permanent. Phys. Rev. A, 80(5), 2009. [doi:10.1103/PhysRevA.80.054302, arXiv:0909.3005]

[57]   Stefan Scheel: Permanents in linear optical networks. 2004. [arXiv:quant-ph/0406127]

[58]   Dan Shepherd and Michael J. Bremner: Temporally unstructured quantum computation. Proc. Roy. Soc. A, 465(2105):1413–1439, 2009. Preprint at arXiv. [doi:10.1098/rspa.2008.0443]

[59]   Yaoyun Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information & Computation, 3(1):84–92, 2003. Preprint at arXiv. [ACM:2011515]

[60]   Peter W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. Preliminary version in FOCS’94. Preprint at arXiv. [doi:10.1137/S0097539795293172]

[61]   Daniel R. Simon: On the power of quantum computation. SIAM J. Comput., 26(5):1474–1483, 1997. Preliminary version in FOCS’94. [doi:10.1137/S0097539796298637]

[62]   Justin B. Spring, Benjamin J. Metcalf, Peter C. Humphreys, W. Steven Kolthammer, Xian-Min Jin, Marco Barbieri, Animesh Datta, Nicholas Thomas-Peter, Nathan K. Langford, Dmytro Kundys, James C. Gates, Brian J. Smith, Peter G. R. Smith, and Ian A. Walmsley: Boson sampling on a photonic chip. Science, 2012 (online). Preprint at arXiv. [doi:10.1126/science.1231692]

[63]   Larry J. Stockmeyer: On approximation algorithms for #P. SIAM J. Comput., 14(4):849–861, 1985. Preliminary version in STOC’83. [doi:10.1137/0214060]

[64]   Madhu Sudan: Maximum likelihood decoding of Reed Solomon codes. In Proc. 37th FOCS, pp. 164–172. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548475]

[65]   Terence Tao and Van H. Vu: On the permanent of random Bernoulli matrices. Advances in Mathematics, 220(3):657–669, 2009. Preprint at arXiv. [doi:10.1016/j.aim.2008.09.006]

[66]   Barbara M. Terhal and David P. DiVincenzo: Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A, 65(3):032325, 2002. Preprint at arXiv. [doi:10.1103/PhysRevA.65.032325]

[67]   Barbara M. Terhal and David P. DiVincenzo: Adaptive quantum computation, constant-depth quantum circuits and Arthur-Merlin games. Quantum Information & Computation, 4(2):134–145, 2004. Preprint at arXiv. [ACM:2011582]

[68]   Max Tillmann, Borivoje Dakić, René Heilmann, Stefan Nolte, Alexander Szameit, and Philip Walther: Experimental boson sampling. 2012. [arXiv:1212.2240]

[69]   Seinosuke Toda: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. Preliminary version in FOCS’89. [doi:10.1137/0220053]

[70]   Lidror Troyansky and Naftali Tishby: Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix. In Proc. 4th Workshop on Physics and Computation (PhysComp’96), 1996. Available here.

[71]    Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/0304-3975(79)90044-6]

[72]   Leslie G. Valiant: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput., 31(4):1229–1254, 2002. Preliminary version in STOC’01. [doi:10.1137/S0097539700377025]

[73]   Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood, and Isaac L. Chuang: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866):883–887, 2001. Preprint at arXiv. [doi:10.1038/414883a]

[74]   Jin yi Cai, Aduri Pavan, and D. Sivakumar: On the hardness of permanent. In Proc. 16th Symp. Theoretical Aspects of Comp. Sci. (STACS’99), pp. 90–99, 1999. [doi:10.1007/3-540-49116-3_8]