Quantum Theory Confirmed Again

Last week, Justin Weinberg asked me and some other people whether we’d be willing to contribute to a group blog post commenting on a paper [1] that had been making the rounds on social media.  You can find our responses over at Daily Nous.

Justin asked that our contributions be relatively short, to get the discussion going.  So, of course, what I did was write a short piece, realize that it was about twice the length that Justin had asked for, and then applied surgery.  Here’s my full piece, which I’ve added to since then, explaining in a bit more detail what the de Broglie-Bohm theory says about the Wigner-Brukner thought experiment.

-----------------------------------------------------------------------------------------

Headline news!  Stop the presses!  A group of experimenters did an experiment, and the results came out exactly the way that our best physical theory of such things says it should, just as everyone expected. Quantum Theory Confirmed Again.

That’s what actually happened, though you’d never know it from the clickbait headline: A quantum experiment suggests there’s no such thing as objective reality [1].

The experiment [2] was inspired by a recent paper by Časlav Brukner, entitled “A No-Go Theorem for Observer-Independent Facts” [3]. The abstract of the paper reporting on the experiment proclaims, “This result lends considerable strength to interpretations of quantum theory already set in an observer-dependent framework and demands for revision of those which are not.”

Here’s a convenient feature of claims of this sort: when you see one, you can be sure, without even going through the details of the argument, that any conclusion to the effect that the predictions of quantum mechanics are incompatible with an objective, observer-independent reality, is simply and plainly false. That is because we have a theory that yields all of the predictions of standard quantum mechanics and coherently describes a single, observer-independent world.  This is the theory that was presented already in 1927 by Louis de Broglie, and was rediscovered in 1952 by David Bohm, and is either called the de Broglie-Bohm pilot wave theory, or Bohmian mechanics, depending on who you’re talking to.  You can be confident that, if you went through the details of a thought-experiment, then (provided that the thought-experiment is sufficiently well-specified), you would find that the de Broglie-Bohm theory gives a consistent, observer-independent, one-world account of the goings on in the experiment, an account that is in complete accord with standard quantum mechanics with regards to predictions of experimental outcomes.

The way that the de-Broglie Bohm theory achieves this is interesting. It is a theory on which the world consists of well-localized particles that obey a non-classical law of motion. There’s always a matter of fact about where things are, on this theory. It’s a deterministic theory, so, given initial conditions, the result of any experiment is determined. But what that result is can depend on what other experiments are performed at the same time; it’s what is called a contextual hidden-variables theory. Moreover, it’s a nonlocal theory: the result of an experiment will sometimes depend on what other experiments are performed at a distance.  This is no accident; Bell’s theorem (see [4]) shows that any theory of this sort has to be nonlocal.

There are other theories, known as dynamical collapse theories, which also yield accounts of a single, observer-independent reality.  These theories yield virtually the same predictions as standard quantum mechanics for all experiments that are currently feasible, but differ from the predictions of quantum mechanics for some experiments involving macroscopic objects.

Much of the confusion surrounding quantum mechanics, which leads smart people to say foolish things, stems from the fact that, in the usual textbook presentations, we are not presented with a coherent physical theory. Typical textbook presentations incorporate something that is called the “collapse postulate.”  This postulate tells you that, when an experiment is done, you dispense with the usual rule for evolving quantum states, and replace the quantum state by one corresponding to the actual outcome of the experiment (which, typically, could not have been predicted from the quantum state). This is call “quantum state collapse.” There is some ambiguity as to its status, which reflects ambiguity as to the status of quantum states. Sometimes collapse is taken to be a real physical process (which it would have to be, if a quantum state represents something physically real); sometimes, collapse is taken to involve mere updating of information (which would be appropriate if a quantum state represents nothing more than an agent’s knowledge about a system). Confusion arises if the two views of collapse are conflated.

If we want to apply the collapse postulate, we need guidance as to when to apply it, and when to use the usual quantum dynamics, and textbooks are inevitably vague on this. In practice, this vagueness tends not to matter much.  But a thought-experiment devised by Eugene Wigner [5] imagines a situation in which it does matter. Brukner’s thought-experiment is a combination of Wigner’s thought-experiment and tests of Bell inequalities.

