Undecidability and Quantum Mechanics

Definition

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.

1. Introduction

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.

2. Undecidability and Quantum Phase Transitions

Different from thermal classical phase transitions (CPT), occurring when the temperature is lowered below a given critical value, QPT are driven by quantum fluctuations, and are testified by a non-analytic behavior of the ground-state properties of the model Hamiltonian H(λ) when the parameter λ varies across a transition point λ_c (see Figure 1, where both kinds of transition are schematically represented). We stress that experiments on cuprate superconductors [26], heavy fermion materials [27], organic conductors [28], and related compounds, have boosted a renewed interest towards the study of QPT. They are caused by the reconstruction of the energy spectrum of the Hamiltonian, especially of the low-lying portion of the excitation spectrum [29]. We point out that the low-energy spectrum can be reconstructed in two qualitatively different ways around the critical point λ_c, and hence the physical quantities may show different behaviors [30]. In the first case, the energy spectrum exhibits a level-crossing in the ground state, and the first derivative of the ground-state energy with respect to λ is usually discontinuous at λ_c; this behavior is usually referred to as first-order QPT.

The second scenario corresponds, roughly, to all other cases in the absence of the ground-state level crossing; in this case, one is faced with a continuous phase transition, as analyzed within the Landau-Ginzburg-Wilson spontaneous symmetry-breaking theory, with the correlation functions of local order parameters playing a crucial role. For completeness, we mention that some systems cannot be described by means of a local order parameter. This is, for instance, the case of systems undergoing topological phase transitions [31] or Berezinskii-Kosterlitz-Thouless phase transitions [32,33,34]. The inherent zero-temperature nature of the QPT makes them impossible to observe directly. However, correlation lengths diverge near the transition, influencing the behavior of the system at finite temperatures. Thus, near a quantum critical point, a distinctive set of collective excitations can be accessed experimentally [35]. The behavior of the system is driven by external parameters and obeys scaling laws with nontrivial exponents, related to the universality class of the transition, and not to the microscopic details [36].

From the theoretical side, the existence of these phases is hardly predicted, and many different approaches have been so far considered. For the scope of the present paper, we confine the analysis to two general techniques.

The first method is the modification of a suitable statistical mechanics inequality, pioneered by Bogoliubov [37,38,39]. The starting point is the celebrated Hohenberg-Mermin-Wagner [40,41] theorem, that essentially states that a continuous symmetry cannot be broken spontaneously at any finite temperature in low-dimensional systems. To apply this method, one should first remove the degeneracy of the model and then study the expectation values involved, the degeneracy being removed by introducing symmetry-breaking terms into the Hamiltonian. This fact has been proven in various models of classical and quantum statistical mechanics and follows from the fact that, in low-dimensional cases, a diverging number of infinitesimally low-lying excitations is created at any finite temperature, and thus the assumption of a non-vanishing order parameter is not self-consistent. It is based on the application of an exact inequality originally due to Bogoliubov [37,38,39], used when there is a broken symmetry.

However, the Hohenberg-Mermin-Wagner theorem says nothing about the existence or non-existence of long-range order in a quantum mechanical system at T = 0. Nevertheless, it is possible to deduce a T = 0 Bogoliubov-like inequality, and to look at spontaneous ordering at T = 0 [42], following the same procedure implemented at finite temperature.

To write down the T = 0 Bogoliubov-like inequality, one assumes, for simplicity, that in the presence of an infinitesimal ordering field there is a unique ground state |0〉, so one writes the expectation value of a generic operator A in the ground state |0〉 as follows:

$$\langle A\rangle =\langle 0\left|A\right|0\rangle .$$

(1)

Then, one defines the T = 0 scalar product between any two operators A and B as:

$$\left(A,B\right)={\displaystyle \sum }_{m\ne 0}\frac{\langle 0\left|A^{†}\right|m\rangle \langle m\left|B\right|0\rangle +\langle 0\left|B\right|m\rangle \langle m\left|A^{†}\right|0\rangle }{E_m-E_0},$$

