Quantum entanglement is a physical resource, like energy, associated with the peculiar nonclassical correlations that are possible between separated quantum systems. Entanglement can be measured, transformed, and purified. A pair of quantum systems in an entangled state can be used as a quantum information channel to perform computational and cryptographic tasks that are impossible for classical systems. The general study of the information-processing capabilities of quantum systems is the subject of quantum information theory.
1. Quantum Entanglement
In 1935 and 1936, Schrödinger published a two-part article in the Proceedings of the Cambridge Philosophical Society in which he discussed and extended a remarkable argument by Einstein, Podolsky, and Rosen. The Einstein-Podolsky-Rosen (EPR) argument was, in many ways, the culmination of Einstein's critique of the orthodox Copenhagen interpretation of quantum mechanics, and was designed to show that the theory is incomplete. (See The Einstein-Podolsky-Rosen Argument in Quantum Theory and Copenhagen Interpretation of Quantum Mechanics.) In classical mechanics the state of a system is essentially a list of the system's properties — more precisely, it is the specification of a set of parameters from which the list of properties can be reconstructed: the positions and momenta of all the particles comprising the system (or similar parameters in the case of fields).
The dynamics of the theory specifies how properties change in terms of a law of evolution for the state. Pauli characterized this mode of description of physical systems as a ‘detached observer’ idealization. See Pauli's letter to Born in The Born-Einstein Letters (Born, 1992; p. 218). On the Copenhagen interpretation, such a description is not possible for quantum systems. Instead, the quantum state of a system should be understood as a catalogue of what an observer has done to the system and what has been observed, and the import of the state then lies in the probabilities that can be inferred (in terms of the theory) for the outcomes of possible future observations on the system. Einstein rejected this view and proposed a series of arguments to show that the quantum state is simply an incomplete characterization of the system. The missing parameters are sometimes referred to as ‘hidden parameters’ or ‘hidden variables’ (although Einstein did not use this terminology, presumably because he did not want to endorse any particular ‘hidden variable’ theory).
It should not be supposed that Einstein's definition of a complete theory included the requirement that it be deterministic. Rather, he required certain conditions of separability and locality for composite systems consisting of separated component systems: each component system separately should be characterized by its own properties (even if these properties manifest themselves stochastically), and it should be impossible to alter the properties of a distant system instantaneously (or the probabilities of these properties) by acting on a local system. In later analyses — notably in Bell's extension of the EPR argument — it became apparent that these conditions, suitably formulated as probability constraints, are equivalent to the requirement that statistical correlations between separated systems should be reducible to probability distributions over common causes (deterministic or stochastic) in the sense of Reichenbach. (See Bell's Theorem and Reichenbach's Common Cause Principle.)
In the original EPR article, two particles are prepared from a source in a certain quantum state and then move apart. There are ‘matching’ correlations between both the positions of the two particles and their momenta: a measurement of either position or momentum on a particular particle will allow the prediction, with certainty, of the outcome of a position measurement or momentum measurement, respectively, on the other particle.
These measurements are mutually exclusive: either a position measurement can be performed, or a momentum measurement, but not both simultaneously. Either correlation can be observed, but the subsequent measurement of momentum, say, after establishing a position correlation, will no longer yield any correlation in the momenta of the two particles. It is as if the position measurement disturbs the correlation between the momentum values.
The puzzle is that the assumption of the completeness of the quantum state of the particle pair is inconsistent with the assignment of labels to the particles separately that could be associated with appropriately correlated values for the outcomes of position and momentum measurements. These labels would be the common causes of the correlations, and would provide an explanation of the correlations in terms of the initial correlations between the properties of the two systems at their source. EPR concluded that the quantum state was incomplete.
Here is how Schrödinger put the puzzle in the first part of his two-part article (Schrödinger, 1935; p. 559):
Yet since I can predict either x1 or p1 without interfering with the system No. 1 and since system No. 1, like a scholar in an examination, cannot possibly know which of the two questions I am going to ask first: it so seems that our scholar is prepared to give the right answer to the first question he is asked, anyhow. Therefore he must know both answers; which is an amazing knowledge; quite irrespective of the fact that after having given his first answer our scholar is invariably so disconcerted or tired out, that all the following answers are ‘wrong.’
What Schrödinger showed was that if two particles are prepared in a quantum state such that there is a matching correlation between two ‘canonically conjugate’ dynamical quantities — quantities like position and momentum whose values suffice to specify all the properties of a classical system — then there are infinitely many dynamical quantities of the two particles for which there exist similar matching correlations: every function of the canonically conjugate pair of the first particle matches with the same function of the canonically conjugate pair of the second particle. Thus (Schrödinger, p. 559) system No. 1 ‘does not only know these two answers but a vast number of others, and that with no mnemotechnical help whatsoever, at least with none that we know of.’
Schrödinger coined the term ‘entanglement’ to describe this peculiar connection between quantum systems (Schrödinger, 1935; p. 555):
When two systems, of which we know the states by their respective representatives, enter into temporary physical interaction due to known forces between them, and when after a time of mutual influence the systems separate again, then they can no longer be described in the same way as before, viz. by endowing each of them with a representative of its own. I would not call that one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought. By the interaction the two representatives [the quantum states] have become entangled.
He added (Schrödinger, 1935; p. 555):
Another way of expressing the peculiar situation is: the best possible knowledge of a whole does not necessarily include the best possible knowledge of all its parts, even though they may be entirely separate and therefore virtually capable of being ‘best possibly known,’ i.e., of possessing, each of them, a representative of its own.
The lack of knowledge is by no means due to the interaction being insufficiently known — at least not in the way that it could possibly be known more completely — it is due to the interaction itself.Attention has recently been called to the obvious but very disconcerting fact that even though we restrict the disentangling measurements to one system, the representative obtained for theother system is by no means independent of the particular choice of observations which we select for that purpose and which by the way are entirely arbitrary. It is rather discomforting that the theory should allow a system to be steered or piloted into one or the other type of state at the experimenter's mercy in spite of his having no access to it.
In the second part of the paper, Schrödinger showed that, in general, a sophisticated experimenter can, by a suitable choice of operations carried out on one system, ‘steer’ the second system into any chosen mixture of quantum states. That is, the second system cannot be steered into any particular quantum state at the whim of the experimenter, but the experimenter can constrain the quantum state into which the second system evolves to lie in any chosen set of states, with a probability distribution fixed by the entangled state.
He found this conclusion sufficiently unsettling to suggest that the entanglement between two separating systems would persist only for distances small enough that the time taken by light to travel from one system to the other could be neglected, compared with the characteristic time periods associated with other changes in the composite system. He speculated that for longer distances each of the two systems might in fact be in a state associated with a certain mixture, determined by the precise form of the entangled state.
Most physicists attributed the puzzling features of entangled quantum states to Einstein's inappropriate ‘detached observer’ view of physical theory, and regarded Bohr's reply to the EPR argument (Bohr, 1935) as vindicating the Copenhagen interpretation. This was unfortunate, because the study of entanglement was ignored for thirty years until John Bell's reconsideration and extension of the EPR argument (Bell, 1964).
Bell looked at entanglement in simpler systems than the EPR case: matching correlations between two-valued dynamical quantities, such as polarization or spin, of two separated systems in an entangled state. What Bell showed was that the statistical correlations between the measurement outcomes of suitably chosen different quantities on the two systems are inconsistent with an inequality derivable from Einstein's separability and locality assumptions — in effect from the assumption that the correlations have a common cause.
Bell's investigation generated an ongoing debate on the foundations of quantum mechanics. One important feature of this debate was confirmation that entanglement can persist over long distances(see Aspect et al.), thus falsifying Schrödinger's supposition of the spontaneous decay of entanglement as two entangled particles separate. But it was not until the 1980s that physicists, computer scientists, and cryptographers began to regard the non-local correlations of entangled quantum states as a new kind of non-classical resource that could be exploited, rather than an embarrassment to be explained away.
For further discussion of entanglement as a physical resource, including measuring entanglement, and the manipulation and purification of entanglement by local operations, see “The Joy of Entanglement” by Popescu and Rohrlich in Lo, Popescu, and Spiller 1998, or Nielsen and Chuang 2000.
2. Exploiting Entanglement: Quantum Teleportation
Consider again Schrödinger's realization that an entangled state could be used to steer a distant particle into one of a set of states, with a certain probability. In fact, this possibility of ‘remote steering’ is even more dramatic than Schrödinger demonstrated. Suppose Alice and Bob share an entangled state of the sort considered by Bell, say two photons in an entangled state of polarization. That is, Alice has in her possession one of the entangled photons, and Bob the other.
Suppose that Alice has an additional photon in an unknown state of polarization |u>, where the notation ‘| >’ denotes a quantum state. It is possible for Alice to perform an operation on the two photons in her possession that will transform Bob's photon into one of four states, depending on the four possible (random) outcomes of Alice's operation: either the state |u>, or a state that is related to |u> in a definite way. Alice's operation entangles the two photons in her possession, and disentangles Bob's photon, steering it into a state |u*>.
After Alice communicates the outcome of her operation to Bob, Bob knows either that |u*> = |u>, or how to transform |u*> to |u> by a local operation. This phenomenon is known as ‘quantum teleportation.’
What is extraordinary about this phenomenon is that Alice and Bob have managed to use their shared entangled state as a quantum communication channel to destroy the state |u> of a photon in Alice's part of the universe and recreate it in Bob's part of the universe. Since the state of a photon requires specifying a direction in space (essentially the value of an angle that can vary continuously), without a shared entangled state Alice would have to convey an infinite amount of classical information to Bob for Bob to be able to reconstruct the state |u> precisely. To see why this is so, consider that the decimal expansion of an angle variable represented by a real number is represented by a potentially infinite sequence of digits between 0 and 9.
The binary expansion is represented by a potentially infinite sequence of 0's and 1's. Ever since Shannon formalized the notion of classical information, the amount of classical information associated with a binary alternative (represented as 0 or 1), where each alternative has equal probability, is measured as one binary digit or ‘bit’. So to specify the value of an arbitrary angle variable requires an infinite number of bits.
To specify the outcome of Alice's operation, which has four possible outcomes with equal probabilities, requires two bits of classical information. Remarkably, Bob can reconstruct the state |u> on the basis of just two bits of classical information communicated by Alice, apparently by exploiting the entangled state as a quantum communication channel to transfer the remaining information. For further discussion of quantum teleportation, see Nielsen and Chuang 2000, or Richard Josza's article “Quantum Information and its Properties” in Lo, Popescu, and Spiller 1998.
3. Quantum Information
Formally, the amount of classical information we gain, on average, when we learn the value of a random variable (or, equivalently, the amount of uncertainty in the value of a random variable before we learn its value) is represented by a quantity called the Shannon entropy, measured in bits (Shannon and Weaver, 1949). A random variable is defined by a probability distribution over a set of values. In the case of a binary random variable, with equal probability for each of the two possibilities, the Shannon entropy is 1 bit, representing maximal uncertainty.
For all other probabilities — intuitively, representing some information about which alternative is more likely — the Shannon entropy is less than 1. For the case of maximal knowledge or zero uncertainty about the alternatives, where the probabilities are 0 and 1, the Shannon entropy is zero. (Note that the term ‘bit’ is used to refer to the basic unit of classical information in terms of Shannon entropy, and to an elementary two-state classical system considered as representing the possible outputs of an elementary classical information source.)
Since information is always embodied in the state of a physical system, we can also think of the Shannon entropy as quantifying the physical resources required to store classical information. Suppose Alice wishes to communicate some classical information to Bob over a classical communication channel such as a telephone line, say an email message.
A relevant question concerns the extent to which the message can be compressed without loss of information, so that Bob can reconstruct the original message accurately from the compressed version. According to Shannon's source coding theorem or noiseless coding theorem (assuming a noiseless telephone line with no loss of information), the minimal physical resource required to represent the message (effectively, a lower bound on the possibility of compression) is given by the Shannon entropy of the source.
What happens if we use the quantum states of physical systems to store information, rather than classical states? It turns out that quantum information is radically different from classical information. The unit of quantum information is the ‘qubit’, representing the amount of quantum information that can be stored in the state of the simplest quantum system, for example, the polarization state of a photon. The term is due to Schumacher (1995), who proved a quantum analogue of Shannon's noiseless coding theorem. (By analogy with the term ‘bit,’ the term ‘qubit’ refers to the basic unit of quantum information in terms of the von Neumann entropy, and to an elementary two-state quantum system considered as representing the possible outputs of an elementary quantum information source.)
As we have seen, an arbitrarily large amount of classical information can be encoded in a qubit. This information can be processed and communicated but, because of the peculiarities of quantum measurement, at most one bit can be accessed! According to a theorem by Holevo, the accessible information in a probability distribution over a set of alternative qubit states is limited by the von Neumann entropy, which is equal to the Shannon entropy only when the states are orthogonal in the space of quantum states, and is otherwise less than the Shannon entropy.
While classical information can be copied or cloned, the quantum ‘no cloning’ theorem (Dieks, 1982; Wootters and Zurek, 1982) asserts the impossibility of cloning an unknown quantum state. To see why, consider how we might construct a classical copying device. A NOT gate is a device that takes a bit as input and produces as output either a 1 if the input is 0, or a 0 if the input is 1. In other words, a NOT gate is a 1-bit gate that flips the input bit.
A controlled-NOT gate, or CNOT gate, takes two bits as inputs, a control bit and a target bit, and flips the target bit if and only if the control bit is 1, while reproducing the control bit. (So there are two inputs, the control and target, and two outputs: the control, and either the target or the flipped target, depending on the value of the control.) A CNOT gate functions as a copying device for the control bit if the target bit is set to 0, because the output of the target bit is then a copy of the control bit (i.e., the input 00 produces output 00, and the input 10 produces output 11).
Insofar as we can think of a measurement as simply a copying operation, a CNOT gate is the paradigm of a classical measuring device. (Imagine Alice equipped with such a device, with input and output control and target wires, measuring the properties of an unknown classical world. The input control wire is a probe for the presence of absence of a property, represented by a 1 or a 0. The target wire functions as the pointer, which is initially set to 0. The output of the target is a 1 or a 0, depending on the presence or absence of the property.)
Suppose we attempt to use our CNOT gate to copy an unknown qubit state. Since we are now proposing to regard the CNOT gate as a device for processing quantum states, the evolution from input states to output states must be effected by a physical quantum transformation. Now quantum transformations are linear on the linear state space of qubits. Linearity of the state space means that for any two qubit states — call them |0> and |1> — that are orthogonal in the space of qubit states, there are qubit states that are represented by linear superpositions or sums of |0> and |1>, with certain coefficients. Such superpositions — e.g., a superposition with coefficients c0, c1 represented symbolically as c0|0> + c1|1> — are non-orthogonal to |0> and to |1>.
Linearity of the transformation means that any transformation must take a qubit state represented by the sum of two orthogonal qubits to a new qubit state that is the sum of the transformed orthogonal qubits. If the CNOT gate succeeds in copying two orthogonal qubits, it cannot succeed in copying a linear superposition of these qubits. Since the gate functions linearly, it must instead produce a state that is a linear superposition of the outputs obtained for the two orthogonal qubits.
That is to say, the output of the gate will be represented by a quantum state that is a sum of two terms, where the first term represents the output of the control and target for the first orthogonal qubit, and the second term represents the output of the control and target for the second orthogonal qubit. This could be expressed as c0|0>|0> + c1|1>|1>. This is an entangled state and not the output that would be required by a successful copying operation, where the control and target each outputs the superposed qubit, expressed as (c0|0> + c1|1>)(c0|0> + c1|1>).
4. Quantum Cryptography
Linearity prevents the possibility of cloning or measuring an unknown quantum state. Similarly, it can be shown that if Alice sends Bob one of two nonorthogonal qubits, Bob can obtain information about which of these qubits was sent only at the expense of disturbing the state. In general, for quantum information there is no information gain without disturbance.
The impossibility of copying an unknown quantum state, or a state that is known to belong to a set of nonorthogonal states with a certain probability, and the existence of a trade-off relation between information gain and state disturbance, is the basis of the application of quantum information to cryptography.
There are quantum protocols involving the exchange of classical and quantum information that Alice and Bob can exploit to share a secret random key, which they can then use to communicate privately. (See Lo's article “Quantum Cryptology” in Lo, Popescu, and Spiller, 1998.) Any attempt by an eavesdropper, Eve, to monitor the communication between Alice and Bob will be detectable, in principle, because Eve cannot gain any quantum information without some disturbance to the quantum communication channel. Moreover, the ‘no cloning’ theorem prohibits Eve from copying the quantum communications and processing them off-line, so to speak, after she monitors the classical communication between Alice and Bob.
While the difference between classical and quantum information can be exploited to achieve successful key distribution, there are other cryptographic protocols that are thwarted by quantum entanglement. Bit commitment is a key cryptographic protocol that can be used as a subroutine in a variety of important cryptographic tasks. In a bit commitment protocol, Alice supplies an encoded bit to Bob.
The information available in the encoding should be insufficient for Bob to ascertain the value of the bit, but sufficient, together with further information supplied by Alice at a subsequent stage when she is supposed to reveal the value of the bit, for Bob to be convinced that the protocol does not allow Alice to cheat by encoding the bit in a way that leaves her free to reveal either 0 or 1 at will.
To illustrate the idea, suppose Alice claims the ability to predict advances or declines in the stock market on a daily basis. To substantiate her claim without revealing valuable information (perhaps to a potential employer, Bob) she suggests the following demonstration: She proposes to record her prediction, before the market opens, by writing a 0 (for ‘decline’) or a 1 (for ‘advance’) on a piece of paper, which she will lock in a safe. The safe will be handed to Bob, but Alice will keep the key. At the end of the day's trading, she will announce the bit she chose and prove that she in fact made the commitment at the earlier time by handing Bob the key.
Of course, the key-and-safe protocol is not provably secure from cheating by Bob, because there is no principle of classical physics that that prevents Bob from opening the safe and closing it again without leaving any trace. The question is whether there exists a quantum analogue of this procedure that is unconditionally secure: provably secure by the laws of physics against cheating by either Alice or Bob. Bob can cheat if he can obtain some information about Alice's commitment before she reveals it (which would give him an advantage in repetitions of the protocol with Alice). Alice can cheat if she can delay actually making a commitment until the final stage when she is required to reveal her commitment, or if she can change her commitment at the final stage with a very low probability of detection.
It turns out that unconditionally secure two-party bit commitment, based solely on the principles of quantum or classical mechanics (without exploiting special relativistic signalling constraints, or principles of general relativity or thermodynamics) is impossible. See Mayers 1997, Lo and Chau 1997 and Lo's article “Quantum Cryptology” in Lo, Popescu, and Spiller 1998 for further discussion. Note that Kent (1999) has shown that one can implement a secure classical bit commitment protocol by exploiting relativistic signalling constraints in a timed sequence of communications between verifiably separated sites for both Alice and Bob.) Roughly, the impossibility arises because at any step in the protocol where either Alice or Bob is required to make a determinate choice (perform a measurement on a particle in the quantum channel, choose randomly and perhaps conditionally between a set of alternative actions to be implemented on the particle in the quantum channel, etc.), the choice can delayed by entangling one or more ‘ancilla’ particles with the channel particle in an appropriate way.
By suitable operations on the ancillas, the channel particle can be ‘steered’ so that this cheating strategy is undetectable. In effect, if Bob can obtain no information about the bit in the safe, then entanglement will allow Alice to ‘steer’ the bit to either 0 or 1 at will.
5. Quantum Computation
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.
6. Interpretative Remarks
Deutsch (1997) has argued that the exponential speed-up in quantum computation, and in general the way a quantum system processes information, can only be properly understood within the framework of Everett's ‘many-worlds’ interpretation (see Everett's Relative-State Formulation of Quantum Mechanics and Many-Worlds Intepretation of Quantum Mechanics). The idea, roughly, is that an entangled state of the sort that arises in the quantum computation of a function, which represents a linear superposition over all possible arguments and corresponding values of the function, should be understood as something like a massively parallel classical computation, for all possible values of a function, in parallel worlds. For an insightful critique of this idea of ‘quantum parallelism’ as explanatory, see Steane 2003.
An alternative view, not much discussed in the literature in this connection, is the quantum logical approach, which emphasizes the non-Boolean structure of properties of quantum systems. (The properties of a classical system form a Boolean algebra, essentially the abstract characterization of a set-theoretic structure.
This is reflected in the Boolean character of classical logic, and the Boolean gates in a classical computer.) From this perspective, the picture is entirely different. Rather than ‘computing all values of a function at once,’ a quantum algorithm achieves an exponential speed-up over a classical algorithm by avoiding the computation of any values of the function at all.
A crucial difference between quantum and classical information is the possibility of selecting an exclusive disjunction, representing a global property of a function, among alternative possible disjunctions — for example, the ‘constant’ disjunction asserting that the value of the function (for both arguments) is either 0 or 1, or the ‘balanced’ disjunction asserting that the value of the function (for both arguments) is either the same as the argument or different from the argument — without determining the truth values of the disjuncts.
Classically, an exclusive disjunction is true if and only if one of the disjuncts is true. This is is redundant information in a quantum computation but essential information classically: an exclusive classical disjunction is true if and only if one of the disjuncts is true. In effect, Deutsch's quantum circuit achieves its speed-up by exploiting the non-Boolean structure of quantum properties to efficiently distinguish between two disjunctive properties, without determining the truth values of the relevant disjuncts (representing the association of individual arguments with corresponding function values).
The point of the procedure is to avoid the evaluation of the function in the determination of the global property, in the sense of producing a value in the range of the function for a value in its domain, and it is this feature — impossible in the Boolean logic of classical computation — that leads to the speed-up relative to classical algorithms. For some recent work by Giuntini and others on logics associated with quantum gates, see under ‘quantum computational logics’ in the Other Internet Resources. (For quantum logic not specifically in relation to quantum computation, see the entry on quantum logic and quantum probability).
Some researchers in quantum information and quantum computation have argued for an information-theoretic interpretation of quantum mechanics. In his review article on quantum computation, Andrew Steane (1998, p. 119) makes the following remark:
Historically, much of fundamental physics has been concerned with discovering the fundamental particles of nature and the equations which describe their motions and interactions. It now appears that a different programme may be equally important: to discover the ways that nature allows, and prevents, information to be expressed and manipulated, rather than particles to move.
Steane concludes his review with the following radical proposal (1998, p. 171):
To conclude with, I would like to propose a more wide-ranging theoretical task: to arrive at a set of principles like energy and momentum conservation, but which apply to information, and from which much of quantum mechanics could be derived. Two tests of such ideas would be whether the EPR-Bell correlations thus became transparent, and whether they rendered obvious the proper use of terms such as ‘measurement’ and ‘knowledge’.
In line with this proposal, Clifton, Bub, and Halvorson 2003 showed that one can derive the basic kinematic features of a quantum description of physical systems from three fundamental information-theoretic constraints:
‘no signaling,’ i.e., no information should be available in the marginal probabilities of measurement outcomes in one region about alternative choices made by an agent in a separated region
the impossibility of perfectly broadcasting the information contained in an unknown physical state (which, for pure states, amounts to ‘no cloning’)
the impossibility of communicating information so as to implement a bit commitment protocol with unconditional security
The analysis is carried out in an algebraic framework (C*-algebras) which allows a mathematically abstract characterization of a physical theory including, as special cases, all classical mechanical theories of both wave and particle varieties, and all variations on quantum theory, including quantum field theories (plus any hybrids of these theories, such as theories with superselection rules).
Within this framework, the three information-theoretic constraints are shown to jointly entail three physical conditions that are taken as definitive of what it means to be a quantum theory in the most general sense, specifically that:
the algebras of observables pertaining to distinct physical systems commute (a condition usually called microcausality or kinematic independence)
any individual system's algebra of observables is noncommutative
the physical world is nonlocal, in that spacelike separated systems can occupy entangled states that persist as the systems separate
As pointed out by Barnum, Dahlsten, Leifer, and Toner 2008, in spite of the apparent generality of the Clifton-Bub-Halvorson theorem, C*-algebraic theories in finite dimensions are essentially classical theories or quantum theories with superselection rules.
Barnum et al. considered a framework of generalized probabilistic theories broad enough to include not only quantum and classical mechanics, but also a wide variety of other ‘superquantum’ theories that can serve as foils, and they proved similar results in this framework; specifically, they showed that for any nonclassical ‘no signaling’ theory that does not permit entanglement between systems, there is a bit-commitment protocol that is exponentially secure in the number of systems involved. See Barrett 2007 and Barnum, Barrett, Leifer, and Wilce 2007 and Barnum, Barrett, Leifer, and Wilce 2006 and 2008 (Other Internet Resources).
Other researchers have considered the problem of what constraints in the class of ‘no signaling’ theories would characterize quantum theories. See Brassard 2005, van Dam 2005 (Other Internet Resources), Skrzypczyk, Brunner, and Popescu 2009 (Other Internet Resources),
Pawlowski et al. 2009, Allcock et al. 2009, Navascues and Wunderlich 2009) for interesting results along these lines. For the relation between the generalized probabilistic theory approach of Barnum et al. and the category-theoretic approach of Coecke et al, see Barnum and Wilce 2008a and 2008b (Other Internet Resources).
See Brukner and Zeilinger 2002 for a different information-theoretic approach to quantum mechanics, and Fuchs 2002 (Other Internet Resources) for a radically Bayesian information-theoretic perspective. For an insightful analysis and critique of the Brukner-Zeilinger position, see Timpson 2003.
1. Quantum Entanglement
In 1935 and 1936, Schrödinger published a two-part article in the Proceedings of the Cambridge Philosophical Society in which he discussed and extended a remarkable argument by Einstein, Podolsky, and Rosen. The Einstein-Podolsky-Rosen (EPR) argument was, in many ways, the culmination of Einstein's critique of the orthodox Copenhagen interpretation of quantum mechanics, and was designed to show that the theory is incomplete. (See The Einstein-Podolsky-Rosen Argument in Quantum Theory and Copenhagen Interpretation of Quantum Mechanics.) In classical mechanics the state of a system is essentially a list of the system's properties — more precisely, it is the specification of a set of parameters from which the list of properties can be reconstructed: the positions and momenta of all the particles comprising the system (or similar parameters in the case of fields).
The dynamics of the theory specifies how properties change in terms of a law of evolution for the state. Pauli characterized this mode of description of physical systems as a ‘detached observer’ idealization. See Pauli's letter to Born in The Born-Einstein Letters (Born, 1992; p. 218). On the Copenhagen interpretation, such a description is not possible for quantum systems. Instead, the quantum state of a system should be understood as a catalogue of what an observer has done to the system and what has been observed, and the import of the state then lies in the probabilities that can be inferred (in terms of the theory) for the outcomes of possible future observations on the system. Einstein rejected this view and proposed a series of arguments to show that the quantum state is simply an incomplete characterization of the system. The missing parameters are sometimes referred to as ‘hidden parameters’ or ‘hidden variables’ (although Einstein did not use this terminology, presumably because he did not want to endorse any particular ‘hidden variable’ theory).
It should not be supposed that Einstein's definition of a complete theory included the requirement that it be deterministic. Rather, he required certain conditions of separability and locality for composite systems consisting of separated component systems: each component system separately should be characterized by its own properties (even if these properties manifest themselves stochastically), and it should be impossible to alter the properties of a distant system instantaneously (or the probabilities of these properties) by acting on a local system. In later analyses — notably in Bell's extension of the EPR argument — it became apparent that these conditions, suitably formulated as probability constraints, are equivalent to the requirement that statistical correlations between separated systems should be reducible to probability distributions over common causes (deterministic or stochastic) in the sense of Reichenbach. (See Bell's Theorem and Reichenbach's Common Cause Principle.)
In the original EPR article, two particles are prepared from a source in a certain quantum state and then move apart. There are ‘matching’ correlations between both the positions of the two particles and their momenta: a measurement of either position or momentum on a particular particle will allow the prediction, with certainty, of the outcome of a position measurement or momentum measurement, respectively, on the other particle.
These measurements are mutually exclusive: either a position measurement can be performed, or a momentum measurement, but not both simultaneously. Either correlation can be observed, but the subsequent measurement of momentum, say, after establishing a position correlation, will no longer yield any correlation in the momenta of the two particles. It is as if the position measurement disturbs the correlation between the momentum values.
The puzzle is that the assumption of the completeness of the quantum state of the particle pair is inconsistent with the assignment of labels to the particles separately that could be associated with appropriately correlated values for the outcomes of position and momentum measurements. These labels would be the common causes of the correlations, and would provide an explanation of the correlations in terms of the initial correlations between the properties of the two systems at their source. EPR concluded that the quantum state was incomplete.
Here is how Schrödinger put the puzzle in the first part of his two-part article (Schrödinger, 1935; p. 559):
Yet since I can predict either x1 or p1 without interfering with the system No. 1 and since system No. 1, like a scholar in an examination, cannot possibly know which of the two questions I am going to ask first: it so seems that our scholar is prepared to give the right answer to the first question he is asked, anyhow. Therefore he must know both answers; which is an amazing knowledge; quite irrespective of the fact that after having given his first answer our scholar is invariably so disconcerted or tired out, that all the following answers are ‘wrong.’
What Schrödinger showed was that if two particles are prepared in a quantum state such that there is a matching correlation between two ‘canonically conjugate’ dynamical quantities — quantities like position and momentum whose values suffice to specify all the properties of a classical system — then there are infinitely many dynamical quantities of the two particles for which there exist similar matching correlations: every function of the canonically conjugate pair of the first particle matches with the same function of the canonically conjugate pair of the second particle. Thus (Schrödinger, p. 559) system No. 1 ‘does not only know these two answers but a vast number of others, and that with no mnemotechnical help whatsoever, at least with none that we know of.’
Schrödinger coined the term ‘entanglement’ to describe this peculiar connection between quantum systems (Schrödinger, 1935; p. 555):
When two systems, of which we know the states by their respective representatives, enter into temporary physical interaction due to known forces between them, and when after a time of mutual influence the systems separate again, then they can no longer be described in the same way as before, viz. by endowing each of them with a representative of its own. I would not call that one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought. By the interaction the two representatives [the quantum states] have become entangled.
He added (Schrödinger, 1935; p. 555):
Another way of expressing the peculiar situation is: the best possible knowledge of a whole does not necessarily include the best possible knowledge of all its parts, even though they may be entirely separate and therefore virtually capable of being ‘best possibly known,’ i.e., of possessing, each of them, a representative of its own.
The lack of knowledge is by no means due to the interaction being insufficiently known — at least not in the way that it could possibly be known more completely — it is due to the interaction itself.Attention has recently been called to the obvious but very disconcerting fact that even though we restrict the disentangling measurements to one system, the representative obtained for theother system is by no means independent of the particular choice of observations which we select for that purpose and which by the way are entirely arbitrary. It is rather discomforting that the theory should allow a system to be steered or piloted into one or the other type of state at the experimenter's mercy in spite of his having no access to it.
In the second part of the paper, Schrödinger showed that, in general, a sophisticated experimenter can, by a suitable choice of operations carried out on one system, ‘steer’ the second system into any chosen mixture of quantum states. That is, the second system cannot be steered into any particular quantum state at the whim of the experimenter, but the experimenter can constrain the quantum state into which the second system evolves to lie in any chosen set of states, with a probability distribution fixed by the entangled state.
He found this conclusion sufficiently unsettling to suggest that the entanglement between two separating systems would persist only for distances small enough that the time taken by light to travel from one system to the other could be neglected, compared with the characteristic time periods associated with other changes in the composite system. He speculated that for longer distances each of the two systems might in fact be in a state associated with a certain mixture, determined by the precise form of the entangled state.
Most physicists attributed the puzzling features of entangled quantum states to Einstein's inappropriate ‘detached observer’ view of physical theory, and regarded Bohr's reply to the EPR argument (Bohr, 1935) as vindicating the Copenhagen interpretation. This was unfortunate, because the study of entanglement was ignored for thirty years until John Bell's reconsideration and extension of the EPR argument (Bell, 1964).
Bell looked at entanglement in simpler systems than the EPR case: matching correlations between two-valued dynamical quantities, such as polarization or spin, of two separated systems in an entangled state. What Bell showed was that the statistical correlations between the measurement outcomes of suitably chosen different quantities on the two systems are inconsistent with an inequality derivable from Einstein's separability and locality assumptions — in effect from the assumption that the correlations have a common cause.
Bell's investigation generated an ongoing debate on the foundations of quantum mechanics. One important feature of this debate was confirmation that entanglement can persist over long distances(see Aspect et al.), thus falsifying Schrödinger's supposition of the spontaneous decay of entanglement as two entangled particles separate. But it was not until the 1980s that physicists, computer scientists, and cryptographers began to regard the non-local correlations of entangled quantum states as a new kind of non-classical resource that could be exploited, rather than an embarrassment to be explained away.
For further discussion of entanglement as a physical resource, including measuring entanglement, and the manipulation and purification of entanglement by local operations, see “The Joy of Entanglement” by Popescu and Rohrlich in Lo, Popescu, and Spiller 1998, or Nielsen and Chuang 2000.
2. Exploiting Entanglement: Quantum Teleportation
Consider again Schrödinger's realization that an entangled state could be used to steer a distant particle into one of a set of states, with a certain probability. In fact, this possibility of ‘remote steering’ is even more dramatic than Schrödinger demonstrated. Suppose Alice and Bob share an entangled state of the sort considered by Bell, say two photons in an entangled state of polarization. That is, Alice has in her possession one of the entangled photons, and Bob the other.
Suppose that Alice has an additional photon in an unknown state of polarization |u>, where the notation ‘| >’ denotes a quantum state. It is possible for Alice to perform an operation on the two photons in her possession that will transform Bob's photon into one of four states, depending on the four possible (random) outcomes of Alice's operation: either the state |u>, or a state that is related to |u> in a definite way. Alice's operation entangles the two photons in her possession, and disentangles Bob's photon, steering it into a state |u*>.
After Alice communicates the outcome of her operation to Bob, Bob knows either that |u*> = |u>, or how to transform |u*> to |u> by a local operation. This phenomenon is known as ‘quantum teleportation.’
What is extraordinary about this phenomenon is that Alice and Bob have managed to use their shared entangled state as a quantum communication channel to destroy the state |u> of a photon in Alice's part of the universe and recreate it in Bob's part of the universe. Since the state of a photon requires specifying a direction in space (essentially the value of an angle that can vary continuously), without a shared entangled state Alice would have to convey an infinite amount of classical information to Bob for Bob to be able to reconstruct the state |u> precisely. To see why this is so, consider that the decimal expansion of an angle variable represented by a real number is represented by a potentially infinite sequence of digits between 0 and 9.
The binary expansion is represented by a potentially infinite sequence of 0's and 1's. Ever since Shannon formalized the notion of classical information, the amount of classical information associated with a binary alternative (represented as 0 or 1), where each alternative has equal probability, is measured as one binary digit or ‘bit’. So to specify the value of an arbitrary angle variable requires an infinite number of bits.
To specify the outcome of Alice's operation, which has four possible outcomes with equal probabilities, requires two bits of classical information. Remarkably, Bob can reconstruct the state |u> on the basis of just two bits of classical information communicated by Alice, apparently by exploiting the entangled state as a quantum communication channel to transfer the remaining information. For further discussion of quantum teleportation, see Nielsen and Chuang 2000, or Richard Josza's article “Quantum Information and its Properties” in Lo, Popescu, and Spiller 1998.
3. Quantum Information
Formally, the amount of classical information we gain, on average, when we learn the value of a random variable (or, equivalently, the amount of uncertainty in the value of a random variable before we learn its value) is represented by a quantity called the Shannon entropy, measured in bits (Shannon and Weaver, 1949). A random variable is defined by a probability distribution over a set of values. In the case of a binary random variable, with equal probability for each of the two possibilities, the Shannon entropy is 1 bit, representing maximal uncertainty.
For all other probabilities — intuitively, representing some information about which alternative is more likely — the Shannon entropy is less than 1. For the case of maximal knowledge or zero uncertainty about the alternatives, where the probabilities are 0 and 1, the Shannon entropy is zero. (Note that the term ‘bit’ is used to refer to the basic unit of classical information in terms of Shannon entropy, and to an elementary two-state classical system considered as representing the possible outputs of an elementary classical information source.)
Since information is always embodied in the state of a physical system, we can also think of the Shannon entropy as quantifying the physical resources required to store classical information. Suppose Alice wishes to communicate some classical information to Bob over a classical communication channel such as a telephone line, say an email message.
A relevant question concerns the extent to which the message can be compressed without loss of information, so that Bob can reconstruct the original message accurately from the compressed version. According to Shannon's source coding theorem or noiseless coding theorem (assuming a noiseless telephone line with no loss of information), the minimal physical resource required to represent the message (effectively, a lower bound on the possibility of compression) is given by the Shannon entropy of the source.
What happens if we use the quantum states of physical systems to store information, rather than classical states? It turns out that quantum information is radically different from classical information. The unit of quantum information is the ‘qubit’, representing the amount of quantum information that can be stored in the state of the simplest quantum system, for example, the polarization state of a photon. The term is due to Schumacher (1995), who proved a quantum analogue of Shannon's noiseless coding theorem. (By analogy with the term ‘bit,’ the term ‘qubit’ refers to the basic unit of quantum information in terms of the von Neumann entropy, and to an elementary two-state quantum system considered as representing the possible outputs of an elementary quantum information source.)
As we have seen, an arbitrarily large amount of classical information can be encoded in a qubit. This information can be processed and communicated but, because of the peculiarities of quantum measurement, at most one bit can be accessed! According to a theorem by Holevo, the accessible information in a probability distribution over a set of alternative qubit states is limited by the von Neumann entropy, which is equal to the Shannon entropy only when the states are orthogonal in the space of quantum states, and is otherwise less than the Shannon entropy.
While classical information can be copied or cloned, the quantum ‘no cloning’ theorem (Dieks, 1982; Wootters and Zurek, 1982) asserts the impossibility of cloning an unknown quantum state. To see why, consider how we might construct a classical copying device. A NOT gate is a device that takes a bit as input and produces as output either a 1 if the input is 0, or a 0 if the input is 1. In other words, a NOT gate is a 1-bit gate that flips the input bit.
A controlled-NOT gate, or CNOT gate, takes two bits as inputs, a control bit and a target bit, and flips the target bit if and only if the control bit is 1, while reproducing the control bit. (So there are two inputs, the control and target, and two outputs: the control, and either the target or the flipped target, depending on the value of the control.) A CNOT gate functions as a copying device for the control bit if the target bit is set to 0, because the output of the target bit is then a copy of the control bit (i.e., the input 00 produces output 00, and the input 10 produces output 11).
Insofar as we can think of a measurement as simply a copying operation, a CNOT gate is the paradigm of a classical measuring device. (Imagine Alice equipped with such a device, with input and output control and target wires, measuring the properties of an unknown classical world. The input control wire is a probe for the presence of absence of a property, represented by a 1 or a 0. The target wire functions as the pointer, which is initially set to 0. The output of the target is a 1 or a 0, depending on the presence or absence of the property.)
Suppose we attempt to use our CNOT gate to copy an unknown qubit state. Since we are now proposing to regard the CNOT gate as a device for processing quantum states, the evolution from input states to output states must be effected by a physical quantum transformation. Now quantum transformations are linear on the linear state space of qubits. Linearity of the state space means that for any two qubit states — call them |0> and |1> — that are orthogonal in the space of qubit states, there are qubit states that are represented by linear superpositions or sums of |0> and |1>, with certain coefficients. Such superpositions — e.g., a superposition with coefficients c0, c1 represented symbolically as c0|0> + c1|1> — are non-orthogonal to |0> and to |1>.
Linearity of the transformation means that any transformation must take a qubit state represented by the sum of two orthogonal qubits to a new qubit state that is the sum of the transformed orthogonal qubits. If the CNOT gate succeeds in copying two orthogonal qubits, it cannot succeed in copying a linear superposition of these qubits. Since the gate functions linearly, it must instead produce a state that is a linear superposition of the outputs obtained for the two orthogonal qubits.
That is to say, the output of the gate will be represented by a quantum state that is a sum of two terms, where the first term represents the output of the control and target for the first orthogonal qubit, and the second term represents the output of the control and target for the second orthogonal qubit. This could be expressed as c0|0>|0> + c1|1>|1>. This is an entangled state and not the output that would be required by a successful copying operation, where the control and target each outputs the superposed qubit, expressed as (c0|0> + c1|1>)(c0|0> + c1|1>).
4. Quantum Cryptography
Linearity prevents the possibility of cloning or measuring an unknown quantum state. Similarly, it can be shown that if Alice sends Bob one of two nonorthogonal qubits, Bob can obtain information about which of these qubits was sent only at the expense of disturbing the state. In general, for quantum information there is no information gain without disturbance.
The impossibility of copying an unknown quantum state, or a state that is known to belong to a set of nonorthogonal states with a certain probability, and the existence of a trade-off relation between information gain and state disturbance, is the basis of the application of quantum information to cryptography.
There are quantum protocols involving the exchange of classical and quantum information that Alice and Bob can exploit to share a secret random key, which they can then use to communicate privately. (See Lo's article “Quantum Cryptology” in Lo, Popescu, and Spiller, 1998.) Any attempt by an eavesdropper, Eve, to monitor the communication between Alice and Bob will be detectable, in principle, because Eve cannot gain any quantum information without some disturbance to the quantum communication channel. Moreover, the ‘no cloning’ theorem prohibits Eve from copying the quantum communications and processing them off-line, so to speak, after she monitors the classical communication between Alice and Bob.
While the difference between classical and quantum information can be exploited to achieve successful key distribution, there are other cryptographic protocols that are thwarted by quantum entanglement. Bit commitment is a key cryptographic protocol that can be used as a subroutine in a variety of important cryptographic tasks. In a bit commitment protocol, Alice supplies an encoded bit to Bob.
The information available in the encoding should be insufficient for Bob to ascertain the value of the bit, but sufficient, together with further information supplied by Alice at a subsequent stage when she is supposed to reveal the value of the bit, for Bob to be convinced that the protocol does not allow Alice to cheat by encoding the bit in a way that leaves her free to reveal either 0 or 1 at will.
To illustrate the idea, suppose Alice claims the ability to predict advances or declines in the stock market on a daily basis. To substantiate her claim without revealing valuable information (perhaps to a potential employer, Bob) she suggests the following demonstration: She proposes to record her prediction, before the market opens, by writing a 0 (for ‘decline’) or a 1 (for ‘advance’) on a piece of paper, which she will lock in a safe. The safe will be handed to Bob, but Alice will keep the key. At the end of the day's trading, she will announce the bit she chose and prove that she in fact made the commitment at the earlier time by handing Bob the key.
Of course, the key-and-safe protocol is not provably secure from cheating by Bob, because there is no principle of classical physics that that prevents Bob from opening the safe and closing it again without leaving any trace. The question is whether there exists a quantum analogue of this procedure that is unconditionally secure: provably secure by the laws of physics against cheating by either Alice or Bob. Bob can cheat if he can obtain some information about Alice's commitment before she reveals it (which would give him an advantage in repetitions of the protocol with Alice). Alice can cheat if she can delay actually making a commitment until the final stage when she is required to reveal her commitment, or if she can change her commitment at the final stage with a very low probability of detection.
It turns out that unconditionally secure two-party bit commitment, based solely on the principles of quantum or classical mechanics (without exploiting special relativistic signalling constraints, or principles of general relativity or thermodynamics) is impossible. See Mayers 1997, Lo and Chau 1997 and Lo's article “Quantum Cryptology” in Lo, Popescu, and Spiller 1998 for further discussion. Note that Kent (1999) has shown that one can implement a secure classical bit commitment protocol by exploiting relativistic signalling constraints in a timed sequence of communications between verifiably separated sites for both Alice and Bob.) Roughly, the impossibility arises because at any step in the protocol where either Alice or Bob is required to make a determinate choice (perform a measurement on a particle in the quantum channel, choose randomly and perhaps conditionally between a set of alternative actions to be implemented on the particle in the quantum channel, etc.), the choice can delayed by entangling one or more ‘ancilla’ particles with the channel particle in an appropriate way.
By suitable operations on the ancillas, the channel particle can be ‘steered’ so that this cheating strategy is undetectable. In effect, if Bob can obtain no information about the bit in the safe, then entanglement will allow Alice to ‘steer’ the bit to either 0 or 1 at will.
5. Quantum Computation
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.
6. Interpretative Remarks
Deutsch (1997) has argued that the exponential speed-up in quantum computation, and in general the way a quantum system processes information, can only be properly understood within the framework of Everett's ‘many-worlds’ interpretation (see Everett's Relative-State Formulation of Quantum Mechanics and Many-Worlds Intepretation of Quantum Mechanics). The idea, roughly, is that an entangled state of the sort that arises in the quantum computation of a function, which represents a linear superposition over all possible arguments and corresponding values of the function, should be understood as something like a massively parallel classical computation, for all possible values of a function, in parallel worlds. For an insightful critique of this idea of ‘quantum parallelism’ as explanatory, see Steane 2003.
An alternative view, not much discussed in the literature in this connection, is the quantum logical approach, which emphasizes the non-Boolean structure of properties of quantum systems. (The properties of a classical system form a Boolean algebra, essentially the abstract characterization of a set-theoretic structure.
This is reflected in the Boolean character of classical logic, and the Boolean gates in a classical computer.) From this perspective, the picture is entirely different. Rather than ‘computing all values of a function at once,’ a quantum algorithm achieves an exponential speed-up over a classical algorithm by avoiding the computation of any values of the function at all.
A crucial difference between quantum and classical information is the possibility of selecting an exclusive disjunction, representing a global property of a function, among alternative possible disjunctions — for example, the ‘constant’ disjunction asserting that the value of the function (for both arguments) is either 0 or 1, or the ‘balanced’ disjunction asserting that the value of the function (for both arguments) is either the same as the argument or different from the argument — without determining the truth values of the disjuncts.
Classically, an exclusive disjunction is true if and only if one of the disjuncts is true. This is is redundant information in a quantum computation but essential information classically: an exclusive classical disjunction is true if and only if one of the disjuncts is true. In effect, Deutsch's quantum circuit achieves its speed-up by exploiting the non-Boolean structure of quantum properties to efficiently distinguish between two disjunctive properties, without determining the truth values of the relevant disjuncts (representing the association of individual arguments with corresponding function values).
The point of the procedure is to avoid the evaluation of the function in the determination of the global property, in the sense of producing a value in the range of the function for a value in its domain, and it is this feature — impossible in the Boolean logic of classical computation — that leads to the speed-up relative to classical algorithms. For some recent work by Giuntini and others on logics associated with quantum gates, see under ‘quantum computational logics’ in the Other Internet Resources. (For quantum logic not specifically in relation to quantum computation, see the entry on quantum logic and quantum probability).
Some researchers in quantum information and quantum computation have argued for an information-theoretic interpretation of quantum mechanics. In his review article on quantum computation, Andrew Steane (1998, p. 119) makes the following remark:
Historically, much of fundamental physics has been concerned with discovering the fundamental particles of nature and the equations which describe their motions and interactions. It now appears that a different programme may be equally important: to discover the ways that nature allows, and prevents, information to be expressed and manipulated, rather than particles to move.
Steane concludes his review with the following radical proposal (1998, p. 171):
To conclude with, I would like to propose a more wide-ranging theoretical task: to arrive at a set of principles like energy and momentum conservation, but which apply to information, and from which much of quantum mechanics could be derived. Two tests of such ideas would be whether the EPR-Bell correlations thus became transparent, and whether they rendered obvious the proper use of terms such as ‘measurement’ and ‘knowledge’.
In line with this proposal, Clifton, Bub, and Halvorson 2003 showed that one can derive the basic kinematic features of a quantum description of physical systems from three fundamental information-theoretic constraints:
‘no signaling,’ i.e., no information should be available in the marginal probabilities of measurement outcomes in one region about alternative choices made by an agent in a separated region
the impossibility of perfectly broadcasting the information contained in an unknown physical state (which, for pure states, amounts to ‘no cloning’)
the impossibility of communicating information so as to implement a bit commitment protocol with unconditional security
The analysis is carried out in an algebraic framework (C*-algebras) which allows a mathematically abstract characterization of a physical theory including, as special cases, all classical mechanical theories of both wave and particle varieties, and all variations on quantum theory, including quantum field theories (plus any hybrids of these theories, such as theories with superselection rules).
Within this framework, the three information-theoretic constraints are shown to jointly entail three physical conditions that are taken as definitive of what it means to be a quantum theory in the most general sense, specifically that:
the algebras of observables pertaining to distinct physical systems commute (a condition usually called microcausality or kinematic independence)
any individual system's algebra of observables is noncommutative
the physical world is nonlocal, in that spacelike separated systems can occupy entangled states that persist as the systems separate
As pointed out by Barnum, Dahlsten, Leifer, and Toner 2008, in spite of the apparent generality of the Clifton-Bub-Halvorson theorem, C*-algebraic theories in finite dimensions are essentially classical theories or quantum theories with superselection rules.
Barnum et al. considered a framework of generalized probabilistic theories broad enough to include not only quantum and classical mechanics, but also a wide variety of other ‘superquantum’ theories that can serve as foils, and they proved similar results in this framework; specifically, they showed that for any nonclassical ‘no signaling’ theory that does not permit entanglement between systems, there is a bit-commitment protocol that is exponentially secure in the number of systems involved. See Barrett 2007 and Barnum, Barrett, Leifer, and Wilce 2007 and Barnum, Barrett, Leifer, and Wilce 2006 and 2008 (Other Internet Resources).
Other researchers have considered the problem of what constraints in the class of ‘no signaling’ theories would characterize quantum theories. See Brassard 2005, van Dam 2005 (Other Internet Resources), Skrzypczyk, Brunner, and Popescu 2009 (Other Internet Resources),
Pawlowski et al. 2009, Allcock et al. 2009, Navascues and Wunderlich 2009) for interesting results along these lines. For the relation between the generalized probabilistic theory approach of Barnum et al. and the category-theoretic approach of Coecke et al, see Barnum and Wilce 2008a and 2008b (Other Internet Resources).
See Brukner and Zeilinger 2002 for a different information-theoretic approach to quantum mechanics, and Fuchs 2002 (Other Internet Resources) for a radically Bayesian information-theoretic perspective. For an insightful analysis and critique of the Brukner-Zeilinger position, see Timpson 2003.
I think the things you covered through the post are quiet impressive, good job and great efforts. I found it very interesting and enjoyed reading all of it...keep it up, lovely job..
ResponderExcluirandroid watch