Geodesic
Undecidability of the Spectral Gap
Forum of Mathematics, Pi, Tome 10 (2022)

Voir la notice de l'article provenant de la source Cambridge University Press

We construct families of translationally invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson’s aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians. 
@article{10_1017_fmp_2021_15,
     author = {Toby Cubitt and David Perez-Garcia and Michael M. Wolf},
     title = {Undecidability of the {Spectral} {Gap}},
     journal = {Forum of Mathematics, Pi},
     publisher = {mathdoc},
     volume = {10},
     year = {2022},
     doi = {10.1017/fmp.2021.15},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2021.15/}
}
TY  - JOUR
AU  - Toby Cubitt
AU  - David Perez-Garcia
AU  - Michael M. Wolf
TI  - Undecidability of the Spectral Gap
JO  - Forum of Mathematics, Pi
PY  - 2022
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2021.15/
DO  - 10.1017/fmp.2021.15
LA  - en
ID  - 10_1017_fmp_2021_15
ER  - 
%0 Journal Article
%A Toby Cubitt
%A David Perez-Garcia
%A Michael M. Wolf
%T Undecidability of the Spectral Gap
%J Forum of Mathematics, Pi
%D 2022
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2021.15/
%R 10.1017/fmp.2021.15
%G en
%F 10_1017_fmp_2021_15
Toby Cubitt; David Perez-Garcia; Michael M. Wolf. Undecidability of the Spectral Gap. Forum of Mathematics, Pi, Tome 10 (2022). doi: 10.1017/fmp.2021.15

[1] Affleck, I., Kennedy, T., Lieb, E. H. and Tasaki, H., ‘Valence bond ground states in isotropic quantum antiferromagnets’, Commun. Math. Phys. 115 (1988), 477–528.Google Scholar | DOI

[2] Aharonov, D., Gottesman, D., Irani, S. and Kempe, J., ‘The power of quantum systems on a line’, Commun. Math. Phys. 287 (2009), 41–65.Google Scholar | DOI

[3] Aizenmann, M., ‘Open problems in mathematical physics’, 1998. http://web.math.princeton.edu/ aizenman/OpenProblems.iamp.Google Scholar

[4] Anderson, P. W., ‘More is different’, Science 177 (1972), 393–396.Google ScholarPubMed | DOI

[5] Anderson, P. W., ‘Resonating valence bonds: a new kind of insulator?’, Mater. Res. Bull. 8 (1973), 153–160.Google Scholar | DOI

[6] Arad, I., Kitaev, A., Landau, Z. and Vazirani, U., ‘An area law and sub-exponential algorithm for 1D systems’, Preprint, 2013, .Google Scholar | arXiv

[7] Arad, I., Landau, Z., Vazirani, U. and Vidick, T., ‘Rigorous RG algorithms and area laws for low energy eigenstates in 1D’, Commun. Math. Phys. 356 (2017), 65–105.Google Scholar | DOI

[8] Bausch, J., Cubitt, T., Lucia, A. and Perez-Garcia, D., ‘Undecidability of the spectral gap in one dimension’, Phys. Rev. X (2020), 031038.Google Scholar | DOI

[9] Bausch, J., Cubitt, T. and Watson, J. D., ‘Uncomputability of phase diagrams’, Nat. Commun. (2021), 452.Google Scholar | DOI

[10] Bausch, J., Cubitt, T. S. and Ozols, M., ‘The complexity of translationally-invariant spin chains with low local dimension’, Ann. Henri Poincare 18 (2017), 3449–3513.Google Scholar | DOI

[11] Bausch, J., T. S. Cubitt, Lucia, A., Perez-Garcia, D. and Wolf, M. M., Size-driven quantum phase transitions’, Proc. Natl. Acad. Sci. (USA) 115 (2018), 19–23.Google ScholarPubMed | DOI

[12] Bendersky, A., Senno, G., De La Torre, G., Figueira, S. and Acin, A., ‘Non-signaling deterministic models for non-local correlations have to be uncomputable’, Phys. Rev. Lett. 118 (2017), 130401.Google Scholar | DOI

[13] Bennett, C. H., ‘Logical reversibility of computation’, IBM J. Res. Develop. 17 (1973), 525–532.Google Scholar | DOI