(2)

where |m⟩ is an eigenstate of the Hamiltonian H with energy E_m. It is straightforward to verify that the map:

(A,B) → c

with $c\in ℂ,$ fulfils the axioms of a true scalar product, implying that the Schwarz inequality holds:

|(A,B)|² ≤ (A,A)(B,B),

(3)

If one chooses the operator B as the commutator between a generic operator C and the model Hamiltonian H_Λ in the following form

$$B=\left[C^{†},H_{\mathsf{\Lambda }}\right],$$

after some algebra one gets

$$\left(A,B\right)=\langle 0\left|\left[C^{†},A^{†}\right]\right|0\rangle ,$$

(4)

the “norm” of the operator B being

$$\left(B,B\right)=\langle [C^{†},\left[H_{\mathsf{\Lambda }},C\right]]\rangle .$$

(5)

Therefore, the T = 0 Bogoliubov’s inequality can be rewritten as

$${\left|\langle \left[C^{†},A^{†}\right]\rangle \right|}^2\le \left(A,A\right)\langle [C^{†},\left[H_{\mathsf{\Lambda }},C\right]]\rangle .$$

(6)

Now, if there is an excitation gap ∆E in the energy spectrum {E_m}, one gets from Equation (2):

$$\left(A,A\right)\le \frac{1}{\Delta E}\left(\langle \left\{A^{†},A\right\}\rangle -2{\left|\langle A^{†}\rangle \right|}^2\right)\le \frac{1}{\Delta E}\langle \left\{A^{†},A\right\}\rangle ,$$

(7)

and the inequality (6) can be cast in the form:

$${\left|\langle \left[C^{†},A^{†}\right]\rangle \right|}^2\le \frac{1}{\Delta E} \langle \left\{A^{†},A\right\}\rangle \langle [C^{†},\left[H_{\mathsf{\Lambda }},C\right]]\rangle .$$

(8)

This inequality looks like the conventional Bogoliubov inequality if the spectral gap ΔE, as defined below, is replaced by the product of the temperature times the Boltzmann constant $k_B$ [37,38,39]. Therefore, one can state that, when there is an excitation gap ΔE in the energy spectrum of a given model Hamiltonian H, at T = 0 there is no long-range order implying that the system under investigation is quantum disordered.

We point out that this kind of approach has been first applied by Auerbach to exclude magnetic order in the Heisenberg model in one dimension [42] and subsequently to various correlated electron models, formulated for low dimensional cases D ≤ 2, where D is the spatial dimension of the system [43,44,45].

Let us also comment on the hypothesis of non-degenerate ground state, assumed above. If the ground state is degenerate, it is nonetheless possible to define a new two-point function (A, B) and it can be shown that this new correlator verifies all the properties of a true scalar product, so that the inequality Equation (8) still holds [43].

The other approach is based on the investigation of the decay of some appropriate correlation functions [46]. Employing the method of complex translation, one gets the expected power law decay (at low temperatures) for the two-point functions, by assuming that the interaction is only smooth. Specifically, the resulting bounds of the correlation functions rule out the possibility of the corresponding long-range orders investigated [47]. The model Hamiltonians to which this approach has been successfully applied include spin [48,49,50,51], electron [52], and electron-boson models on lattices [53], also for degenerate ground states [54]. The resulting bounds of the correlation functions rule out the possibility of the corresponding magnetic and/or charge long-range orders [55].

Interestingly, the McBryan-Spencer method [46] can be extended to zero temperature [55], allowing for the investigation of decay of correlation functions that may give indication of the existence of QPT, within the model Hamiltonian under investigation. We point out that this statement holds for quantum many-body systems considered in low dimensional cases D ≤ 2 [43,44,45], under the assumption of a non-vanishing spectral gap ΔE [55].

