Quantum entanglement is damn hard to explain in layman’s terms. Not because entanglement is complicated — it isn’t — but because entanglement is so dangerously close to some concepts we are familiar with in the classical world, like communication and common-cause correlation.

Quantum entanglement is a physical resource, like energy, associatedwith the peculiar nonclassical correlations that are possible betweenseparated quantum systems. Entanglement can be measured, transformed,and purified. A pair of quantum systems in an entangled state can beused as a quantum information channel to perform computational andcryptographic tasks that are impossible for classical systems. Thegeneral study of the information-processing capabilities of quantumsystems is the subject of quantum information theory.

1. Quantum Entanglement

In 1935 and 1936, Schrödinger published a two-part article in theProceedings of the Cambridge Philosophical Society in whichhe discussed and extended an argument by Einstein, Podolsky, andRosen. The Einstein-Podolsky-Rosen (EPR) argument was, in many ways,the culmination of Einstein’s critique of the orthodoxCopenhagen interpretation of quantum mechanics and was designed toshow that the theory is incomplete. (See the entries on the Einstein-Podolsky-Rosen argument in quantum theory and the Copenhagen interpretation of quantum mechanics.) In classical mechanics the state of a system is essentially a list ofthe system’s properties — more precisely, it is thespecification of a set of parameters from which the list of propertiescan be reconstructed: the positions and momenta of all the particlescomprising the system (or similar parameters in the case of fields).The dynamics of the theory specifies how properties change in terms ofa law of evolution for the state. In a letter to Max Born, WolfgangPauli characterized this mode of description of physical systems as a‘detached observer’ idealization (see TheBorn-Einstein Letters, Born, 1992; p. 218). On the Copenhageninterpretation, such a description is not possible for quantumsystems. Instead, the quantum state of a system should be understoodas a catalogue of what an observer has done to the system and what hasbeen observed, and the import of the state then lies in theprobabilities that can be inferred (in terms of the theory) for theoutcomes of possible future observations on the system. Einsteinrejected this view and proposed a series of arguments to show that thequantum state is simply an incomplete characterization of a quantumsystem. The missing parameters are sometimes referred to as‘hidden parameters’ or ‘hidden variables.’

It should not be supposed that Einstein’s notion of a completetheory included the requirement that the theory should bedeterministic. Rather, he required certain conditions of separabilityand locality for composite systems consisting of separated componentsystems: each component system separately should be characterized byits own properties (its own ‘being-thus,’ as Einstein putit — ‘So-sein’ in German), and it should beimpossible to alter the properties of a distant system instantaneously(or the probabilities of these properties) by acting on a localsystem. In later analyses, notably in Bell’s argument for thenonlocality of quantum correlations, it became apparent that theseconditions, suitably formulated as probability constraints, areequivalent to the requirement that statistical correlations betweenseparated systems should be reducible to probability distributionsover common causes (deterministic or stochastic) in the sense ofReichenbach. (See the entries on Bell’s theorem and Reichenbach’s common cause principle.)

In the original EPR article, two particles are prepared from a sourcein a certain ‘pure’ quantum state of the composite system(a state that cannot be expressed as a mixture or probabilitydistribution of other pure quantum states, and cannot be reduced to apure quantum state of each particle separately). After the particlesmove apart, there are ‘matching’ correlations between boththe positions of the two particles and their momenta: a measurement ofeither position or momentum on a particular particle will allow theprediction, with certainty, of the outcome of a position measurementor momentum measurement, respectively, on the other particle. Thesemeasurements are mutually exclusive: either a position measurement canbe performed, or a momentum measurement, but not both simultaneously.The subsequent measurement of momentum, say, after establishing aposition correlation, will no longer yield any correlation in themomenta of the two particles. It is as if the position measurementdisturbs the correlation between the momentum values, and conversely.Apart from this peculiarity that either correlation can be observed,but not both for the same pair of quantum particles, the position andmomentum correlations for the quantum particles are exactly like theclassical correlations between two billiard balls after a collision.Classical correlations can be explained by a common cause, orcorrelated ‘elements of reality.’ The EPR argument is thatquantum mechanics is incomplete because these common causes orelements of reality are not included in the quantum state description.

Here is how Schrödinger put the puzzle in the first part of histwo-part article (Schrödinger, 1935; p. 559):

Yet since I can predict either (x_1) or (p_1) withoutinterfering with the system No. 1 and since system No. 1, like ascholar in an examination, cannot possibly know which of the twoquestions I am going to ask first: it so seems that our scholar isprepared to give the right answer to the first question he isasked, anyhow. Therefore he must know both answers; which isan amazing knowledge; quite irrespective of the fact that after havinggiven his first answer our scholar is invariably so disconcerted ortired out, that all the following answers are ‘wrong.’

What Schrödinger showed was that if two particles are prepared inan EPR quantum state, where there is a matching correlation betweentwo ‘canonically conjugate’ dynamical quantities(quantities like position and momentum whose values suffice to specifyall the properties of a classical system), then there are infinitelymany dynamical quantities of the two particles for which there existsimilar matching correlations: every function of the canonicallyconjugate pair of the first particle matches with the same function ofthe canonically conjugate pair of the second particle. So(Schrödinger, p. 559) system No. 1 ‘does not only knowthese two answers but a vast number of others, and that with nomnemotechnical help whatsoever, at least with none that we knowof.’

