Quantum Information Processing

by Bram Vermeer and Harry Buhrman

Work on quantum entanglement at CWI gives new insight in the non-locality of Nature. There is also a surprising connection to fault tolerant computing and the feasibility of quantum computers.

In 1935 Einstein, Podolsky, and Rosen devised a famous thought experiment. In quantum mechanics, it is possible to construct two particles that are strongly coupled. Suppose that Alice has one particle in Amsterdam and Bob has the other in New York. When Alice measures her particle she will observe a random outcome 0 or 1, each with equal probability. The same is true for Bob. However, Alice and Bob always obtain the same value. Such particles are called entangled. It seems that the outcome of Alice’s measurement instantaneously influences Bob’s one. However, this should not be possible since nothing goes faster than the speed of light.

In order to explain this apparent non-local phenomenon one tried to come up with local hidden variable models. If the outcome of Alice’s and Bob’s measurement was already known at the time the two entangled particles were created, then their correlation would not require instantaneous communication.

Keep communication simple. How much information does Bob have to send to Alice in order to fix a date?

It was John Bell who in 1964 came up with the description of a clever experiment that would shed more light on the situation. He created a game and showed that if quantum mechanics is non-local, then Alice and Bob could win this with higher probability than what is classically possible. In the early 1980’s Alain Aspect and his group (Orsay, France) demonstrated that Nature is indeed non-local and there is no local hidden variable model that can explain it.

Quantum Computing and Entanglement
Quantum computing groups at CWI and in North-America addressed in the late 1990’s the non-locality issue in more operational terms. In quantum mechanics entangled particles can not be used for communication. This non-signalling property is important since it would otherwise be in direct conflict with Einstein’s theory of relativity. But our research groups showed that certain distributed computation tasks can be solved with less communication when one makes use of entanglement.

Take for example the agenda problem: Alice and Bob want to make an appointment and need to know the free slots in each others agenda. If Alice and Bob have a quantum computer and share entangled particles, they can agree with significantly less communication than what is classically possible. For certain problems, there is even an exponential saving in communication (although savings are not always possible). In certain cases entanglement can be used to communicate more efficiently, but it cannot be used to replace communication altogether.

Beyond Quantum Mechanics
To understand the non-local aspect of Nature better, Popescu and Rohrlich investigated in the 1990s in more detail a non-locality game, called the CHSH game. This game can be won with probability roughly 85 percent when making use of entanglement whereas without, it can only be won 75 percent of the time. They showed that this game can in principle be won 100 percent of the time without violating the non-signalling primitive. They raised the question: "Why is Nature not more non-local?"

A partial answer was given by Wim van Dam, at the time PhD student at CWI. He showed that if Nature allowed the CHSH game to be won with 100 percent, then every distributed communication task would become trivial, and would only require a single bit.

Harry Buhrman (CWI and University of Amsterdam), Falk Unger (CWI), and groups in Montreal and Bristol examined the case when Nature would allow this game to be won with a probability between 85 percent – the quantum mechanical bound – and 100 percent – the ideal Popescu-Rohrlich bound. Their findings – reported in Phys. Rev. Letters and reviewed in Nature Physics – show something remarkable. There is a sharp threshold with respect to the probability to win the CHSH game and communication required for every distributed task. They show that when the game is won with a probability around 90 percent still every distributed computation problem can be solved with one single bit of communication. On the other hand, at 85 percent many problems require a lot of communication. These results indicate a different reason why Nature is not more non-local than at least 90 percent, since this would render communication tasks trivial. It is a fascinating open problem whether the true threshold of trivial communication lies at the quantum mechanical bound of 85 percent, or higher.

The Feasibility of a Quantum Computer
These results have intriguing consequences for the efficiency of computers. The high-speed computers that are set to make their entry in the coming years will inevitably be prone to errors. Computer science has a solution for this problem in the form of fault-tolerant algorithms. The components that carry out these adjustments are also susceptible to error. This implies that there are limits to the degree of error that can be rectified in this manner. This threshold is important when it comes to quantum computers since they will inevitably be prone to error. They should therefore be designed with fault-tolerance in mind. But this raises the question: at what level of error is quantum computing impossible?

Buhrman and fellow researchers have discovered a surprising connection between fault-tolerant computation and the results on non-locality. By exploiting this connection they have constructed a new upper bound for the error threshold, above which quantum computers would be unable to function. The exact bound of this error threshold is important to establish since it shows exactly how reliable the components of a quantum computer must be in order to function properly. Currently the best known bound for the error threshold is still far away from the errors observed during experiments in the laboratories around the world.

Link:
http://www.cwi.nl/ins4

Please contact:
Harry Buhrman
CWI, The Netherlands
Tel: +31 20 592 4076
E-mail: Harry.Buhrmancwi.nl