The importance of entanglement?

Quantum information can be processed, but the accessibility of this information is limited by the Holevo bound (mentioned in Section 3). David Deutsch (1985) first showed how to exploit quantum entanglement to perform a computational task that is impossible for a classical computer. Suppose we have a black box or oracle that evaluates a function f. The arguments of f (inputs) are either 0 or 1. The values (outputs) of f (which are also 0 or 1) are either the same for both arguments (in which case f is constant), or different for the two arguments (in which case f is said to be ‘balanced’). We are interested in determining whether f is constant or balanced. Now, classically, the only way to do this is to run the black box or query the oracle twice, for both arguments 0 and 1, and to pass the values (outputs of f) to a circuit that determines whether they are the same (for ‘constant’) or different (for ‘balanced’). Deutsch showed that if we use quantum states and quantum gates to store and process information, then we can determine whether f is constant or balanced in one evaluation of the function f. The trick is to design the circuit (the sequence of gates) to produce the answer to a global question about the function (‘constant’ or ‘balanced’) in an output qubit register that can then be read out or measured.

Consider again the quantum CNOT gate, with two orthogonal qubits |0> and |1> as possible inputs for the control, and |0> as the input for the target. One can think of the input control and output target qubits, respectively, as the argument and associated value of a function. This CNOT function associates the value 0 with the argument 0 and the value 1 with the argument 1. For a linear superposition of the orthogonal qubits with equal coefficients as input to the control, represented as |0> + |1> (ignoring the coefficients, for simplity), and the qubit |0> as the input to the target, the output is the entangled state |0>|0> + |1>|1>, a linear superposition in which the first term represents the argument 0 and associated value (0) of the CNOT function, and the second term represents the argument 1 and associated value (1) of the CNOT function. The entangled state represents all possible arguments and corresponding values of the function as a linear superposition, but this information is not accessible. What can be shown to be accessible, by a suitable choice of quantum gates, is information about whether or not the function has certain global properties. This information is obtainable without reading out the evaluation of any individual arguments and values. (Indeed, accessing information in the entangled state about a global property of the function will typically require losing access to all information about individual arguments and values.)

The situation is analogous for Deutsch's function f. Here the output of f can be represented as either |0>|0> + |1>|0> or >|0>|1> + |1>|1> (in the ‘constant’ case), or |0>|0> + |1>|1> or |0>|1> + |1>|0> (in the ‘balanced’ case). The two entangled states in the ‘constant’ case are orthogonal in the 4-dimensional two-qubit state space and span a plane. Call this the ‘constant’ plane. Similarly, the two entangled states in the ‘balanced’ case span a plane, the ‘balanced’ plane. These planes are orthogonal in the 4-dimensional state space, except for an overlap: a line, representing a (non-entangled) two-qubit state. It is therefore possible to design a measurement to distinguish the two global properties of f, ‘constant’ or ‘balanced,’ with a certain probability (actually, 1/2) of failure, when the measurement yields an outcome corresponding to the overlap state, which is common to the two cases. Nevertheless, only one query of the function is required when the measurement succeeds in identifying the global property. With a judicious choice of quantum gates, it is even possible to design a quantum circuit that always succeeds in distinguishing the two cases in one run.

Deutsch's example shows how quantum information, and quantum entanglement, can be exploited to compute a global property of a function in one step that would take two steps classically. While Deutsch's problem is rather trivial, there now exist several quantum algorithms with interesting applications, notably Shor's factorization algorithm for factoring large composite integers in polynomial time (with direct application to ‘public key’ cryptography, a widely used classical cryptographic scheme) and Grover's database search algorithm. Shor's algorithm achieves an exponential speed-up over any known classical algorithm. For algorithms that are allowed access to oracles (whose internal structure is not considered), the speed-up can be shown to be exponential over any classical algorithm in some cases, e.g., Simon's algorithm. See Nielsen and Chuang 2000, Barenco's article “Quantum Computation: An Introduction” in Lo, Popescu, and Spiller 1998, Bub 2006 (Section 6), as well as the entry on quantum computing.

Note that there is currently no proof that a quantum algorithm can solve an NP-complete problem in polynomial time (the factorization problem is not NP-complete), so the efficiency of quantum computers relative to classical computers might turn out to be illusory. If there is indeed a speed-up, it would seem to be due to the phenomenon of entanglement. The amount of information required to describe a general entangled state of n qubits grows exponentially with n. The state space (Hilbert space) has 2n dimensions, so a general entangled state is a superposition of 2n n-qubit states. In classical mechanics there are no entangled states: a general n-bit composite system can be described with just n times the amount of information required to describe a single bit system. So the classical simulation of a quantum process would involve an exponential increase in the classical informational resource required to represent the quantum state, as the number of qubits that become entangled in the evolution grows linearly, and there would be a corresponding exponential slowdown in calculating the evolution, compared to the actual quantum computation performed naturally by the system. Nevertheless, there is no consensus in the literature as to what exactly explains the apparent speed-up. For a discussion, see Bub 2007, 2010.