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

(Phys.org)—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 Phys.org. "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 quantum systems). 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 others¹ 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 channel 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 information theory – 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 quantum entanglement is actually a real phenomenon," Briët notes. "It's predicted to exist by quantum mechanics, 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."

Copyright 2013 Phys.org
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of Phys.org.