## Saturday, 12 December 2015

### Decision problems in continuous spaces: a follow-up

Follow-up to Thursday's post, clarifying what the issue is, as I now have a better understanding of what Cubitt et al. achieved.

Here's the tl;dr version:   The question addressed is by Cubitt et al is, in their words, "Given a quantum many-body Hamiltonian, is the system to be described gapped or gapless?"  They show that, in a very strong sense, the problem is undecidable.  My claim is that this is much more than is needed to demonstrate undecidability in the sense relevant to decision problems in physics, and that, in the sense relevant to  physics, undecidability is generic. [Edited 12-13-15]

Question: what should be meant by a decision problem of this sort?

When it comes to decision problems regarding sets of integers, there's no issue.  Thanks to Church, Turing, and Post, we have a well-agreed upon definition of computable function on the natural numbers, and of decidable subset of the natural numbers: a  subset A of the natural numbers is decidable if and only if it is recursive, that is, if and only if there is a computable function f such that f(n) is equal to 1 if nA, and 0 otherwise.

But the question posed isn't one of classifying integers, it's one of classifying Hamiltonians.  Given a Hilbert space, there are uncountably many Hermitian operators on the space, and so we can't code up the full decision problem in natural numbers that we can feed into a Turing machine.

What Cubitt at al. do is to construct a family of Hamiltonians that depend on a real parameter φ, such that the system is gapped for some values of  φ, and gapless for others.  Clearly, if this restricted problem is undecidable, then the general problem is.

So, let's think about decision problems on the reals.  How should we think of the question of whether a given subset A of the reals is algorithmically decidable?

I can think of a few ways to do this.

1. There is a widely accepted notion of a computable function on the reals.  We could adopt that, and ask whether there is a computable function f such that f(x) is equal to 1 if x is in A, and 0 if not.
2. Alternatively, one could restrict the problem to the computable reals.  There are only countably many of those, and they can be indexed by the code-numbers of the Turing machines that compute them.  We could ask whether there is a computable function f such that f(n) is equal to 1 if n is the index of a Turing machine that computes a real number x that is in A, and equal to 0 if n is the index of a Turing machine that computes a real number x that is not in A.  We don't care what it does when n is not the index of a machine that computes a number; it can fail to halt, for all we care.
3. One could restrict the problem to rationals.  We can index the rationals by natural numbers, and we can ask whether there is a computable function  f such that f(n) is equal to 1 if n is the index of a rational number in A, and equal to 0 if it's not.
In effect, Cubitt et al. showed that the problem they posed is undecidable in sense 3.  And that's by far the hardest question of the three, and doing so took a lot of work.

Clearly, if a problem is undecidable in sense 3, it's undecidable.  But I want to claim that sense 1, which is far weaker, is really the relevant sense.  This is, perhaps, disappointing, because it makes the question of decision problems on the reals into a boring one.

First: what is a computable function on the reals? The standard answer, known as Grzegorczyk computability, is reminiscent of floating point computation.  A program that computes a real function works with rationals as approximations to inputs and outputs.  Suppose you want the program to compute the value of f(x) within a certain rational degree of precision ε. You provide the program with ε, and with rational approximations to the input x.  The program is allowed to request closer and closer approximations to the input, which you are obliged to provide, but it has to halt and yield an approximation, within ε, to f(x), after finitely many steps.

This is, I think, the notion of computable function relevant to decision problems in physics.    If you are asked to decide whether a given physical system, characterized by certain parameters, is in one class or another, you can ask the experimentalists to provide you with values of the parameters, but they will only be able to yield approximations within experimental error.  You might ask them for better and better information about the relevant parameters, but, if you are to render a decision, you have to do so with only an approximation to the input parameter.

It's easy to see that, on this notion of a computable function on the reals, all computable functions are continuous.   Which means that, in sense 1, there are no non-boring decision problems.

This strikes some people as counter-intuitive.  But it is, I claim, the right answer.

Here's why.  Recall that a sequence {xn} of real numbers is a computable sequence if and only if there is a computable function that yields rational approximations, within 2-m, to xn, as a function of n and m.  I claim that
• a necessary condition for a function f on the reals to be a computable function is that it map computable sequences onto computable sequences, and
•  a necessary condition for a set A of reals to be decidable is that, for every computable sequence {xn}, the sequence {χA(xn)}is a computable sequence of 1s and 0s, where χA is the characteristic function of A.
Before reading on, taking a moment to ask yourself whether you agree.

If you do agree that these are necessary conditions on the relevant notions, they have far-reaching consequences.  Mazur (1963, Th. 4.28) proved the following (see also Weihrauch 2000, Th. 9.1.2).
• If is a real-valued  function on the reals that maps computable sequences to computable sequences, then, if {ak}is a computable sequence that converges to a computable limit a, the sequence {f(ak)} converges to f(a).
Suppose, now, that you accept what I suggested, above, should be taken to be a necessary condition for a subset of the reals to be decidable.  Then this means that equality is undecidable.  Deciding whether a real number is in the singleton set {0} is an undecidable problem.  Similarly for simple subsets of the reals; the interval [0, 1] is undecidable.

What people who work in computable analysis do, in light of this, is to replace questions of deciding membership in a set of reals with other questions.  We can, for example, ask whether, for a given set A, there is a computable function is equal to 1 in the interior of A, equal to 0 in the exterior, and is undefined on its boundary.  Or we can ask whether the distance function dA(x), defined as the greatest lower bound of |xy| for yA, is a a computable function.  See Weihrauch 2000, Chs 4 & 5 for more on this sort of thing.

It seems to me that, given a fixed Hilbert space, one ought to be able to extend notions like these to subsets of the set of all Hermitian operators on the space.  It would be interesting to see how the spectral gap problem looks from that point of view.

References

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

Mazur, S. (1963). Computable Analysis. Rozprawy Matematyczne 33, 1-111.

Weihrauch, Klaus (2000). Computable Analysis. Springer.

## Thursday, 10 December 2015

### 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 qk 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 qk(m) is always less than 2m.   A sequence of numbers {xn}  is a computable sequence if and only if there is an algorithm that delivers a rational number that is within a distance 2m of xn, 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 {xn} such that xn 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 {xn} 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