Schrödinger coined the term ‘entanglement’ todescribe this peculiar connection between quantum systems(Schrödinger, 1935; p. 555):

When two systems, of which we know the states by their respectiverepresentatives, enter into temporary physical interaction due toknown forces between them, and when after a time of mutual influencethe systems separate again, then they can no longer be described inthe same way as before, viz. by endowing each of them with arepresentative of its own. I would not call that one butrather the characteristic trait of quantum mechanics, the onethat enforces its entire departure from classical lines of thought. Bythe interaction the two representatives [the quantum states] havebecome entangled.

He added (Schrödinger, 1935; p. 555):

Another way of expressing the peculiar situation is: the best possibleknowledge of a whole does not necessarily include the bestpossible knowledge of all its parts, even though they may beentirely separate and therefore virtually capable of being ‘bestpossibly known,’ i.e., of possessing, each of them, arepresentative of its own. The lack of knowledge is by no means due tothe interaction being insufficiently known — at least not in theway that it could possibly be known more completely — it is dueto the interaction itself.

Attention has recently been called to the obvious but verydisconcerting fact that even though we restrict the disentanglingmeasurements to one system, the representative obtained forthe other system is by no means independent of the particularchoice of observations which we select for that purpose and which bythe way are entirely arbitrary. It is rather discomfortingthat the theory should allow a system to be steered or piloted intoone or the other type of state at the experimenter’s mercy inspite of his having no access to it.

In the second part of the paper, Schrödinger showed that anexperimenter, by a suitable choice of operations carried out on onemember of an entangled pair, possibly using additional‘ancilla’ or helper particles, can ‘steer’ thesecond system into a chosen mixture of quantum states, with aprobability distribution that depends on the entangled state. Thesecond system cannot be steered into a particular quantum stateat the whim of the experimenter, but for many copies of the entangledpair, the experimenter can constrain the quantum state of the secondsystem to lie in a chosen set of quantum states, where these statesare correlated with the possible outcomes of measurements carried outon the entangled paired systems, or the paired systems plus ancillas.He found this conclusion sufficiently unsettling to suggest that theentanglement between two separating systems would persist only fordistances small enough that the time taken by light to travel from onesystem to the other could be neglected, compared with thecharacteristic time periods associated with other changes in thecomposite system. He speculated that for longer distances the twosystems might in fact be in a correlated mixture of quantum statesdetermined by the entangled state.

Most physicists attributed the puzzling features of entangled quantumstates to Einstein’s inappropriate ‘detachedobserver’ view of physical theory and regarded Bohr’sreply to the EPR argument (Bohr, 1935) as vindicating the Copenhageninterpretation. This was unfortunate, because the study ofentanglement was ignored for thirty years until John Bell’sreconsideration of the EPR argument (Bell, 1964). Bell looked atentanglement in simpler systems than the EPR example: matchingcorrelations between two-valued dynamical quantities, such aspolarization or spin, of two separated systems in an entangled state.What Bell showed was that the statistical correlations between themeasurement outcomes of suitably chosen different quantitieson the two systems are inconsistent with an inequality derivable fromEinstein’s separability and locality assumptions — ineffect from the assumption that the correlations have a common cause.This inequality is now known as Bell’s inequality, and variousrelated inequalities can be derived as a necessary condition forclassical or common cause correlations.

Bell’s investigation generated an ongoing debate on thefoundations of quantum mechanics. One important feature of this debatewas confirmation that entanglement can persist over long distances,thus falsifying Schrödinger’s supposition of thespontaneous decay of entanglement as two entangled particles separate.(Free space entanglement of photons has been confirmed in experimentsbetween the Canary Islands of La Palma and Tenerife, a distance of 143km. See Herbst et al 2014.) But it was not until the 1980sthat physicists, computer scientists, and cryptologists began toregard the non-local correlations of entangled quantum states as a newkind of non-classical physical resource that could be exploited,rather than an embarrassment for quantum mechanics to be explainedaway. For a discussion of entanglement — what it is, why it isconceptually puzzling, and what you can do with it, including a simpleproof of Bell’s theorem — see the graphic novelTotally Random: Why Nobody Understands Quantum Mechanics (ASerious Comic on Entanglement), Bub and Bub 2018. For furtherdiscussion of entanglement as a physical resource, including measuringentanglement, and the manipulation and purification of entanglement bylocal operations, see “The Joy of Entanglement” by Popescuand Rohrlich in Lo, Popescu, and Spiller 1998, Nielsen and Chuang2000, or Bub 2016.

2. Exploiting Entanglement: Quantum Teleportation

