Never mind the noise: Quantum entanglement allows channel information rate to exceed Shannon zero-error capacity

Jan 23, 2013 by Stuart Mason Dambrot feature
(i) Channel with five inputs (numbers) and five outputs (letters), where an input symbol x is connected to an output symbol a if P(a|x) > 0. Notice that none of the five pairs (0, 2), (1,4), (2,1). (3,3), (4,0) can be confused with one another, as either the first or the second two symbols are nonconfusable. (ii) Confusability graph of the channel, the five cycle C5. Copyright © PNAS, doi:10.1073/pnas.1203857110

(—As developed by Claude Shannon, information theory defines channel capacity as the maximum rate at which information can be sent through the channel. This capacity can be mathematically described using a graph associated with the channel. Specifically, a graph's Shannon zero-error capacity is the maximum rate at which messages can be sent through a noisy channel with zero probability of error. However, the Shannon capacity does not reflect the fact that on atomic scales, nature behaves according to quantum mechanics. Recently, scientists studying asymptotic behavior in entangled sender-receiver quantum systems at Centrum Wiskunde & Informatica, The Netherlands have identified families of graphs for which entanglement allows the Shannon capacity to be exceeded.

Dr. Jop Briët discussed the challenges he and his colleagues, Dr. Dion Gijswijt and Prof. Harry Buhrman, encountered in determining if for a family of graphs, the entanglement-assisted capacity exceeds the Shannon capacity. (A graph has as many points as there are inputs to the channel. Such a graph is usually referred to as the channel's confusability graph, because two points are connected by a line if they can be confused with each other when one of them is sent through the channel.) "The two parameters that we wanted to separate – the Shannon capacity and the entanglement-assisted capacity – are similar in the sense that they indicate how effectively one can communicate over a noisy communications channel," Briët tells "In the entanglement-assisted case the sender and receiver have an extra resource – quantum entanglement – so the latter parameter is always at least as large as the former."

Briët points out that in the two extreme cases these parameters are actually equal: If the communications channel is perfect (i.e., noiseless), entanglement gives no advantage at all. On the other hand, entanglement cannot improve this situation if only a single message can be sent with zero error.

In entanglement-assisted communication, Briët explains, there are two parties (sender and receiver) and two resources (a noisy communication channel and a pair of entangled ). The sender has one of the systems and the receiver the other, and the two parties can perform measurements (that is, experiments) on their respective quantum systems. While the outcomes of such experiments can usually not be predicted in advance, making measurements on entangled systems can still lead to useful results because outcomes of an experiment done by the sender and an experiment done by the receiver, though random, can be strongly correlated. "The entanglement-assisted communication protocol we consider," Briët adds, "dates back at least as far as the work of Charles Bennett and others1 in 2002."

Suppose the sender can do ten different experiments, labeled with the numbers 1 to 10, and suppose that the possible inputs to the channel are the letters of the alphabet A to Z, Briët illustrates. The sender picks an experiment (for example, experiment number three), and depending on the outcome sends one of the letters – in this example, the letter P – through the channel to the receiver. Because the channel is noisy, the receiver gets a symbol that could be a P, B, D, or R. Based on this list of four letters the receiver chooses an experiment to perform on his quantum system and associates a number between 1 and 10 with each of the possible outcomes. "The punchline," Briët says, "is that it's sometimes possible to set things up so that the only possible outcome of the receiver's experiment is the number of the experiment done by the sender – in this case the number three."

Therefore, Briët points out, in the above example the sender could send any one of ten different messages with zero probability of error. Moreover, he adds, their main result shows that this number can be larger than the average number of messages that can be sent with zero error if no entanglement was used, thereby exceeding the zero-error Shannon capacity.

"To show that entanglement can sometimes allow a sender and receiver to communicate more efficiently," Briët continues, "one needs to create a channel for which one can prove that the entanglement-assisted capacity is large, but the Shannon capacity is small. However, proving good bounds on these parameters is notoriously difficult. It took over two decades and a brilliant mathematician to compute the Shannon capacity of the pentagon, which is the graph associated with a particular that has only five inputs and outputs! Only for a very few special cases can we currently say something non-trivial about these parameters."

The challenge then, says Briët, was to find a "sweet spot" among these special cases where the researchers can prove good bounds on both the entanglement-assisted and Shannon capacities. They looked at a particular class of graphs often used in quantum computing and – so-called orthogonality graphs – that show that entanglement or some other quantum resource can make some classical information processing task easier. (In an orthogonality graph, points in a two, three or higher-dimensional space are labeled by arrows; a pair of such points are labeled by a line if the associated arrows are orthogonal – that is, in perpendicular directions.) "In this sense," Briët notes, "these graphs were natural candidates for the type of result we were after. Using available techniques it is a fairly straightforward calculation to show that the orthogonality graphs have very large entanglement-assisted capacity – but it was unknown, and it still is, if the Shannon capacity is any smaller."

Their key insight, Briët says, was that they could slightly morph the orthogonality graphs to end up a class of graphs that lie in the kind of the previously-mentioned sweet spot. "Essentially, what we did is take one of these graphs and throw away three-quarters of it, not just any, but such that we are left with a quarter that has enough structure for us to be able to bound the two capacities. In addition, to bound the two capacities we had to use two quite different techniques." To show that their graphs had very high entanglement-assisted capacity, they borrowed ideas from geometry, while to show the graphs' low Shannon capacity they tapped algebra.

"To argue that entanglement should be used to speed up communication in practice, our results would need to be strengthened," Briët acknowledges. "In our setting we made stronger assumptions on how tolerable a little noise is than is reasonable in real-world situations. A next step would be to weaken these assumptions, for example to one where the receiver is happy if he can narrow down what the sender was trying to transmit to a small list of possibilities, as opposed to receiving the messages without ambiguity."

"There are close links between entanglement-assisted communication and physical experiments that are meant to test if is actually a real phenomenon," Briët notes. "It's predicted to exist by , but since that's only a mathematical model of how nature could work, this doesn't mean that it has to exist. Convincing experiments were already performed in the early eighties, but because experimental set-ups are bound to have small defects, skeptics argue that no hard conclusion can be drawn from them. Physicists are still trying to come up with ever-better and better experiments that are robust against such defects," Briët concludes, "so that even if they are taken into account one cannot argue that the results could have been produced if entanglement wasn't present in the experimental set-up."

Explore further: Longer distance quantum teleportation achieved

More information: Violating the Shannon capacity of metric graphs with entanglement, PNAS published online before print December 24, 2012, doi:10.1073/pnas.1203857110


1Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem, IEEE Transactions on Information Theory Volume: 48, Issue: 10 Page(s): 2637-2655 Oct 2002

Related Stories

Entanglement can help in classical communication

Mar 30, 2011

( -- When most of us think of entanglement, our minds jump immediately to quantum communication. "Entanglement has become very well known and useful in quantum communication," Robert Prevedel tells Preved ...

Entanglement recycling makes teleportation more practical

Jan 17, 2013

(—Working in the exotic-sounding field of quantum teleportation, physicists are trying to make it easier to transmit quantum information in the form of qubits from one location to another without having the qubits ...

Explained: The Shannon limit

Jan 19, 2010

It's the early 1980s, and you’re an equipment manufacturer for the fledgling personal-computer market. For years, modems that send data over the telephone lines have been stuck at a maximum rate of 9.6 kilobits ...

New record in quantum communications

Aug 30, 2012

(—Researchers from The Australian National University have taken a quantum leap towards developing the next-generation super-fast networks needed to drive future computing.

Recommended for you

Quantum mechanics to charge your laptop?

Sep 18, 2014

Top scientists from UC Berkeley and MIT found the expertise they lacked at FIU. They invited Sakhrat Khizroev, a professor with appointments in both medicine and engineering, to help them conduct research ...

Physicists design zero-friction quantum engine

Sep 16, 2014

( —In real physical processes, some energy is always lost any time work is produced. The lost energy almost always occurs due to friction, especially in processes that involve mechanical motion. ...

User comments : 9

Adjust slider to filter visible comments by rank

Display comments: newest first

3.3 / 5 (7) Jan 23, 2013
Not surprising, seeing how QM maximizes up front information (no hidden parameters, uses the minimum parameter set).

Akin to how quantum states can be squeezed to achieve better performance, going below uncertainty limits by using predetermined parameters, the channel is squeezed by using predetermined protocol. Neat!
Jan 23, 2013
This comment has been removed by a moderator.
3 / 5 (4) Jan 23, 2013
omerbashich, you don't win any points for sloppy use of English or physics. If you did a Ph.D. dissertation and used "abridge" where you meant "bridge" (as you did, several times, in your discussion at your blog site), your committee would have required you to correct that error before approving the document.
(If you did use "bridge" correctly there, and/or corrected it per requirement, why are you not using it correctly now?)

regarding physics: you say, at your site,
"- Fast-moving clocks might be ticking slower due to drag/friction of moving parts (be it spring mechanism or atomic orbits) which compose clocks against... something;"

Care to speculate as to what "something" might be? And maybe even *support* your speculation?
Also: in the experiment where a stationary atomic clock was compared to one that was flown quickly, the fast-moving clock and the stationary clock were necessarily built the same way, so any drag effects would be equal--and would not make a difference.
2 / 5 (8) Jan 24, 2013
Entanglement is instant "communication".

It conflicts with Einsteins relativity theory.

What if the speed of light varies through time and space?

That would create some interesting theory. At least I think so.

Antimatter becomes the mind and consciousness of all living entities.

You are your own universe.

Reality is where the minds (antimatter) meets the physical universe.

Interested? Then read my philosophical multiverse theory.

Google crestroyer theory, and find it instantly.
3 / 5 (8) Jan 24, 2013
Entanglement is instant "communication".

It conflicts with Einsteins relativity theory.

It doesn't conflict with Einstein because it is not information transmission (which is subtly different from the notion of communication).
Information requires a priori knowledge of what it is you want to send (the message) AND a posteriori correlation of what you receive to said encoded message.

Communication requires ONLY the a posteriori correlation but does not require that you know what you send).

So faster than light information transmission is forbidden in an Einsteinian universe - faster than light communication is not.
2.3 / 5 (3) Jan 24, 2013
But otto, no, it's not. It doesn't. But it can't. No and noooooo. What the ....??? In your own mind maybe. No, no and no.

Why would anyone read your theory?
1.7 / 5 (6) Jan 24, 2013
you don't win any points for sloppy use of English or physics.

Who cares about English or physics? But we can talk after you get out of your invisibility coat. Leave the top hat at home.

Just for you: I propose a new theory (in fluent English), it's called Theory of Tiny Bunnies. Basically, there are like these, uhm... real small, like, uhm... bunnies. And they, and they, and they I mean fill like, the whole Space n stuff. They so small you actually can't see them? But, but, but we may actually live in the stomach of one of real giant bunny! And, and, and that's why we're not really aware of all the bunnies out there. Which are infinitely many? Uhm, the reason, the reason, the reason we know they exist however, is coz, is coz, is coz cabbage and carrot don't grow in Space, which is a well established fact so that, so that, so that, since tiny bunnies obviously ate all the carrot and cabbage, that's how, that's how we know tiny bunnies are real. Stockholm, there I came.
3 / 5 (4) Jan 24, 2013
Who cares about English
A doctoral committee, for one example, as you already know (if you actually were a Ph.D. candidate). Disingenuousness gets you nowhere.

or physics?
Erm, physicists? (Of which community you are apparently not well qualified to be a member.)

But we can talk
Only if you put down the crack pipe first, and avoid the idiot's babble you posted in lieu of a cogent reply.

You still need to address the notions of drag/friction in atomic clocks, and how it could have made a difference in identical mechanisms.

Respond in a useful manner, or else stop trolling and go home.
1.8 / 5 (5) Jan 24, 2013
Who cares about English

I propose a new theory (in fluent English), it's called Theory of Tiny Bunnies. Basically, there are like these, uhm... real small, like, uhm... bunnies. (inquire above for details)

In the meantime, on planet Earth: "How Wineland & Haroche Stole My Discovery (and got 2012 PHYSICS NOBEL PRIZE for it...)"
1 / 5 (2) Jan 25, 2013
T.W. Barrett asserts Shannon was aware of the following distinction:

"Shannon's work involves the resolution of the uncertainties considering final outcome in the face of a repertoire of possible occurrences, the occurrences possibly varying in their probability of occurrence. The accent is on hypothetical transmission of events defined abstractly, so that a temporal aspect is given to the theory. Thus, his work may more properly be termed transmission theory - to distinguish it from information theory based strictly on energy distribution - a distinction he [Shannon] was aware of."

As a fan boy of T.W. Barrett, I can not be helped - so I agree.
The Spanish researchers agree on this as well.

AA asserts the following the distinction:
Information transmission and information transfer are not interchangeable. Bravo.

The comparison drawn by the Spanish researchers is admissible or at least we all agree there is a distinction. One is used as a measure for the other.