The Unsolvable Problem

The three of us were sitting together in a café in Seefeld, a small town deep in the Austrian Alps. It was the summer of 2012, and we were stuck. Not stuck in the café—the sun was shining, the snow on the Alps was glistening, and the beautiful surroundings were sorely tempting us to abandon the mathematical problem we were stuck on and head outdoors. We were trying to explore the connections between 20th-century mathematical results by Kurt Gödel and Alan Turing and quantum physics. That, at least, was the dream. A dream that had begun back in 2010, during a semester-long program on quantum information at the Mittag-Leffler Institute near Stockholm.

Some of the questions we were looking into had been explored before by others, but to us this line of research was entirely new, so we were starting with something simple. Just then, we were trying to prove a small and not very significant result to get a feel for things. For months now, we had had a proof (of sorts) of this result. But to make the proof work, we had to set up the problem in an artificial and unsatisfying way. It felt like changing the question to suit the answer, and we were not very happy with it. Picking the problem up again during the break after the first session of talks at the workshop in Seefeld that had brought us together in 2012, we still could not see any way around our problems. Half-jokingly, one of us (Michael Wolf) asked, “Why don’t we prove the undecidability of something people really care about, like the spectral gap?”

At the time, we were interested in whether certain problems in physics are “decidable” or “undecidable”—that is, can they ever be solved? We had gotten stuck trying to probe the decidability of a much more minor question, one few people care about. The “spectral gap” problem Michael was proposing that we tackle (which we will explain later) was one of central importance to physics. We did not know at the time whether this problem was or was not decidable (although we had a hunch it was not) or whether we would be able to prove it either way. But if we could, the results would be of real relevance to physics, not to mention a substantial mathematical achievement. Michael’s ambitious suggestion, tossed off almost as a jest, launched us on a grand adventure. Three years and 146 pages of mathematics later, our proof of the undecidability of the spectral gap was published in Nature.

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

To understand what this means, we need to go back to the beginning of the 20th century and trace some of the threads that gave rise to modern physics, mathematics and computer science. These disparate ideas all lead back to German mathematician David Hilbert, often regarded as the greatest figure of the past 100 years in the field. (Of course, no one outside of mathematics has heard of him. The discipline is not a good route to fame and celebrity, although it has its own rewards.)

The Mathematics of Quantum Mechanics

Hilbert’s influence on mathematics was immense. Early on, he developed a branch of mathematics called functional analysis—in particular, an area known as spectral theory, which would end up being key to the question within our proof. Hilbert was interested in this area for purely abstract reasons. But as so often happens, his mathematics turned out to be exactly what was necessary to understand a question that was perplexing physicists at the time.

If you heat a substance up, it begins to glow as the atoms in it emit light (hence the phrase “red hot”). The yellow-orange light from sodium street lamps is a good example: sodium atoms predominantly emit light at a wavelength of 590 nanometers, in the yellow part of the visible spectrum. Atoms absorb or release light when electrons within them “jump” between energy levels, and the precise frequency of that light depends on the energy gap between the levels. The frequencies of light emitted by heated materials thus give us a “map” of the gaps between the atom’s different energy levels. Explaining these atomic emissions was one of the problems physicists were wrestling with in the first half of the 20th century. The question led directly to the development of quantum mechanics, and the mathematics of Hilbert’s spectral theory played a prime role.

One of these gaps between quantum energy levels is especially important. The lowest possible energy level of a material is called its ground state. This is the level it will sit in when it has no heat. To get a material into its ground state, scientists must cool it down to extremely low temperatures in a laboratory. Then, if the material is to do anything other than sit in its ground state, something must excite it to a higher energy. The easiest way is for it to absorb the smallest amount of energy it can, just enough to take it to the next energy level above the ground state—the first excited state. The energy gap between the ground state and this first excited state is so critical that it is often just called the spectral gap.

In some materials, there is a large gap between the ground state and the first excited state. In other materials, the energy levels extend all the way down to the ground state without any gaps at all. Whether a material is “gapped” or “gapless” has profound consequences for its behavior at low temperatures. It plays a particularly significant role in quantum phase transitions.

