Slashdot Mirror
The Viterbi Algorithm and Quantum Communications
eldavojohn writes "There have been a lot of tests in using quantum mechanics to communicate across large distances. But a student & a professor at USC have proven that the Viterbi algorithm can be applied to quantum communication. In the traditional Alice sends Bob a message scenario, '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.'"
I wish Alice and Bob would just go ahead and do it already. Everybody knows they have the hots for one another.
And for that matter what is the chance Alice will just say it once?
Go ask Alice. I think she'll know.
For those wondering what use this has.
Say you had.... a buttload of code, and wanted to find the context free grammar for the language. You could use a Viterbi algorithm to pull out a statistically likely parse tree (the Viterbi Parse). The thing you're pulling from is often called a Markov process which is a model for the evolution of a state changing, memoryless system. So, over time, you can retrieve a grammar from a running process.
How this applies to QM is left as an exercise to the reader (5 stars, unless you're Don K His-self, in which case it's 2).
ianaqp
And for those of you wondering...
Markov was Chekov's evil twin on Star Trek.
Intron: the portion of DNA which expresses nothing useful.
So you're suggesting Bob and Alice get entangled? That's spooky... too bad we wouldn't be able to watch.
I'm not smart enough to figure out the details of what they've done, but it sounds like really promising work. "Communication" is perhaps too narrow a term for the applications, though.
A big part of the problem with building quantum computers right now is keeping the qubits stable. The real world is constantly trying to "observe" (or interfere with) the qubits. When that happens, your quantum states break down and you lose your computation. This is a bit reason why we've only been able to build small (5-qubit) machines: it's very hard to keep things isolated and stable.
If you have a practical error correction code scheme (using a Viterbi decoder, like in this article), then things might be a bit easier. Maybe instead of 5 very stable qubits, you could have 20 sort-of-stable qubits, where you expect that half of them will be lost to noise. It would still be a net win.
TFA is a bit short on details, as expected for a general-audience press release. In particular, they throw the word "Viterbi" out there without ever explaining what the heck it means; probably an artifact of USC containing the *Viterbi* School of Engineering. The juicy technical bits can be found in his thesis here:
Title: Quantum Coding with Entanglement ... and for a basic overview of the underlying concepts, of course the Wikipedia page on the Viterbi algorithm is helpful.
Authors: Mark M. Wilde
Thesis PDF