## 1. Quantum Entanglement



In 1935 and 1936, Schrodinger published a two-part article in the
*Proceedings of the Cambridge Philosophical Society* in which
he discussed and extended an 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 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 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. In a letter to Max Born, Wolfgang
Pauli characterized this mode of description of physical systems as a
'detached observer' idealization (see *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 a quantum
system. The missing parameters are sometimes referred to as
'hidden parameters' or 'hidden variables.'



It should not be supposed that Einstein's notion of a complete
theory included the requirement that the theory should 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 (its own 'being-thus,' as Einstein put
it -- 'So-sein' in German), 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 argument for the
nonlocality of quantum correlations, 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 the entries on
 Bell's theorem
 and
 Reichenbach's common cause principle.)



In the original EPR article, two particles are prepared from a source
in a certain 'pure' quantum state of the composite system
(a state that cannot be expressed as a mixture or probability
distribution of other pure quantum states, and cannot be reduced to a
pure quantum state of each particle separately). After the particles
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.
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, and conversely.
Apart from this peculiarity that either correlation can be observed,
but not both for the same pair of quantum particles, the position and
momentum correlations for the quantum particles are exactly like the
classical correlations between two billiard balls after a collision.
Classical correlations can be explained by a common cause, or
correlated 'elements of reality.' The EPR argument is that
quantum mechanics is incomplete because these common causes or
elements of reality are not included in the quantum state
description.



Here is how Schrodinger put the puzzle in the first part of his
two-part article (Schrodinger, 1935; p. 559):



> 
> Yet since I can predict *either* \(x\_1\) or \(p\_1\) 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 Schrodinger showed was that if two particles are prepared in
an EPR quantum state, where there are matching correlations for
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. So
(Schrodinger, 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.'



Schrodinger coined the term 'entanglement' to
describe this peculiar connection between quantum systems
(Schrodinger, 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 (Schrodinger, 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
> the *other* 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, Schrodinger showed that an
experimenter, by a suitable choice of operations carried out on one
member of an entangled pair, possibly using additional
'ancilla' or helper particles, can 'steer' the
second system into a chosen mixture of quantum states, with a
probability distribution that depends on the entangled state. The
second system cannot be steered into a *particular* quantum
state at the whim of the experimenter, but for many copies of the
entangled pair, the experimenter can constrain the quantum state of
the second system to lie in a chosen set of quantum states, where
these states are correlated with the possible outcomes of measurements
carried out on the entangled paired systems, or the paired systems
plus ancillas. 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 the two
systems might in fact be in a correlated mixture of quantum states
determined by 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 of the EPR argument (Bell, 1964). Bell looked at
entanglement in simpler systems than the EPR example: matching
correlations between two-valued dynamical quantities, such as
polarization in a particular direction or spin in a particular
direction, 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.
This inequality is now known as Bell's inequality, and various
related inequalities can be derived as a necessary condition for
classical or common cause correlations.



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,
thus falsifying Schrodinger's supposition of the
spontaneous decay of entanglement as two entangled particles separate.
(Free space entanglement of photons has been demonstrated over a
distance of 143 km and, using satellites to distribute
entanglement, between locations more than 1200 km apart on earth. See
Herbst *et al* 2014 and Yin *et al* 2017.) But it
was not until the 1980s that physicists, computer scientists, and
cryptologists began to regard the non-local correlations of entangled
quantum states as a new kind of non-classical physical resource that
could be exploited, rather than an embarrassment for quantum mechanics
to be explained away. For a discussion of entanglement -- what it
is, why it is conceptually puzzling, and what you can do with it,
including a simple proof of Bell's theorem -- see the
graphic novel *Totally Random: Why Nobody Understands Quantum
Mechanics (A Serious Comic on Entanglement)*, Bub and Bub 2018.
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, Bub 2016, and the classic Nielsen and Chuang 2011.
Alain Aspect, John F. Clauser, and Anton Zeilinger were awared the
2022 Nobel Prize in physics for their pioneering experiments on
entangled photons, validating Bell's insight and initiating the field
of quantum information.


## 2. Exploiting Entanglement: Quantum Teleportation



Consider again Schrodinger'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
Schrodinger demonstrated. Suppose Alice and Bob share an
entangled pure state of the sort considered by Bell, say two photons
in an entangled state of polarization, where Alice has in her
possession one of the entangled photons, and Bob has the second paired
photon. Suppose that Alice receives an additional photon in an unknown
state of polarization \(\ket{u}\), where the notation '\(\ket{\
}\)' 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 \(\ket{u}\), or a state that is related to \(\ket{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 \(\ket{u^\*}\). After Alice communicates the outcome of her
operation 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.' After
the teleportation procedure the state \(\ket{u}\) remains unknown to
both Alice and Bob.



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 \(\ket{u}\) of a photon in Alice's
part of the universe and recreate it in Bob's part of the
universe. Since the linear polarization state of a photon requires
specifying a direction in space (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 \(\ket{u}\) precisely. The amount of
classical 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 arbitrary
angle as a decimal requires an infinite sequence of digits between 0
and 9, or an infinite sequence of 0s and 1s in binary notation. The
outcome of Alice's operation, which has four possible outcomes
with equal probability of 1/4, can be specified by two bits of
classical information. Remarkably, Bob can reconstruct the state
\(\ket{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.
The idea was first proposed by Bennett *et al* in
1993. For further discussion of quantum teleportation, see
Nielsen and Chuang 2011, or Richard Josza's article
"Quantum Information and its Properties" in Lo, Popescu,
and Spiller 1998. Quantum teleportation has been achieved over a
distance of around 100 km on earth, and 1400 km between earth and a
satellite (Zeilinger, 2018). The development of a quantum internet
using satellites to transmit entangled photons will rely on
quantum teleportation.


## 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
one bit, representing maximal uncertainty. For all other probabilities
-- intuitively, representing some information about which
alternative is more likely -- the Shannon entropy is less than
one. 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. 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.) 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: the input 00 produces output 00, and
the input 10 produces output 11 (here the first bit is the control and
the second bit is the target). 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 or 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 a 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. Quantum
transformations are linear on the linear state space of qubits.
Linearity of the *state space* means that any sum or
superposition with coefficients \(c\_0, c\_1\) of two qubit states in
the state space is also a qubit state in the state space. Linearity of
the *transformation* requires that the transformation should
take a qubit state represented by the sum of two qubit states to a new
qubit state that is the sum of the transformed qubit states. If the
CNOT gate succeeds in copying two orthogonal qubit states, represented
as \(\ket{0},\ket{1}\), it cannot succeed in copying a general 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 qubit states. 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 qubit state, and the second term
represents the output of the control and target for the second
orthogonal 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 would
be required by a successful copying operation (where the control and
target 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 secret
message, without revealing any information to Eve, an eavesdropper.
They can do this in a classical world if they share a 'one-time
pad,' a cryptographic key represented by a sequence of random
bits at least as long as the number of bits required to communicate
the message. In fact, this is the only secure way to achieve perfect
security in a classical world. To send a message to Bob, Alice
communicates which bits in the key Bob should flip. The resulting
sequence of bits is the message. In addition, they would need to have
some way of encoding messages as sequences of bits, by representing
letters of the alphabet and spaces and punctuation symbols as binary
numbers, which could be done by some standard, publicly available
scheme.



The problem is that messages communicated in this way are only secret
if Alice and Bob use a different one-time pad for each message. If
they use the same one-time pad for several messages, Eve could gain
some information about the correspondence between letters of the
alphabet and subsequences of bits in the key by relating statistical
features of the messages to the way words are composed of letters. To
share a new key they would have to rely on trusted couriers or some
similar method to distribute the key. There is no way to guarantee the
security of the key distribution procedure in a classical world.



Copying the key without revealing that it has been copied is also a
problem for the shared key that Alice and Bob each store in some
supposedly secure way. But the laws of physics in a classical world
cannot guarantee that a storage procedure is completely secure, and
they cannot guarantee that breaching the security and copying the key
will 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 through
the 'monogamy' of entangled state correlations: no third
party can share entanglement correlations between Alice and Bob.
Moreover, any attempt by Eve to measure the quantum systems in the
entangled state shared by Alice and Bob will destroy the entangled
state. Alice and Bob can detect this by checking a Bell
inequality.



One way to do this is by a protocol originally proposed by Artur
Ekert. Suppose Alice has a collection of photons, one for each
entangled pair in the state \(\ket{0}\ket{0} + \ket{1}\ket{1}\)
(ignoring the equal coefficients, for simplicity), and Bob has the
collection of paired photons. Alice measures the polarization of her
photons randomly in directions, \(0, \pi/8, 2\pi/8\) with respect to
some direction \(z\) they agree on in advance, and Bob measures the
polarizations of his photons randomly in directions \(\pi/8, 2\pi/8,
3\pi/8\). They communicate the directions of their polarization
measurements publicly, but not the outcomes, and they divide the
measurements into two sets: one set when they both measured
polarization in the direction \(\pi/8\), or when they both measured
polarization in the direction \(2\pi/8\), and one set when Alice
measured polarization in directions \(0\) or \(2\pi/8\) and Bob
measured polarization in directions \(\pi/8\) or \(3\pi/8\). For the
first set, when they measured the polarization in the same direction,
the outcomes are random but perfectly correlated in the entangled
state so they share these random bits as a cryptographic key. They use
the second set to check a Bell inequality, which reveals whether or
not the entangled state has been altered by the measurements of an
eavesdropper. (See Ekert, 1991.)



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 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 signaling 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. (Kent 1999 has shown that one can implement a secure
classical bit commitment protocol by exploiting relativistic signaling
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 committed bit, then entanglement will allow Alice to
'steer' the bit to either 0 or 1 at will. 



In 2022 the US National Institute of Standards and Technology (NIST)
announced a suite of encryption protocols designed to be secure
against attacks by a quantum computer:
 NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. 


## 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
Boolean function \(f\), where the arguments or inputs of \(f\) are
either 0 or 1, and the values or outputs of \(f\) are also 0 or 1. The
outputs are either the same for both inputs (in which case \(f\) is
said to be constant), or different for the two inputs (in which case
\(f\) is said to be balanced). Suppose we are interested in
determining whether \(f\) is constant or balanced. 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 in an output
qubit 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 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, and the qubit \(\ket{0}\) as the input to the
target, the output is the entangled state \(\ket{0} \ket{0}\) +
\(\ket{1} \ket{1}\) (ignoring the coefficients, for simplicity). This
is 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 \(\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 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 two planes, representing two
alternative quantum disjunctions, are orthogonal except for an
intersection 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 a
measurement to distinguish the two alternative disjunctive or 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 disjunctive or 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. For more on quantum
computing and quantum algorithms, see Nielsen and Chuang 2011,
Barenco's article "Quantum Computation: An
Introduction" in Lo, Popescu, and Spiller 1998, Bub 2006
(Section 6), Abhijith et al 2022, 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 (see the entry on
 computational complexity theory for
 the concept of an NP-complete problem), so the efficiency of quantum
computers relative to classical computers could 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 \(2^n\)
dimensions, and a general entangled state is a superposition of
\(2^n\) \(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 by the system.


## 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 the
entries 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 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 the
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 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 computing the answer to a disjunctive or global question about a
function (e.g., whether a Boolean function is constant or balanced)
without computing redundant information (e.g., the output values for
different inputs to the function). 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 0 *or* 1, or the
'balanced' disjunction asserting that the value of the
function (for both arguments) is 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. 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 inputs to the function with
corresponding outputs). The point of the procedure is to avoid the
evaluation of the function for specific inputs in the determination of
the global property, and it is this feature -- impossible in the
Boolean logic of classical computation -- that leads to the
speed-up relative to classical algorithms. (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'.
> 



There has been considerable research in the framework of so-called
'generalized probability theories' or
'Boxworld' on the problem of what information-theoretic
constraints in the class of 'no signaling' theories would
characterize 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, Ramanathan *et al* 2010, and
Ringbauer *et al* (2014) for interesting results along
these lines. Chiribella and Spekkens 2016 is a collection of articles
based on a conference at the Perimeter institute of Theoretical
Physics in Waterloo, Canada on new research at the interface of
quantum foundations and quantum information. See Fuchs 2014 and the
entry on
 quantum-Bayesian and pragmatist views of quantum theory 
 for a discussion of QBism, a radically
subjectivist information-theoretic perspective.