Logo: University of Southern California

Entanglement unties a tough quantum information problem

Linked daughter qubits create efficient message mistake detection syndromes
Eric Mankin
September 29, 2006 —
Todd Brun: "operating close to the theoretical limit..."
Error correction coding is a fundamental process that underlies all of information science, but the task of adapting classical error correction codes to quantum computing has long bumped up against an apparent fundamental limitation.

A new approach by three theorists working at the USC Viterbi School of Engineering dramatically changes the rules of the game.  They report in Science that adding entangled photons as part of the message stream  opens the door to using the entire error coding playbook.

"This method allows the use of highly efficient turbo codes, operating close to the theoretical limits of efficiency, something never before possible," says Todd Brun, an associate professor in the Viterbi School's department of electrical engineering, who is lead author on the study.

Error correction coding dates back to the classic work by Claude Shannon, founder of the field of information science, who proved messages could survive noise perfectly intact up to a certain limit — a limit called "channel capacity" — if they were made redundant.

The simplest error correction code is simply to repeat the same message over and over. People talking frequently use informal error-correction codes, on phones, for example: "That's 'C' as in Charlie, 'A' as in Apple..."

More formally, following Shannon's insight, mathematicians over the past five decades have developed much more efficient methods. These sophisticated error correction codes work by spreading one or more bits of information redundantly among a larger number of bits. If errors occur, they can be detected (and reversed) by measuring the encoded bits. These measurements — called error syndromes — are the key to the correction process.

Irving Reed, a USC emeritus professor and National Academy of Engineering member who was co-creator of one of the most widely used of these codes, the Reed-Solomon codes, discusses their importance to computer science and electronics in general in his 2005 memoir, Alaska to Algorithms.

"The human mind is capable by the use of context and language redundancy to intuitively perform error-correction," he writes. "But electronic equipment is extremely fussy: it demands a perfection that isn't found in the noisy real world. Error coding permits these fastidious machines to function as part of real world systems, in real time."

Brun says quantum computing systems, which process quantum data ("qubits") carried on single photons, are even more fastidious than electronic ones and error codes are even more necessary. But the physical laws govering quantum messages create a problem for coders.

The solution devised by the co-authors — Brun, assistant professor Igor Devetak, and graduate student Min-Hsiu Hsieh — is to include some entangled qubits in the mix.

Entangled qubits are a remarkable species that come in linked pairs. They are created when, for example, high-energy photons go through certain materials, which convert them into two lower energy photons.

These twin daughters remain linked even when they are separated, so something that happens to one is echoed in the other, instantaneously, no matter how far apart they are, an effect that, although predicted by quantum mathematics, remains so strange and counter-intuitive that it is sometimes called "spooky physics."

Entanglement has attracted intense interest as a way of encryption, since any attempt to intercept a message carried on one entangled photons immediately shows up on the remote sister as a warning.

The USC method doesn't use a continuous stream of entangled photons. Rather, it mixes normal and entangled ones. One property that entanglement provides is that two measurements, which would be incompatible on a single qubit, can sometimes be done by measuring both halves of an entangled pair — and it is this property that Brun and his collaborators utilize.

The USC researchers, and particularly Hsieh, are working to calculate the optimal mix of entangled versus unentangled photons for error coding performance. But even at its present stage, "we think this is a significant result and a promising direction," concludes Brun.

Several grants from the National Science Foundation supported the research