Since both methods, however, rely on the concept of spectral gap, we will now review this notion. Thus, we state that there is a uniform gap above the ground state sector of the Hamiltonian H if the energy spectrum of H satisfies the following conditions:

(1)

the ground state of H is q-fold (quasi)degenerate in the sense that there are q eigenvalues, E_0,1,..., E_0,q in the ground state sector at the bottom of the spectrum of H such that

ΔE = max _{μ,μ′} |E_0,μ − E_0,μ′| → 0 as |Λ_s| → ∞,

(9)

|Λ_s| being the cardinality of the set Λ_s;

(2)

the separation between the ground-state energy and all the other energies within the spectrum is larger than a positive constant ΔE, which is independent of the dimension of |Λ_s|.

If these conditions are fulfilled, we may state that the model Hamiltonian H exhibits a spectral gap ΔE above the ground state sector.

We point out that the spectral gap is certainly one of the most important quantities of a quantum many-body model, being strictly related to the low-temperature behavior of a system. Indeed, gapped systems exhibit non-critical behavior, without long-range correlations [56,57], while gapless systems exhibit critical behavior, signaled by the presence of long-range correlations.

Due to its relevance within many-body quantum systems, many seminal results in mathematical physics refer to the investigation of the spectral gap in specific systems. As paradigmatic examples, we mention the Lieb-Schultz-Mattis theorem that states that the Heisenberg chain for half-integer spins is gapless [58], the famous Haldane conjecture [59,60] that suggests that the integer-spin antiferromagnetic Heisenberg model in one dimension has a non-vanishing spectral gap, and the proof of the validity of this conjecture for the one-dimensional antiferromagnetic Affleck-Kennedy-Lieb-Tasaki (AKLT) model [61]. In the same context, it has also been recently demonstrated that for the two-dimensional spin-3/2 AKLT model [62,63], as well as for similar spin Hamiltonians [64,65], the gap can be exactly computed for specific topological configurations of the underlying lattice.

Outstandingly, it has been elegantly shown that the spectral gap problem is undecidable for some specific quantum systems [24,25]. In particular, it has been proved by a standard argument that algorithmic undecidability also implies axiomatic independence. This means that, for assigned local interactions, to infer if the resultant model exhibits a gap or it is gapless is algorithmically undecidable. This in turn implies that there exist Hamiltonian models for which the presence or absence of the spectral gap is not determined by the underlining mathematical axioms, as previously stated.

We would like to comment that this remark can be reinterpreted as a form of the undecidability defined within the frame of Gödel incompleteness theorem [66]. To prove this statement, it has been shown that the spectral gap problem can be encoded in the halting problem [67] for Turing machines [22,23]. Within this approach, it follows that the spectral gap problem is at least as hard as the halting one. We remind that Turing proved that the latter problem is undecidable, so that, since the spectral gap depends on the outcome of the corresponding halting problem, one may infer that there exists no algorithm to determine whether an arbitrary model is gapped or gapless, suggesting that there exist models for which the presence or absence of a spectral gap is independent of the axioms of the mathematical theory adopted. This proof refers to 2D or higher-dimensional models describing some sort of artificial magnetic systems [24,25]. Nevertheless, despite some indications that 1D lattice models are simpler than higher-dimensional ones, it has been very recently proved that also for a family of 1D spin models with translationally invariant nearest-neighbor interactions, no algorithm can determine the presence of a spectral gap [68].

Now, let us take a step back and discuss both the implications and the limitations of the results previously summarized. The results discussed about the existence of QPT concern well consolidated mathematical approaches, applied to models of quantum many-body systems, to rule out specific orderings at T = 0.

On the other hand, we commented on recent results about the undecidability of the spectral gap. This statement implies that an algorithm or a computable criterion that solves the spectral gap problem on a general ground cannot exist. Specifically, it has been proved that there are Hamiltonians for which one can neither prove nor disprove the presence of a gap [24,25].