Consider again Schrödinger’s realization that an entangledstate could be used to steer a distant particle into one of a set ofstates, with a certain probability. In fact, this possibility of‘remote steering’ is even more dramatic thanSchrödinger demonstrated. Suppose Alice and Bob share anentangled pure state of the sort considered by Bell, say two photonsin an entangled state of polarization, where Alice has in herpossession one of the entangled photons, and Bob has the second pairedphoton. Suppose that Alice receives an additional photon in an unknownstate of polarization (ket{u}), where the notation ‘(ket{})’ denotes a quantum state. It is possible for Alice toperform an operation on the two photons in her possession that willtransform Bob’s photon into one of four states, depending on thefour possible (random) outcomes of Alice’s operation: either thestate (ket{u}), or a state that is related to (ket{u}) in adefinite way. Alice’s operation entangles the two photons in herpossession, and disentangles Bob’s photon, steering it into astate (ket{u^*}). After Alice communicates the outcome of heroperation to Bob, Bob knows either that (ket{u^*}) = (ket{u}),or how to transform (ket{u^*}) to (ket{u}) by a local operation.This phenomenon is known as ‘quantum teleportation.’ Afterthe teleportation procedure the state (ket{u}) remains unknown toboth Alice and Bob.

What is extraordinary about this phenomenon is that Alice and Bob havemanaged to use their shared entangled state as a quantum communicationchannel to destroy the state (ket{u}) of a photon in Alice’spart of the universe and recreate it in Bob’s part of theuniverse. Since the linear polarization state of a photon requiresspecifying a direction in space (the value of an angle that can varycontinuously), without a shared entangled state Alice would have toconvey an infinite amount of classical information to Bob for Bob tobe able to reconstruct the state (ket{u}) precisely. The amount ofclassical information associated with a binary alternative,represented as 0 or 1, where each alternative has equal probability,is one binary digit or ‘bit.’ To specify an arbitraryangle as a decimal requires an infinite sequence of digits between 0and 9, or an infinite sequence of 0s and 1s in binary notation. Theoutcome of Alice’s operation, which has four possible outcomeswith equal probability of 1/4, can be specified by two bits ofclassical information. Remarkably, Bob can reconstruct the state(ket{u}) on the basis of just two bits of classical informationcommunicated by Alice, apparently by exploiting the entangled state asa quantum communication channel to transfer the remaining information.For further discussion of quantum teleportation, see Nielsen andChuang 2000, or Richard Josza’s article “QuantumInformation and its Properties” in Lo, Popescu, and Spiller1998.

3. Quantum Information

Formally, the amount of classical information we gain, on average,when we learn the value of a random variable (or, equivalently, theamount of uncertainty in the value of a random variable before welearn its value) is represented by a quantity called the Shannonentropy, measured in bits (Shannon and Weaver, 1949). A randomvariable is defined by a probability distribution over a set ofvalues. In the case of a binary random variable, with equalprobability for each of the two possibilities, the Shannon entropy isone bit, representing maximal uncertainty. For all other probabilities— intuitively, representing some information about whichalternative is more likely — the Shannon entropy is less thanone. For the case of maximal knowledge or zero uncertainty about thealternatives, where the probabilities are 0 and 1, the Shannon entropyis zero. (Note that the term ‘bit’ is used to refer to thebasic unit of classical information in terms of Shannon entropy, andto an elementary two-state classical system considered as representingthe possible outputs of an elementary classical informationsource.) Spore galactic adventures cheat mod.

Since information is always embodied in the state of a physicalsystem, we can also think of the Shannon entropy as quantifying thephysical resources required to store classical information. SupposeAlice wishes to communicate some classical information to Bob over aclassical communication channel such as a telephone line. A relevantquestion concerns the extent to which the message can be compressedwithout loss of information, so that Bob can reconstruct the originalmessage accurately from the compressed version. According toShannon’s source coding theorem or noiseless coding theorem(assuming a noiseless telephone line with no loss of information), theminimal physical resource required to represent the message(effectively, a lower bound on the possibility of compression) isgiven by the Shannon entropy of the source.

What happens if we use the quantum states of physical systems to storeinformation, rather than classical states? It turns out that quantuminformation is radically different from classical information. Theunit of quantum information is the ‘qubit’, representingthe amount of quantum information that can be stored in the state ofthe simplest quantum system, for example, the polarization state of aphoton. The term is due to Schumacher (1995), who proved a quantumanalogue of Shannon’s noiseless coding theorem. (By analogy withthe term ‘bit,’ the term ‘qubit’ refers to thebasic unit of quantum information in terms of the von Neumann entropy,and to an elementary two-state quantum system considered asrepresenting the possible outputs of an elementary quantum informationsource.) An arbitrarily large amount of classical information can beencoded in a qubit. This information can be processed and communicatedbut, because of the peculiarities of quantum measurement, at most onebit can be accessed. According to a theorem by Holevo, the accessibleinformation in a probability distribution over a set of alternativequbit states is limited by the von Neumann entropy, which is equal tothe Shannon entropy only when the states are orthogonal in the spaceof 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 copyingdevice. A NOT gate is a device that takes a bit as input and producesas output either a 1 if the input is 0, or a 0 if the input is 1. Inother words, a NOT gate is a 1-bit gate that flips the input bit. Acontrolled-NOT gate, or CNOT gate, takes two bits as inputs, a controlbit and a target bit, and flips the target bit if and only if thecontrol bit is 1, while reproducing the control bit. So there are twoinputs, the control and target, and two outputs: the control, andeither the target or the flipped target, depending on the value of thecontrol. A CNOT gate functions as a copying device for the control bitif the target bit is set to 0, because the output of the target bit isthen a copy of the control bit: the input 00 produces output 00, andthe input 10 produces output 11 (here the first bit is the control andthe second bit is the target). Insofar as we can think of ameasurement as simply a copying operation, a CNOT gate is the paradigmof a classical measuring device. Imagine Alice equipped with such adevice, with input and output control and target wires, measuring theproperties of an unknown classical world. The input control wire is aprobe for the presence of absence of a property, represented by a 1 ora 0. The target wire functions as the pointer, which is initially setto 0. The output of the target is a 1 or a 0, depending on thepresence or absence of the property.

