Undecidability and Quantum Mechanics

Version	Summary	Created by	Modification	Content Size	Created at	Operation
1		Canio NOCE	--	1099	2022-08-26 11:12:01	\|
2	format done	Vicky Zhou	Meta information modification	1099	2022-08-26 11:18:19	\|

Peer Reviewed

This is a peer-reviewed entry published in Encyclopedia Journal, full entry can be found at 10.3390/encyclopedia2030103

Recently, great attention has been devoted to the problem of the undecidability of specific questions in quantum mechanics. In this context, it has been shown that the problem of the existence of a spectral gap, i.e., energy difference between the ground state and the first excited state, is algorithmically undecidable. Using this result herein proves that the existence of a quantum phase transition, as inferred from specific microscopic approaches, is an undecidable problem, too. Indeed, some methods, usually adopted to study quantum phase transitions, rely on the existence of a spectral gap. Since there exists no algorithm to determine whether an arbitrary quantum model is gapped or gapless, and there exist models for which the presence or absence of a spectral gap is independent of the axioms of mathematics, it infers that the existence of quantum phase transitions is an undecidable problem.

undecidability spectral gap quantum phase transition

In the 1930s, Kurt Gödel proved that for some statements in mathematics it is impossible to demonstrate whether they are true, or false. In this respect, one is faced with so-called undecidable statements. Since this pioneering and seminal work, many examples of undecidable problems have been exhibited, and research in this area is still fruitful because undecidable problems arise naturally in many branches of mathematics ^[1]. Intriguingly, it is worth finding out whether certain fundamental questions of physics, specifically in quantum mechanics, may be assumed to fall in this category. In particular, a growing interest towards undecidability in quantum systems is nowadays driven by the increased importance of quantum information ^[2]^[3]^[4]^[5]^[6]^[7]^[8]^[9]^[10]^[11].

Although rare, there are some noteworthy outcomes related to the impossibility of obtaining exact results for certain physical models. We begin by mentioning the pioneering work of Komar ^[12], that proved the existence of undecidable properties in quantum field theories. Specifically, he showed that there is, in general, no effective procedure for determining whether two arbitrarily given states of a quantum system, having an infinite number of degrees of freedom, are macroscopically distinguishable. In the framework of standard quantum mechanics, Moore reported interesting statements on undecidability of the long-term behavior of a particle in-a-box problem ^[13]. He indeed showed that the motion with few degrees of freedom can be mapped into a Turing machine and recognized that even if the initial conditions are known exactly, any question about their long-term dynamics is undecidable. Again, in the context of quantum mechanics, Lloyd ^[2] showed that even though the time evolution operator for any quantum-mechanical computer possesses a block diagonal form, the diagonal decomposition of the program state is uncomputable if the quantum-mechanical system is capable of universal computation. It should be noted that they are uncomputable in the sense that there is no algorithm that will approximate them to a certain, finite precision, in finite time. Consequently, a quantum mechanical theory for a universe where local variables support universal computation cannot supply their spectral decomposition, so that a “theory of everything” can be correct and basically incomplete at the same time. Furthermore, it is worth mentioning a very recent and elegant result on the uncomputability of the phase diagram of condensed matter systems ^[14], where it is exactly demonstrated by constructing a continuous one-parameter family of Hamiltonians that the phase diagram of the related many body models is in general uncomputable. The undecidability of some problems was also investigated by Wolfram ^[15], who, assuming that physical processes can be reviewed as computations, showed that it is difficult to answer questions about them. Specifically, using cellular automata he provided explicit examples of various formally undecidable and computationally intractable problems, also suggesting that such problems are rather common in physical models. It is also reported that quantum control problems, both for open and closed systems, are in general not algorithmically solvable ^[16]. This means that once a desired value for a given target has been chosen, no algorithm can decide whether dynamics of an arbitrary quantum system can be manipulated by accessible external interactions in such a way to reach that desired value. Moreover, undecidable systems exhibit a novel type of renormalization group flow, revealing a form of unpredictability that is qualitatively different and more extreme than chaotic renormalization group flows ^[17]. Finally, it has also been recently shown that in quantum field theory some questions are undecidable in a precise mathematical sense. In particular, it is demonstrated that no algorithm can tell us whether a given two-dimensional supersymmetric Lagrangian theory breaks supersymmetry, or not ^[18]. Very recently, thermalization in isolated quantum many-body systems has also been shown to represent an undecidable problem ^[19]; the resulting undecidability even applies to one-dimensional shift-invariant systems, where nearest-neighbor interaction is considered and the initial state is a fixed product one.

Concerning classical results, undecidability and incompleteness were discussed by Richardson ^[20], who stated that the theory of elementary functions is undecidable in classical analysis. From this deduction, da Costa and Doria inferred that undecidability and incompleteness are found everywhere in mathematical physics, since, when modelling physical phenomena, the function spaces which are usually considered all include the algebra of elementary functions ^[21].

