The Universe’s Ultimate Complexity Revealed by Simple Quantum Games

One of the biggest and most basic questions in physics involves the number of ways to configure the matter in the universe. If you took all that matter and rearranged it, then rearranged it again, then rearranged it again, would you ever exhaust the possible configurations, or could you go on reconfiguring forever?

Physicists don’t know, but in the absence of certain knowledge, they make assumptions. And those assumptions differ depending on the area of physics they happen to be in. In one area they assume the number of configurations is finite. In another they assume it’s infinite. For now, at least, there’s no way to tell who’s right.

But over the last couple years, a select group of mathematicians and computer scientists has been busy creating games that could theoretically settle the question. The games involve two players placed in isolation from each other. The players are asked questions, and they win if their answers are coordinated in a certain way. In all of these games, the rate at which players win has implications for the number of different ways the universe can be configured.

“There’s this philosophical question: Is the universe finite or infinite-dimensional?” said Henry Yuen, a theoretical computer scientist at the University of Toronto. “People will think this is something you can never test, but one possible way of resolving this is with a game like what William came up with.”

Yuen was referring to William Slofstra, a mathematician at the University of Waterloo. In 2016 Slofstra invented a game that involves two players who assign values to variables in hundreds of simple equations. Under normal circumstances even the most cunning players will sometimes lose. But Slofstra proved that if you give them access to an infinite amount of an unorthodox resource — entangled quantum particles — it becomes possible for the players to win this game all the time.

Other researchers have since refined Slofstra’s result. They’ve proved that you don’t need a game with hundreds of questions to reach the same conclusion Slofstra did. In 2017 three researchers proved that there are games with just five questions that can be won 100 percent of the time if the players have access to an unlimited number of entangled particles.

These games are all modeled on games invented more than 50 years ago by the physicist John Stewart Bell. Bell developed the games to test one of the strangest propositions about the physical world made by the theory of quantum mechanics. A half-century later, his ideas may turn out to be useful for much more than that.

Magic Squares

Bell came up with “nonlocal” games, which require players to be at a distance from each other with no way to communicate. Each player answers a question. The players win or lose based on the compatibility of their answers.

One such game is the magic square game. There are two players, Alice and Bob, each with a 3-by-3 grid. A referee tells Alice to fill out one particular row in the grid — say the second row — by putting either a 1 or a 0 in each box, such that the sum of the numbers in that row is odd. The referee tells Bob to fill out one column in the grid — say the first column — by putting either a 1 or a 0 in each box, such that the sum of the numbers in that column is even. Alice and Bob win the game if Alice’s numbers give an odd sum, Bob’s give an even sum, and — most important — they’ve each written down the same number in the one square where their row and column intersect.

Here’s the catch: Alice and Bob don’t know which row or column the other has been asked to fill out. “It’s a game that would be trivial for the two players if they could communicate,” said Richard Cleve, who studies quantum computing at the University of Waterloo. “But the fact that Alice doesn’t know what question Bob was asked and vice versa means it’s a little tricky.”

In the magic square game, and other games like it, there doesn’t seem to be a way for the players to win 100 percent of the time. And indeed, in a world completely explained by classical physics, 89 percent is the best Alice and Bob could do.

But quantum mechanics — specifically, the bizarre quantum phenomenon of “entanglement” — allows Alice and Bob to do better.

In quantum mechanics, the properties of fundamental particles like electrons don’t exist until the moment you measure them. Imagine, for example, an electron moving rapidly around the circumference of a circle. To find its position you perform a measurement. But prior to the measurement, the electron has no definite position at all. Instead, the electron is characterized by a mathematical formula expressing the likelihood that it’s in any given position.

When two particles are entangled, the complex probability amplitudes that describe their properties are intertwined. Imagine two electrons that were entangled such that if a measurement identifies the first electron in one position around the circle, the other must occupy a position directly across the circle from it. This relationship between the two electrons holds when they’re right next to each other and when they’re light-years apart: Even at that distance, if you measure the position of one electron, the position of the other becomes instantly determined, even though no causal event has passed between them.

The phenomenon seems preposterous because there’s nothing about our non-quantum-scale experience to suggest such a thing is possible. Albert Einstein famously derided entanglement as “spooky action at a distance” and argued for years that it couldn’t be true.

To implement a quantum strategy in the magic square game, Alice and Bob each take one of a pair of entangled particles. To determine which numbers to write down, they measure properties of their particles — almost as if they were rolling correlated dice to guide their choice of answers.

What Bell calculated, and what many subsequent experiments have shown, is that by exploiting the strange quantum correlations found in entanglement, players of games like the magic square game can coordinate their answers with greater exactness and win the game more than 89 percent of the time.

Bell came up with nonlocal games as a way to show that entanglement was real, and that our classical view of the world was incomplete — a conclusion that was very much up for grabs in Bell’s time. “Bell came up with this experiment you could do in a laboratory,” Cleve said. If you recorded higher-than-expected success rates in these experimental games, you’d know the players had to be exploiting some feature of the physical world not explained by classical physics.

What Slofstra and others have done since then is similar in strategy, but different in scope. They’ve shown that not only do Bell’s games imply the reality of entanglement, but some games have the power to imply a whole lot more — like whether there is any limit to the number of configurations the universe can take.

More Entanglement, Please

In his 2016 paper Slofstra proposed a kind of nonlocal game involving two players who provide answers to simple questions. To win, they have to give responses that are coordinated in a certain way, as in the magic square game.

Imagine, for example, a game that involves two players, Alice and Bob, who have to match socks from their respective sock drawers. Each player has to choose a single sock, without any knowledge of the sock the other has chosen. The players can’t coordinate ahead of time. If their sock choices form a matching pair, they win.

