[1]   Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang: Linear time algorithm for quantum 2SAT. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), volume 55 of LIPIcs, pp. 15:1–15:14. Schloss Dagstuhl, 2016. [doi:10.4230/LIPIcs.ICALP.2016.15, arXiv:1508.06340]

[2]    Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121–123, 1979. [doi:10.1016/0020-0190(79)90002-4]

[3]   Niel de Beaudrap and Sevag Gharibian: A linear time algorithm for quantum 2-SAT. In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), volume 50 of LIPIcs, pp. 27:1–27:21. Schloss Dagstuhl, 2016. [doi:10.4230/LIPIcs.CCC.2016.27, arXiv:1508.07338]

[4]   Sergey Bravyi: Efficient algorithm for a quantum analogue of 2-SAT. Contemporary Mathematics, 536:33–48, 2011. [doi:10.1090/conm/536, arXiv:quant-ph/0602108]

[5]   Jianxin Chen, Xie Chen, Ruanyao Duan, Zhengfeng Ji, and Bei Zeng: No-go theorem for one-way quantum computing on naturally occurring two-level systems. Phys. Rev. A, 83(5):050301, 2011. [doi:10.1103/PhysRevA.83.050301, arXiv:1004.3787]

[6]   Henri Cohen: A Course in Computational Algebraic Number Theory. Volume 138 of Graduate Texts in Mathematics. Springer, 1993. [doi:10.1007/978-3-662-02945-9]

[7]   Stephen A. Cook: The complexity of theorem-proving procedures. In Proc. 3rd STOC, pp. 151–158. ACM Press, 1971. [doi:10.1145/800157.805047]

[8]   Martin Davis, George Logemann, and Donald W. Loveland: A machine program for theorem-proving. Commun. ACM, 5(7):394–397, 1962. [doi:10.1145/368273.368557]

[9]   Martin Davis and Hilary Putnam: A computing procedure for quantification theory. J. ACM, 7(3):201–215, 1960. [doi:10.1145/321033.321034]

[10]   Jens Eisert, Marcus Cramer, and Martin B. Plenio: Area laws for the entanglement entropy. Rev. Mod. Phys., 82(1):277–306, 2010. [doi:10.1103/RevModPhys.82.277, arXiv:0808.3773]

[11]   Shimon Even, Alon Itai, and Adi Shamir: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691–703, 1976. Preliminary version in FOCS’75. [doi:10.1137/0205048]

[12]   David Gosset and Daniel Nagaj: Quantum 3-SAT is QMA₁-complete. SIAM J. Comput., 45(3):1080–1128, 2016. Preliminary version in FOCS’13. [doi:10.1137/140957056, arXiv:1302.0290]

[13]   David Harvey, Joris van der Hoeven, and Grégoire Lecerf: Even faster integer multiplication. J. Complexity, 36:1–30, 2016. [doi:10.1016/j.jco.2016.03.001, arXiv:1407.3360]

[14]   Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki: Separability of mixed states: necessary and sufficient conditions. Phys. Lett. A, 223(1–2):1–8, 1996. [doi:10.1016/S0375-9601(96)00706-2, arXiv:quant-ph/9605038]

[15]   Zhengfeng Ji, Zhaohui Wei, and Bei Zeng: Complete characterization of the ground-space structure of two-body frustration-free Hamiltonians for qubits. Phys. Rev. A, 84(4):042338, 2011. [doi:10.1103/PhysRevA.84.042338, arXiv:1010.2480]

[16]   Richard M. Karp: Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York, 1972. [doi:10.1007/978-1-4684-2001-2_9]

[17]   Alexei Yu. Kitaev: Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–30, 2003. [doi:10.1016/S0003-4916(02)00018-0, arXiv:quant-ph/9707021]

[18]    Alexei Yu. Kitaev, Alexander Shen, and Mikhail N. Vyalyi: Classical and Quantum Computation. Amer. Math. Soc., 2002. [doi:10.1090/gsm/047]

[19]   Melven R. Krom: The decision problem for a class of first-order formulas in which all disjunctions are binary. Mathematical Logic Quarterly, 13(1–2):15–20, 1967. [doi:10.1002/malq.19670130104]

[20]   Christopher R. Laumann, Roderich Moessner, Antonello Scarddichio, and Shivaji L. Sondhi: Random quantum satisfiability. Quantum Inf. Comput., 10(1):1–15, 2010. Link at ACM DL. [arXiv:0903.1904]

[21]   Leonid Anatolevich Levin: Universal sequential search problems. Problems of Information Transmission, 9(3):265–266, 1973. Available at Math-Net.Ru.

[22]   Christos H. Papadimitriou: On selecting a satisfying truth assignment (extended abstract). In Proc. 32nd FOCS, pp. 163–169. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SFCS.1991.185365]

[23]   Asher Peres: Separability criterion for density matrices. Phys. Rev. Lett., 77(8):1413–1415, 1996. [doi:10.1103/PhysRevLett.77.1413, arXiv:quant-ph/9604005]

[24]   Subir Sachdev: Quantum phase transitions. Wiley Online Library, 2007. [doi:10.1002/9780470022184.hmm108]

[25]   Guifre Vidal, José Ignacio Latorre, Enrique Rico, and Alexei Yu. Kitaev: Entanglement in quantum critical phenomena. Phys. Rev. Lett., 90(22):227902, 2003. [doi:10.1103/PhysRevLett.90.227902, arXiv:quant-ph/0211074]