QUANTUM COMPUTING AND TELEPORTATION

In the 1980s and 1990s a series of revolutionary developments in the foundations of quantum mechanics led to what would later become the thriving fields of quantum information, quantum computation, and quantum cryptography. The roots of this revolution lie in the debate between Albert Einstein and Niels Bohr on the interpretation of quantum mechanics, specifically in the notion of "entangled" quantum states at the heart of the Einstein-Podolsky-Rosen argument for the incompleteness of quantum mechanics. What Einstein, Podolsky, and Rosen showed in their 1935 paper "Can Quantum-Mechanical Description of Physical Reality be Considered Complete?" was that composite quantum systems, consisting of spatially separated subsystems, could exist in certain states with peculiar nonclassical correlations between the outcomes of measurements on the subsystems. They argued that these correlations are incompatible with the assumption that the quantum state is a complete description of the system.

In a two-part commentary on the paper, Schrödinger referred to these states as being "entangled." Roughly thirty years later John Bell re-examined the Einstein-Podolsky-Rosen argument and showed that quantum mechanics could not be completed in the way Einstein would have liked, because the correlations of entangled states violate an inequality that an Einsteinian completion of quantum mechanics would have to satisfy. Essentially Bell showed that the correlations are inconsistent with any explanation in terms of a common cause (whether deterministic or stochastic) originating in the preparation of the state.

The salient feature of quantum information-processing tasks is the exploitation of entanglement as a new physical resource. Entanglement can be used to teleport quantum states, to exponentially outperform classical computers, and to implement cryptographic procedures that are impossible classically.

Teleportation as Remote "Steering"

Schroödinger regarded entangled states as problematic because they allow the possibility of what he called remote "steering," which he regarded as unacceptable in a physical theory. As it turns out the teleportation of quantum states is an experimentally confirmed application of remote "steering" between two separated systems.

Consider Alice and Bob, the traditional protagonists in any two-party communication protocol. Suppose Alice and Bob each holds one of a pair of quantum particles associated with binary-valued physical quantities or "observables." An example would be a pair of spin-½ particles, with two possible values, + and −, for the spin in some direction, say the z -direction. Alice's particle might be represented by the pure quantum state |+〉_A and Bob's particle by the pure quantum state |−〉_B. A spin state is represented as a unit vector in a 2-dimensional vector space, a so-called Hilbert space, the representation space for quantum states. The state of the composite two-particle system is a product state:
|+〉_A |−〉_B
represented by a vector in the 4-dimensional product Hilbert space for the two particles. An entangled pure state is a linear sum or "superposition" of product states that cannot itself be expressed as a product state. (More generally, for mixed states, representing mixtures or probability distributions of pure states, an entangled state is a state that cannot be represented as a convex combination or probability distribution of product states.)

Suppose Alice and Bob each holds one of a pair of particles in the entangled state:

The coefficients (here ±1/√2) can be complex numbers in general, and the squares of the absolute values of the coefficients (which are required to sum to 1: here ½ in both cases) represent the probabilities of obtaining the corresponding values of the relevant observables on measurement (+ and −, or − and +, for A and B ). It turns out that Bob's state, which defines the statistics for measurement outcomes on his particle, can be represented as an equal weight mixture of the orthogonal states |+〉_B, |−〉_B, but equivalently as an infinity of other mixtures including, to take a specific example, the equal weight mixture of the four nonorthogonal states, represented as superpositions with complex coefficients ±α, ±β in the 2-dimensional Hilbert space of Bob's particle:
|ϕ ₁〉_B = α |+〉_B + β |−〉_B
|ϕ ₂〉_B = α |+〉_B − β |−〉_B
|ϕ ₃〉_B = β |+〉_B + α |−〉_B
|ϕ ₄〉_B = β |+〉_B − α |−〉_B

If Alice measures the spin observable with outcomes associated with the two possible states |+〉_A, |−〉_A on her particle A, and Bob measures the corresponding spin observable on his particle B, Alice's outcomes will be oppositely correlated with Bob's outcomes (+ with −, and − with +). If instead Alice prepares a spin-½ particle A′ in the state |ϕ 〉₁〉_A′ = α |+〉_A′ + β |−〉_A′ and measures an observable on the pair of systems A +A′ in her possession with possible outcomes corresponding to the four orthogonal states:

(the so-called Bell states), she will obtain the outcomes 1, 2, 3, 4 with equal probability, and these outcomes will be correlated with Bob's states |ϕ ₁〉_B, |ϕ ₂〉_B, |ϕ ₃〉_B, |ϕ ₄〉_B (i.e., if Bob checks to see whether his particle is in the state |ϕ_i 〉 _B when Alice reports that she obtained the outcome i =1, 2, 3, 4, he will find that this is always in fact the case). This follows because:
|ϕ ₁〉_A′ |ψ 〉 = ½(−|1〉|ϕ ₁〉_B − |2〉|ϕ ₂〉_B + |3〉|ϕ ₃〉_B + |4〉|ϕ ₄〉_B )
In this sense, Alice can "steer" Bob's particle into any equivalent mixture generating the same statistics by an appropriate local measurement.