A phase transition happens when a material undergoes a sudden and dramatic change in its properties. We are all very familiar with some phase transitions—such as water transforming from its solid form of ice into its liquid form when heated up. But there are more exotic quantum phase transitions that happen even when the temperature is kept extremely low. For example, changing the magnetic field around a material or the pressure it is subjected to can cause an insulator to become a superconductor or cause a solid to become a superfluid.

How can a material go through a phase transition at a temperature of absolute zero (−273.15 degrees Celsius), at which there is no heat at all to provide energy? It comes down to the spectral gap. When the spectral gap disappears—when a material is gapless—the energy needed to reach an excited state becomes zero. The tiniest amount of energy will be enough to push the material through a phase transition. In fact, thanks to the weird quantum effects that dominate physics at these very low temperatures, the material can temporarily “borrow” this energy from nowhere, go through a phase transition and “give” the energy back. Therefore, to understand quantum phase transitions and quantum phases, we need to determine when materials are gapped and when they are gapless.

Because this spectral gap problem is so fundamental to understanding quantum phases of matter, it crops up all over the place in theoretical physics. Many famous and long-standing open problems in condensed matter physics boil down to solving this problem for a specific material. A closely related question even crops up in particle physics: there is very good evidence that the fundamental equations describing quarks and their interactions have a “mass gap.” Experimental data from particle colliders such as the Large Hadron Collider near Geneva support this notion, as do massive number-crunching results from supercomputers. But proving the idea rigorously from the theory seems to be extremely difficult. So difficult, in fact, that this problem, called the Yang-Mills mass gap problem, has been named one of seven Millennium Prize problems by the Clay Mathematics Institute, and anyone who solves it is entitled to a $1-million prize. All these problems are particular cases of the general spectral gap question. We have bad news for anyone trying to solve them, though. Our proof shows that the general problem is even trickier than we thought. The reason comes down to a question called the Entscheidungsproblem.

Unanswerable Questions

By the 1920s Hilbert had become concerned with putting the foundations of mathematics on a firm, rigorous footing—an endeavor that became known as Hilbert’s program. He believed that whatever mathematical conjecture one might make, it will in principle be possible to prove either that it is true or that it is false. (It had better not be possible to prove that it is both, or something has gone very wrong with mathematics!) This idea might seem obvious, but mathematics is about establishing concepts with absolute certainty. Hilbert wanted a rigorous proof.

In 1928 he formulated the Entscheidungsproblem. In English this translates to “the decision problem.” It asks whether there is a procedure, or “algorithm,” that can decide whether mathematical statements are true or false.

For example, the statement “Multiplying any whole number by 2 gives an even number” can easily be proved true, using basic logic and arithmetic. Other statements are less clear. What about the following example? “If you take any whole number, and repeatedly multiply it by 3 and add 1 if it’s odd, or divide it by 2 if it’s even, you always eventually reach the number 1.” (Have a think about it.)

Unfortunately for Hilbert, his hopes were to be dashed. In 1931 Gödel published some remarkable results now known as his incompleteness theorems. Gödel showed that there are perfectly reasonable mathematical statements about whole numbers that can be neither proved nor disproved. In a sense, these statements are beyond the reach of logic and arithmetic. And he proved this assertion. If that is hard to wrap your head around, you are in good company. Gödel’s incompleteness theorems shook the foundations of mathematics to the core.

Here is a flavor of Gödel’s idea: If someone tells you, “This sentence is a lie,” is that person telling the truth or lying? If he or she is telling the truth, then the statement must indeed be a lie. But if he or she is lying, then it is true. This quandary is known as the liar paradox. Even though it appears to be a perfectly reasonable English sentence, there is no way to determine whether it is true or false. What Gödel managed to do was to construct a rigorous mathematical version of the liar paradox using only basic arithmetic.

The next major player in the story of the Entscheidungsproblem is Alan Turing, the English computer scientist. Turing is most famous among the general public for his role in breaking the German Enigma code during World War II. But among scientists, he is best known for his 1937 paper “On Computable Numbers, with an Application to the Entscheidungsproblem.” Strongly influenced by Gödel’s result, the young Turing had given a negative answer to Hilbert’s Entscheidungsproblem by proving that no general algorithm to decide whether mathematical statements are true or false can exist. (American mathematician Alonzo Church also independently proved this just before Turing. But Turing’s proof was ultimately more significant. Often in mathematics, the proof of a result turns out to be more important than the result itself.)

To solve the Entscheidungsproblem, Turing had to pin down precisely what it meant to “compute” something. Nowadays we think of computers as electronic devices that sit on our desk, on our lap or even in our pocket. But computers as we know them did not exist in 1936. In fact, “computer” originally meant a person who carried out calculations with pen and paper. Nevertheless, computing with pen and paper as you did in high school is mathematically no different from computing with a modern desktop computer—just much slower and far more prone to mistakes.

Turing came up with an idealized, imaginary computer called a Turing machine. This very simple imaginary machine does not look like a modern computer, but it can compute everything that the most powerful modern computer can. In fact, any question that can ever be computed (even on quantum computers or computers from the 31st century that have yet to be invented) could also be computed on a Turing machine. It would just take the Turing machine much longer.

A Turing machine has an infinitely long ribbon of tape and a “head” that can read and write one symbol at a time on the tape, then move one step to the right or left along it. The input to the computation is whatever symbols are originally written on the tape, and the output is whatever is left written on it when the Turing machine finally stops running (halts). The invention of the Turing machine was more important even than the solution to the Entscheidungsproblem. By giving a precise, mathematically rigorous formulation of what it meant to make a computation, Turing founded the modern field of computer science.

Having constructed his imaginary mathematical model of a computer, Turing then went on to prove that there is a simple question about Turing machines that no mathematical procedure can ever decide: Will a Turing machine running on a given input ever halt? This question is known as the halting problem. At the time, this result was shocking. Mathematicians have become accustomed to the fact that any conjecture we are working on could be provable, disprovable or undecidable.

Where We Come In

In our result, we had to tie all these disparate threads back together. We wanted to unite the quantum mechanics of the spectral gap, the computer science of undecidability and Hilbert’s spectral theory to prove that—like the halting problem—the spectral gap problem was one of the undecidable ones that Gödel and Turing taught us about.

Chatting in that café in Seefeld in 2012, we had an idea for how we might be able to prove a weaker mathematical result related to the spectral gap. We tossed this idea around, not even scribbling on the back of a napkin, and it seemed like it might work. Then the next session of talks started. And there we left it.

A few months later one of us (Toby Cubitt) visited Michael in Munich, and we did what we had not done in Seefeld: jotted some equations down on a scrap of paper and convinced ourselves the idea worked. In the following weeks, we completed the argument and wrote it up properly in a private four-page note. (Nothing in mathematics is truly proved until you write it down—or, better still, type it up and show it to a colleague for scrutiny.) Conceptually this was a major advance. Before that, the idea of proving the undecidability of the spectral gap was more of a joke than a serious prospect. Now we had the first glimmerings that it might actually be possible. But there was still a very long way to go. We could not extend our initial idea to prove the undecidability of the spectral gap problem itself.

Burning the Midnight Coffee

We attempted to make the next leap by linking the spectral gap problem to quantum computing. In 1985 Nobel Prize–winning physicist Richard Feynman published one of the papers that launched the idea of quantum computers. In that paper, Feynman showed how to relate ground states of quantum systems to computation. Computation is a dynamic process: you supply the computer with input, and it goes through several steps to compute a result and outputs the answer. But ground states of quantum systems are completely static: the ground state is just the configuration a material sits in at zero temperature, doing nothing at all. So how can it make a computation?

The answer comes through one of the defining features of quantum mechanics: superposition, which is the ability of objects to occupy many states simultaneously, as, for instance, Erwin Schrödinger’s famous quantum cat can be alive and dead at the same time. Feynman proposed constructing a quantum state that is in a superposition of the various steps in a computation—initial input, every intermediate step of the computation and final output—all at once. Alexei Kitaev of the California Institute of Technology later developed this idea substantially by constructing an imaginary quantum material whose ground state looks exactly like this.

If we used Kitaev’s construction to put the entire history of a Turing machine into the material’s ground state in superposition, could we transform the halting problem into the spectral gap problem? In other words, could we show that any method for solving the spectral gap problem would also solve the halting problem? Because Turing had already shown that the halting problem was undecidable, this would prove that the spectral gap problem must also be undecidable.