In the variant of Wigner’s thought-experiment invoked by Brukner, a friend of Wigner’s, named Friend, who is locked in a hermetically sealed lab, does an experiment, with two possible results, which we will call up and down, on a particle that is prepared in a particular, known quantum state, chosen so that the two outcomes of the experiment have equal probability. Wigner considers the quantum state of the content of Friend’s lab. If the collapse postulate is applied at the end of Friend’s experiment, the quantum state of the lab should be the one corresponding to the result that Friend obtained,  up or down.  If, on the other hand, the no-collapse rules of quantum state evolution apply, the quantum state is a state that is represented as a sum of up and down states.

Fig. 1. Wigner's Friend thought-experiment. From [3].

Moreover, if Wigner has unlimited powers of manipulation and no qualms about doing violence to his friend, the question of whether the quantum state is collapsed when Friend does her experiment can be decided experimentally.  The easiest way to do this would probably be to precisely reverse the velocity of everything inside Friend’s lab and wait a while, so that the experiment is undone, removing any trace, in Friend’s memory, her lab equipment, and any system that might carry a record of the experimental result, of the outcome of the experiment. For the sake of argument suppose this could be done.  Then, if no collapse has occurred, this would restore the original state of the particle that Friend experimented upon, and we could then do an experiment to test for this state.  Label the results of this experiment yes or no.  If no collapse occurs when Friend does her experiment, the result will be yes with certainty, and, if Friend’s experiment collapses the state, the result will be yes with probability ½ and no with probability ½. A Wigner with the powers we are imagining him to have could do the experiment repeatedly, and so determine whether or not Friend’s experiment collapses the quantum state.

What do the two observer-independent theories we have mentioned would say about this thought experiment? The de Broglie-Bohm theory says that the quantum state always obeys the usual, no-collapse law of evolution. However, the quantum state isn’t an exhaustive description of physical reality; at the end of Friend’s experiment, there is an objective matter of fact about which result she obtained. Wigner can verify that the quantum state has not collapsed, but only at the expense of erasing Friend’s memory and any other trace of the outcome. None of this is an ad hoc adjustment of the theory to handle cases like this, it’s what the theory, as we have it, tells us about this case.

A collapse theory would also say that Friend has obtained a definite result. But, on a theory like that, when Wigner does his experiment to determine whether the quantum state has collapsed, he would find that it has.

Obviously, Proietti et al. have not achieved a full-blown realization of the Wigner-Brukner thought-experiment. The equivalent of the Friend, in their experiment, is a single photon. The set-up of their experiment, unlike that of the full-blown Wigner’s Friend thought-experiment, is one in which collapse theories predict no collapse.

Puzzlement about the Wigner thought-experiment stems from the conjunction of (1) an assumption that, if the quantum state hasn’t collapsed, there’s no matter of fact about what the result of Friend’s experiment is (false on the de Broglie-Bohm theory) and (2) an assumption that Wigner will find that the state has not collapsed (false on a collapse theory).  Any theory according to which there is an objective, observer-independent world must violate one of these assumptions.

Brukner’s version of the thought-experiment involves a pair of hermetically sealed labs, each containing an observer playing the role of Wigner’s friend, and an observer outside each of these labs.  The external observers, named, Alice and Bob, each have a choice of two experiments that they can perform on the contents of the two labs (which, of course, include the internal observer,  who are named Charlie and Debbie).  The possible experiments of Alice (carried out on Charlie’s lab) are labelled A₁ and A₂, and the possible experiments of Bob (carried out on Debbie’s lab) are B₁ and B₂. The experiments A₁, B₁ are chosen so that they amount to asking Charlie and Debbie what they saw.  The experiments A₂, B₂ are chosen to be equivalent to the sort of experiment that Wigner is imagined to do, in the Wigner’s friend thought experiment.

Fig. 2. Brukner's thought-experiment. From [3].