Combining these outcomes, we can state that, at least for the above-mentioned model Hamiltonians, the existence of a QPT is an undecidable problem. Indeed, since, on the one hand there exists no algorithm to determine whether an arbitrary model is gapped or gapless, and on the other hand there exist models for which the presence or absence of a spectral gap is independent of the axioms of mathematics, the above reported conclusion can be trivially derived since the existence of a QPT is intimately related to the presence of a spectral gap.

3. Conclusions

As discussed in the previous Section, the possibility that under specific conditions a mathematical model exhibits a quantum phase transition cannot be decided a priori. In this respect, even numerical approaches and tools do not allow definitive conclusions to be drawn. Nonetheless, it is also worth noting that numerical approaches are applied worldwide to investigate many-body systems because they may represent, in many cases, the simplest approximation to real systems. However, it is well known that numerical simulations are computationally difficult, and often intractable as larger and larger lattice sizes are considered, also leading in some cases to physical inconsistencies. For instance, it may happen that a system displays all the features of a gapless model, with the gap of the finite system decreasing monotonically with increasing size, but, at some threshold size, it may suddenly switch towards a large gap. Thus, we cannot generally infer exact statements using numerical simulations based on large-size extrapolations.

As an exemplary case of the interplay between the existence of the spectral gap and QPT, we may refer to the periodic Anderson model (PAM) [69]. The related Hamiltonian, largely used in the investigation of metallic compounds containing transition metal or rare earth atoms, describes the complex interplay generated by the hybridization of a set of strongly correlated electrons belonging to localized magnetic impurities with the electrons of an ordinary conduction band. The exact solution of the model is known only in a few special limits [69,70], and in general one has to resort to approximation techniques specifically devised for the analysis of the strong coupling regime [71,72,73,74,75,76,77,78,79].

It is widely accepted that the low-dimensional PAM at half-filling might have an energy gap [80,81]. Indeed, for bipartite lattices, the energy band of the conduction electrons is symmetric, so that the inclusion of a hybridization term opens a gap at zero energy. Thus, the ground state at vanishing Coulomb repulsion is the state where the lower hybridized band is fully occupied, with the upper hybridized one empty. Moreover, exact results show that this state is a unique ground state. When the Coulomb repulsion is turned on, continuity arguments suggest that there is a finite energy gap separating the excited states from the ground state, with the latter still exhibiting no level crossing. This conclusion, based on a naive approach, is not completely correct. Indeed, at least in the 1D case, the PAM can be mapped into the Kondo lattice model by means of the Schrieffer-Wolff transformation [82,83], and this model always exhibits a finite spin excitation gap, narrower than the charge gap. Hence, the ground state is an incompressible spin liquid for any non-vanishing exchange coupling [84], implying that it is quantum disordered, further suggesting that the PAM ground state is quantum disordered, too [44]. For completeness we mention that in the one-dimensional case, numerical results also show that an excitation gap exists for any finite value of the Coulomb repulsion between localized electrons [85,86]. Nevertheless, in two dimensions, numerical data indicate that the PAM exhibits an ordered phase at zero temperature, suggesting that there are gapless magnetic excitations. However, exact analytical results for this case do not exist to corroborate the numerical calculations [69].

We can thus say that qualitative arguments and numerical results do not support a unified picture about the possible existence of the spectral gap, this consequently sustaining the undecidability of the QPT, as commented and addressed in this paper.

In this context, it is noticeable that the general results obtained by Cubitt et al. [24,25] question the validity of the extrapolation scaling procedures by which results obtained for finite-size systems are extended to infinite-size ones. Referring to the model Hamiltonian families considered in Refs. [24,25], it may happen that the increase of the system size makes a gapless low-energy spectrum evolve into one characterized by a gap of finite magnitude, or vice-versa, a gap exhibited up to a relatively small size may abruptly close when the size is suitably increased. The threshold value of the lattice size at which this transition occurs is in general uncomputable.

