Viterbi Algorithm Takes a Quantum Leap

08/06/08
Graduate student’s research on data transmission will serve as his Ph.D. thesis.
By Eric Mankin
Faculty adviser Todd Brun, left, and graduate student Mark Wilde

Photo/Eric Mankin
The Viterbi algorithm, the 41-year-old tool for rapidly eliminating dead-end possibilities in the reception of digital data, has a new application to go alongside its daily use in cell phone communications, bioinformatics, speech recognition and other areas of information technology.

In a recent set of papers, two investigators from the USC school that bears the name of the algorithm’s inventor said it can play a key role in quantum communication.

Mark Wilde, a graduate student at the USC Viterbi School of Engineering, collaborated with his faculty adviser Todd Brun on the work. The research also will serve as his thesis, for which he will receive a Ph.D. from the school’s Ming Hsieh Department of Electrical Engineering this month.

Brun, an associate professor in the Hsieh Department, is also deputy director of the USC Center for Quantum Information Science & Technology.

The quantum communication applications Wilde and Brun explored are for an environment in which a sender named Alice (the traditional sender name) is trying to send a quantum message to a receiver named (again by tradition) Bob, using a stream of pairs of “entangled” photons.

“Such photons,” in the words of the recent New Scientist story, “obey the strange principles of quantum physics, whereby disturbing the state of one will instantly disturb the other, no matter how much distance there is between them.”

Such a system has been proposed for a variety of uses, including space-based communication, and progress is being made on the physical devices that might create entangled photons for messages. But noise is created in the transmission of quantum data, an issue the USC work addresses using the time-tested Viterbi algorithm.

In the system considered by Wilde and Brun, Alice encodes each quantum bit of the message with the help of an ebit, an entangled qubit. She sends her part of the encoded quantum message over a noisy quantum communication channel, a process that can introduce errors.

From his side, Bob receives what Alice sent and combines her transmitted qubits with his half of the ebits. He measures all of the qubits, processes the results of the measurements, performs recovery operations and finally decodes them, receiving the message qubits Alice sent. At the conclusion of the process, Bob will have the transmitted quantum information error-free.

The above description is a condensed and simplified paraphrase of what is in fact a much more complex process.

But the bottom line question remains: How does Bob know that the message he now has was transmitted correctly?

The fact that the noisy quantum communication channel can be modeled as a sequential process of steps, each step of which changes the state of the system, offers an opening. The Viterbi algorithm is, precisely, a way of analyzing the products of such processes, technically called Markov processes.

In the analysis by Wilde and Brun, Bob watches the step coming out of his measurement process, testing them against statistical probabilities using standard Viterbi tools.

Cell phones use similar programming to correct for errors in the transmission of digital voice data.

The result: Bob can reliably spot errors and knows which message qubits are bogus before he opens the message crucial because opening it destroys it; and if the message is garbled, he has nothing.

Wilde plans to work on future extensions of these ideas with researchers at NEC Laboratories in Princeton, N.J., the Center for Quantum Technologies in Singapore and the Quantum Institute at Los Alamos National Laboratory.