Generic Undecidability of Decision Problems in a Continuous Space: Is undecidability of the spectral gap surprising?

An article by Toby S. Cubitt, David Perez-Garcia, and Michael M. Wolf, “Undecidability of the Spectral Gap,” published today in Nature, has been receiving some attention (at least as judged by the number of my facebook friends who have shared or commented on it!)  It’s been called “genuinely shocking, and probably a big surprise for almost everybody working on condensed-matter theory” (Christian Gogolin, quoted by Castelvecchi).

I don’t mean to rain on anyone’s parade, but I wonder whether it should be regarded as surprising.  It seems to me that the result follows from something that is well-known in the field of computable analysis: undecidability of equality of real numbers.

Turing machines operate on integer inputs; to deal with real numbers, we use rational approximations.  Since there are countably many rationals, we can index them by natural numbers; pick your favourite enumeration, and let q_k be the rational number indexed by k.  A real number x is computable if and only if there is an algorithm that delivers rational approximations to x, as a function of desired degree of accuracy; that is, if there is an algorithm that delivers k(m) as a function of m, such that the distance between x and q_k(m) is always less than 2^–m.   A sequence of numbers {x_n}  is a computable sequence if and only if there is an algorithm that delivers a rational number that is within a distance 2^–m of x_n, as a function of n and m.

Now, if I hand you an algorithm for computing a number x (or an oracle that delivers rational approximations to any desired degree of precision), can you decide whether or not the number is equal to 0?

If the number is not equal to 0, then knowing a sufficiently precise rational approximation to the number will tell you that.  But if you keep computing closer and closer rational approximations and don’t find the number bounded away from zero, then you don’t know whether the number is zero, or whether a closer rational approximation will bound it away from zero.  You don’t know when to stop.

This should sound familiar, as it is reminiscent of the Halting Problem.  And, in fact, it is easy to show that the undecidability of equality is equivalent to the Halting Problem.

Given a Universal Turing machine T,  it is easy to construct a computable sequence {x_n} such that x_n is greater than zero if T halts on input n and is equal to zero if it doesn’t  (see my 1995 and 1997).  So, if we could effectively decide which members of the computable sequence {x_n} are equal to zero, we could solve the halting problem.

This means that, if we have any decision problem that asks whether a given quantity that is a calculable function of real-valued input parameters is equal to zero or not, it’s an undecidable problem.  All computable functions on the reals are continuous!  (Weihrauch 2000, Th. 4.3.1)

This is why I’m not surprised by the Cubitt et al. result.

The result concerns 2-dimensional L×L  lattices of spins, with nearest-neighbour interactions.  The system is gapped if there is a number γ such that, for sufficiently large L, the difference between the energy of the ground state and the energies of all excited states is at least γ.  The system is gapless if, in the thermodynamic limit, it has continuous spectrum above the ground state.  The authors construct a family of interaction Hamiltonians h(φ), depending on an input parameter φ, such that whether or not the spectrum is gapped depends on the value of φ, and they rig things so that there is a computable sequence of numbers {φ(n)} such that whether or not the system with interaction Hamiltonian h(φ(n)) is gapped or gapless depends on whether or not a Universal Turing machine halts on input n.

If all that is needed to show that the problem is undecidable is to construct a family of Hamiltonians, depending on input parameter φ , such that there is a computable sequence {φ_n } of input parameters such that the system is gapped if a Universal Turing Machine halts on input n and gapless if it doesn’t, then I can’t help but wonder whether it could be done more simply.

Suppose we construct interactions h(λ) such that whether the system is gapped or gapless depends on whether the input parameter λ is greater than zero. Then, without further ado, there is, as mentioned above, a computable sequence {λ_n} of input parameters such that the system is gapped if a Universal Turing Machine halts on input n and gapless if it doesn’t, and we can conclude that the problem is not effectively decidable as a function of the input parameter.

References

Castevecchi, Davide (2015), “Paradox at the heart of mathematics makes physics problem unanswerable.”  Nature News, 9 December 2015, http://www.nature.com/news/paradox-at-the-heart-of-mathematics-makes-physics-problem-unanswerable-1.18983.

Cubitt,  Toby S., David Perez-Garcia, & Michael M. Wolf, “Undecidability of the spectral gap” Nature 528 (10 December 2015), 207–211.

Myrvold, Wayne C. (1995). “Computability in Quantum Mechanics,” in Werner DePauli-Schimanovich, Eckehart Köhler, and Friedrich Stadler, eds., The Foundational Debate: Complexity and Constructivity in Mathematics and Physics (Kluwer Academic Publishers, 1995), pp. 33–46.   Available at http://philpapers.org/rec/MYRCIQ