Encoding the halting problem in a quantum state was not a new idea. Seth Lloyd, now at the Massachusetts Institute of Technology, had proposed this almost two decades earlier to show the undecidability of another quantum question. Daniel Gottesman of the Perimeter Institute for Theoretical Physics in Waterloo and Sandy Irani of the University of California, Irvine, had used Kitaev’s idea to prove that even single lines of interacting quantum particles can show very complex behavior. In fact, it was Gottesman and Irani’s version of Kitaev’s construction that we hoped to make use of.

But the spectral gap is a different kind of problem, and we faced some apparently insurmountable mathematical obstacles. The first had to do with supplying the input into the Turing machine. Remember that the undecidability of the halting problem is about whether the Turing machine halts on a given input. How could we design our imaginary quantum material in a way that would let us choose the input to the Turing machine to be encoded in the ground state?

When working on that earlier problem (the one we were still stuck on in the café in Seefeld), we had an idea of how to rectify the issue by putting a “twist” in the interactions between the particles and using the angle of this rotation to create an input to the Turing machine. In January 2013 we met at a conference in Beijing and discussed this plan together. But we quickly realized that what we had to prove came very close to contradicting known results about quantum Turing machines. We decided we needed a complete and rigorous proof that our idea worked before we pursued the project further.

At this point, Toby had been part of David Pérez-García’s group at Complutense University of Madrid for more than two years. In that same month he moved to the University of Cambridge, but his new apartment there was not yet ready, so his friend and fellow quantum information theorist Ashley Montanaro offered to put him up. For those two months, he set to work producing a rigorous proof of this idea. His friend would find him at the kitchen table in the morning, a row of empty coffee mugs next to him, about to head to bed, having worked through the night figuring out details and typing them up. At the end of those two months, Toby sent around the completed proof.

In Remembrance of Tilings Past

This 29-page proof showed how to overcome one of the obstacles to connecting the ground state of a quantum material to computation with a Turing machine. But there was an even bigger obstacle to that goal: the resulting quantum material was always gapless. If it is always gapless, the spectral gap problem for this particular material is very easy to solve: the answer is gapless!

Our first idea from Seefeld, which proved a much weaker result than we wanted, nonetheless managed to get around this obstacle. The key was using “tilings.” Imagine you are covering a large bathroom floor with tiles. In fact, imagine it is an infinitely big bathroom. The tiles have a very simple pattern on them: each of the four sides of the tile is a different color. You have various boxes of tiles, each with a different arrangement of colors. Now imagine there is an infinite supply of tiles in each box. You, of course, want to tile the infinite bathroom floor so that the colors on adjacent tiles match. Is this possible?

The answer depends on which boxes of tiles you have available. With some sets of colored tiles, you will be able to tile the infinite bathroom floor. With others, you will not. Before you select which boxes of tiles to buy, you would like to know whether or not they will work. Unfortunately for you, in 1966 mathematician Robert Berger proved that this problem is undecidable.

One easy way to tile the infinite bathroom floor would be to first tile a small rectangle so that colors on opposite sides of it match. You could then cover the entire floor by repeating this rectangular pattern. Because they repeat every few tiles, such patterns are called periodic. The reason the tiling problem is undecidable is that nonperiodic tilings also exist: patterns that cover the infinite floor but never repeat.

Back when we were discussing our first small result, we studied a 1971 simplification of Berger’s original proof made by Raphael M. Robinson of the University of California, Berkeley. Robinson constructed a set of 56 different tiles that, when used to tile the floor, produce an interlocking pattern of ever larger squares. This fractal pattern looks periodic, but in fact, it never quite repeats itself. We extensively discussed ways of using tiling results to prove the undecidability of quantum properties. But back then, we were not even thinking about the spectral gap. The idea lay dormant.

In April 2013 Toby paid a visit to Charlie Bennett at IBM’s Thomas J. Watson Research Center. Among Bennett’s many achievements before becoming one of the founding fathers of quantum information theory was his seminal 1970s work on Turing machines. We wanted to quiz him about some technical details of our proof to make sure we were not overlooking something. He said he had not thought about this stuff for 40 years, and it was high time a younger generation took over. (He then went on to very helpfully explain some subtle mathematical details of his 1970s work, which reassured us that our proof was okay.)