Charlie and Debbie perform their experiments on a pair of particles prepared in a quantum state that is chosen so that (on the assumption that the usual rule of quantum evolution applies to their experiments, and there’s no collapse), the predicted quantum statistics for Alice and Bob’s experiment violate a Bell inequality. This has the consequence, via a theorem due to Arthur Fine [6], that we can’t think of these statistics as arising from a probability distribution over definite values of A₁, A₂, B₁, B₂, that are merely revealed upon measurement.

What does the de Broglie-Bohm theory say about this experiment?  First, that Charlie and Debbie will observe definite outcomes, and that Alice and Bob can learn these outcomes by performing experiments A₁ and B₁.  Second, if an A₂ experiment is performed on Charlie’s lab, all trace of Charlie’s result will be erased, and if a B₂ experiment is performed on Debbie’s lab, all trace of her result will be erased. 

The quantum state used in the experiment predicts correlations between the outcomes of the experiments, and the de Broglie-Bohm theory will get these right.  If A₁ B₁ experiments are performed in a repeated series of tests, Bob’s result will be correlated with Alice’s result, and hence with Charlie’s result, which is reflected in Alice’s.  If A₁ B₂ experiments are performed, again, Bob’s result will be correlated with Alice’s, and hence also with Charlie’s.  If A₂ B₁ experiments are performed, Alice’s result will be correlated with Bob’s, and hence also with Debbie’s.  It’s at this point that it looks like there’s a conflict with quantum mechanics.  If A₂ B₂ experiments are performed, the de Broglie-Bohm theory predicts that the results are correlated, just the way quantum mechanics says that they should be.  You might be tempted to conclude that, in this case, Alice’s result is still correlated with Debbie’s, and Bob’s with Charlie’s, on the (reasonable-seeming) assumption that Alice’s result is still the same as it would have been if Bob had done the B₁ experiment, and Bob’s result is the same as it would have been if Alice had done the A₁ experiment.

But (as I already mentioned) this can’t be done: there’s no way to maintain all four of the pairwise correlations:

1. The correlation between the results obtained by Charles and Debbie.

2. The correlation between the results of Alice’s A₂-experiment and Bob’s B₂-experiment.

3. The correlation between the result of Alice’s A₂-experiment and Debbie’s result, which we would have found if Bob had done a B₁-experiment.

4. The correlation between the result of Bob’s B₂-experiment and Charlie’s result, which we would have found if Alice had done an A₁-experiment.