Suppose we attempt to use a CNOT gate to copy an unknown qubit state.Since we are now proposing to regard the CNOT gate as a device forprocessing quantum states, the evolution from input states to outputstates must be effected by a physical quantum transformation. Quantumtransformations are linear on the linear state space of qubits.Linearity of the state space means that any sum orsuperposition with coefficients (c_0, c_1) of two qubit states inthe state space is also a qubit state in the state space. Linearity ofthe transformation requires that the transformation should takea qubit state represented by the sum of two qubit states to a newqubit state that is the sum of the transformed qubit states. If theCNOT gate succeeds in copying two orthogonal qubit states, representedas (ket{0},ket{1}), it cannot succeed in copying a general linearsuperposition of these qubits. Since the gate functions linearly, itmust instead produce a state that is a linear superposition of theoutputs obtained for the two orthogonal qubit states. That is to say,the output of the gate will be represented by a quantum state that isa sum of two terms, where the first term represents the output of thecontrol and target for the first qubit state, and the second termrepresents the output of the control and target for the secondorthogonal qubit state. This could be expressed as (c_0 ket{0}ket{0}) + (c_1 ket{1} ket{1}), which is an entangled state(unless (c_0) or ( c_1) is zero) rather than the output that wouldbe required by a successful copying operation (where the control andtarget each outputs the superposition qubit state (c_0 ket{0}) +(c_1 ket{1})).

4. Quantum Cryptography

Suppose Alice and Bob are separated and want to communicate a secretmessage, without revealing any information to Eve, an eavesdropper.They can do this in a classical world if they share a ‘one-timepad,’ a cryptographic key represented by a sequence of randombits at least as long as the number of bits required to communicatethe message. In fact, this is the only secure way to achieve perfectsecurity in a classical world. To send a message to Bob, Alicecommunicates which bits in the key Bob should flip. The resultingsequence of bits is the message. In addition, they would need to havesome way of encoding messages as sequences of bits, by representingletters of the alphabet and spaces and punctuation symbols as binarynumbers, which could be done by some standard, publicly availablescheme.

The problem is that messages communicated in this way are only secretif Alice and Bob use a different one-time pad for each message. Ifthey use the same one-time pad for several messages, Eve could gainsome information about the correspondence between letters of thealphabet and subsequences of bits in the key by relating statisticalfeatures of the messages to the way words are composed of letters. Toshare a new key they would have to rely on trusted couriers or somesimilar method to distribute the key. There is no way to guarantee thesecurity of the key distribution procedure in a classical world.

Copying the key without revealing that it has been copied is also aproblem for the shared key that Alice and Bob each store in somesupposedly secure way. But the laws of physics in a classical worldcannot guarantee that a storage procedure is completely secure, andthey cannot guarantee that breaching the security and copying the keywill always be detected. So apart from the key distribution problem,there is a key storage problem.

Quantum entanglement provides a way of solving these problems throughthe ‘monogamy’ of entangled state correlations: no thirdparty can share entanglement correlations between Alice and Bob.Moreover, any attempt by Eve to measure the quantum systems in theentangled state shared by Alice and Bob will destroy the entangledstate. Alice and Bob can detect this by checking a Bellinequality.

One way to do this is by a protocol originally proposed by ArturEkert. Suppose Alice has a collection of photons, one for eachentangled pair in the state (ket{0}ket{0} + ket{1}ket{1})(ignoring the equal coefficients, for simplicity), and Bob has thecollection of paired photons. Alice measures the polarization of herphotons randomly in directions, (0, pi/8, 2pi/8) with respect tosome direction (z) they agree on in advance, and Bob measures thepolarizations of his photons randomly in directions (pi/8, 2pi/8,3pi/8). They communicate the directions of their polarizationmeasurements publicly, but not the outcomes, and they divide themeasurements into two sets: one set when they both measuredpolarization in the direction (pi/8), or when they both measuredpolarization in the direction (2pi/8), and one set when Alicemeasured polarization in directions (0) or (2pi/8) and Bobmeasured polarization in directions (pi/8) or (3pi/8). For thefirst set, when they measured the polarization in the same direction,the outcomes are random but perfectly correlated in the entangledstate so they share these random bits as a cryptographic key. They usethe second set to check a Bell inequality, which reveals whether ornot the entangled state has been altered by the measurements of aneavesdropper. (See Ekert, 1991.)

The simpsons games. Well, sort of.

