There are many supposedly real world applications of computability, but most of them are theoretical and don't apply to situations we are likely to encounter. Now we have a result which proves that a very simple question in quantum mechanics is undecidable.

The problem with undecidability is that there is always an infinity or two wrapped up in it. For example, take the halting problem - you can't write a program that will decide if any other program eventually halts or loops forever. The proof of this shows that if you had such a program then you could easily construct a paradox so such a program cannot exist. 

The halting problem result is often misapplied to the real world to prove something cannot be known or computed, and yet the small matter that the programs in question have to be unbounded isn't taken into account, see for example Halting Problem Used To Prove A Robot Cannot Computably Kill A Human. 

If you can place a limit on the size of the programs that you are trying to decide the halting question for then you can write a program that decides if they halt and no paradox can be constructed. 

Put simply and crudely undecidability needs an infinity somewhere.

A recent paper in nature , Undecidability of the spectral gap by Toby S. Cubitt, David Perez-Garcia, Michael M. Wolf, is creating some excitement because it proves that a simple quantum question is undecidable. 

The spectral gap is the energy difference between the ground state and the first excited state. By definition you might think that the terms ground state and excited state imply that there would be an energy difference, but no. The spectral gap question is simply to determine is there is a gap or not. Of course, real systems can have gaps that are so small they are effectively gap-less, but this is a mathematical question and the answer has to be precise. 

If you know some quantum mechanics you will understand what is required here is to determine the lowest pair of eigenvalues of the Hamiltonian of the system. So what this theory is about at its most abstract is linear algebra. 

What the paper claims to prove is:

"Though one may be able to solve the spectral gap problem in specific cases, our result implies that it is in general logically impossible to say whether a many-body quantum system is gapped or gapless."

To be more precise:

1. The spectral gap problem is algorithmically undecidable: there cannot exist any procedure which, given the matrix elements of the local interactions of the Hamiltonian, determines whether the resulting model is gapped or gapless. This is precisely the same sense in which the Halting Problem is undecidable.

and

2. The spectral gap problem is axiomatically independent: given any consistent axiomatisation of mathematics, there exist quantum many-body Hamiltonians for which the presence or absence of the spectral gap is not determined by the axioms of mathematics. This is the form of undecidability encountered in Godel’s incompleteness theorem. 

These are quite shocking results that imply that mathematics is limited in the way it can describe the world. It means there are systems that you can specify precisely that you cannot say are gapped or not gapped using mathematics. 

The theorem is proved using a simpler system than a completely general Hamiltonian - a set of particles forming an LxL grid interacting via their spin. The elements of the matrices are assumed to be algebraic numbers - i.e. simple roots of polynomials to make sure that the matrices don't start out being non-computable. 

All very reasonable but you might be asking where the infinity comes into the question?

The simple answer is that the question is being asked for a system where L is allowed to got to infinity. 

That is, the system is gapped if the set of systems for finite L tend to a gapped limit as L ->  ∞. 

The actual definition used is more subtle and precise than this, but this is where the infinity comes in to the picture. 

So the result we have is that the spectral gap problem is undecidable for a system with an infinite number of particles. 

Of course any real system has a lot of particles but not an infinite number of particles and so it is decidable.

Is this a useful and important result?

Probably, because reasoning about infinity is part of mathematical logic and this result tells us that trying to reason about real systems by considering the limit at infinity might not be so useful after all. 

The authors of the paper point this out and go in for a detailed discussion of what sorts of behavior the undecidability might create in finite models:

"As the system size increases, the Hamiltonian will initially look exactly like a gapless system, with the low-energy spectrum appearing to converge to a continuum. But at some threshold lattice size, a constant spectral gap will suddenly appear."

and:

"Not only can the lattice size at which the system switches from gapless to gapped be arbitrarily large, the threshold at which this transition occurs is uncomputable"

This raises the possibility that quantum systems have found another way to be weird:

"This implies that we can never know whether the system is truly gapless, or whether increasing the lattice size—even by just one more lattice site—would reveal it to be gapped."

Sounds like sensitivity to initial conditions to me, aka chaos theory.

Read the paper, if only to find out how tiling enters the proof as a link between the physics and the Turing machine. 

More Information

Undecidability of the Spectral Gap (full version)

Undecidability of the Spectral Gap (short version)

Related Articles

Quantum Cats       

Microsoft Open Sources Quantum Computing       

The Machine In The Ghost       

What Is Computable?       

Solve The Riemann Hypothesis With A Quantum Computer       

The Programmer's Guide to Chaos       

What Is Computable?       

What is a Turing Machine?       

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook, Google+ or Linkedin. 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info