[14] Bennett, C. H., ‘Undecidable dynamics’, Nature 346 (1990), 606–607.Google Scholar | DOI

[15] Berger, R., ‘The undecidability of the domino problem’, Mem. Amer. Math. Soc. 66 (1966), 1–72.Google Scholar

[16] Bernstein, E. and Vazirani, U., ‘Quantum complexity theory’, SIAM J. Comput. 26(5) (1997), 1411–1473.Google Scholar | DOI

[17] Blum, L. and Smale, S., ‘The Gödel incompleteness theorem and decidability over a ring’, in Hirsch, M. W., Marsden, J. E. and Shub, M., eds., From Topology to Computation: Proceedings of the Smalefest (Springer, New York, 1993), 321–339.Google Scholar | DOI

[18] Bravyi, S. and Gosset, D., ‘Gapped and gapless phases of frustration-free spin-1/2 chains’, J. Math. Phys. 56 (2015), 061902.Google Scholar | DOI

[19] Bravyi, S., Hastings, M. and Michalakis, S., ‘Topological quantum order: stability under local perturbations’, J. Math. Phys. 51 (2010), 093512.Google Scholar | DOI

[20] Cubitt, T., Gu, M., Perales, A, Perez-Garcia, D. and Wolf, M. M., ‘Undecidability in physics: a quantum information perspective’, In preparation, 2022.Google Scholar

[21] G. De las Cuevas, Cubitt, T. S., Cirac, J. I., Wolf, M. M. and Pérez-García, D., ‘Fundamental limitations in the purifications of tensor networks’, J. Math. Phys. 57(7) (2016), 071902.Google Scholar

[22] Cubitt, T. S., Perez-Garcia, D. and Wolf, M. M., ‘Undecidability of the spectral gap’, Nature 528 (2015), 207–211.Google ScholarPubMed | DOI

[23] Cubitt, T. S, Perez-Garcia, D. and Wolf, M. M, ‘Comment on “On the uncomputability of the spectral gap’, Preprint, 2016, .Google Scholar | arXiv

[24] De Roeck, W. and Salmhofer, M., ‘Persistence of exponential decay and spectral gaps for interacting fermions’, Commun. Math. Phys. 365(2) (2019), 773–796.Google Scholar | DOI

[25] Domany, E. and Kinzel, W., ‘Equivalence of cellular automata to Ising models and directed percolation’, Phys. Rev. Lett. 53(4) (1984), 311.Google Scholar | DOI

[26] Eisert, J., Cramer, M. and Plenio, M. B, ‘Colloquium: area laws for the entanglement entropy’, Rev. Modern Phys. 82(1) (2010), 277.Google Scholar | DOI

[27] Eisert, J., Müller, M. P. and Gogolin, C., ‘Quantum measurement occurrence is undecidable’, Phys. Rev. Lett. 108 (2012), 260501, 6.Google ScholarPubMed | DOI

[28] Elkouss, D. and Pérez-García, D., ‘Memory effects can make the transmission capability of a communication channel uncomputable’, Nat. Commun. 9 (2018), 1149.Google ScholarPubMed | DOI

[29] Fernández-González, C., Schuch, N., Wolf, M. M., Cirac, J. I. and Pérez-García, D., ‘Frustration free gapless Hamiltonians for matrix product states’, Commun. Math. Phys. 333 (2015), 299–333.Google Scholar | DOI

[30] Feynman, R., ‘Quantum mechanical computers’, Optics News 11 (1985), 11–20.Google Scholar | DOI

[31] Fredkin, E. and Toffoli, T., ‘Conservative logic’, Int. J. Theoret. Phys. 21(3) (1982), 219–253.Google Scholar | DOI

[32] Gottesman, D. and Irani, S., ‘The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems’, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS’09 (IEEE Computer Society, Washington, DC, 2009), 95–104.Google Scholar

[33] Grünbaum, B. and Shephard, G. C., Tilings and Patterns (W.H. Freeman and Company, New York, 1987).Google Scholar