While the difference between classical and quantum information can beexploited to achieve successful key distribution, there are othercryptographic protocols that are thwarted by quantum entanglement. Bitcommitment is a key cryptographic protocol that can be used as asubroutine in a variety of important cryptographic tasks. In a bitcommitment protocol, Alice supplies an encoded bit to Bob. Theinformation available in the encoding should be insufficient for Bobto ascertain the value of the bit, but sufficient, together withfurther information (supplied by Alice at a subsequent stage when sheis supposed to reveal the value of the bit), for Bob to be convincedthat the protocol does not allow Alice to cheat by encoding the bit ina way that leaves her free to reveal either 0 or 1 at will.

To illustrate the idea, suppose Alice claims the ability to predictadvances or declines in the stock market on a daily basis. Tosubstantiate her claim without revealing valuable information (perhapsto a potential employer, Bob) she suggests the followingdemonstration: She proposes to record her prediction, before themarket opens, by writing a 0 (for ‘decline’) or a 1 (for‘advance’) on a piece of paper, which she will lock in asafe. The safe will be handed to Bob, but Alice will keep the key. Atthe end of the day’s trading, she will announce the bit shechose and prove that she in fact made the commitment at the earliertime by handing Bob the key. Of course, the key-and-safe protocol isnot provably secure from cheating by Bob, because there is noprinciple of classical physics that that prevents Bob from opening thesafe and closing it again without leaving any trace. The question iswhether there exists a quantum analogue of this procedure that isunconditionally secure: provably secure by the laws of physics againstcheating by either Alice or Bob. Bob can cheat if he can obtainsome information about Alice’s commitment before shereveals it (which would give him an advantage in repetitions of theprotocol with Alice). Alice can cheat if she can delay actually makinga commitment until the final stage when she is required to reveal hercommitment, or if she can change her commitment at the final stagewith 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 signaling constraints, orprinciples of general relativity or thermodynamics) is impossible. SeeMayers 1997, Lo and Chau 1997 and Lo’s article “QuantumCryptology” in Lo, Popescu, and Spiller 1998 for furtherdiscussion. (Kent 1999 has shown that one can implement a secureclassical bit commitment protocol by exploiting relativistic signalingconstraints in a timed sequence of communications between verifiablyseparated sites for both Alice and Bob.) Roughly, the impossibilityarises because at any step in the protocol where either Alice or Bobis required to make a determinate choice (perform a measurement on aparticle in the quantum channel, choose randomly and perhapsconditionally between a set of alternative actions to be implementedon the particle in the quantum channel, etc.), the choice can delayedby entangling one or more ancilla particles with the channel particlein an appropriate way. By suitable operations on the ancillas, thechannel particle can be ‘steered’ so that this cheatingstrategy is undetectable. In effect, if Bob can obtain no informationabout the committed bit, 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 thisinformation is limited by the Holevo bound (mentioned in Section 3).David Deutsch (1985) first showed how to exploit quantum entanglementto perform a computational task that is impossible for a classicalcomputer. Suppose we have a black box or oracle that evaluates aBoolean function (f), where the arguments or inputs of (f) areeither 0 or 1, and the values or outputs of (f) are also 0 or 1. Theoutputs are either the same for both inputs (in which case (f) issaid to be constant), or different for the two inputs (in which case(f) is said to be balanced). Suppose we are interested indetermining whether (f) is constant or balanced. Classically, theonly 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 tostore and process information, then we can determine whether (f) isconstant or balanced in one evaluation of the function (f). Thetrick is to design the circuit (the sequence of gates) to produce theanswer to a global question about the function in an outputqubit register that can then be read out or measured.

Consider again the quantum CNOT gate, with two orthogonal qubits(ket{0}) and (ket{1}) as possible inputs for the control, and(ket{0}) as the input for the target. One can think of the inputcontrol and output target qubits, respectively, as the argument andassociated value of a function. This CNOT function associates thevalue 0 with the argument 0 and the value 1 with the argument 1. For alinear superposition of the orthogonal qubits with equal coefficientsas input to the control, and the qubit (ket{0}) as the input to thetarget, the output is the entangled state (ket{0} ket{0}) +(ket{1} ket{1}) (ignoring the coefficients, for simplicity). Thisis a linear superposition in which the first term represents theargument 0 and associated value 0 of the CNOT function, and the secondterm represents the argument 1 and associated value 1 of the CNOTfunction. The entangled state represents all possible arguments andcorresponding values of the function as a linear superposition, butthis information is not accessible. What can be shown to beaccessible, by a suitable choice of quantum gates, is informationabout whether or not the function has certain global properties. Thisinformation is obtainable without reading out the evaluation of anyindividual arguments and values. (Indeed, accessing information in theentangled state about a global property of the function will typicallyrequire losing access to all information about individual argumentsand values.)