It should be noted that there are two ways in which one may speak of undecidability ^[1]. In the first case, one says that a single statement is called undecidable if it, or its negation, cannot be deduced starting from the axioms of the underlying theory. In the second case, one can say that a family of problems with affirmative or negative answers is called undecidable if no algorithm terminates with the right answer, independently of the problem belonging to the family investigated. Hereafter, the word undecidability will be used in the sense given by the second meaning, and, importantly, the undecidable problem we refer to can be traced back to the halting problem ^[22]^[23].

The aim of this paper is to discuss a new exact result on the undecidability in quantum mechanics. Starting from a recent achievement on the undecidability of the spectral gap of a condensed matter system ^[24]^[25], here we will prove that the existence of a quantum phase transition (QPT), as inferred from specific microscopic approaches, is an undecidable problem.

To this end, we will first summarize the main achievements about QPT, with special attention towards the theoretical methods used to trace back QPT, emphasizing their properties and range of validity. Then, we will formally define the spectral gap for a generic microscopic model Hamiltonian, discussing a recent statement about its existence in quantum systems, and showing that the existence of such a gap is in general an undecidable statement. Thus, combining these results, we infer that the existence of QPT within a generic microscopic model is undecidable too, at least for low-dimensional systems.

References

Poonen, B. Undecidable problems: A sampler. In Interpreting Gödel; Kennedy, J., Ed.; Cambridge University Press: Cambridge, UK, 2014; pp. 211–241.
Lloyd, S. Quantum-mechanical computers and uncomputability. Phys. Rev. Lett. 1993, 71, 943–946.
Lloyd, S. Necessary and sufficient conditions for quantum computation. J. Modern Opt. 1994, 41, 2503–2520.
Van den Nest, M.; Briegel, H.J. Measurement-based quantum computation and undecidable logic. Found. Phys. 2008, 38, 448–457.
Wolf, M.M.; Cubitt, T.S.; Pérez-García, D. Are problems in quantum information theory (un)decidable? arXiv 2011, arXiv:1111.5425.
Eisert, J.; Müller, M.P.; Gogolin, C. Quantum measurement occurrence is undecidable. Phys. Rev. Lett. 2012, 108, 260501.
Morton, J.; Biamonte, J. Undecidability in tensor network states. Phys. Rev. A 2012, 86, 030301.
Kliesch, M.; Gross, D.; Eisert, J. Matrix-product operators and states: NP-hardness and undecidability. Phys. Rev. Lett. 2014, 113, 160503.
De las Cuevas, G.; Cubitt, T.S.; Cirac, J.I.; Wolf, M.M.; Pérez-García, D. Fundamental limitations in the purifications of tensor networks. J. Math. Phys. 2016, 57, 071902.
Bendersky, A.; Senno, G.; de la Torre, G.; Figueira, S.; Acín, A. Nonsignaling deterministic models for nonlocal correlations have to be uncomputable. Phys. Rev. Lett. 2017, 118, 130401.
Elkouss, D.; Pérez-García, D. Memory effects can make the transmission capability of a communication channel uncomputable. Nat. Comm. 2018, 9, 11491–11495.
Komar, A. Undecidability of macroscopically distinguishable states in quantum field theory. Phys. Rev. 1964, 133, B542–B544.
Moore, C. Unpredictability and undecidability in dynamical systems. Phys. Rev. Lett. 1990, 64, 2354–2357.
Bausch, J.; Cubitt, T.S.; Watson, J.D. Uncomputability of phase diagrams. Nat. Comm. 2021, 12, 452.
Wolfram, S. Undecidability and intractability in theoretical physics. Phys. Rev. Lett. 1985, 54, 735–738.
Bondar, D.I.; Pechen, A.N. Uncomputability and complexity of quantum control. Sci. Rep. 2020, 10, 1195.
Watson, J.D.; Onorati, E.; Cubitt, T.S. Uncomputably complex renormalisation group flows. arXiv 2021, arXiv:2102.05145.
Tachikawa, Y. Undecidable problems in quantum field theory. arXiv 2022, arXiv:2203.16689.
Shiraishi, N.; Matsumoto, K. Undecidability in quantum thermalization. Nat. Commun. 2021, 12, 5084.
Richardson, D. Some undecidable problems involving elementary functions of a real variable. J. Symb. Log. 1968, 33, 514–520.
da Costa, N.C.A.; Doria, F.A. Undecidability and incompleteness in classical mechanics. Int. J. Theor. Phys. 1991, 30, 1041–1073.
Turing, A.M. On computable numbers, with an application to the entscheidungsproblem. J. Math. 1936, 58, 345–363.
Turing, A.M. On computable numbers, with an application to the entscheidungsproblem. A correction. Proc. London Math. Soc. 1938, 2, 544–546.
Cubitt, T.S.; Pérez-García, D.; Wolf, M.M. Undecidability of the spectral gap. Nature 2015, 528, 207–211.
Cubitt, T.S.; Pérez-García, D.; Wolf, M.M. Undecidability of the spectral gap (full version). arXiv 2015, arXiv:1502.04573.

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.

Upload a video for this entry

Information

Subjects: Quantum Science & Technology

Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :

Canio Noce

Alfonso Romano

View Times: 1.4K

Entry Collection: Applications of Quantum Mechanics

Online Date: 26 Aug 2022

Table of Contents

Video Upload Options

Confirm

References