For more than half a century, aperiodic dense laying has fascinated mathematicians, amateurs, and researchers in many other fields. Now, two physicists have discovered a connection between aperiodic paving and a seemingly unrelated branch of computer science: the study of how quantum computers in the future will encode information to protect it from error. They showed how to transform Penrose paving into a novel quantum error-correcting code, and also constructed similar error-correcting codes based on two other types of aperiodic paving.
Compile | Wang Qingfa
The two researchers proved that Penrose Tilings, the famous pattern that never repeats, are mathematically equivalent to a quantum error correction method.
If you want to tile your bathroom floor, square tiles are the easiest option – they fit seamlessly in a grid pattern and can be extended infinitely. This square grid has many properties common to the dense spread: moving the entire grid by a fixed amount results in a pattern that is indistinguishable from the original. But for many mathematicians, such a "periodic" dense paving is boring. If you've seen a small area, you've seen it all.
In the 60s of the 20th century, mathematicians began to study "non-periodic" dense sets with richer behaviors. Perhaps the most famous is a pair of diamond-shaped pavements discovered in the 70s of the 20th century by the multi-talented physicist and future Nobel laureate Roger Penrose. These two copies of the pavement can form an infinite number of different patterns that can last forever, known as the Penrose pavement. However, no matter how you arrange the paving, you won't get a pattern that repeats periodically.
"These are graphics that shouldn't be there," says Nicholas Bruckman, a physicist at the University of Bristol.
For more than half a century, aperiodic dense laying has fascinated mathematicians, amateurs, and researchers in many other fields. Now, two physicists have discovered a connection between aperiodic paving and a seemingly unrelated branch of computer science: the study of how quantum computers in the future will encode information to protect it from error. In a paper [1] published in November 2023 on the preprint server arxiv.org, researchers show how to transform Penrose Dense Laying into a novel quantum error-correcting code. They also built similar error correction codes based on two other types of aperiodic dense laying.
At the heart of the correspondence between the two is a simple observation: in aperiodic dense laying and quantum error-correcting codes, knowing a small part of a large system does not help to understand the system as a whole. The Power of Analogical Thinking
"This seems to be the beauty of what seems obvious in hindsight," said Toby Cubitt, a quantum information researcher at University College London. "You think, 'Why didn't I think of that?'"
"Strange" knowledge
Ordinary computers use bits with two different states to represent information, labeled 0 and 1. Qubits or qubits also have two states, but they can also be guided into so-called superposition states, where 0 and 1 states coexist. By taking advantage of more complex superposition states involving multiple qubits, quantum computers can perform certain calculations faster than any traditional machine.
However, quantum superposition states are sensitive monsters. Measure the qubits in the superposition state, which will collapse to 0 or 1, erasing any ongoing computations. Worse still, errors due to the weak interaction between the qubit and its environment can have a devastating effect on the measurement. Anything that touches a qubit in the wrong way, whether it's a curious researcher or an outlier photon, can disrupt computing.
Tiles at Penrose's feet
This extreme vulnerability may make quantum computing sound hopeless. But in 1995, applied mathematician Peter Shore discovered an ingenious way to store quantum information. His coding has two key attributes. First, it can tolerate errors that affect only a single qubit. Second, it comes with a bug-correcting program that prevents them from piling up and derailing calculations. Shore's discovery is the first example of a quantum error-correcting code, and its two key properties are the defining features of all such codes.
The first feature stems from a simple principle: secret information is less vulnerable when it is fragmented. Spy networks employ similar tactics. Each spy has very little knowledge of the entire network, so even if any individual is arrested, the organization remains safe. Quantum error-correcting codes take this logic to the extreme. In a quantum spy network, no individual spy will know anything, but together they will know a lot.
Each quantum error-correcting code is a specific scheme that distributes quantum information across many qubits, forming a collective superposition state. This procedure effectively converts a set of physical qubits into a single virtual qubit. Repeat this process several times, using a large number of qubits, and you get many virtual qubits that you can use to perform calculations.
The physical qubits that make up each virtual qubit are like those unwitting quantum spies. Measure any of them and you won't know the state of the virtual qubit it belongs to – a property known as local indistinguishability. Since each physical qubit does not encode any information, an error in a single qubit does not break the calculation. Important information is somehow everywhere, but not in any particular place.
"You can't boil it down to any one 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 eventually fall as errors accumulate. This is where the second feature of quantum error-correcting codes, actual error correction, comes into play. This is closely related to local indistinguishability: since an error in a single qubit does not destroy any information, any error can always be reversed using a given program specific to each error-correcting code.
Take a ride
Zhi Li, a postdoctoral fellow at the Perimeter Institute of Theoretical Physics at the University of Waterloo in Canada, is well versed in quantum error correction theory. But when he spoke with his colleague Rail, Boyle, the subject was far from his thoughts. It was the fall of 2022, and two physicists were talking on a night shuttle bus from Waterloo to Toronto. Boyle, an expert in non-cyclical density, lived in Toronto at the time and is now at the University of Edinburgh. He is a familiar face on these shuttle bus trips, which often get stuck in traffic.
"Normally, congestion can be very difficult," Boyle said, "and this one was the best of all time." ”
Before that fateful night, Li Zhi and Boyle knew each other's work, but their fields of study did not directly overlap, and they never had a one-on-one conversation. But like countless researchers in other fields, Li Zhi is curious about aperiodic dense paving. "It's hard not to be interested in it," he said.
When Boyle mentions a special property of aperiodic paving—local indistinguishability—interest becomes infatuation. In this context, the term means something different. The same set of pavements can form an infinite number of pavements that look completely different, but it is impossible to distinguish between any two pavements by examining any local area. This is because a finite small area of any pavement, no matter how large, will appear somewhere among the other pavements.
"If I let you stop in one bunk or another and spend your whole life exploring, you'll never know which bunk I'll let you stop," Boyle said.
For Zhi Li, this looks very similar to the definition of local indistinguishability in quantum error correction. He mentioned the connection, and Boyle was immediately intrigued. The mathematical basis between the two is very different, but the similarities are fascinating and should not be overlooked.
Li and Boyle wondered if they could establish a more precise connection between these two definitions of local indistinguishability by constructing a quantum error-correcting code based on a class of aperiodic dense paving. They continued their discussions throughout the two-hour shuttle bus journey, and when they got to Toronto, they determined that such a code was possible – just by building a formal proof. (Translator's note: This is the terrible thing about the big model after learning the relationship of various categories, after all, the category is the relationship of the relationship, the relationship of the relationship, the relationship of the relationship. ）
Quantum Dense Paving
Li Zhi and Boyle decided to start with Penrose Secret Shop, which was simple and familiar. To translate them into quantum error-correcting codes, they first need to define what quantum states and errors will look like in this unusual system. This part is easy. An infinite two-dimensional plane covered by Penrose paving, like a qubit grid, can be described using the mathematical framework of quantum physics: quantum states are specific pavings rather than zeros and 1s. A bug simply removes a region of the dense paved pattern, just as some error in a qubit array erases the state of each qubit in a small cluster.
The next step is to identify the densely paved configuration that is not affected by local errors, just like the virtual qubit state in a normal quantum error-correcting code. The workaround, as in normal error correction codes, is to use superposition. The carefully chosen Penrose pavé superposition resembles the arrangement of bathroom tiles proposed by the world's most indecisive interior designers. Even if a part of that chaotic blueprint is missing, it won't reveal any information about the entire layout.
In order for this approach to work, Li Zhi and Boyle first had to distinguish between two qualitatively different relationships between different Penrose secret shops. Given any one pavement, you can generate an infinite number of new pavements by translating or rotating it in any direction. The set of all the paved piles that are generated in this way is called an equivalence class.
But not all Penrose shops are in the same equivalence class. The pavement in one equivalent class cannot be transformed into the pavement in another class by any combination of rotation and translation – these two infinite patterns are qualitatively distinct, but still locally indistinguishable.
By establishing this distinction, Li Zhi and Boyle can finally construct an error correction code. To recap, in ordinary quantum error-correcting codes, a virtual qubit is encoded in a superposition of physical qubits. In their pave-based error correction code, a similar state is a superposition of all pavements within a single equivalence class. If the plane is laid in this superposition, the void can be filled without exposing the overall quantum state information.
"Penrose somehow learned about quantum error correction before the invention of the quantum computer," Boyle said.
Li Zhi and Boyle's instincts during the bus journey were correct. At a deep level, these two definitions of local indistinguishability are inherently indistinguishable.
Find the pattern
Despite being mathematically defined, Li Zhi and Boyle's new error correction code is hardly feasible. The edges of the pavement in Penrose pavé do not occur 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, such as qubit grids. To make matters worse, Penrose paved is locally indistinguishable on an infinite plane, which does not apply in a finite real world.
Boyle and Zhi Li jointly constructed a quantum error-correcting code based on aperiodic dense paving
"It's a very wonderful connection," says Barbara Tehar, a quantum computing researcher at Delft University of Technology. "But it's good to be practical. ”
Zhi Li and Boyle have already taken a step forward in this direction by constructing two other dense-paved error-correcting codes, one of which is finite in one case and discrete in the other. Discrete error-correcting codes can also become limited, but other challenges remain. These two finite error-correcting codes can only correct errors that are clustered together, while the most popular quantum error-correcting codes can deal with randomly distributed errors. It's unclear if this is an inherent limitation of dense-based code, or if it can be circumvented by a more clever design.
"There's a lot of follow-up work that can be done," said Felix Flick, a physicist at the University of Bristol. "That's what all good papers should be. ”
It's not just the technical details that need to be understood more – new discoveries also raise more fundamental questions. An obvious next step is to determine which other dense lays can also be used as error correction codes. Just last year, mathematicians discovered a family of aperiodic paving, each using only one type of paving. "It will be very interesting to see how these latest developments might relate to quantum error correction problems," Penrose wrote in an email.
Another direction is to explore the connection between quantum error-correcting codes and certain quantum gravitational models. In a 2020 paper, Boyle, Flick, and the late Madeleine Dickens showed that aperiodic paving occurs in the spatiotemporal geometry of these models. But the connection stems from an attribute of Mipu that doesn't work in the work of Li Zhi and Boyle. It seems that quantum gravity, quantum error correction, and aperiodic paving are different parts of a puzzle that researchers are just beginning to understand their contours. As with the aperiodic dentification itself, figuring out how these pieces fit together can be very subtle.
"There's a deep foundation between these different things," Flick said. "This enticing series of connections is waiting to be figured out. ”
bibliography
[1] https://arxiv.org/abs/2311.13040
This article is reprinted with permission from the WeChat public account "Qingxi", and the original text is translated from
https://www.quantamagazine.org/never-repeating-tiles-can-safeguard-quantum-information-20240223/
Special Reminder
1. Enter the "Boutique Column" at the bottom menu of the "Huipu" WeChat official account to view a series of popular science articles on different themes.
2. "Back to Park" provides the function of searching for articles by month. Follow the official account and reply to the four-digit year + month, such as "1903", to get the article index in March 2019, and so on.