The situation is analogous for Deutsch’s function (f). Herethe output of (f) can be represented as either (ket{0} ket{0} +ket{1} ket{0}) or (ket{0} ket{1} + ket{1} ket{1}) in the‘constant’ case, or (ket{0} ket{0} + ket{1} ket{1})or (ket{0} ket{1} + ket{1} ket{0}) in the ‘balanced’case. The two entangled states in the ‘constant’ case areorthogonal in the 4-dimensional two-qubit state space and span aplane. Call this the ‘constant’ plane. Similarly, the twoentangled states in the ‘balanced’ case span a plane, the‘balanced’ plane. These two planes, representing twoalternative quantum disjunctions, are orthogonal except for anintersection or overlap in a line, representing a product(non-entangled) state, where each qubit separately is in the state(ket{0} + ket{1}). It is therefore possible to design ameasurement to distinguish the two alternative disjunctive or globalproperties of (f), ‘constant’ or ‘balanced,’with a certain probability (actually, 1/2) of failure, when themeasurement yields an outcome corresponding to the overlap state,which is common to the two cases. Nevertheless, only one query of thefunction is required when the measurement succeeds in identifying theglobal property. With a judicious choice of quantum gates, it is evenpossible to design a quantum circuit that always succeeds indistinguishing the two cases in one run.

Deutsch’s example shows how quantum information and quantumentanglement can be exploited to compute a disjunctive or globalproperty of a function in one step that would take two stepsclassically. While Deutsch’s problem is rather trivial, therenow exist several quantum algorithms with interesting applications,notably Shor’s factorization algorithm for factoring largecomposite integers in polynomial time (with direct application to‘public key’ cryptography, a widely used classicalcryptographic scheme) and Grover’s database search algorithm.Shor’s algorithm achieves an exponential speed-up over anyknown classical algorithm. For algorithms that are allowed accessto oracles (whose internal structure is not considered), the speed-upcan be shown to be exponential over any classical algorithmin some cases, e.g., Simon’s algorithm. See Nielsen and Chuang2000, Barenco’s article “Quantum Computation: AnIntroduction” 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 cansolve an NP-complete problem in polynomial time, so the efficiency ofquantum computers relative to classical computers could turn out to beillusory. If there is indeed a speed-up, it would seem to be due tothe phenomenon of entanglement. The amount of information required todescribe a general entangled state of (n) qubits grows exponentiallywith (n). The state space (Hilbert space) has (2^n) dimensions,and a general entangled state is a superposition of (2^n)(n)-qubit states. In classical mechanics there are no entangledstates: a general (n)-bit composite system can be described withjust (n) times the amount of information required to describe asingle bit system. So the classical simulation of a quantum processwould involve an exponential increase in the classical informationalresource required to represent the quantum state, as the number ofqubits that become entangled in the evolution grows linearly, andthere would be a corresponding exponential slowdown in calculating theevolution, compared to the actual quantum computation performed by thesystem.

6. Interpretative Remarks

Deutsch (1997) has argued that the exponential speed-up in quantumcomputation, and in general the way a quantum system processesinformation, can only be properly understood within the framework ofEverett’s ‘many-worlds’ interpretation (see theentries on Everett’s relative-state formulation of quantum mechanics and the many-worlds interpretation of quantum mechanics). The idea, roughly, is that an entangled state of the sort that arisesin the quantum computation of a function, which represents a linearsuperposition over all possible arguments and corresponding values ofthe function, should be understood as something like a massivelyparallel 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 emphasizes the non-Boolean structure of propertiesof quantum systems. The properties of a classical system form aBoolean algebra, essentially the abstract characterization of aset-theoretic structure. This is reflected in the Boolean character ofclassical logic, and the Boolean gates in a classical computer. Fromthis perspective, the picture is entirely different. Rather than‘computing all values of a function at once,’ a quantumalgorithm achieves an exponential speed-up over a classical algorithmby computing the answer to a disjunctive or global question about afunction (e.g., whether a Boolean function is constant or balanced)without computing redundant information (e.g., the output values fordifferent inputs to the function). A crucial difference betweenquantum and classical information is the possibility of selecting anexclusive disjunction, representing a global property of a function,among alternative possible disjunctions — for example, the‘constant’ disjunction asserting that the value of thefunction (for both arguments) is 0 or 1, or the‘balanced’ disjunction asserting that the value of thefunction (for both arguments) is the same as the argument ordifferent from the argument — without determining the truthvalues of the disjuncts.

Classically, an exclusive disjunction is true if and only if one ofthe disjuncts is true. Deutsch’s quantum circuit achieves itsspeed-up by exploiting the non-Boolean structure of quantum propertiesto efficiently distinguish between two disjunctive properties, withoutdetermining the truth values of the relevant disjuncts (representingthe association of individual inputs to the function withcorresponding outputs). The point of the procedure is to avoid theevaluation of the function for specific inputs in the determination ofthe global property, and it is this feature — impossible in theBoolean logic of classical computation — that leads to thespeed-up relative to classical algorithms. (For quantum logic notspecifically in relation to quantum computation, see the entry on quantum logic and quantum probability).

Some researchers in quantum information and quantum computation haveargued for an information-theoretic interpretation of quantummechanics. In his review article on quantum computation, Andrew Steane(1998, p. 119) makes the following remark:

Historically, much of fundamental physics has been concerned withdiscovering the fundamental particles of nature and the equationswhich describe their motions and interactions. It now appears that adifferent programme may be equally important: to discover the waysthat nature allows, and prevents, information to be expressedand 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-rangingtheoretical task: to arrive at a set of principles like energy andmomentum conservation, but which apply to information, and from whichmuch of quantum mechanics could be derived. Two tests of such ideaswould be whether the EPR-Bell correlations thus became transparent,and whether they rendered obvious the proper use of terms such as‘measurement’ and ‘knowledge’.