Now, remote "steering" in this probabilistic sense is precisely what makes quantum teleportation possible. Suppose Alice and Bob share a pair of spin-½ particles A and B in the entangled state and Alice is given a spin-½ particle A′ in an unknown state |ϕ ₁〉. There is no procedure by which Alice can determine the unknown state, but if Alice measures the composite system A +A′ in the Bell basis, she will "steer" Bob's particle into one of the states |ϕ ₁〉_B, |ϕ ₂〉_B, |ϕ ₃〉_B, |ϕ,₄〉_B with equal probability. If Alice tells Bob the outcome of her measurement, Bob can apply a local operation corresponding to a transformation in the Hilbert space of his particle to obtain the state |ϕ ₁〉_B.

Note that before Alice sends Bob the outcome of her measurement, the quantum state that Bob assigns to his particle—the information represented by the mixed state—is unchanged by Alice's measurement operation, even though after Alice's measurement the probability is ¼ that the state of Bob's particle is in fact |ϕ ₁〉 (in this case the local operation to obtain the state is represented by the identity). The trick that results in the transference of the state |ϕ ₁〉 from Alice to Bob, without the particle A′ traveling from Alice to Bob, is the ability afforded Alice by the shared entangled state to correlate one of four measurement outcomes (each occurring with probability ¼) with one of four states that together represent a particular decomposition of Bob's mixed state. The transference of the state of A′ to Bob's particle is accomplished by Bob's operation, which requires that Alice sends the information about her measurement outcome to Bob. In the teleportation protocol the state of the particle A′ is destroyed by Alice's measurement and recreated as the state of Bob's particle by Bob's operation—in fact, the systems A and A′ end up in an entangled state as the result of Alice's measurement. (Note that if the state |ϕ ₁〉 of A′ were not destroyed there would be two copies of the state, which would violate the quantum "no cloning" theorem.)

Computation via Entanglement

The field of quantum computation was launched in the 1980s with two seminal papers by David Deutsch in 1985 and Richard Feynman in 1982. The basic idea can be illustrated by the first genuinely quantum algorithm, proposed by Deutsch, later improved by Duetsch and Jozsa in 1992.

Consider a function ƒ that maps an input value x =0 or x =1 onto an output value that is either 0 or 1. The algorithm for computing ƒ might be quite complicated. To take Mermin's example, ƒ(x ) might represent the value of the millionth bit in the binary expansion of √(2+x ), so that ƒ(0) is the millionth bit in the expansion of √2 while ƒ(1) is the millionth bit in the expansion of √3. Suppose we are interested in whether the function ƒ(x ) is constant for both values of x or takes different values for both values of x —whether the millionth bit of √2 is the same as the millionth bit of √3, or not. With a classical computer we would have to run through the algorithm twice to evaluate ƒ(0) and ƒ(1) and then compare these values. With a quantum computer it is possible to answer the question in a single run of the algorithm.

We might represent the computation of ƒ by a classical computer as follows:
〈0 〉〈0 〉 → 〈0 〉〈ƒ(0) 〉
〈1 〉〈0 〉 → 〈1 〉〈ƒ(1) 〉
where 〈x 〉〈ƒ(x ) 〉 represents the input and output registers for the computation, and → represents the mapping defined by the algorithm.

In the case of a quantum computer the input and output registers are quantum states, specifically here "qubits," or states represented as orthogonal vectors in a 2-dimensional Hilbert space:
|0〉|0〉 → |0〉|ƒ(0)〉
|1〉|0〉 → |1〉|ƒ(1)〉
Here → represents the quantum mechanical implementation of the algorithm by quantum transformations of the input state. We could put the input register into a superposition of quantum states 1/√2(|O〉 + 1〉), in which case, since the quantum transformations are linear maps, the quantum implementation of the algorithm yields:

This state is a linear superposition of both possible inputs and the associated outputs of ƒ, apparently representing the computation for all possible values. Unfortunately however only a single read-out is possible: if we make a measurement on both registers, we obtain just one of the possible results with probability ½, and the original state, in which all possible inputs and associated outputs are represented, is altered. So there is no advantage over a classical computer.