Bennett has an immense store of scientific knowledge. Because we had been talking about Turing machines and undecidability, he e-mailed copies of a couple of old papers on undecidability he thought might interest us. One of these was the same 1971 paper by Robinson that we had studied. Now the time was right for the ideas sowed in our earlier discussions to spring to life. Reading Robinson’s paper again, we realized it was exactly what we needed to prevent the spectral gap from vanishing.

Our initial idea had been to encode one copy of the Turing machine into the ground state. By carefully designing the interactions between the particles, we could make the ground state energy a bit higher if the Turing machine halted. The spectral gap—the energy jump to the first excited state—would then depend on whether the Turing machine halted or not. There was just one problem with this idea, and it was a big one. As the number of particles increased, the additional contribution to the ground state energy got closer and closer to zero, leading to a material that was always gapless.

But by adapting Berger’s tiling construction, we could instead encode many copies of exactly the same Turing machine into the ground state. In fact, we could attach one copy to each square in Robinson’s tiling pattern. Because these are identical copies of the same Turing machine, if one of them halts, they all halt. The energy contributions from all these copies add up. As the number of particles increases, the number of squares in the tiling pattern gets bigger. Thus, the number of copies of the Turing machine increases, and their energy contribution becomes huge, giving us the possibility of a spectral gap.

Exams and Deadlines

One significant weakness remained in the result we had proved. We could not say anything about how big the energy gap was when the material was gapped. This uncertainty left our result open to the criticism that the gap could be so small that it might as well not exist. We needed to prove that the gap, when it existed, was actually large. The first solution we found arose when we considered materials in three dimensions instead of the planar materials we had been thinking about until then.

When you cannot stop thinking about a mathematical problem, you make progress in the most unexpected places. David worked on the details of this idea in his head while he was supervising an exam. Walking along the rows of tables in the hall, he was totally oblivious to the students working feverishly around him. Once the test was over, he committed this part of the proof to paper.

We now knew that getting a big spectral gap was possible. Could we also get it in two dimensions, or were three necessary? Remember the problem of tiling an infinite bathroom floor. What we needed to show was that for the Robinson tiling, if you got one tile wrong somewhere but the colors still matched everywhere else, then the pattern formed by the tiles would be disrupted only in a small region centered on that wrong tile. If we could show this “robustness” of the Robinson tiling, it would imply that there was no way of getting a small spectral gap by breaking the tiling only a tiny bit.

By the late summer of 2013, we felt we had all the ingredients for our proof to work. But there were still some big details to be resolved, such as proving that the tiling robustness could be merged with all the other proof ingredients to give the complete result. The Isaac Newton Institute for Mathematical Science in Cambridge, England, was hosting a special workshop on quantum information for the whole of the autumn semester of 2013. All three of us were invited to attend. It was the perfect opportunity to work together on finishing the project. But David was not able to stay in Cambridge for long. We were determined to complete the proof before he left.

The Isaac Newton Institute has blackboards everywhere—even in the bathrooms! We chose one of the blackboards in a corridor (the closest to the coffee machine) for our discussions. We spent long hours at the blackboard developing the missing ideas, then divided the task of making these ideas mathematically rigorous among us. This process always takes far more time and effort than it seems on the blackboard. As the date of David’s departure loomed, we worked without interruption all day and most of the night. Just a few hours before he left for home, we finally had a complete proof.

In physics and mathematics, researchers make most results public for the first time by posting a draft paper to the arXiv.org preprint server before submitting it to a journal for peer review. Although we were now fairly confident the entire argument worked and the hardest part was behind us, our proof was not ready to be posted. There were many mathematical details to be filled in. We also wanted to rewrite and tidy up the paper (we hoped to reduce the page count in the process, although in this we would completely fail). Most important, although at least one of us had checked every part of the proof, no one had gone through it all from beginning to end.