We would also like to draw attention to a very recent paper [87] devoted to an epistemological analysis of the undecidability of the spectral gap, as presented in Refs. [23,24]. In that paper, it is stressed that any method for extrapolating the asymptotic behavior from a finite-size system could fail, and that the undecidability is determined in the context of specific highly artificial models, which cannot be fully representative of real physical systems. Nevertheless, the claim that the fact that lattice Hamiltonians do not allow to draw definite conclusions about the spectral gap problem, does not imply that specific problems cannot be solved referring to specific Hamiltonians (see, for instance, Ref. [88], where it is shown that operator spectra can be computed by means of suitable optimal algorithms, clearly defining the limits of what digital computers can achieve). Therefore, they also argue that “to state that a proposition or a problem is physically undecidable seems inappropriate, as undecidability would mean a lack of physical content, and that these results support a ‘no-free-lunch’ [89] view on problem-solving and an analytical approach over an axiomatic one” [87]. In other words, mathematical impossibility-theorems are relevant in science, not because they tell us something about nature itself, but because in our effort of understanding observations, they provide fundamental hints about what we can expect from our theories and from the related underlying mathematical models. Of course, one can always extend the original set of axioms with another axiom set that simply says whether the previously undecidable statement is true.

In this context, it is worth recalling the point of view of Stephen Hawking on this subject. In his famous lecture on Gödel and the End of Physics [90], he tried to give an answer to the question of whether one ever finds a complete form of the laws of nature. By a complete form, he meant a theory such that, using its axioms, one is in principle able to predict the dynamics of the system under investigation to an arbitrary accuracy, knowing its state at one time. Classical mechanics represents a paradigmatical example of complete theory, since, if at one time one knows the positions and velocities of all the particles in the universe, Newton laws enable us to calculate their positions and velocities at any other time, past or future.

However, going towards modern physics, the experience with gravity and quantum mechanics suggests that the above-mentioned completeness proposition no more applies. The problem is that general relativity and quantum mechanics seem to be incompatible, in the sense that despite various approaches of different kinds developed in recent years (string theory, loop quantum gravity, twistor theory, etc.), no complete and unified theory of quantum gravity has so far been formulated. Apart from this apparent impossibility, Hawking pointed out that the search for understanding will never come to an end, and that one will always have the challenge of new discoveries. Therefore, if Gödel theorem ensures there would always be a job for mathematicians, at the same time Hawking infers that the search for new theories for the physicist is a never-ending story.

Whenever Gödel theorem applies, one deals with incompleteness statements concerning the undecidability of some propositions that can neither be proved nor be confuted. In particular, undecidability is associated with logical conflicts which arise when self-referential claims are made, according to which a given system asks to define itself in its own terms. In physics this typically happens when statements refer to the whole universe, so that the observer is necessarily a part of the observed system [91]. In this case, the application of the Gödel theorem implies that there will always be some questions that, at least partially, remain undecidable. Each new answer thus enlarges our comprehension, but at the same time makes more and more evident that our knowledge is incomplete, and a lot still remains to be done. In this respect, we should accept that a “theory of everything”, that is, a finite ultimate theory fully explaining the universe laws by means of few and simple first principles, cannot be formulated since the search for it is a process that will never come to an end [10,11]: “the more we know, the more we know that we know less” [91].

As a final consideration, we would like to comment on the limitations of our result. First, we do not exclude the possibility that one proves the presence or absence of QPT in specific model Hamiltonians. Indeed, our result only excludes the possibility to obtain a general and definitive criterion to assess this feature. Moreover, we emphasize that the relevance of numerical simulations on finite-size systems is not lessened by our conclusions. Second, undecidability is shown here in specific microscopic approaches to QPT, which is another limitation of our result. In principle, one needs to proceed toward a unified general theoretical approach proving the existence of the spectral gap, or to find a restricted class of physical Hamiltonians whose outcome of QPT is decidable. These options are nowadays open problems and are left for future works.