There has been considerable research in the framework of so-called‘generalized probability theories’ or‘Boxworld’ on the problem of what information-theoreticconstraints in the class of ‘no signaling’ theories wouldcharacterize quantum theories. See Brassard 2005, van Dam 2005,Skrzypczyk, Brunner, and Popescu 2009, Pawlowski et al. 2009,Allcock et al. 2009, Navascues and Wunderlich 2009),Al–Safi and Short 2013, and Ramanathan et al. forinteresting results along these lines. Chiribella and Spekkens 2016 isa collection of articles based on a conference at the Perimeterinstitute of Theoretical Physics in Waterloo, Canada on new researchat the interface of quantum foundations and quantum information. SeeFuchs 2014 for a discussion of QBism, a radically subjectiveinformation-theoretic perspective.

Bibliography

• Al-Safi, S.W., Short, A.J., 2014. “Reversible Dynamics inStrongly Non-Local Boxworld Systems,” Journal of Physics A:Mathematical and Theoretical 47: 325303.
• Alcock, J., Brunner, N., Pawlowski, M., Scarani, V., 2009.“Recovering Part of the Quantum Boundary from InformationCausality,” Physical Review A, 80: 040103 [available online].
• Aspect, A., Grangier, P., Roger, G., 1982. “ExperimentalTests of Bell’s Inequalities Using Time-VaryingAnalyzers,” Physical Review Letters, 49:1804–1807.
• Barrett, J., 2007. “Information Processing in GeneralizedProbabilistic Theories,” Physical Review A, 75:032304.
• Barrett, J., Hardy, L., Kent, A., 2005. “No signaling andQuantum Key Distribution,” Physical Review Letters, 95:010503.
• Bell, J.S., 1964. “On the Einstein-Podolsky-RosenParadox” Physics, 1: 195–200.
• Bennett, C.H., DiVincenzo, B.D., 2000. “Quantum Informationand Computation,” Nature, 404: 247–255.
• Bohr, N., 1935. “Can Quantum-Mechanical Description ofPhysical Reality be Considered Complete?,” PhysicalReview, 38: 696–702.
• Born, M. (ed.), 1992. The Born-Einstein Letters,Dordrecht: Reidel.
• Brassard, G., 2005. “Is Information the Key?,”Nature Physics, 1: 2–4.
• Bub, J., 2006. “Quantum Information and Computation,”in John Earman and Jeremy Butterfield (eds.), Philosophy ofPhysics (Handbook of Philosophy of Science), Amsterdam: NorthHolland, pp. 555–660 [available online].
• –––, 2007. “Quantum Computation from a Quantum LogicalPerspective,” Quantum Information and Computation, 7:281–296.
• –––, 2008. “Quantum Computation and PseudotelepathicGames,” Philosophy of Science, 75: 458–472.
• –––, 2016. Bananaworld: Quantum Mechanics forPrimates, Oxford: Oxford University Press.
• Bub, T. and Bub, J., 2018. Totally Random: Why NobodyUnderstands Quantum Mechanics (A Serious Comic on Entanglement),Princeton: Princeton University Press.
• Chiribella, G. and Spekkens, R., 2016. Quantum Theory:Informational Foundations and Foils, New York, Springer.
• Deutsch, D., 1985. “Quantum Theory, the Church-TuringPrinciple and the Universal Quantum Computer,” Proceedingsof the Royal Society (London), A400: 97–117.
• –––, 1997. The Fabric of Reality, London:Penguin.
• Dieks, D., 1982. “Communication by EPR Devices,”Physics Letters A, 92: 271–272.
• Einstein, A., Podolsky, B., Rosen, N., 1935. “CanQuantum-Mechanical Description of Physical Reality be ConsideredComplete?,” Physical Review, 47: 777–780.
• Ekert, A., 1991. “Quantum Cryptography Based on Bell’sTheorem” Physical Review Letters, 67:661–663.
• Ekert, A. and Renner, R., 2014. “The Ultimate PhysicalLimits of Privacy,” Nature, 507: 443–447.
• Everett, H., 1957. “‘Relative State’ Formulationof Quantum Mechanics,” Reviews of Modern Physics, 29:454–462.
• Feynman, R., 1996. Feynman Lectures on Computation, J.G.Hey and R.W. Allen (eds.), Reading, MA: Addison-Wesley PublishingCompany.
• Fuchs, C.A., 2014. “An Introduction to QBism with anApplication to the Locality of Quantum Mechanics,” AmericanJournal of Physics, 82: 749–754.
• Herbst, T., Scheidl, T., Fink, M., Handsteiner, J., Wittmann, B.,Ursin, R., Zeilinger, A., 2015. “Teleportation of Entanglementover 143 km,” Proceedings of the National Academy ofSciences of the United States of America 112: 14202 –5 [available online].
• Holevo, A.S., 1973. “Statistical Problems in QuantumPhysics,” in G. Murayama and J.V. Prokhorov (eds.)Proceedings of the Second Japan-USSR Symposium on ProbabilityTheory, Berlin: Springer, pp. 104–109.
• Kent, A., 1999. “Unconditionally Secure BitCommitment,” Physical Review Letters, 83:1447–1450.
• –––, 2012. “Unconditionally Secure Bit Commitment byTransmitting Measurement Outcomes,” Physical ReviewLetters, 109: 130501.
• Lo, H.-K., Chau, H.F., 1997. “Is Quantum Bit CommitmentReally Possible?,” Physical Review Letters, 78:3410–3413.
• Lo, H.-K., Popescu, S., Spiller, T., 1998. Introduction toQuantum Computation and Information, Singapore: WorldScientific.
• Mayers, D., 1997. “Unconditionally Secure Quantum BitCommitment is Impossible,” Physical Review Letters, 78:3414–3417.
• Navascues, M. and Wunderlich, H., 2009. “A Glance Beyond theQuantum Model,” Proceedings of the Royal Society A,466: 881–890 [available online].
• Nielsen, M.A., Chuang, I.L., 2000. Quantum Computation andQuantum Information, Cambridge: Cambridge University Press.
• Pawlowski, M., Patarek, T., Kaszlikowski, D., Scarani, V., Winter,A.,and Zukowski, M., 2009. “A New Physical Principle:Informaiton Causality,” Nature, 461: 1101.
• Ramanathan, R., Patarek, T., Kay, A., Kurzynski, P., Kaszkilowski,D., 2010. “Local Realism of Macroscopic Correlations,”Physical Review Letters, 107: 060405.
• Schrödinger, E., 1935. “Discussion of ProbabilityRelations Between Separated Systems,” Proceedings of theCambridge Philosophical Society, 31: 555–563; 32 (1936):446–451.
• Schumacher, B., 1995. “Quantum Coding,” PhysicalReview A, 51: 2738–2747.
• Shannon, C.E., Weaver, W., 1949. The Mathematical Theory ofCommunication, Urbana: University of Illinois Press.
• Skrzypczyk, P., Brunner, N. and Popescu, S., 2009,“Emergence of Quantum Correlations from NonlocalitySwapping,” Physical Review Letters, 102: 110402.
• Steane, A.M., 1998. “Quantum Computing,” Reportson Progress in Physics, 61: 117–173.
• –––, 2003. “A Quantum Computer Needs Only OneUniverse” Studies in History and Philosophy of ModernPhysics, 34B: 469–478 [available online].
• Timpson, C.G., 2013. Quantum Information Theory and theFoundations of Quantum Mechanics, Oxford, Oxford UniversityPress.
• van Dam, W., 2013. “Implausible consequences of superstrongnonlocality,” Natural Computing, 12(1):9–12.
• van Fraassen, B., 1982. “The Charybdis of Realism:Epistemological Implications of Bell’s Inequality,”Synthese, 52: 25–38.
• Wootters, W.K., Zurek, W.H., 1982. “A Single Quantum Cannotbe Cloned,” Nature, 299: 802–803.