In summer 2014 David was on a sabbatical at the Technical University of Munich with Michael. Toby went out to join them. The plan was to spend this time checking and completing the whole proof, line by line. David and Toby were sharing an office. Each morning David would arrive with a new printout of the draft paper, copious notes and questions scribbled in the margins and on interleaved sheets. The three of us would get coffee and then pick up where we had left off the day before, discussing the next section of the proof at the blackboard. In the afternoon, we divided up the work of rewriting the paper and adding the new material and of going through the next section of the proof. Toby was suffering from a slipped disc and could not sit down, so he worked with his laptop propped on top of an upturned garbage bin on top of the desk. David sat opposite, the growing pile of printouts and notes taking up more and more of his desk. On a couple of occasions, we found significant gaps in the proof. These turned out to be surmountable, but bridging them meant adding substantial material to it. The page count continued to grow.

After six weeks, we had checked, completed and improved every single line of the proof. It would take another six months to finish writing everything up. Finally, in February 2015, we uploaded the paper to arXiv.org.

What It All Means

Ultimately what do these 146 pages of complicated mathematics tell us?

First, and most important, they give a rigorous mathematical proof that one of the basic questions of quantum physics cannot be solved in general. Note that the “in general” here is critical. Even though the halting problem is undecidable in general, for particular inputs to a Turing machine, it is often still possible to say whether it will halt or not. For example, if the first instruction of the input is “halt,” the answer is pretty clear. The same goes if the first instruction tells the Turing machine to loop forever. Thus, although undecidability implies that the spectral gap problem cannot be solved for all materials, it is entirely possible to solve it for specific materials. In fact, condensed matter physics is littered with such examples. Nevertheless, our result proves rigorously that even a perfect, complete description of the microscopic interactions between a material’s particles is not always enough to deduce its macroscopic properties.

You may be asking yourself if this finding has any implications for “real physics.” After all, scientists can always try to measure the spectral gap in experiments. Imagine if we could engineer the quantum material from our mathematical proof and produce a piece of it in the lab. Its interactions are so extraordinarily complicated that this task is far, far beyond anything scientists are ever likely to be able to do. But if we could and then took a piece of it and tried to measure its spectral gap, the material could not simply throw up its hands and say, “I can’t tell you—it’s undecidable.” The experiment would have to measure something.

The answer to this apparent paradox lies in the fact that, strictly speaking, the terms “gapped” and “gapless” make mathematical sense only when the piece of material is infinitely large. Now, the 10²³ or so atoms contained in even a very small piece of material represent a very large number indeed. For normal materials, this is close enough to infinity to make no difference. But for the very strange material constructed in our proof, large is not equivalent to infinite. Perhaps with 10²³ atoms, the material appears in experiments to be gapless. Just to be sure, you take a sample of material twice the size and measure again. Still gapless. Then, late one night, your graduate student comes into the lab and adds just one extra atom. The next morning, when you measure it again, the material has become gapped! Our result proves that the size at which this transition may occur is incomputable (in the same Gödel-Turing sense that you are now familiar with). This story is completely hypothetical for now because we cannot engineer a material this complex. But it shows, backed by a rigorous mathematical proof, that scientists must take special care when extrapolating experimental results to infer the behavior of the same material at larger sizes.

After the work described here was complete, we went on to extend it to one-dimensional systems and phase diagrams. Other important problems in quantum physics have since been shown to be undecidable using techniques from computer science, with profound consequences for mathematics. In 1935 Einstein, Podolsky and Rosen realized that quantum mechanics predicted what they called “spooky action at distance”—correlations between pairs of entangled quantum particles that are not possible under classical physics. In a major breakthrough, a team led by Zhengfeng Ji of the University of Technology Sydney recently announced a result proving that estimating such correlations, even to within some reasonable precision, is undecidable in general. Their result disproves a deep conjecture in mathematics that had been open for more than 40 years.

And now we come back to the Yang-Mills problem—the question of whether the equations describing quarks and their interactions have a mass gap. Computer simulations indicate that the answer is yes, but our result suggests that determining for sure may be another matter. Could it be that the computer-simulation evidence for the Yang-Mills mass gap would vanish if we made the simulation just a tiny bit larger? Our result cannot say, but it does open the door to the intriguing possibility that the Yang-Mills problem, and other problems important to physicists, may be undecidable.

And what of that original small and not very significant result we were trying to prove all those years ago in a café in the Austrian Alps? Actually, we are still working on it.