[34] Gu, M., Weedbrook, C., Perales, A. and Nielsen, M. A., ‘More really is different’, Physica D 238 (2009 835–839.Google Scholar | DOI

[35] Haegeman, J., Michalakis, S., Nachtergaele, B., Osborne, T. J, Schuch, N. and Verstraete, F., ‘Elementary excitations in gapped quantum spin systems’, Phys. Rev. Lett. 111(8) (2013), 080401.Google ScholarPubMed | DOI

[36] Haldane, F. D. M., ‘Nonlinear field theory of large-spin Heisenberg antiferromagnets: semiclassically quantized solitons of the one-dimensional easy-axis Néel state’, Phys. Rev. Lett. 50 (1983), 1153–1156.Google Scholar | DOI

[37] Han, T.-H., Helton, J. S., Chu, S., Nocera, D. G., Rodriguez-Rivera, J. A., Broholm, C. and Lee, Y. S., ‘Fractionalized excitations in the spin-liquid state of a Kagome-lattice antiferromagnet’, Nature 492 (2012), 406–410.Google ScholarPubMed | DOI

[38] Hastings, M. B., ‘Lieb-Schultz-Mattis in higher dimensions’, Phys. Rev. B 69 (2004), 104431.Google Scholar | DOI

[39] Hastings, M. B., ‘An area law for one-dimensional quantum systems’, J. Stat. Mech.: Theory and Experiment 2007(8) (2007), P08024.Google Scholar

[40] Hastings, M. B, ‘Entropy and entanglement in quantum ground states’, Phys. Rev. B 76(3) (2007), 035114.Google Scholar | DOI

[41] Hastings, M. B., ‘The stability of free fermi Hamiltonians’, J. Math. Phys. (2019), 042201.Google Scholar | DOI

[42] Hastings, M.B. and Koma, T., ‘Spectral gap and exponential decay of correlations’, Commun. Math. Phys., 265 (2006), 781–804.Google Scholar | DOI

[43] Hofstadter, D. R., ‘Energy levels and wave functions of Bloch electrons in rational and irrational magnetic fields’, Phys. Rev. B 14(9) (1976), 2239–2249.Google Scholar | DOI

[44] Iqbal, Y., Poilblanc, D. and Becca, F., ‘Vanishing spin gap in a competing spin-liquid phase in the Kagome Heisenberg antiferromagnet’, Phys. Rev. B 89(2) (2014), 020407.Google Scholar | DOI

[45] Kanter, I., ‘Undecidability principle and the uncertainty principle even for classical systems’, Phys. Rev. Lett. 64 (1990), 332–335.Google ScholarPubMed | DOI

[46] Kempe, J., Kitaev, A. and Regev, O., ‘The complexity of the local Hamiltonian problem’, SIAM J. Comput. 35 (2006), 1070–1097.Google Scholar | DOI

[47] Kitaev, A. Y., Shen, A. H. and Vyalyi, M. N., ‘Classical and Quantum Computation, Graduate Studies in Mathematics, Vol. 47 (American Mathematical Society, Providence, RI, 2002).Google Scholar

[48] Kliesch, M., Gross, D. and Eisert, J., ‘Matrix-product operators and states: NP-hardness and undecidability’, Phys. Rev. Lett. 113 (2014), 160503.Google ScholarPubMed | DOI

[49] Komar, A., ‘Undecidability of macroscopically distinguishable states in quantum field theory’, Phys. Rev. 133 (1964), B542–B544.Google Scholar | DOI

[50] Kozen, D., Automata and Computability (Springer Science & Business Media, New York, 1997).Google Scholar | DOI

[51] Landau, Z., Vazirani, U. and Vidick, T., ‘A polynomial-time algorithm for the ground state of one-dimensional gapped local Hamiltonians’, Nat. Phys. 11 (2013), 566–569.Google Scholar | DOI

[52] Lemm, M., Sandvik, A. W. and Wang, L., ‘Existence of a spectral gap in the Affleck–Kennedy–Lieb–Tasaki model on the hexagonal lattice’, Phys. Rev. Lett. 124(17) (2020), 177204.Google ScholarPubMed | DOI

[53] Lieb, E. H., Schultz, T. D. and Mattis, D. C., ‘Two soluble models of an antiferromagnetic chain’, Ann. Phys. 16 (1961), 407–466.Google Scholar | DOI

[54] Lloyd, S., ‘Quantum-mechanical computers and uncomputability’, Phys. Rev. Lett. 71(6) (1993), 943.Google ScholarPubMed | DOI

[55] Lloyd, S., ‘Necessary and sufficient conditions for quantum computation’, J. Modern Opt. 41(12) (1994), 2503–2520.Google Scholar | DOI

[56] Lloyd, S., ‘On the uncomputability of the spectral gap’, Preprint, 2016, .Google Scholar | arXiv

[57] Michalakis, S. and Pytel, J., ‘Stability of frustration-free Hamiltonians’, Commun. Math. Phys. 322(2) (2013), 277–302.Google Scholar | DOI

[58] Miękisz, J., ‘Stable quasicrystalline ground states’, J. Stat. Phys. 88 (1997), 691–711.Google Scholar | DOI

[59] Moore, C., ‘Unpredictability and undecidability in dynamical systems’, Phys. Rev. Lett. 64 (1990), 2354–2357.Google ScholarPubMed | DOI

[60] Morton, J. and Biamonte, J., ‘Undecidability in tensor network states’, Phys. Rev. A 86 (2012), 030301.Google Scholar | DOI

[61] Nachtergaele, B. and Sims, R., ‘Lieb-Robinson bounds and the exponential clustering theorem’, Commun. Math. Phys. 265(1) (2006), 119–130.Google Scholar | DOI

[62] Nielsen, M. A. and Chuang, I. L., Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000).Google Scholar