Given these uncertainties it’s unclear which socks Alice and Bob should pick in the morning — at least in a classical world. But if they can employ entangled particles they have a better chance of matching. By basing their color choice on the results of measurements of a single pair of entangled particles they could coordinate along that one attribute of their socks.

Yet they’d still be guessing blindly about all the other attributes — whether they were wool or cotton, ankle-height or crew. But with additional entangled particles they’d get access to more measurements. They could use one set to correlate their choice of material and another to correlate their choice of sock height. In the end, because they were able to coordinate their choices for many attributes, they’d be more likely to end up with a matching pair than if they’d only been able to coordinate for one.

“More complicated systems allow for more correlated measurements, which enable coordination at more complicated tasks,” Slofstra said.

The questions in Slofstra’s game aren’t really about socks. They involve equations such as a + b + c and b + c + d. Alice can make the value of each variable either 1 or 0 (and the values have to remain consistent across the equations — b has to have the same value in every equation where it appears). And her equations have to sum to various numbers.

Bob is given just one of Alice’s variables, say b, and asked to assign a value to it: 0 or 1. The players win if they both assign the same value to whichever variable Bob is given.

If you and a friend were to play this game, there’s no way you could win it all the time. But with the aid of a pair of entangled particles, you could win more consistently, as in the sock game.

Slofstra was interested in understanding whether there is an amount of entanglement past which a team’s winning probability stops increasing. Perhaps players could achieve an optimal strategy if they shared five pairs of entangled particles, or 500. “We’d hoped you could say, ‘You need this much entanglement to play it optimally,’” Slofstra said. “That’s not what is true.”

He found that adding more pairs of entangled particles always increased the winning percentage. Moreover, if you could somehow exploit an infinite number of entangled particles, you would be able to play the game perfectly, winning 100 percent of the time. This clearly can’t be done in a game with socks — ultimately you’d run out of sock features to coordinate. But as Slofstra’s game has made clear, the universe can be far knottier than a sock drawer.

Is the Universe Infinite?

Slofstra’s result came as a shock. Eleven days after his paper appeared, the computer scientist Scott Aaronson wrote that Slofstra’s result touches “on a question of almost metaphysical significance: namely, what sorts of experimental evidence could possibly bear on whether the universe was discrete or continuous?”

Aaronson was referring to the different states the universe can take — where a state is a particular configuration of all the matter within it. Every physical system has its own state space, which is an index of all the different states it can take.

Researchers talk about a state space as having a certain number of dimensions, reflecting the number of independent characteristics you can adjust in the underlying system.

For example, even a sock drawer has a state space. Any sock might be described by its color, its length, its material, and how raggedy and worn it is. In this case, the dimension of the sock drawer’s state space is four.

A deep question about the physical world is whether there’s a limit to the size of the state space of the universe (or of any physical system). If there is a limit, it means that no matter how large and complicated your physical system is, there are still only so many ways it can be configured. “The question is whether physics allows there to be physical systems that have an infinite number of properties that are independent of each other that you could in principle observe,” said Thomas Vidick, a computer scientist at the California Institute of Technology.

The field of physics is undecided on this point. In fact, it maintains two contradictory views.

On the one hand, students in an introductory quantum mechanics course are taught to think in terms of infinite-dimensional state spaces. If they model the position of an electron moving around a circle, for instance, they’ll assign a probability to each point on the circle. Because there are infinite points, the state space describing the electron’s position will be infinite-dimensional.

“In order to describe the system we need a parameter for every possible position the electron can be in,” Yuen said. “There are infinitely many positions, so you need infinitely many parameters. Even in one-dimensional space [like the circle], the state space of the particle is infinite-dimensional.”

But perhaps the idea of infinite-dimensional state spaces is nonsense. In the 1970s, the physicists Jacob Bekenstein and Stephen Hawking calculated that a black hole is the most complicated physical system in the universe, yet even its state can be specified by a huge but finite number of parameters — approximately 10⁶⁹ bits of information per square meter of the black hole’s event horizon. This number — the “Bekenstein bound” — suggests that if a black hole doesn’t require an infinite-dimensional state space, then nothing does.

These competing perspectives on state spaces reflect fundamentally different views about the nature of physical reality. If state spaces are truly finite-dimensional, this means that at the smallest scale, nature is pixelated. But if electrons require infinite-dimensional state spaces, physical reality is fundamentally continuous — an unbroken sheet even at the finest resolution.

So which is it? Physics hasn’t devised an answer, but games like Slofstra’s could, in principle, provide one. Slofstra’s work suggests a way to test the distinction: Play a game that can only be won 100 percent of the time if the universe allows for infinite-dimensional state spaces. If you observe players winning every time they play, it means they’re taking advantage of the kinds of correlations that can only be generated through measurements on a physical system with an infinite number of independently tunable parameters.

“He gives an experiment such that, if it can be realized, then we conclude the system that produced the statistics that were observed must have infinite degrees of freedom,” Vidick said.

There are barriers to actually carrying out Slofstra’s experiment. For one thing, it’s impossible to certify any laboratory result as occurring 100 percent of the time.

“In the real world you’re limited by your experimental setup,” Yuen said. “How do you distinguish between 100 percent and 99.9999 percent?”

But practical considerations aside, Slofstra has shown that there is, mathematically at least, a way of assessing a fundamental feature of the universe that might otherwise have seemed beyond our ken. When Bell first came up with nonlocal games, he hoped that they’d be useful for probing one of the most beguiling phenomena in the universe. Fifty years later, his invention has proved to have even more depth than that.