Now we are interested in a global property of ƒ, whether ƒ is constant or balanced. Remarkably it turns out that we can answer this question in just one run of the algorithm, but at the expense of foregoing any information about the value of the function for either input. The final state is a product state (of the two registers) if ƒ(0) =ƒ(1) and an entangled state if ƒ(0) ≠ƒ(1). By appropriate quantum transformations (see the discussion in Mermin's Lecture Notes on Quantum Computation ) this state can be transformed to:

if ƒ(0) =ƒ(1), and to:

if ƒ0) ≠ƒ(1), where 0̄ = 1 and 1̄ = 0. The outcome of a measurement on the input register, + or −, will distinguish whether ƒ(0) = ƒ(1) or ƒ(0) ≠ ƒ(1).

Note that a measurement of the output register will yield the value ƒ(0) or f(0)̄ with probability ½, that is, 0 or 1 with probability ½, which provides no information about the value of ƒ for either input. In general a quantum computation involves the evolution of correlations in successive entangled states to a final state in which a measurement can determine the answer to a question about a global property of a function. The global property here is a disjunctive property:
(ƒ(0) =ƒ(1) =0) ∨(ƒ(0) =ƒ(1) =1)
or:
((ƒ(0) =1) ∧(ƒ(1) =0)) ∨((ƒ(0) =0) ∧(ƒ(1) =1))
and the computation yields one or other of these disjunctions in the final measurement, which excludes the possibility of recording of the values of the disjuncts. The two alternative disjunctions are represented in the 4-dimensional Hilbert space of the two registers as quantum disjunctions, corresponding to two orthogonal 2-dimensional planes. Depending on whether the function is constant or balanced, the final state of the two registers is represented by a vector lying in one or the other of these two planes, and this can be determined by a measurement of the input register.

The Deutsch-Jozsa algorithm is a simple example of a quantum algorithm. More sophisticated quantum computation algorithms, such as Shor's algorithm for finding the prime factors of a number, demonstrate an exponential speed-up over classical computation. The foundational significance of quantum computation concerns our understanding of computational complexity, that is, the relative efficiency of computational algorithms, rather than our characterization of the class of computable functions as those functions computable by a Turing machine. What quantum computation achieves is the possibility of solving a problem in a run-time (or number of computational steps) that increases as a polynomial function of the size of the input, while the computation using a classical computer would require superpolynomial, typically exponential, time. The difference can be quite dramatic. A classical computer of the sort available as of this writing would take an amount of time longer than the age of the universe to factor a 250-digit number into its two prime factors, using the fastest known algorithm. By contrast a quantum computer using Shor's algorithm could find the factors in minutes.

See also Bell, John, and Bell's Theorem; Bohr, Niels; Einstein, Albert; Hilbert, David; Many Worlds/Many Minds Interpretation of Quantum Mechanics; Quantum Mechanics; Schrödinger, Erwin.

Bibliography

Bell, John S. "On the Einstein-Podolsky-Rosen Paradox." Physics 1 (1964): 195–200. Reprinted in Speakable and Unspeakable in Quantum Mechanics, John S. Bell. Cambridge, U.K.: Cambridge University Press, 1987.

Bennett, Charles, Gilles Brassard, Claude Crepeau, Richard Jozsa, Asher Peres, and William Wootters. "Teleporting an Unknown Quantum State via Dual Classical and EPR Channels." Physical Review Letters 70 (1993): 1895–1899.

Bohr, Niels. "Discussion with Einstein on Epistemological Problems in Modern Physics." In Albert Einstein: Philosopher-Scientist, edited by Paul A. Schilpp, 201–241. La Salle, IL: Open Court, 1949.

Brassard, Gilles, Samuel Braunstein, and Richard Cleve. "Teleportation as a Quantum Computation." Physica D 120 (1998): 43–47.

Brown, Julian. Minds, Machines, and the Multiverse. New York: Simon and Schuster, 2000.

Deutsch, David. "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer." Proceedings of the Royal Society of London A400 (1985): 97.

Deutsch, David, and Richard Jozsa. "Rapid Solution of Problems of Quantum Computation." Proceedings of the Royal Society of London A425 (1968): 73–90.

Einstein, Albert, Boris Podolsky, and Nathan Rosen. "Can Quantum-Mechanical Description of Physical Reality be Considered Complete?" Physical Review 47 (1935): 777–780.

Feynman, Richard P. "Simulating Physics with Computers." International Journal of Theoretical Physics 21 (1982): 467–488.

Mermin, David N. Lecture Notes on Quantum Computation. Available from http://people.ccmr.cornell.edu/mermin/qcomp/CS483.html.

Nielsen, Michael, and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000.

Schrödinger, Erwin. "Discussion of Probability Relations Between Separated Systems." Proceedings of the Cambridge Philosophical Society 31 (1935): 555–563.

Schrödinger, Erwin. "Probability Relations between Separated Systems." Proceedings of the Cambridge Philosophical Society 32 (1936): 446–452.

Jeffrey Bub (2005)