Nonlocality and communication complexity

Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary $k$-bit messages cannot be compressed into messages of $k-1$ qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.

Figure 1

The basic communication scenario: Alice receives an $n$-bit string $x$ as input and sends one message to Bob, who must output $x$. For this task, a quantum message is no more efficient than a classical message.

Figure 2

The basic communication complexity scenario: Alice and Bob receive $n$-bit strings $x$ and $y$, respectively, as input and their goal to compute some function of these values $f(x,y)$ as Bob’s output. There are tasks of this form where communication in terms of quantum messages is much more efficient than communication in terms of classical messages. The number of qubits can be exponentially smaller than the number of bits. Note that in this framework we do not take into account the time and other resources that Alice and Bob spend locally (although in practice it turns out that their local computations are almost always efficient).

Figure 3

The general form of a nonlocality scenario involving three parties: Alice, Bob, and Carol receive inputs $s$, $t$, and $u$, respectively, and are required to produce outputs $a$, $b$, and $c$, respectively, satisfying certain conditions. Once the inputs are received, no communication is permitted between the parties. For the specific GHZ scenario, it is possible to accomplish the task if the parties are in possession of a tripartite entangled state. Without the prior entanglement, it is impossible to accomplish the task.

Figure 4

The nonlocality scenario involving two parties: Alice and Bob receive inputs $s$ and $t$, respectively, and are required to produce outputs $a$ and $b$, respectively, satisfying certain conditions. Once the inputs are received, no communication is permitted between the parties. For the specific CHSH scenario, it is possible to accomplish the task with probability ${\cos }^2(\pi ∕8)=0.853\dots$ if the parties are in possession of an ebit. Without the prior entanglement, the highest possible success probability is $3∕4$.

Figure 5

The simultaneous message passing variant of the communication complexity scenario: Alice and Bob receive $n$-bit strings $x$ and $y$, respectively, as input and their communication is restricted to each sending one message to a third party, called the referee. From these messages, the referee computes some function $f(x,y)$ as the output of the protocol. There are tasks of this form where communication in terms of quantum messages is exponentially more efficient than communication in terms of classical messages.

Figure 6

Quantum circuit to test if $|\varphi ⟩=|\psi ⟩$ or $\left|⟨\varphi |\psi ⟩\right|⩽\frac{1}{3}$.

Figure 7

(Color online) Bell inequality with two remote atomic qubits. The left-hand side is a schematic description of the experiment reported by 88 in which the internal states of two ions separated by about $1\mathrm{m}$ were entangled. Measurements on the two ions then allowed the violation of the CHSH inequality with the detection loophole closed. A series of laser pulses simultaneously excites both ${\mathrm{Yb}}^{+}$ ions in such a way that when they deexcite they emit a photon whose polarization is entangled with the ion. A lens is used to couple the photons into optical fibers. The wave plate $(\lambda ∕4)$ is used for convenience to convert circular polarization into linear polarization. The two photons interfere on a beam splitter (BS) and are detected by photomultiplier tubes (PMTs). Simultaneous detection of a photon by the two PMTs signals that the photons were in a Bell state, thereby realizing entanglement swapping: the two ions are now entangled. The internal states of the ions are then measured, enabling a violation of the CHSH inequality. Note that there are many inefficiencies in this experiment: only a fraction of emitted photons are coupled into the optical fibers and only a fraction of the photons reaching the PMTs are detected. But when two photons are detected, one knows with certainty that the two ions are entangled. The right-hand side is a photograph of one of the ion traps. The other trap is similar and located about $1\mathrm{m}$ away on the same optical table. Both courtesy of Monroe and Matsukevich.