For the cases in which Alice does an A₂-experiment and Bob does a B₂-experiment, the de Broglie-Bohm theory is obliged to respect the quantum correlations in (2).  Since Charlie and Debbie actually do their experiments, and obtain results (and, in principle, could have compared them if Alice and Bob had not intervened), the theory also respects the quantum correlations in (1).  It predicts that, in the cases in which Alice does an A₂-experiment and Bob does a B₂-experiment, at least one of the correlations (3) and (4), represented by blue lines in Figure 3, will be broken. Exactly how will depend crucially on the details of how the experiments are done (for example: if Alice does her experiment first, and then Bob, Alice’s results will still be correlated with Debbie’s, but Bob’s resuls won't be correlated with Charlie’s).

Figure 3. In the cases in which A₂ and B₂ experiments are done, the de Broglie-Bohm theory yields the quantum correlations between Charlie’s and Debbie’s results, and between Alice’s and Bob’s, at the expense of the correlations indicated by the blue lines. 

Could we check to see whether, in this case, the correlations (3) and (4) are maintained? No, because, as we’ve emphasized, Alice’s A₂-experiment requires erasing all trace of Charlie’s result, and Bob’s B₂-experiment requires erasing all trace of Debbie’s result.  The de Broglie-Bohm theory promises only to recover quantum probabilistic predictions for all records of experimental results that exist at a given time.  And it does that.

References

  

[1] “A quantum experiment suggests there’s no such thing as objective reality.” MIT Technology Review, March 12, 2019.

[2] Proietti, Massimo, et al. , “Experimental rejection of observer-independence in the quantum world.” arXiv:1902.05080v1 [quant-ph].

[3] Brukner, Časlav , “A No-Go Theorem for Observer-Independent Facts,” Entropy 20 (2018), 350.

[4] Myrvold, Wayne, Marco Genovese, Marco and Abner Shimony, “Bell’s Theorem.” The Stanford Encyclopedia of Philosophy (Spring 2019 Edition), Edward N. Zalta (ed.).

[5] Wigner, Eugene, “Remarks on the mind-body question,” in The Scientist Speculates, I. J. Good (ed.).   London, Heinemann, 1961: 284–302.

[6] Arthur Fine, “Hidden variables, joint probability, and the Bell inequalities.” Physical Review Letters 48 (1982): 291–295.

Actual philosophers talking about particle physics

In yesterday's Backreaction post, Sabine Hossenfelder takes on a paper by Bernardo Kastrup that argues for a form of panpsychism. Neither panpsychism nor Kastrup will receive any defense from me. What interests me is the way she summarizes her post at the end:

Summary: If a philosopher starts speaking about elementary particles, run.

Now, some people enjoy ridiculing philosophers who talk about things they don't understand. Those who want to engage in it will surely be disappointed to learn that Kastrup is not a professional philosopher. According to his website, his Ph.D. is in computer engineering. He lists no affiliation with any academic department of philosophy (though he does say that he has worked at CERN and at the Philips Research Laboratories).

This may leave readers wondering what sorts of things actual professional philosophers say when they talk about particle physics. If you're interested, I have two suggestions.

• One good place to start is the Epistemology of the LHC Project, based in Wuppertal.


• I also suggest,  as a general rule, that if you want a sense of what's happening in any area of philosophy of physics, take a look at recent issues of a journal that I co-edit, Studies in History and Philosophy of Modern Physics.  You can, for example, do a search on keyword "particle physics."     Run with it!

Earth-to-space quantum teleportation: not yet?

From The Guardian, July 12

The headlines the past few days have been full of stories about an experiment performed by a Chinese group of researchers.  You can read the report of the experiment here, if you like:

Ren, et al., Ground-to-satellite quantum teleportation, arXiv:1707.00934v1

The claims about ground-to-space quantum teleportation are, I'm sorry to say, misleading.  and not merely for the usual reason, that what's called "quantum teleportation" is nothing at all like a Star Trek transporter.  In this case, it's because what was done isn't even what's usually called quantum teleportation between the earth lab and the satellite.

The quantum teleportation protocol (see any good book on quantum information theory, or the original paper), involves preparing a pair of particles, say, photons, in a maximally entangled state.  One of the pair is given to Alice, the sender, and the other, to Bob, who is some distance away.   The cool thing is that, once they share this entangled pair, they can use it to prepare Bob's photon in some desired state (which might even be unknown to both Alice and Bob), with less classical communication than would otherwise be required.

Here's how it works.  Alice is given a photon in the desired state.  Call this photon #1, and call the pair shared by Alice and Bob, photons #2 and #3.  Alice performs what is known as a Bell-State Measurement (BSM) on photons 1 and 2.  This is an operation that leaves photons 1 and 2 in one of four maximally entangled states, and projects Bob's photon, #3, into a state that, depending on the outcome of the BSM, is either the desired state or related to it in a simple way.  Alice then communicates the result of the BSM to Bob (this involves distinguishing between four possibilities, and so requires only two classical bits), who then knows what he has to do to put his photon into the desired state.  The possible choices for the desired state are endless.  This means that communicating what the desired state is to Bob, via classical communication, would require an unlimited amount of classical communication.  The shared entanglement drastically reduces the amount of classical communication desired.

The key to this, and what makes it hard to do, is that Alice and Bob must first share entangled particles, and it's not easy to maintain entanglement over a distance.

But that's something that the Ren et al. teleportation experiment did not do.  They produced the entangled pair 2,3 in the earth-based lab (Ngiri), perform the Bell-State Measurement, which disentangles 2 from 3,  on the ground, and then send photon 3 to the satellite (Micius).  In the report, they write,

In the current work, the entangled photon source and the BSM are performed at the same location on the ground. A next step toward real network connections is to realize long-distance entanglement distribution prior to the BSM.

No long-distance entanglement, no long-distance teleportation.

In a separate experiment, reported in a paper uploaded one day after the first, the group exhibited long-distance entanglement distribution.

Yin, et al., Satellite-Based Entanglement Distribution Over 1200 kilometers. arXiv:1707.01339

 But, if I'm reading these papers correctly, they haven't yet combined the two.  So, they're close to earth-to-satellite quantum teleportation. But they're not there yet.

Did Bergson Influence Einstein’s Nobel Prize?

 In a recent book, The Physicist & the Philosopher (Princeton University Press, 2015), and in a Nautilus post a few weeks ago, historian Jimena Canales claims that the philosopher Henri Bergson’s criticisms of relativity theory influenced the Nobel Prize committee in its deliberations regarding a prize for Einstein, and helped ensure that there would be no Nobel Prize for relativity.

Interesting, if true.  Moreover, if true, this is something that has evaded Einstein’s biographers, and so would be a major contribution to Einstein scholarship.  But I’m not convinced.

Why not? Canales’ claim is based, not on new documentary evidence previously unavailable to historians, but on a novel and idiosyncratic reinterpretation of something that has long been in the public record, the presentation speech by Svante Arrhenius, Chair of the Nobel Prize Committee.  I don’t think that the text of the speech bears out Canales’ interpretation.  Moreover, Canales’ claim is at odds with the conclusion drawn by Abraham Pais, who was permitted to examine the documents considered by the Nobel Prize committee and devoted a section of his biography of Einstein to what he found.  I will quote Pais’ conclusion below.

Background: in 1905, his “annus mirabilis,” Einstein published a number of seminal papers.  This included the classic papers on special relativity, one on Brownian motion, and one in which he introduced the hypothesis of light quanta.  From this hypothesis Einstein derived a prediction about the photoelectric effect: that there would be a linear relation between the energy of electrons released by light impinging on a metal and the frequency of the light.  This relation was confirmed in 1916 by the careful experiments of Robert Millikan.  In 1915 Einstein added the general theory of relativity to his list of accomplishments, and it was Eddington's eclipse observations of 1919, verifying a prediction of general relativity, that brought him widespread fame outside the physics community.  By 1921 it was clear that he deserved a Nobel prize, and there was an embarrassment of riches as to what to base the award on.

Honestly, I would have regarded it as a tough call. The 1905 paper on special relativity is terrific, but it's largely a (much-needed) clarification of the foundations of electrodynamics, and much of its content is foreshadowed in the work of others, notably Lorentz and Poincaré. I've recently had occasion to read through much of Einstein's work on the light quantum hypothesis (in conjunction with supervising a dissertation by Molly Kao), and I've come to appreciate how instrumental Einstein was in the development of the quantum theory.  General relativity is certainly worth a Nobel Prize, but nonetheless, I’m not sure that the Nobel Prize committee’s decision to single out the light quantum work was not the right decision.

At any rate, in 1922 Einstein was awarded the Nobel Prize for 1921 (deferred one year).  The citation said that the Prize was “for his services to Theoretical Physics, and especially for his discovery of the law of the photoelectric effect.”  Here's what Arrhenius says in the opening of his presentation speech.

Your Majesty, Your Royal Highnesses, Ladies and Gentlemen.

There is probably no physicist living today whose name has become so widely known as that of Albert Einstein. Most discussion centres on his theory of relativity. This pertains essentially to epistemology and has therefore been the subject of lively debate in philosophical circles. It will be no secret that the famous philosopher Bergson in Paris has challenged this theory, while other philosophers have acclaimed it wholeheartedly. The theory in question also has astrophysical implications which are being rigorously examined at the present time.

Throughout the first decade of this century the so-called Brownian movement stimulated the keenest interest. In 1905 Einstein founded a kinetic theory to account for this movement by means of which he derived the chief properties of suspensions, i.e. liquids with solid particles suspended in them. This theory, based on classical mechanics, helps to explain the behaviour of what are known as colloidal solutions, a behaviour which has been studied by Svedberg, Perrin, Zsigmondy and countless other scientists within the context of what has grown into a large branch of science, colloid chemistry.

A third group of studies, for which in particular Einstein has received the Nobel Prize, falls within the domain of the quantum theory founded by Planck in 1900. This theory asserts that radiant energy consists of individual particles, termed “quanta”, approximately in the same way as matter is made up of particles, i.e. atoms. This remarkable theory, for which Planck received the Nobel Prize for Physics in 1918, suffered from a variety of drawbacks and about the middle of the first decade of this century it reached a kind of impasse. Then Einstein came forward with his work on specific heat and the photoelectric effect ...

Compare this with Canales’ account of the presentation speech (quoting from the Nautilus post, which reproduces, close to word-for-word, the opening pages of the book):

The chairman for the Nobel Committee for Physics explained that although “most discussion centers on his theory of relativity,” it did not merit the prize. Why not? The reasons were surely varied and complex, but the culprit mentioned that evening was clear: “It will be no secret that the famous philosopher Bergson in Paris has challenged this theory.” Bergson had shown that relativity “pertains to epistemology” rather than to physics—and so it “has therefore been the subject of lively debate in philosophical circles.”

One thing leaps out: Canales attributes a role to Bergson that  Arrhenius does not. Arrhenius does not say that Bergson had shown that relativity pertains to epistemology; he says that relativity “pertains especially to epistemology” and for this reason has been a topic of discussions, pro and con, by philosophers, and he says this before mentioning Bergson. He then says that the theory has been challenged by one philosopher, Bergson, and acclaimed wholeheartedly by others.

Crucially, he does not say that Bergson’s criticisms played any role in the Prize Committee’s deliberations. Canales says that it would have been clear to the audience that Bergson was being mentioned as an explanation for why it was the photoelectric effect, rather than relativity, that was singled out for specific recognition among Einstein’s contributions to theoretical physics, but this is her interpretation, and she offers no evidence that anyone in the audience took it that way.   Canales’ claim that Bergson’s criticisms influenced the Committee’s decision is based solely on this reading of what Arrhenius said that day; this seems to me a very thin thread on which to hang such a claim.

Some light on what did influence the decision is shed in the section entitled “How Einstein got the Nobel Prize” of Pais’ biography, ‘Subtle is the Lord...’. Pais was given access to Committee Reports and letters of proposal concerning Einstein's Nobel Prize, and he reports on these documents in that section.  Pais does not report any mention of  Bergson’s critiques during the Committee’s deliberations. What do seem to have played a crucial role are reports prepared in 1921 and 1922 by Committee member Allvar Gullstrand on the status of the theory of relativity, written at the request of the Committee.  These reports, says Pais, are “highly critical of relativity.”  (Canales omits mention of these reports, though, in the book, she cites this section of Pais’ book, and quotes from his conclusion.)

Pais sums up his conclusions about why Einstein was not awarded the Nobel Prize for relativity in the final paragraphs of that section, which I quote in full.

Why did Einstein not get the Nobel prize for relativity? Largely, I believe, because the Academy was under so much pressure to award him.  The many letters sent in his behalf were never the result of any campaign. Leading physicists had recognized him for what he was. It is understandable that the Academy was in no hurry to award relativity before experimental issues were clarified, first in special relativity, later in general relativity.  It was the Academy’s bad fortune not to have anyone among its members who could competently evaluate the content of relativity theory in early years.  Oseen’s proposal to give the award for the photoeffect must have come as a relief  of conflicting pressures.

Was the photoeffect worth a Nobel prize? Without a doubt. Einstein’s paper on that subject was the first application of quantum theory to systems other than pure radiation. That paper showed true genius. The order of awards for quantum physics was perfect: first Planck, then Einstein, then Bohr. It is a touching twist of history that the Committee, conservative by inclination, would honor Einstein for the most revolutionary contribution he ever made to physics.

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 n ∈ A, 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 {x_n} of real numbers is a computable sequence if and only if there is a computable function that yields rational approximations, within 2^-m, to x_n, 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 {x_n}, the sequence {χ_A(x_n)}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 f  is a real-valued  function on the reals that maps computable sequences to computable sequences, then, if {a_k}is a computable sequence that converges to a computable limit a, the sequence {f(a_k)} 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 d_A(x), defined as the greatest lower bound of |x – y| for y ∈ A, 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.