Graphs May Prove Key in Search for Holy Grail of Quantum Error Correction

In February 2019, JQI Fellow Alicia Kollár, who is also an assistant professor of physics at UMD, bumped into Adrian Chapman, then a postdoctoral fellow at the University of Sydney, at a quantum information conference. Although the two came from very different scientific backgrounds, they quickly discovered that their research had a surprising commonality. They both shared an interest in graph theory, a field of math that deals with points and the connections between them.

Chapman found graphs through his work in quantum error correction—a field that deals with protecting fragile quantum information from errors in an effort to build ever-larger quantum computers.  He was looking for new ways to approach a long-standing search for the Holy Grail of quantum error correction: a way of encoding quantum information that is resistant to errors by construction and doesn’t require active correction. Kollár had been pursuing new work in graph theory to describe her photon-on-a-chip experiments, but some of her results turned out to be the missing piece in Chapman’s puzzle.

Their ensuing collaboration resulted in a new tool that aids in the search for new quantum error correction schemes—including the Holy Grail of self-correcting quantum error correction. They published their findings recently in the journal Physical Review X Quantum(link is external).

Quantum computers are made up of quantum hardware, fundamentally different from our everyday, “classical” computers. Large-scale quantum computers, if built, would be able to factor numbers that stump even current supercomputers. Perhaps most importantly, they would allow us to simulate the world in its full quantum complexity.

Powerful as they are, quantum computers are very difficult to build, in part because quantum information is very fragile and prone to errors. “The noise is very strong at the quantum scale,” says Chapman.  “And this makes quantum error correction very difficult.”

To protect fragile quantum information—and make stable quantum computers—there needs to be a way to correct errors. Classically, the brute force way to protect against errors is to repeat a bit of information—instead of 0, store or send 000. Then, if by some chance an error flips one of the bits (say to 010), the majority vote still says 0. With quantum information, it’s a bit trickier. For one, reading out quantum information destroys it. If you look at the quantum bits—called qubits—to check whether an error occurred, you destroy the information and can’t use it in a future computation. So, scientists have had to come up with clever ways of encoding quantum information and checking for errors without disturbing the underlying information.

“This is the key,” Kollár says. "If you ever measure something directly about your qubit, it's gone. You need some redundancy that allows you to tell if something has happened without knowing the underlying information.”

The Holy Grail would be a quantum error correcting code—a prescription for how the information is encoded and how to check for errors—in which each new error would require more and more energy. So, if you make the quantum computer cold enough, errors might pop up occasionally, but they wouldn't proliferate. This is called self-healing, kind of like self-care for quantum computers. There are quantum error correcting codes that are known to be self-healing, but they only work in four dimensions—one more than exists in this world.

The search for a self-healing quantum error correcting code that works in our earthly dimensions is an arduous one. To check if an error correcting code has this self-healing property, it’s not enough to know what the code is. It’s also necessary to know the energy cost of all the different kinds of errors. For many quantum error correcting codes, this is nearly impossible to calculate without already having a quantum computer.

All of the quantum error correcting codes discovered so far can be crudely sorted into two categories. The simpler ones are called stabilizer codes. They encode one qubit of quantum information into several qubits (like writing 0 as 000) and define operations to check for all possible errors. The energy cost of errors and almost all relevant information is easy to calculate. Sadly, there are theorems that indicate none of these simpler codes are likely to be self-healing in under four dimensions.

The second category of codes—the more complicated subsystem codes—also define encodings and error-check operations, but some “errors” are allowed to go unchecked. It’s kind of like taking 0000 and 0001 as both signifying 0, and not caring about the last bit. This often makes the check operations quicker to do in practice, but some of the error checks can no longer be done in any order—measuring one check will change the result of another one. Unlike stabilizer codes, calculating the energies of all the possible errors for subsystem codes is a costly computational task.

To forge new paths toward finding a self-healing quantum error correcting code, it’s important to find ways to calculate things about these more complicated subsystem codes. And, as it turns out, graph theory can help.

A graph, mathematically speaking, is a collection of points, called nodes, with some pairs of points connected by a line, called an edge. They can be drawn as a big spiderweb-like network.

In the new paper, the researchers showed that some subsystem codes can be represented as a certain kind of graph. Furthermore, these particular graphs are identical to graphs that represent an entirely different physical setting—a bunch of electrons (or any fermions for that matter) that don’t interact with each other. In some configurations, figuring out all the energies of non-interacting electrons is straightforward.

Leveraging this new graph-based bridge between non-interacting electrons and quantum error correcting codes, the researchers were able to calculate the energies of the free electrons in the one setting and map the results back to the original error correcting code. They could exactly calculate everything they might need to know to determine if the code is self-correcting.

“With an exactly solvable code like this,” Kollár says, “you can in principle compute everything about it. So, it gives a unique opportunity to understand what about the code controls what final properties.”

Not all subsystem codes can be drawn as the right kind of graph. But the researchers developed a systematic way to look for codes with graph-friendly properties.

“I had a seemingly unrelated pure mathematics project studying graph spectra,” says Kollár, “and we realized that the numerical scripts that I had for that project could easily be modified to compute the energy cost of errors for the kinds of codes that Adrian and his collaborators had been looking at.”

They found at least one subsystem code whose energies could be mapped out with this graph-based technique. They say this particular code is unlikely to be used in practice, and it isn’t self-correcting. Still, it represents one of the first two-dimensional subsystem codes whose entire energy landscape can be mapped out. And it adds an entirely new tool in the search for the Holy Grail of error correction.

“I think we know a lot more about looking for this Holy Grail than we did before,” says Kollár. “But it's still a Holy Grail. It is not going to be an easy thing to find—if it exists.”

Story by Dina Genkina

In addition to Kollár and Chapman, Steven Flammia, a physicist at the AWS Center for Quantum Computing and the Institute for Quantum Information and Matter at the California Institute of Technology, was an author on the publication.