3175x175(CURRENT).thumb.jpg.b05acc060982b36f5891ba728e6d953c.jpg)
Two researchers have proved that Penrose tilings, famous patterns that never repeat, are mathematically equivalent to a kind of quantum error correction.
If you want to tile a bathroom floor, square tiles are the simplest option—they fit together without any gaps in a grid pattern that can continue indefinitely. That square grid has a property shared by many other tilings: Shift the whole grid over by a fixed amount, and the resulting pattern is indistinguishable from the original. But to many mathematicians, such “periodic” tilings are boring. If you’ve seen one small patch, you’ve seen it all.
In the 1960s, mathematicians began to study “aperiodic” tile sets with far richer behavior. Perhaps the most famous is a pair of diamond-shaped tiles discovered in the 1970s by the polymathic physicist and future Nobel laureate Roger Penrose. Copies of these two tiles can form infinitely many different patterns that go on forever, called Penrose tilings. Yet no matter how you arrange the tiles, you’ll never get a periodic repeating pattern.
“These are tilings that shouldn’t really exist,” said Nikolas Breuckmann, a physicist at the University of Bristol.
For over half a century, aperiodic tilings have fascinated mathematicians, hobbyists, and researchers in many other fields. Now, two physicists have discovered a connection between aperiodic tilings and a seemingly unrelated branch of computer science: the study of how future quantum computers can encode information to shield it from errors. In a paper posted to the preprint server arxiv.org in November, the researchers showed how to transform Penrose tilings into an entirely new type of quantum error-correcting code. They also constructed similar codes based on two other kinds of aperiodic tiling.
At the heart of the correspondence is a simple observation: In both aperiodic tilings and quantum error-correcting codes, learning about a small part of a large system reveals nothing about the system as a whole.
“It’s one of those beautiful things that seems obvious in retrospect,” said Toby Cubitt, a quantum information researcher at University College London. “You’re like, ‘Why didn’t I think of that?’”
Forbidden Knowledge
Ordinary computers represent information using bits with two distinct states, labeled 0 and 1. Quantum bits, or qubits, likewise have two states, but they can also be coaxed into so-called superpositions in which their 0 and 1 states coexist. By harnessing more elaborate superpositions involving many qubits, quantum computers can perform certain computations much faster than any conventional machine.
Yet quantum superpositions are skittish creatures. Measure a qubit in a superposition state and it will collapse to either 0 or 1, wiping out any computation in progress. To make matters worse, errors stemming from feeble interactions between qubits and their environment can mimic the destructive effects of measurement. Anything that rubs a qubit the wrong way, whether it’s a nosy researcher or a stray photon, can spoil the computation.
This extreme fragility might make quantum computing sound hopeless. But in 1995, the applied mathematician Peter Shor discovered a clever way to store quantum information. His encoding had two key properties. First, it could tolerate errors that only affected individual qubits. Second, it came with a procedure for correcting errors as they occurred, preventing them from piling up and derailing a computation. Shor’s discovery was the first example of a quantum error-correcting code, and its two key properties are the defining features of all such codes.
The first property stems from a simple principle: Secret information is less vulnerable when it’s divided up. Spy networks employ a similar strategy. Each spy knows very little about the network as a whole, so the organization remains safe even if any individual is captured. But quantum error-correcting codes take this logic to the extreme. In a quantum spy network, no single spy would know anything at all, yet together they’d know a lot.
Each quantum error-correcting code is a specific recipe for distributing quantum information across many qubits in a collective superposition state. This procedure effectively transforms a cluster of physical qubits into a single virtual qubit. Repeat the process many times with a large array of qubits, and you’ll get many virtual qubits that you can use to perform computations.
The physical qubits that make up each virtual qubit are like those oblivious quantum spies. Measure any one of them and you’ll learn nothing about the state of the virtual qubit it’s a part of—a property called local indistinguishability. Since each physical qubit encodes no information, errors in single qubits won’t ruin a computation. The information that matters is somehow everywhere, yet nowhere in particular.
“You can’t pin it down to any individual qubit,” Cubitt said.
All quantum error-correcting codes can absorb at least one error without any effect on the encoded information, but they will all eventually succumb as errors accumulate. That’s where the second property of quantum error-correcting codes kicks in—the actual error correction. This is closely related to local indistinguishability: Because errors in individual qubits don’t destroy any information, it’s always possible to reverse any error using established procedures specific to each code.
Taken for a Ride
Zhi Li, a postdoc at the Perimeter Institute for Theoretical Physics in Waterloo, Canada, was well versed in the theory of quantum error correction. But the subject was far from his mind when he struck up a conversation with his colleague Latham Boyle. It was the fall of 2022, and the two physicists were on an evening shuttle from Waterloo to Toronto. Boyle, an expert in aperiodic tilings who lived in Toronto at the time and is now at the University of Edinburgh, was a familiar face on those shuttle rides, which often got stuck in heavy traffic.
“Normally they could be very miserable,” Boyle said. “This was like the greatest one of all time.”
Before that fateful evening, Li and Boyle knew of each other’s work, but their research areas didn’t directly overlap, and they’d never had a one-on-one conversation. But like countless researchers in unrelated fields, Li was curious about aperiodic tilings. “It’s very hard to be not interested,” he said.
Interest turned into fascination when Boyle mentioned a special property of aperiodic tilings: local indistinguishability. In that context, the term means something different. The same set of tiles can form infinitely many tilings that look completely different overall, but it’s impossible to tell any two tilings apart by examining any local area. That’s because every finite patch of any tiling, no matter how large, will show up somewhere in every other tiling.
“If I plop you down in one tiling or the other and give you the rest of your life to explore, you’ll never be able to figure out whether I put you down in your tiling or my tiling,” Boyle said.
To Li, this seemed tantalizingly similar to the definition of local indistinguishability in quantum error correction. He mentioned the connection to Boyle, who was instantly transfixed. The underlying mathematics in the two cases was quite different, but the resemblance was too intriguing to dismiss.
Li and Boyle wondered whether they could draw a more precise connection between the two definitions of local indistinguishability by building a quantum error-correcting code based on a class of aperiodic tilings. They continued talking through the entire two-hour shuttle ride, and by the time they arrived in Toronto they were sure that such a code was possible—it was just a matter of constructing a formal proof.
Quantum Tiles
Li and Boyle decided to start with Penrose tilings, which were simple and familiar. To transform them into a quantum error-correcting code, they’d have to first define what quantum states and errors would look like in this unusual system. That part was easy. An infinite two-dimensional plane covered with Penrose tiles, like a grid of qubits, can be described using the mathematical framework of quantum physics: The quantum states are specific tilings instead of 0s and 1s. An error simply deletes a single patch of the tiling pattern, the way certain errors in qubit arrays wipe out the state of every qubit in a small cluster.
The next step was to identify tiling configurations that wouldn’t be affected by localized errors, like the virtual qubit states in ordinary quantum error-correcting codes. The solution, as in an ordinary code, was to use superpositions. A carefully chosen superposition of Penrose tilings is akin to a bathroom tile arrangement proposed by the world’s most indecisive interior decorator. Even if a piece of that jumbled blueprint is missing, it won’t betray any information about the overall floor plan.
For this approach to work, Li and Boyle first had to distinguish two qualitatively different relationships between distinct Penrose tilings. Given any tiling, you can generate an infinite number of new tilings by shifting it in any direction or rotating it. The set of all tilings generated this way is called an equivalence class.
But not all Penrose tilings fall into the same equivalence class. A tiling in one equivalence class can’t be transformed into a tiling in another class through any combination of rotations and translations—the two infinite patterns are qualitatively different, yet still locally indistinguishable.
With this distinction in place, Li and Boyle could finally construct an error-correcting code. Recall that in an ordinary quantum error-correcting code, a virtual qubit is encoded in superpositions of physical qubits. In their tiling-based code, the analogous states are superpositions of all tilings within a single equivalence class. If the plane is tiled with this kind of superposition, there’s a procedure for filling in gaps without revealing any information about the overall quantum state.
“The Penrose tiling somehow knew about quantum error correction before the invention of the quantum computer,” Boyle said.
Li and Boyle’s intuition on the bus ride had been right. At a deep level, the two definitions of local indistinguishability were themselves indistinguishable.
Finding the Pattern
Though mathematically well defined, Li and Boyle’s new code was hardly practical. The edges of tiles in Penrose tilings don’t fall at regular intervals, so specifying their distribution requires continuous real numbers rather than discrete integers. Quantum computers, on the other hand, typically use discrete systems like grids of qubits. Worse, Penrose tilings are only locally indistinguishable on an infinite plane, which doesn’t translate well to the finite real world.
“It is a very curious connection,” said Barbara Terhal, a quantum computing researcher at the Delft University of Technology. “But it’s also good to bring it down to earth.”
Li and Boyle have taken a step in that direction already, by constructing two other tiling-based codes in which the underlying quantum system is finite in one case and discrete in the other. The discrete code can also be made finite, but other challenges remain. Both finite codes can only correct errors that are clustered together, whereas the most popular quantum error-correcting codes can handle randomly distributed errors. It’s not yet clear whether this is an inherent limitation of tiling-based codes or if it could be circumvented with a cleverer design.
“There’s lots of follow-up work that can be done,” said Felix Flicker, a physicist at the University of Bristol. “All good papers should do that.”
It’s not just the technical details that need to be better understood—the new discovery raises more fundamental questions as well. One obvious next step is to determine which other tilings also work as codes. Just last year, mathematicians discovered a family of aperiodic tilings that each only use a single tile. “It would be fascinating to see how these recent developments might perhaps connect with the quantum error-correction issue,” Penrose wrote in an email.
Another direction involves exploring connections between quantum error-correcting codes and certain models of quantum gravity. In a 2020 paper, Boyle, Flicker and the late Madeline Dickens showed that aperiodic tilings appear in the space-time geometry of those models. But that connection stemmed from a property of the tilings that plays no role in Li and Boyle’s work. It seems quantum gravity, quantum error correction, and aperiodic tilings are different pieces of a puzzle whose contours researchers are just beginning to understand. As with aperiodic tilings themselves, figuring out how those pieces fit together can be remarkably subtle.
“There are deep roots connecting these different things,” Flicker said. “This tantalizing set of connections is begging to be worked out.”
Recommended Comments
There are no comments to display.
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.