The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
by Daniel Gottesman and Sandy Irani
Theory of Computing, Volume 9(2), pp. 31-116, 2013
Bibliography with links to cited articles
[1] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe: The power of quantum systems on a line. In Proc. 48th FOCS, pp. 373–383. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.46]
[2] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe: The power of quantum systems on a line. Comm. Math. Physics, 287(1):41–65, 2009. Preliminary version at arXiv. Extended abstract in FOCS’07. [doi:10.1007/s00220-008-0710-3]
[3] Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby: On the theory of average case complexity. J. Comput. System Sci., 44(2):193–219, 1992. Preliminary version in STOC’89. [doi:10.1016/0022-0000(92)90019-F]
[4] Robert Berger: The undecidability of the domino problem. Memoirs of the Am. Math. Soc., 66:1–72, 1966.
[5] 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]
[6] Alberto Bertoni, Massimiliano Goldwurm, and Violetta Lonati: The complexity of unary tiling recognizable picture languages: Nondeterministic and unambiguous cases. Fundam. Inform., 91(2):231–249, 2009. Preliminary version in STACS’07. [doi:10.3233/FI-2009-0042]
[7] Jean-Philippe Bouchaud and Marc Mézard: Self induced quenched disorder: A model for the glass transition. J. Phys. I France, 4(8):1109–1114, 1994. Preprint at arXiv. [doi:10.1051/jp1:1994240]
[8] David Deutsch: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Royal Society of London Series A, 400(1818):97–117, 1985. [doi:10.1098/rspa.1985.0070]
[9] Peter van Emde Boas: The convenience of tilings. In Andrea Sorbi, editor, Complexity, Logic, and Recursion Theory, pp. 331–363. Marcel Dekker Inc, 1997.
[10] Martin Fürer: The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). In Logic and Machines: Decision and Complexity, volume 171 of LNCS, pp. 312–319. Springer, 1984. [doi:10.1007/3-540-13331-3_48]
[11] Hana Galperin and Avi Wigderson: Succinct representations of graphs. Inf. Control, 56(3):183–198, 1983. [doi:10.1016/S0019-9958(83)80004-7]
[12] Daniel Gottesman and Sandy Irani: The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems, 2009. Conference version in FOCS’09. [arXiv:0905.2419]
[13] Erich Grädel: Dominoes and the complexity of subclasses of logical theories. Ann. Pure Appl. Logic, 43(1):1–30, 1989. [doi:10.1016/0168-0072(89)90023-7]
[14] Albert E. Ingham: On the difference between consecutive primes. Quarterly Journal of Mathematics (Oxford Series), 8(1):255–266, 1937. [doi:10.1093/qmath/os-8.1.255]
[15] Sandy Irani: Ground state entanglement in one dimensional translationally invariant quantum systems. J. Math. Phys., 51(2):022101, 2010. Preprint at arXiv. [doi:10.1063/1.3254321]
[16] Dominik Janzing, Pawel Wocjan, and Shengyu Zhang: A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation. New J. Phys., 10(9):093004, 2008. Preprint at arXiv. [doi:10.1088/1367-2630/10/9/093004]
[17] Emmanuel Jeandel and Pascal Vanier: Periodicity in tilings. In 14th Internat. Conf. Developments in Language Theory (DLT’10), pp. 243–254. Springer, 2010. Preprint at arXiv. [doi:10.1007/978-3-642-14455-4_23]
[18] Neil D. Jones and Alan L. Selman: Turing machines and the spectra of first-order formulas. J. Symbolic Logic, 39(1):139–150, 1974. Available at JSTOR. Preliminary version in STOC’72.
[19] A. S. Kahr, Edward F. Moore, and Hao Wang: Entscheidungsproblem reduced to the ∀∃∀ case. Proc. Natl. Acad. Sci. USA, 48(3):365–377, 1962. JSTOR.
[20] Alastair Kay: Computational power of symmetric Hamiltonians. Phys. Rev. A, 78(1):012346, 2008. Preprint at arXiv. [doi:10.1103/PhysRevA.78.012346]
[21] 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]
[22] Alexei Kitaev, Alexander H. Shen, and Michael N. Vyalyi: Classical and Quantum Computation. AMS, 2002. [ACM:863284]
[23] Leonid A. Levin: Average case complete problems. SIAM J. Comput., 15(1):285–286, 1986. Preliminary version in STOC’84. [doi:10.1137/0215020]
[24] Harry R. Lewis: Complexity of solvable cases of the decision problem for the predicate calculus. In Proc. 19th FOCS, pp. 35–47. IEEE Comp. Soc. Press, 1978. [doi:10.1109/SFCS.1978.9]
[25] Harry R. Lewis and Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 2 edition, 1997. [ACM:549820]
[26] Yi-Kai Liu, Matthias Christandl, and Frank Verstraete: Quantum computational complexity of the N-representability problem: QMA complete. Phys. Rev. Lett., 98(11):110503, 2007. Preprint at arXiv. [doi:10.1103/PhysRevLett.98.110503]
[27] Daniel Nagaj and Pawel Wocjan: Hamiltonian quantum cellular automata in one dimension. Phys. Rev. A, 78(3):032311, 2008. Preprint at arXiv. [doi:10.1103/PhysRevA.78.032311]
[28] Roberto Oliveira and Barbara M. Terhal: The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information & Computation, 8(10):900–924, 2008. Preprint at arXiv. [ACM:2016987]
[29] Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995.
[30] Christos H. Papadimitriou and Mihalis Yannakakis: A note on succinct representations of graphs. Inf. Control, 71(3):181–185, 1986. [doi:10.1016/S0019-9958(86)80009-2]
[31] Rohit Parikh: On context-free languages. J. ACM, 13(4):570–581, 1966. [doi:10.1145/321356.321364]
[32] Paul W. K. Rothemund and Erik Winfree: The program-size complexity of self-assembled squares. In Proc. 32nd STOC, pp. 459–468. ACM Press, 2000. [doi:10.1145/335305.335358]
[33] Leslie G. Valiant: The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410–421, 1979. [doi:10.1137/0208032]
[34] Hao Wang: Proving theorems by pattern recognition II. Bell Systems Technical Journal, 40:1–41, 1961.
[35] Erik Winfree: Algorithmic Self-Assembly of DNA. Ph. D. thesis, California Institute of Technology, 1998.