[1]   Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão, and Or Sattath: The pursuit for uniqueness: extending Valiant-Vazirani theorem to the probabilistic and quantum settings, 2008. arXiv:0810.4840.

[2]   Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe: The power of quantum systems on a line. Comm. Math. Phys., 287(1):41–65, 2009. Preliminary version in FOCS’07. [doi:10.1007/s00220-008-0710-3]

[3]   Dorit Aharonov and Tomer Naveh: Quantum NP - A survey, 2002. arXiv:quant-ph/0210077.

[4]   Eric W. Allender: The complexity of sparse sets in P (preliminary report). In Proc. 1st Structure in Complexity Theory Conf. (1986), volume 223 of Lecture Notes in Comput. Sci., pp. 1–11. Springer, 1986. [doi:10.1007/3-540-16486-3_85]

[5]   Eric W. Allender and Roy S. Rubinstein: P-printable sets. SIAM J. Comput., 17(6):1193–1202, 1988. [doi:10.1137/0217075]

[6]   László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM Press, 1985. [doi:10.1145/22145.22192]

[7]   Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello: Stabilization of quantum computations by symmetrization. SIAM J. Comput., 26(5):1541–1557, 1997. [doi:10.1137/S0097539796302452]

[8]   Rajendra Bhatia: Matrix Analysis. Volume 169 of Graduate Texts in Mathematics. Springer, 1997. Springer.

[9]   Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf: Quantum fingerprinting. Phys. Rev. Lett., 87(16), 2001. arXiv:quant-ph/0102001. [doi:10.1103/PhysRevLett.87.167902]

[10]   Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser: Quantum computation by adiabatic evolution. 2000. arXiv:quant-ph/0001106.

[11]   Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85. [doi:10.1137/0218012]

[12]   Joachim Grollmann and Alan L. Selman: Complexity measures for public-key cryptosystems. SIAM J. Comput., 17(2):309–335, 1988. Preliminary version in FOCS’84. [doi:10.1137/0217018]

[13]   Matthew B. Hastings: An area law for one-dimensional quantum systems. J. Statistical Mechanics: Theory and Experiment, 2007(8):P08024, 2007. arXiv:0705.2024. [doi:10.1088/1742-5468/2007/08/P08024]

[14]   Lane A. Hemaspaandra, Sanjay Jain, and Nikolai K. Vereshchagin: Banishing robust Turing completeness. Internat. J. Found. Comput. Sci., 4(3):245–265, 1993. Preliminary version in LFCS’92. [doi:10.1142/S012905419300016X]

[15]   Alfred Horn: Doubly stochastic matrices and the diagonal of a rotation matrix. Amer. J. Math., 76(3):620–630, 1954. [doi:10.2307/2372705]

[16]   Dominik Janzing, Pavel Wocjan, and Thomas Beth: Identity check is QMA-complete, 2003. arXiv:quant-ph/0305050.

[17]    Alastair Kay: Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems. Phys. Rev. A, 76(3):030307, 2007. arXiv:0704.3142. [doi:10.1103/PhysRevA.76.030307]

[18]   Julia Kempe, Alexei Kitaev, and Oded Regev: The complexity of the Local Hamiltonian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04. [doi:10.1137/S0097539704445226]

[19]   Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi: Classical and Quantum Computation. Volume 47 of Graduate Studies in Mathematics. Amer. Math. Soc., 2002. Translated from the 1999 Russian original by Lester J. Senechal, AMS.

[20]   Emanuel Knill: Quantum randomness and nondeterminism, 1996. arXiv:quant-ph/9610012.

[21]   Ker-I Ko: On some natural complete operators. Theoret. Comput. Sci., 37(1):1–30, 1985. [doi:10.1016/0304-3975(85)90085-4]

[22]   Johannes Köbler, Uwe Schöning, Seinosuke Toda, and Jacobo Torán: Turing machines with few accepting computations and low sets for PP. J. Comput. System Sci., 44(2):272–286, 1992. Preliminary version in Structure In Complexity Theory, 1989. [doi:10.1016/0022-0000(92)90022-B]

[23]   Yi-Kai Liu: Consistency of local density matrices is QMA-complete. In Proc. 10th Internat. Workshop on Randomization and Computation (RANDOM’06), volume 4110 of Lecture Notes in Comput. Sci., pp. 438–449. Springer, 2006. arXiv:quant-ph/0604166. [doi:10.1007/11830924_40]

[24]   Yi-Kai Liu, Matthias Christandl, and Frank Verstraete: Quantum computational complexity of the N-representability problem: QMA-complete. Phys. Rev. Lett., 98(11), 2007. arXiv:quant-ph/0609125. [doi:10.1103/PhysRevLett.98.110503]

[25]   Chris Marriott and John Watrous: Quantum Arthur-Merlin games. Comput. Complexity, 14(2):122–152, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0194-x]

[26]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000. [doi:10.1017/CBO9780511976667]

[27]   Roberto Oliveira and Barbara Terhal: The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput., 8(10):900–924, 2008. arXiv:quant-ph/0504050. [ACM:2016987]

[28]   Rajesh P. N. Rao, Jörg Rothe, and Osamu Watanabe: Upward separation for FewP and related classes. Inform. Process. Lett., 52(4):175 – 180, 1994. [doi:10.1016/0020-0190(94)90123-6]

[29]   Or Sattath: The pursuit of uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings. Master’s thesis, Hebrew University in Jerusalem, 2009.

[30]   Jacobo Torán: Counting the number of solutions. A survey of recent inclusion results in the area of counting classes. In Mathematical Foundations of Computer Science (MFCS’90), volume 452 of Lecture Notes in Comput. Sci., pp. 121–134. Springer, 1990. [doi:10.1007/BFb0029600]

[31]   Leslie G. Valiant and Vijay V. Vazirani: NP is as easy as detecting unique solutions. Theoret. Comput. Sci., 47(1):85–93, 1986. Preliminary version in STOC’85. [doi:10.1016/0304-3975(86)90135-0]

[32]   John Watrous: Succinct quantum proofs for properties of finite groups. In Proc. 41st FOCS, pp. 537–546. IEEE Comp. Soc. Press, 2000. arXiv:cs/0009002. [doi:10.1109/SFCS.2000.892141]