[63] Oliveira, R. and Terhal, B., ‘The complexity of quantum spin systems on a two-dimensional square lattice’, Quantum Inf. Comput. 8 (2008), 0900–0924.Google Scholar

[64] Omohundro, S., ‘Modelling cellular automata with partial differential equations’, Physica D: Nonlinear Phenomena 10(1–2) (1984), 128–134.Google Scholar | DOI

[65] Orús, R., ‘A practical introduction to tensor networks: matrix product states and projected entangled pair states’, Ann. Phys. 349 (2014), 117–158.Google Scholar | DOI

[66] Osadchy, D. and Avron, J. E., ‘Hofstadter butterfly as quantum phase diagram’, J. Math. Phys. 42(12) (2001), 5665–5671.Google Scholar | DOI

[67] Pomata, N. and Wei, T.-C., ‘Demonstrating the AKLT spectral gap on 2D degree-3 lattices’, Phys. Rev. Lett. 124 (2020), 177203.Google ScholarPubMed | DOI

[68] Poonen, B., ‘Undecidable problems: a sampler’, in Kennedy, J., ed., Interpreting Gödel: Critical Essays (Cambridge University Press, 2014), 211–241.Google Scholar

[69] Pour-El, M. B. and Richards, I., ‘The wave equation with computable initial data such that its unique solution is not computable’, Adv. Math. 39(3) (1981), 215–239.Google Scholar | DOI

[70] Robinson, R., ‘Undecidability and nonperiodicity for tilings of the plane’, Invent. Math. 12 (1971), 177–209.Google Scholar | DOI

[71] Slofstra, W., ‘Tsirelson’s problem and an embedding theorem for groups arising from non-local games’, Preprint, 2016, J. Amer. Math. Soc. (2020), 1–56.Google Scholar | DOI

[72] Turing, A., ‘On computable numbers, with an application to the entscheidungsproblem’, Proc. London Math. Soc. 42 (1936), 230–265.Google Scholar

[73] Van Den Nest, M. and Briegel, H. J., ‘Measurement-based quantum computation and undecidable logic’, Found. Phys. 38(5) (2008), 448–457.Google Scholar | DOI

[74] Wang, H., ‘Proving theorems by pattern recognition’, Bell System Tech. J. 40 (1961), 1–41.Google Scholar | DOI

[75] Wolf, M. M., Cubitt, T. S. and Perez-Garcia, D., ‘Are problems in quantum information theory (un)decidable?’, Preprint, 2011, .Google Scholar | arXiv

[76] Yan, S., Huse, D. A. and White, S. R., ‘Spin-liquid ground state of the S=1/2 Kagome Heisenberg antiferromagnet’, Science 332 (2011), 1173–1176.Google ScholarPubMed | DOI

[77] Yedidia, A. and Aronson, A., ‘A relatively small Turing machine whose behavior is independent of set theory’, Complex Systems 25 (2016), 297–327.Google Scholar | DOI

[78] Yu, A., Kitaev (1995).Google Scholar | arXiv

Cité par Sources :