Academic Tools

How to cite this entry.

Preview the PDF version of this entry at the Friends of the SEP Society.

Look up this entry topic at the Internet Philosophy Ontology Project (InPhO).

Enhanced bibliography for this entryat PhilPapers, with links to its database.

Other Internet Resources

• arXiv E-print Archive for Quantum Physics.
• Todd Brun’s Lecture Notes on Quantum Information Processing.
• John Preskill’s Course on Quantum Information and Computation.
• Oxford Quantum, Oxford University.
• Institute for Quantum Optics and Quantum Information, Austrian Academy of Sciences.
• GAP-Optique, University of Geneva.
• Centre for Quantum Technologies, University of Singapore.
• Joint Quantum Institute, University of Maryland.
• The Dream Machine, New Yorker article on quantum computing, 2011.
• New Quantum Theory Could Explain the Flow of Time, article in Wired, 2014, reprinted from QuantaMagazine.
• Spooky Actions at a Distance?, David Mermin’s Oppenheimer Lecture.

Related Entries

Bell’s Theorem quantum mechanics: Copenhagen interpretation of quantum mechanics: Everett’s relative-state formulation of quantum mechanics: many-worlds interpretation of quantum theory: quantum computing quantum theory: quantum logic and probability theory quantum theory: the Einstein-Podolsky-Rosen argument in Reichenbach, Hans: common cause principle

When talking about love and romance, people often bring up unseen and mystical connections.Such connections exist in the subatomic world as well, thanks to a bizarre and counterintuitive phenomenon called.The basic idea of quantum entanglement is that two particles can be intimately linked to each other even if separated by billions of light-years of space; a change induced in one will affect the other. In 1964, physicist John Bell posited that such changes can occur instantaneously, even if the particles are very far apart. Bell's Theorem is regarded as an important idea in modern physics, but it seems to make little sense. After all, had proven years before that information cannot travel faster than the speed of light.Indeed, Einstein famously described the entanglement phenomenon as 'spooky action at a distance.'

This cartoon helps explain the idea of entangled particles. Alice and Bob represent photon detectors, which NASA's Jet Propulsion Laboratory and the National Institute of Standards and Technology developed. (Image credit: NASA/JPL-Caltech)In the last half-century, many researchers have run experiments that aimed to test Bell's Theorem.