——— (1997). “The Decision Problem for Entanglement.”  In Robert S. Cohen, Michael Horne & John Stachel (eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies for Abner Shimony. (Kluwer Academic Publishers), pp. 177–190.  Available at http://philpapers.org/rec/MYRTDP

Weihrauch, Klaus (2000).  Computable Analysis: An Introduction. Springer.

Public Library Talk: Einstein and the Atom

I'm giving a talk tomorrow (Wednesday, October 28), at the Central Branch of the London Public Library, (251 Dundas Street), 7 PM, Stevenson & Hunt Room.   The talk will be non-technical, and accessible to all.  Please join me, if you can!

Einstein and the Atom.

 Abstract:
Einstein’s name is widely associated with the “atom bomb,” via the formula E = mc². Less widely known is that he played a key role in providing evidence that atoms exist at all. One of Einstein’s early papers was an analysis of Brownian motion, the ceaseless dance of tiny particles, such as pollen grains, suspended in a fluid. The dance of pollen grains, Einstein realized, was evidence that they are being buffeted by smaller particles, beyond microscopic resolution. This talk will be about the ingenuity required to turn the visible into evidence about the invisible.

Was Einstein Wrong?

Some headlines from the past day or so:

• Dutch News: Dutch scientists show Einstein was wrong about ‘spooky action’
• Time magazine, What Einstein Got Wrong About the Speed of Light
• The New York Times, Sorry, Einstein.Quantum Study Suggests ‘Spooky Action’ Is Real.

This sort of thing is nothing new, of course.  Many  discussions of Einstein's attitude towards quantum mechanics suggest that Einstein simply refused to accept a straightforward consequence of quantum mechanics: non-locality.

Now, if you have no reason to believe something, and you don’t believe it, but it happens to be true, then, in one sense, you’re wrong in your belief.  But you can’t be accused of being unreasonable or irrational.  So, in an uninteresting sense, Einstein was wrong, in not having beliefs that scientists would later provide good evidence for.  But the same could be said of everybody, ever.

Einstein didn’t believe that nonlocality was a feature of the world. But should he have? Was he wrong not to believe in nonlocality?  What reason did anyone have, in 1935, or in the late ‘40s, when he wrote his fullest discussions of his attitude towards quantum mechanics, for thinking that nonlocality was a feature of physical reality?

We can’t fault Einstein for not having read Bell’s 1964 paper, or for not having read the December 20, 1982 issue of Physical Review Letters—after all, he was no longer alive by the time Doc Brown and Marty McFly arrived in 1955, and, besides, as far as we know, they didn’t bring literature of that sort with them. We can't fault him, either, for not having read this week's issue of Nature.  Hindsight is 20-20, and we now know two things that, as far as I know, nobody really knew during Einstein’s lifetime.

1. Some quantum correlations are not locally explicable.
2. Quantum correlations persist when the systems are separated by a large distance.

The first, of course, is Bell's theorem, and the second we know through a series of increasingly impressive experimental demonstrations of violations of Bell inequalities.  Re 1:  As Bell himself emphasized, the mere fact that outcomes of spatially separated experiments are correlated is no indication of any sort of nonlocality.  As you're reading this, someone else on the other side of the world might be reading the same words.  No spooky action-at-a-distance is needed to explain this; nor is there any need for direct influence between the two of you, as there's a common source for what's displayed on your computer screen, and what is being displayed on the other side of the world.

 

As I’ve emphasized in earlier blog posts (here and here),  Einstein was not nearly as dogmatic about locality as he is sometimes painted to be.  He did not regard the assumptions of locality and separability as non-negotiable; his attitude was that one could, indeed, drop them as requirements on a physical theory, given good reason.  But he saw no reason to do so.  He wrote, in 1948,

if I consider the physical phenomena with which I am acquainted, and especially those which are so successfully comprehended by means of quantum-mechanics, then, nevertheless, I nowhere find a fact which makes it appear to me probable that one has to give up requirement II [of locality and separability]. For that reason I am inclined to believe that the description afforded by quantum-mechanics is to be viewed … as an incomplete and indirect description of reality, that will again be replaced later by a complete and direct description (Einstein 1948; translation in Howard 1985).

Systems that are interacting or have interacted, and whose quantum-mechanical state is entangled, have probabilistically correlated behaviour.  That by itself isn’t enough to answer Einstein’s challenge to point to a phenomenon that would count as evidence for a breakdown of locality. Correlations are already familiar in classical probability theory: for example, if two classical  systems interact, a probability distribution that represents thermal equilibrium will involve correlations between the two.  An answer to Einstein’s challenge would have to give us some reason to think that quantum correlations aren’t like that.

My question for historians: did anyone even attempt to provide an argument of that kind, during Einstein’s lifetime?

References

Aspect, A., J. Dalibard, and G. Roger (1982). Experimental test of Bell’s inequalities using time-varying analyzers. Physical Review Letters 49, 1804-1807.

Bell, John S.,  (1964). On the Einstein-Podolsky-Rosen Paradox. Physics 1, 195-200.

Einstein, Albert (1948). Quanten-mechanik und wirklichkeit. Dialectica 2, 320–324.

Hensen, B. et al. (2015).  Loophole-free Bell inequality violation using electron spinsseparated by 1.3 kilometres. Nature, online 21 October 2015.

Howard, Don (1985). “Einstein on Locality and Separability.” Studies in History and Philosophy of Science 16, 171-201.

Bohr's reply to EPR (Part III)

Did Bohr find a flaw in the EPR argument?

He says he did.  In a brief note (Bohr 1935a) published soon after the publication of the EPR paper, in his fuller reply to EPR (1935b), and in his later (1949) recap of his discussions with Einstein about QM, Bohr claims to have discovered an ambiguity in the EPR reality criterion.

The EPR reality criterion reads:

If, without in any way disturbing a system, we can predict with certainty (i.e. with probability equal to unity) the value of a physical quantity, then there exists an element of physical reality corresponding to this physical quantity (EPR 1935, p. 777).

Here’s what Bohr says about the alleged ambiguity:

the wording of the above-mentioned criterion of physical reality proposed by Einstein, Podolsky and Rosen contains an ambiguity as regards the expression “without in any way disturbing a system.” Of course there is in a case like that just considered no question of a mechanical disturbance of the system under investigation during the last critical stage of the measuring procedure. But even at this stage there is essentially the question of an influence on the very conditions which define the possible types of predictions regarding the future behavior of the system.  Since these conditions constitute an inherent element of the description of any phenomenon to which the term “physical reality” can be properly attached, we see that the argumentation of the mentioned authors does not justify their conclusion that quantum-mechanical description is essentially incomplete (Bohr 1935b, p. 700; 1949, p. 324).

EPR consider two systems that interact for a while, and then, after a certain time, no longer interact.  On the basis of this absence of interaction, they conclude that what is done to the first system produces no change in the state of the second system.  According to Bohr, this is ambiguous between two readings.

1. They could mean that an experiment performed on the first system produces no mechanical disturbance of the other.
2. On the other hand, they could mean that an experiment performed on the first system has no effect on the types of predictions that can be made about the other.

I submit that there is no ambiguity, because (2) is not a possible reading of what EPR meant.  Of course the choice of experiment done on one particle has an effect on the sorts of predictions that can be made about the other; that’s the whole point of the argument!  And EPR do note that, since the choices are mutually exclusive, to make a choice means losing the opportunity to make the other sort of prediction about the other particle:

one would not arrive at our conclusion if one insisted that two or more physical quantities can be regarded as simultaneous elements of reality only when they can be simultaneously measured or predicted. On this point of' view, since either one or the other, but not both simultaneously, of the quantities P and Q can be predicted, they are not simultaneously real (p. 780).

Bohr says that that the conditions that define the possible types of prediction that can be made about a system constitute an inherent element of the description of any phenomenon to which the term “physical reality” can be properly attached.  This sounds to me as if he saying that being able to predict the outcome of a position “measurement” is a condition for applying the concept of position, and being able to predict the outcome a momentum “measurement” is a condition for applying the concept of momentum. But, if that’s what he’s saying, he’s simply taking the out that EPR offer at the end of their paper.  They note that this way out has the consequence that the reality of properties of one system depends on what is done to the other.  If that is, indeed, what Bohr is saying, then one wishes he had said so straightforwardly!

References

Bohr, Niels (1935a).  Quantum Mechanics and Physical Reality. Nature 136, 65.

——— (1935b). Can Quantum-Mechanical Description of Physical Reality Be Considered Complete? Physical Review 48, 696-702.

——— (1949).  Discussions with Einstein on Epistemological Problems in Atomic Physics, in P.A. Schilpp, ed., Albert Einstein: Philosopher-Scientist (Chicago: Open Court Press), 199–241.

Einstein, Albert, Boris Podolsky, and Nathan Rosen (1935), Can Quantum-Mechanical Description of Physical Reality Be Considered Complete? Physical Review 47, 777-780.