Featured Research

from universities, journals, and other organizations

Viterbi Algorithm Goes Quantum

Date:
August 6, 2008
Source:
University of Southern California
Summary:
The Viterbi Algorithm, the elegant 41-year-old logical tool for rapidly eliminating dead end possibilities in reception of digital data, has a new application to go alongside its ubiquitous daily use in cell phone communications, bioinformatics, speech recognition and many other areas of information technology.

Alice would like to transmit a stream of quantum information to Bob. She shares entanglement in the form of ebits before quantum communication begins. Red qubits belong to Alice and blue qubits belong to Bob. She repeatedly performs a series of encoding operations and transmits her qubits as soon as they are encoded. The noisy quantum communication channel corrupts her transmitted qubits. Bob receives her qubits and combines them with his half of the ebits. He performs measurements and Viterbi processing of the measurement results to diagnose the channel errors and performs recovery operations based on the results of the Viterbi algorithm. He then performs a decoding circuit and finally possesses the qubits that Alice first sent.
Credit: USC Viterbi School of Engineering

The Viterbi Algorithm, the elegant 41-year-old logical tool for rapidly eliminating dead end possibilities in data transmission, has a new application to go alongside its ubiquitous daily use in cell phone communications, bioinformatics, speech recognition and many other areas of information technology.

In a recent set of papers two investigators from the University of Southern California school that bears the name of the algorithm's inventor say it can play a key role in quantum communication.

Mark Wilde, a graduate student in the USC Viterbi School of Engineering, collaborated with his faculty advisor Todd Brun on the work. The research is also his thesis, for which he will receive a PhD from the School's Ming Hsieh Department of Electrical Engineering in August.

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 "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 [entangled] 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 in between them."

Use of 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 entanged photons for messages. But noise is created in the transmission of quantum data, an issue the USC work addresses using the time-hallowed 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, a ballet in which Alice and Bob can exploit ancilla or helper qubits, gauge or noisy qubits, and ebits to transmit both quantum and classical information.

But the bottom line question coming out remains, how does Bob know that the dancers were following the music, 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 progressions, called "Markov processes."

In Wilde and Brun's analysis, 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 it is garbled, he has nothing.

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

The research was funded by NSF.

References:

M.M. Wilde and T.A. Brun, "Unified quantum convolutional coding," in IEEE International Symposium on Information Theory (arXiv:0801.0821), July 2008.

M.M. Wilde, Quantum Coding with Entanglement, Ph.D. Thesis, University of Southern California, arXiv:0806.4214, August 2008.

M.M. Wilde and T.A. Brun, Quantum convolutional coding with shared entanglement: general structure, submitted to IEEE Transactions on Information Theory (arxiv:0807.3803), 2007.

M.M. Wilde and T.A. Brun, Entanglement-Assisted Quantum Convolutional Coding, submitted to IEEE Transactions on Information Theory (arXiv:0712.2223), 2007.

M.M. Wilde, H. Krovi and T.A. Brun, Convolutional Entanglement Distillation, submitted to IEEE Transactions on Information Theory (arxiv:0708.3699), 2007.


Story Source:

The above story is based on materials provided by University of Southern California. Note: Materials may be edited for content and length.


Cite This Page:

University of Southern California. "Viterbi Algorithm Goes Quantum." ScienceDaily. ScienceDaily, 6 August 2008. <www.sciencedaily.com/releases/2008/07/080731173129.htm>.
University of Southern California. (2008, August 6). Viterbi Algorithm Goes Quantum. ScienceDaily. Retrieved August 29, 2014 from www.sciencedaily.com/releases/2008/07/080731173129.htm
University of Southern California. "Viterbi Algorithm Goes Quantum." ScienceDaily. www.sciencedaily.com/releases/2008/07/080731173129.htm (accessed August 29, 2014).

Share This




More Computers & Math News

Friday, August 29, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

JPMorgan Chase Confirms Possible Cyber Attack

JPMorgan Chase Confirms Possible Cyber Attack

Reuters - US Online Video (Aug. 28, 2014) Attackers stole checking and savings account information and lots of other data from JPMorgan Chase, according to the New York Times. Other banks are believed to be victims as well. Fred Katayama reports. Video provided by Reuters
Powered by NewsLook.com
Spend 2 Minutes Watching This Smartwatch Roundup

Spend 2 Minutes Watching This Smartwatch Roundup

Newsy (Aug. 28, 2014) LG announces a round-faced smartwatch, Samsung adds 3G connectivity to its latest wearable, and Apple will reportedly announce the iWatch on Sept. 9. Video provided by Newsy
Powered by NewsLook.com
Why Apple Might Add Mobile Payment Options To iPhone 6

Why Apple Might Add Mobile Payment Options To iPhone 6

Newsy (Aug. 28, 2014) A report by Wired suggests Apple's next iPhone will feature a mobile payment system and near-field communication. Video provided by Newsy
Powered by NewsLook.com
Hackerspace Provides Hackers Creative Haven

Hackerspace Provides Hackers Creative Haven

AP (Aug. 27, 2014) HeatSync Labs, a so-called hackerspace in Mesa, Arizona provides members and the public alike a space to allow their creative juices to flow and make their tech dreams into a reality. (Aug 27) Video provided by AP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins