This is page 1

Printer: Opaque this

Quantum Computation

“Because nature isn’t classical, dammit...” Richard P. Feynman

André Berthiaume^{1}

ABSTRACT Historically, Turing machines have been the paradigm by which we defined computability and efficiency. This is based on Church’s thesis that everything effectively computable can also be computed on a Turing machine. But since our world behaves quantum mechanically, it seems reasonable to also consider computing models that make use of quantum mechanical properties. First stated by Benioff [Ben82] and Feynman [Fey82], this idea was formalized by Deutsch [Deu85] when he introduced his quantum computer and, later on, quantum gate arrays. This paper gives an introduction to quantum computing and briefly looks at a few results in quantum computation, not the least of which is Shor’s polynomial time factoring algorithm ([Sho94] and [Sho95]).

1 The Need for Quantum Mechanics

Why introduce quantum mechanics in computation? The opening quote, if a little blunt, captures the essence of the answer. At the center of computer science are two questions: what problems are computable and how efficiently can they be computed? Historically, (probabilistic) Turing machines have been the paradigm by which we defined computability and efficiency. This is based on Church’s thesis that everything effectively computable can also be computed on a Turing machine. But since our world behaves quantum mechanically, it seems reasonable to also consider computing models that make use of quantum mechanical properties. First stated by Benioff [Ben82] and Feynman [Fey82], this idea was formalized by Deutsch [Deu85] when he defined the first quantum computing model that made full use ofn quantum superposition. This paper gives an introduction to Deutsch’s quantum computing model and briefly looks at a few results in quantum computation, not the least of which is Shor’s polynomial time factoring algorithm.

Before defining a quantum computing model, some basic notions of quantum mechanics must be introduced. A comprehensive presentation of quantum mechanics is beyond the scope of this paper, but fortunately only the very simplest systems are used for quantum computation: two-state systems or finite groups of two-state systems. The next section introduces the relevant notions for these special cases. Quantum gate arrays will be defined next and, after a few examples of their capabilities, the results leading to Shor’s algorithm will be briefly reviewed. The last section addresses some of the difficulties facing the actual construction of a quantum computer.

1Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands (berthiau@cwi.nl).

Because of space restriction, it will not be possible to include the historical context which lead to many of the subjects discussed here. Where possible, we will give references for more detailed accounts. For a more exhaustive review of the history of quantum computation (dating back almost 50 years), the reader should consult [Ben96].

2 Basic Principles of Quantum Mechanics

We now introduce the basic rules of quantum mechanics through a series of principles. Young’s celebrated two-slit experiment will serve as a background to illustrate these principles.

FIGURE 1. Young’s two-slits experiment. Curves A and B show the light intensity when only one hole is open. Curve C shows the interference pattern when both holes are open. (the curves are exaggerated)

In Young’s experiment (figure 1), light coming out of a hole in the left wall must go through two small holes in the center wall. A detector on the right wall measures the light intensity at different positions along the length of the wall. If only one hole is open, the intensity reaches its maximum at a position directly in line with that hole and the source s. As the detector moves away from that position, the intensity slowly fades and eventually vanishes. When both holes are open, the intensity pattern is not the sum of the two one-hole intensities, as one would expect, but an alternation of bright and dark fringes. This effect is caused by the interference of the light coming out from both holes. Surprisingly, the interference persists even when the source s is dim enough to send only one photon at a time; if many runs are made and a photon count is kept for various positions, the same pattern of bright and dark fringes appears. Each photon seems to interfere with itself.

2.1 Probability Amplitudes

The self-interference appearing in Young’s experiment is just one example illustrating that classical intuition cannot be applied to quantum systems. The purpose of this section is not to explain why such strange behavior appears at the quantum level but merely to state the rules for these behaviors. Following Feynman’s example [FLS64], these rules are presented as the principles of quantum mechanics.

Definition 2.1 For a given experiment, an event is a set of initial and final conditions.

For example, an event in Young’s experiment is “a photon leaves the source s and arrives in the detector at position x”. The goal of quantum mechanics is to predict whether an event can happen or not. The first principle of quantum mechanics defines the probability of an event actually happening.

First Principle: The probability p of an event is given by the square norm of a complex number α (called a probability amplitude or simply amplitude).

p = ∥α∥^{2}

The probability amplitude of an event will be noted as follow:

⟨ final condition | initial condition ⟩

For example, the above event can be written as

⟨ a photon is detected at position x | a photon leaves s ⟩

or more succinctly ⟨x|s⟩. The bracket notation, due to Dirac, is reminiscent of conditional probabilities and can be read as: ⟨x|s⟩ is the amplitude of detecting a photon at position x given that a photon left the source s. In fact, amplitudes can be treated in the same way as probabilities. Consider again Young’s experiment. If a photon leaves the source and arrives at the detector, it must do so by going through the holes in the wall. That is to say, the event ⟨x|s⟩ can be broken down in two sequential events: the photon first leaves the source s and arrives to the middle wall, then the photon comes out of this middle wall and arrives at the detector. But to go through the middle wall, the photon has two option: either through hole 1 or hole 2. The following two principles indicate how the laws for addition and multiplication of probabilities also apply to amplitudes.

Second Principle: If an event can be divided in two sequential subevents, the amplitude of the event is the product of the amplitudes for each of the sub-events.

Third Principle: If an event can occur in several alternative ways, then the amplitude of the event is the sum of the amplitudes for each alternative taken separately.

From these two principles:

⟨x|s⟩ = ⟨x|wall⟩⟨wall|s⟩  (1.1)
= ⟨x|1⟩⟨1|s⟩ + ⟨x|2⟩⟨2|s⟩  (1.2)

where ⟨x|i⟩ is the amplitude of a photon arriving at x given it came out of hole i and ⟨i|s⟩ is the amplitude of a photon entering hole i given that it left the source s. Equation 1.2 implicitly considers terms of the form ⟨x|1⟩⟨2|s⟩ or ⟨x|2⟩⟨1|s⟩ to be equal to zero. Informally speaking, these would be asking: “what is the amplitude that a photon leaves s, goes through hole 1, comes out of hole 2 and then arrives at x?” and similarly for the other case. The answer must include the amplitude of going from hole 1 to hole 2 (⟨2|1⟩) and vice versa (⟨1|2⟩). So the correct bracket form for the above questions should be: ⟨x|1⟩⟨1|2⟩⟨2|s⟩ and ⟨x|2⟩⟨2|1⟩⟨1|s⟩. One can verify experimentally that whenever a photon is detected entering one hole, it is never detected coming out of the opposite hole. Equations 1.3 and 1.4 express this situation in terms of amplitudes of events.

⟨1|1⟩ = ⟨2|2⟩ = 1  (1.3)
⟨1|2⟩ = ⟨2|1⟩ = 0  (1.4)

No matter where the detector is positioned, the amplitude ⟨x|s⟩ is completely determined by the amplitudes to transit to and from the two holes. For this reason, the holes are natural elements for expressing events. This leads to the following definition:

Definition 2.2 The set B = {i | i is the label of some condition} is a set of basis states if for all i, j ∈ B

⟨i|j⟩ = \{ \begin{matrix}1 & if i = j \\ 0 & otherwise \end{matrix}

and for any initial condition Y and final condition X, we have

⟨X|Y ⟩ = ∑_{i∈B} ⟨X|i⟩⟨i|Y ⟩

Fourth Principle: Any event can be described in terms of a set of basis states by giving the transition amplitudes to and from those basis states.

Young’s experiment seems to have only one possible set of basis states (namely, B = {1, 2}) but actually, for any experiment, there is an infinite number of sets of basis state. Some appear naturally, such as the two holes in this experiment, and others less so. The notion of basis states can be better understood through an analogy with a three dimensional real vector space V and the dot product in that space. Let the three vectors

e⃗_{1} = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ), e⃗_{2} = ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ) and e⃗_{3} = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} )

be the canonical basis of V and let

A⃗ = ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) and B⃗ = ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} )

be two vectors in V. The following is a non-standard yet valid expression for the dot product of A⃗ and B⃗:

A⃗ · B⃗ = a_{1}b_{1} + a_{2}b_{2} + a_{3}b_{3}
= (A⃗ · e⃗_{1})(e⃗_{1} · B⃗) + (A⃗ · e⃗_{2})(e⃗_{2} · B⃗) + (A⃗ · e⃗_{3})(e⃗_{3} · B⃗)
= ∑_{i=1}^{3} (A⃗ · e⃗_{i})(e⃗_{i} · B⃗)

This last line is similar to the equation for ⟨X|Y ⟩ in definition 2.2. The vectors A⃗ and B⃗ correspond to the two conditions X and Y and the set of canonical basis vectors corresponds to the set of basis states. In this sense, ⟨X|Y ⟩ ≡ ⟨X| · |Y ⟩. The analogy can be pushed further still. Consider the following:

B⃗ = b_{1}e⃗_{1} + b_{2}e⃗_{2} + b_{3}e⃗_{3}
= ∑_{i=1}^{3} e⃗_{i}b_{i}

= ∑_{i=1}^{3} e⃗_{i}(e⃗_{i} · B⃗)

This simply is the previous equation for A⃗ · B⃗ where we abstracted A⃗. In other words, B⃗ is the vector sum of its components along each of the basis vectors e⃗_{1}, e⃗_{2} and e⃗_{3}. Similarly, the initial states Y of ⟨X|Y ⟩ can be expressed in terms of the set of basis states by abstracting X.

|Y ⟩ = ∑_{i∈B} |i⟩⟨i|Y ⟩  (1.5)

(Note: ⟨·|·⟩ is just a scalar number, so |i⟩⟨i|Y ⟩ = ⟨i|Y ⟩|i⟩ but the second form is preferred.) The left and right halves of ⟨·|·⟩ are named bra and ket respectively. Equation 1.5 defines the state of an initial condition Y as function of B, the set of basis states. The ket |Y ⟩ is called a state vector and it lies in a complex vector space (Hilbert space) yspanned by the basis vector associated with the basis states in B. Similarly,

⟨X| = ∑_{j∈B} ⟨X|j⟩⟨j|

defines the state of a final condition X as function of B. The ⟨X| and |Y ⟩ could also be written using another set of basis state just as B⃗ can be written in a basis other than the canonical one. Section 2.2 and 2.4 will present examples where multiple sets of basis states naturally appear. For a basis set B, the state |Y ⟩ is said to be in quantum superposition of the basis states in B, if more than one ⟨i|Y ⟩ is non-zero.

By the first principle, the square norm of an amplitude gives a probability of the corresponding event. By the fourth principle, any event can be expressed as a function of the amplitude corresponding to each basis states. Since probabilities must add up to 1, there should be some constraint on the amplitudes:

Fifth Principle: For any set of basis states B and for any initial con-

dition Y:

∑_{i∈B} ∥⟨i|Y ⟩∥^{2} = 1

This follows from the definition of a set of basis states which has to be complete (all possibilities are accounted for) and orthogonal (⟨i|j⟩ = 0 if i ≠ j, 1 otherwise).

We leave as an exercise the proof of the following theorem (recall that α^{∗} is the complex conjugate of α.)

Theorem 2.1 For any condition A and B, ⟨B|A⟩ = ⟨A|B⟩^{∗}.

From which we derive that if |φ⟩ = ∑_{i∈B} α_{i}|i⟩ then

⟨φ| = ∑_{i∈B} α_{i}⟨i|

All these principles can be put together in the following situation: consider a system whose initial condition is expressed by the state vector

|Y ⟩ = ∑_{i∈B} β_{i}|i⟩

where β_{i} = ⟨i|Y ⟩, the amplitude of the system under consideration in each of the basis states i. Now consider a general final condition

⟨X| = ∑_{j∈B} α_{j}⟨j|

where α_{i} = ⟨X|i⟩. What is the amplitude of finding the system in condition X given that it was initially prepared in Y?

⟨X|Y ⟩ = (∑_{j∈B} α_{j}⟨j|) (∑_{i∈B} β_{i}|i⟩) = ∑_{i∈B} α_{i}β_{i} by def. 2.2

2.2 Qubits and How to Observe Them

The five principles presented in section 2 are completely general and apply to any quantum system. However, for the sake of clarity, we will limit our attention to systems of interest for quantum computation, namely qubits and quantum registers. We begin by defining a qubit, the quantum version of bit, as defined by Schumacher [Sch95].

Definition 2.3 A qubit is a quantum state |φ⟩ of the form

|φ⟩ = α|0⟩ + β|1⟩

where α, β ∈ C and ∥α∥^{2} + ∥β∥^{2} = 1

The above definition leaves the actual medium of a qubit completely undefined. It is of no importance whether the qubit is encoded in the polarization of a photon, the spin of an atom, the up/down orientation of lamp-post or the alive/dead state of Schrödinger’s poor cat^{2} as long as the object is treated according to the principles given in this introduction. There is nothing in principle that forbids one from getting quantum mechanical effects with lamp-posts or cats. In practice, however, it might be easier to use photons or atoms. The word “easier” should be taken loosely; in the last section, we will discuss briefly the issues regarding actual implementations of qubits and, more generally, quantum computers.

The main difference between qubits and classical bits is that a bit can only be set to either 0 or 1while a qubit |φ⟩ can take on any (uncountable) quantum superposition of |0⟩ and |1⟩. This means an infinite amount of information could potentially be encoded in a single qubit by appropriately defining the amplitudes α and β. Unfortunately, what goes in does not necessarily come out. Quantum mechanics imposes very strict rules as to how to extract information out of quantum state. This is done through a mathematical construct called an observable. Let |φ⟩ be the state of a quantum system. We have a probe P at our disposal to measure some property of |φ⟩. This property could be the direction, the position or even a simple yes/no question. We need to model the action of the probe P on the state |φ⟩.

2My apologies to Simone and Hugin and all other cats who might read this paper.

Definition 2.4 Let H be the Hilbert space used to represent the state vectors of a quantum system. An observable O is a set of subspaces E_{1}, E_{2}, …, E_{k} ⊆ H such that these subspaces completely partition H. i.e.

E_{1} × E_{2} × ⋯ × E_{k} = H

and

∀ i, j ∈ {1, …, k}, i ≠ j : E_{i} ⊥ E_{j}

An observable is the mathematical representation of the probes P. The next principle defines the effect of an observation of a state vector.

Sixth Principle: Let |φ⟩ be a state vector in a state space H and let O = {E_{1}, E_{2}, …, E_{k}} be an observable. Since O partitions H, |φ⟩ can be expressed as a linear superposition of its components along each of the E_{i}’s:

|φ⟩ = ∑_{i=1}^{k} α_{i}|φ_{E_{i}}⟩

where |φ_{E_{i}}⟩ lies in E_{i}. Observing the state |φ⟩ with O will cause the following:

1. One of the E_{i} will be selected with probability ∥α_{i}∥^{2}.

2. The state |φ⟩ will “collapse” to |φ_{E_{i}}⟩ (renormalized).

3. The only classical information given by O is which subspace (i) was selected. All information not in |φ_{E_{i}}⟩ is lost.

To each possible output value of the probe corresponds a subspace in the observable. Since all these values are different from each other, the corresponding subspace must be orthogonal. Again, any observable is allowed in principle for observing a quantum state. Whether the physical apparatus that corresponds to that specific observable is easy to build is a different matter entirely.

The standard observable for a qubit is B = {E0, E1} where E0 and E1 are spanned by the two basis vectors |0⟩ and |1⟩ respectively. An example of a non-standard observable on a qubit is O = {E0′, E1′} where E0′ and E1′ are spanned by

|0′⟩ = \frac{1}{\sqrt{2}}(|0⟩ + |1⟩) and |1′⟩ = \frac{1}{\sqrt{2}}(|0⟩ − |1⟩)

respectively. The reader can check that E0′ and E1′ have the correct properties of an observable. The next section will emphasize how the information in a qubit is linked to which observable is used to read them.

2.3 Digression in Quantum Cryptography

If qubits are encoded in the polarization of photons, the two observables B and O in section 2.2 have a simple physical implementations. Define |0⟩ and |1⟩ as horizontally and vertically polarized photons. Then B is a horizontally positioned polarizing filter and O is a polarizing filter set at 45 degrees from the horizontal. This forms the basic set-up for quantum cryptography. Alice, the sender, wants to send her secret bit to Bob, the receiver. They agree that 0 will be encoded as a photon either in state |0⟩ or |0′⟩ (based on a coin flip) and a 1 is similarly send as either |1⟩ or |1′⟩. Bob must read the the photons either with B or O. Table 1.1 shows the various outcomes for each possible choice of encoding (by Alice) and observable (by Bob). As an example, assume Alice’s bit is a zero. Her coin-flip instructs

Alice Bob  Alice’s state  result  Correctness
sends uses relative to Bob and probability
|0⟩  B  |0⟩  0 (prob 1)  correct
O  \frac{1}{\sqrt{2}}(|0′⟩ + |1′⟩) 0′/1′ (prob 50%)  random
|0′⟩  B  \frac{1}{\sqrt{2}}(|0⟩ + |1⟩) 0/1 (prob 50%)  random
O  |0′⟩  0′ (prob 1)  correct
|1⟩  B  |1⟩  1 (prob 1)  correct
O  \frac{1}{\sqrt{2}}(|0′⟩ − |1′⟩) 0′/1′ (prob 50%)  random
|1′⟩  B  \frac{1}{\sqrt{2}}(|0⟩ − |1⟩) 0/1 (prob 50%)  random
O  |1′⟩  1′ (prob 1)  correct

TABLE 1.1. Depending on how Alice will encode her secret bit and what observable will be used by Bob, Bob’s read-out of the photon send by Alice will either be correct or completely randomized.

to encode it as a |0⟩. If Bob chooses the observable B to observe Alice’s incoming photon, he will get a 0 outcome with certainty and will know Alice’s bit (assume Alice discloses her bases to Bob in a later discussion). However, Bob could choose the O observable to read the incoming photon.

The reader can check that

|0⟩ = \frac{1}{\sqrt{2}}(|0′⟩ + |1′⟩)

Bob thus has 50% probability of getting the 0′ outcome and 50% probability of getting the 1′ outcome. Similar arguments hold for each case of table 1.1. To learn more about the importance of this situation, see [BBB^{+}92],

[BBE92] and [Bra93]. The point of this digression was to demonstrate that the information of a quantum state is a function of the observable used. The same state |φ⟩ observed with two different observable can give a definite answer in one case and a totally randomized answer in the other.

2.4 Evolution of a Quantum System

The situations considered up to now were static in the sense that the initial state did not change after being set. Once the initial state vector |Y ⟩ was defined, we considered amplitudes of the form ⟨X|Y ⟩ for some ⟨X|. But to compute something with quantum states, some transformation of the initial state will have to be performed. Suppose an apparatus A is used to execute this transformation on the initial state |Y ⟩. The events of interest are now of the type “what is the amplitude for the final condition X given that the initial condition Y went through apparatus A?”. In the bracket notation, this is written as

⟨X|A|Y ⟩

The next principle gives the mathematical representation of A.

Seventh Principle: State vectors are transformed by unitary matrices. Relative to a set of basis state B, A_{i,j} (i, j ∈ B) is the amplitude of going from state i to state j.

A matrix U is unitary if UU^{†} = U^{†}U = I (U^{†} is the conjugate transpose of U). In principle, any unitary transformation on a quantum state is allowed but constructing a physical device corresponding to any given matrix U might pose some technological problems.

A simple example of qubit transformation can be made with polarized photons. A polarized photon going through a transparent tank of sugar water will have its polarization slowly rotated^{3}. The amount of rotation depends on the length of the tank and the density of sugar. By appropriately setting these parameters, the tank can be made to induce a 45 degree rotation on incoming photons. If |0⟩ and |1⟩ respectively correspond to horizontally and vertically polarized photon, then the tank has the following effect:

3Actually, more than just the polarization will be affected, but for simplicity, we will ignore these other effects.

|0⟩ will be transformed into \frac{1}{\sqrt{2}}(|0⟩ + |1⟩) and  (1.6)
|1⟩ will be transformed into \frac{1}{\sqrt{2}}(−|0⟩ + |1⟩)  (1.7)

The transformation induced on the basis states completely determines the matrix A. If |φ⟩ = α|0⟩ + β|1⟩ is shot through the tank, it will come out transformed into state |φ′⟩ where

|φ′⟩ = A|φ⟩
= A(α|0⟩ + β|1⟩)
= αA|0⟩ + βA|1⟩  (by linearity)
= α (\frac{1}{\sqrt{2}}(|0⟩ + |1⟩))

+ β (\frac{1}{\sqrt{2}}(−|0⟩ + |1⟩)) (by eqn. 1.6, 1.7)

= \frac{1}{\sqrt{2}}(α − β)|0⟩ + \frac{1}{\sqrt{2}}(α + β)|1⟩

Or, in more familiar matrix-and-vector style:

A = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & −1 \\ 1 & 1 \end{matrix} ) , |φ⟩ = ( \begin{matrix}α \\ β \end{matrix} )

and

|φ′⟩ = A|φ⟩ = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & −1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}α \\ β \end{matrix} ) = ( \begin{matrix}\frac{1}{\sqrt{2}}(α − β) \\ \frac{1}{\sqrt{2}}(α + β) \end{matrix} )

Another transformation very similar to that induced by A is “square root of not”. The name is derived form the fact a qubit going through two identical ¬^{√_{\overline{Not}}}-apparatuses comes out in a state corresponding to the boolean inverse of its initial value. The ¬^{√_{\overline{Not}}} transformation is given below; the reader is encouraged to check that it performs as stated.

¬^{√_{\overline{Not}}} = \frac{1}{4} ( \begin{matrix}1 − i & 1 + i \\ 1 + i & 1 − i \end{matrix} )

A qubit can be set, transformed and observed. But to do serious computation, more than a single qubit is required. The next section introduces the last few mathematical tools needed for quantum computation.

2.5 Quantum Registers

Quantum computations generally use more than just one qubit. The mathematical formalism introduced so far must be adapted to the treatment of groups of qubits.

Definition 2.5 A quantum register is an ordered set of a finite number of qubits.

Definition 2.6 The standard basis B of an n-qubit quantum register is

B = {|i⟩ | i is an n-bit binary string}

Let |φ_{1}⟩ = α_{0}|0⟩ + α_{1}|1⟩ and |φ_{2}⟩ = β_{0}|0⟩ + β_{1}|1⟩ be two qubits composing a 2-qubit quantum register. The state vector |ψ⟩ of the register is defined as the tensor product of the states |φ_{1}⟩ and |φ_{2}⟩

|ψ⟩ = |φ_{1}⟩ ⊗ |φ_{2}⟩ = (∑_{i=0}^{1} α_{i}|i⟩) ⊗ (∑_{j=0}^{1} β_{j}|j⟩)

= ∑_{i,j=0}^{1} α_{i}β_{j}(|i⟩ ⊗ |j⟩)

By definition, the tensor product maps |i⟩ ⊗ |j⟩ (where i and j are basis states to |ij⟩. This allows us to write |ψ⟩ as

|ψ⟩ = ∑_{i,j=0}^{α_{i}β_{j}|ij⟩}

Similarly, let A and B be two unitary matrices corresponding to two apparatuses operating on |φ_{1}⟩ and |φ_{2}⟩ separately. The combined action of A and B on the joint state |ψ⟩ = |φ_{1}⟩ ⊗ |φ_{2}⟩ is defined as a 4 × 4 matrix C where

C = A ⊗ B = ( \begin{matrix}a_{11}B & a_{12}B \\ a_{21}B & a_{22}B \end{matrix} )

It is easily verified that the tensor product has the following property

(A ⊗ B)(|φ_{1}⟩ ⊗ |φ_{2}⟩) = (A|φ_{1}⟩) ⊗ (B|φ_{2}⟩)

and that it preserves unitarity.

So far, we seem to only complicate the notation for a basically simple situation: two independent qubits are acted upon by two independent apparatuses. But the point in joining two qubits is specifically to allow them to be dependent. In fact, not all states of a 2-qubit quantum register can be expressed as the tensor product of single qubit states. An example of such state is

|ψ⟩ = \frac{1}{\sqrt{2}}(|00⟩ + |11⟩)

If |ψ⟩ is observed with the observable corresponding to the standard basis, the results “00” or “11” will be seen each with probability 50%, but the results “01” or “10” will never be observed. When the state of an n-qubit register cannot be expressed as the tensor product of n qubit states, the register is said to be entangled. Similarly, not all 4 × 4 unitary matrices can be expressed as the tensor product of two 2 × 2 unitary matrices. One such matrix is

C = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} )

which effects the following mapping of the basis states of the register: if the register’s state is such that the first qubit is 0 no action is performed, otherwise the value of the second qubit is negated. The above matrix performs the operation called controlled-not on two qubits. As such, it is the first example of a quantum computation introduced here. For the importance of the controlled-not operation, see [BBC^{+}95].

It is a simple matter to generalize what has been presented in this section to represent the state of an n-qubit register. The general state vector |ψ⟩ of an n-qubit quantum register is

|ψ⟩ = ∑_{i=0}^{2^{n}−1} α_{i}|i⟩

and the 2^{n} vectors |i⟩ form the set of basis states of the register (note that within |·⟩, the i stands for the binary expansion of the value i). This means that |ψ⟩ is a vector in a 2^{n} dimensional Hilbert space and operations are defined by 2^{n} ×2^{n} unitary matrices. Observables for extracting information from the state vectors are partitions of the 2^{n} dimensional Hilbert space.

We are now ready to apply these notions of quantum mechanics to computation.

3 Computing with Quantum Registers

The original quantum computing model proposed by Deutsch was essentially a Turing machine, but with the added properties that tape cells and the head’s state could be in quantum superposition. Deutsch also constrained the transition function by requiring it to induce a unitary evolution of the Turing machine. This was of course necessary to respect quantum mechanical principles, but it made programming quantum Turing machines even more nightmarish than programming classical ones. Verifying that a given transition function corresponds to a unitary evolution is non-trivial. Bernstein and Vazirani give three rules for verifying that a transition function performs its computation in a unitary fashion [BV93], but even using this method still requires unnatural programming skills.

In classical complexity theory, uniform circuit families are also commonly used as a computing model. Turing machine and uniform circuit families are effectively equivalent in computing power in that they can simulate one another with negligible complexity overhead. This makes the use of one or the other a matter of taste. There exists a quantum equivalent to uniform circuit families: quantum gate arrays. They were introduced by Deutsch ([Deu89]) and studied extensively by many authors (see [BBC^{+}95] for a detailed review of quantum gate arrays). Yao [Yao93] has shown that acyclic quantum gate arrays could simulate quantum Turing machines, thus making the use of one or the other a matter of choice. However, since quantum gate arrays allow a more natural way to introduce unitarity in computation, they are emerging as the standard quantum computing model. In what follows, the diagrams and gate array notation are as in [BBC^{+}95].

3.1 Quantum Gate Arrays

The diagram below represents a general quantum gate array. The initial (basis) state of the register is on the left and time flows from left to right. One might think of the particles composing the register as travelling through the different gates. At the right end is the observable that extracts information from the register after it has gone through all the gates.

b_{7} b_{6} b_{5} b_{4} b_{3} b_{2} b_{1}  A_{1}  A_{2} . . . . . . . . . . . . . . . . . . . . . A_{n} [figure: O]

The sequence of A_{i}’s with observable O is what constitutes a quantum program. Formally speaking, the A_{i} gate should be of some well-defined form corresponding to some definition of elementary steps. For the purpose of this paper, it is sufficient to consider any quantum gate acting on only one or two qubits to be such an elementary step. The reader is encouraged to consult [BBC^{+}95] for more details on the notion of elementary quantum gates. Also, in our gate arrays, we will not always specify all the elementary gates: in some cases we will simply convince ourselves that the necessary elementary gates could be written down. This procedure is analogous to writing pseudo-code for classical Turing machine and will provide a better intuitive approach.

To illustrate the programming of quantum gate arrays, we will use a variation of the Deutsch-Jozsa Problem [DJ92]. First, we define two properties of functions from {0, 1}^{n} to {0, 1}:

Definition 3.1 A function f : {0, 1}^{n} → {0, 1} is non-balanced if one of the two values of f has majority.

Definition 3.2 A function f : {0, 1}^{n} → {0, 1} is non-constant if there exist x, y ∈ {0, 1}^{n} such that f(x) ≠ f(y).

Notice that most (but not all) functions from {0, 1}^{n} to {0, 1} have both properties simultaneously. The modified Deutsch-Jozsa problem is described as follow:

\underline{Modified Deutsch-Jozsa Problem (mdjp)}:

Input: a computable function f : {0, 1}^{n} → {0, 1}

Problem: to answer either “non-balanced” or “non-constant”, but the answer must apply to f.

The original Deutsch-Jozsa problem dealt with strings rather than functions and was the first example of a problem which could be solved exponentially faster on a quantum computer than on a Turing machine [DJ92]. By recasting the original problem in the context of promise-problems, Berthiaume and Brassard in [BB94], [BB92a] and [BB92b] proved some early results in relativized quantum complexity theory. These results were improved upon first by Bernstein and Vazirani [BV93] and then by Simon [Sim94] who proved the following theorem.

Theorem 3.1 (Simon) There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a quantum computer, but any probabilistic Turing machine with bouded error probability claiming to solve this problem (using the oracle) will require exponential time on infinitely many inputs.

Simon’s theorem is the strongest argument in favor of the superiority of quantum computers over Turing machines. Moreover, the quantum gate array used in Simon’s proof is similar to the one used by Shor for his factoring algorithm. In this section, we present a solution to the mdjp using quantum gate arrays. This allows us to introduce, in section 4, the gate array used in the proof of theorem 3.1. In section 5, we outline the quantum component of Shor’s factoring algorithm.

We now present a quantum solution to the mdjp. According to the principles given in section 2, a valid quantum algorithm corresponds to a unitary matrix. But programming in terms of unitary matrices is unnatural to humans who prefer to think in terms of sequential steps. We need to break down the mdjp into a sequence of unitary operations. If each of these sequential steps are simple enough, asserting their unitarity should be a relatively easy task. Just how simple need be these steps? Ideally, they should be broken down to what we defined as elementary gates, but in some cases, this will be unnecessary. The following theorem (Lecerf [Lec63] and Bennett [Ben73]) greatly simplifies quantum thinking:

Theorem 3.2 (Lecerf-Bennett) For any Turing machine T computing a function f there exists a reversible Turing machine T′ computing ⟨x, f(x)⟩ on input x and whose running time is within a constant factor of the running time of T. The cost in space is also polynomial in |x|, but all the tape cells used in the process of computing ⟨x, f(x)⟩ will be reset back to zero (reversibly). These tape cells are referred collectively as the workspace.

Reversible Turing machines are such that at any point in the computation, two operations are possible: continue the computation forward one step or undo the previous step. For a more precise definition, see [Lan61] or the review in [BL85]. Benioff [Ben82] and Deutsch [Deu85] have shown that quantum Turing machines can directly simulate reversible Turing machines. Since quantum Turing machines (and thus also to quantum gate arrays) are reversible^{4}, we have the following corollary:

Corollary 3.3 A Turing-computable function f is always computable on a quantum gate array (with a negligible increase in the time complexity).

Consider the mdjp. The input function is computable so, by the Lecerf-Bennett theorem, there exists a reversible Turing machine that computes ⟨x, f(x)⟩ on input x. By definition of the problem, x is an n-bit value and f(x) is a single bit. By corollary 3.3, this implies the existence of a unitary matrix F that computes f on n-bit values in the following sense. Consider the quantum gate corresponding to F:

x { 0^{0^{m} {} F } x f(x)^{} 0^{m}}
F |x, 0, 0^{m}⟩ ⟶ |x, f(x), 0^{m}⟩

This gate works on an (n + 1 + m)-qubit register; the top n qubits encode the input x ∈ {0, 1}^{n}. Those qubits must have the same value before and after the gate: if they are changed during the computation itself, they must be returned to their initial value . The next qubit, initially set to 0, will have the value of f(x) at the output of the gate. The last m qubits are the “workspace” that comes about in theorem 3.2: before and after the computation, they are set to 0^{m}, but within the gate itself, those qubits will be used and reversibly reset to zero afterwards. We do not specify the exact circuitry of elementary gates within the F gate, but by theorem 3.2 and corollary 3.3 we are certain that it can be done in accordance with the quantum principles. Also, for clarity, we will not usually display the qubits used as workspace since they serve no purpose outside the gates themselves. Therefore, the above gate F will displayed as follow:

4Apart from the observation, which is inherently irreversible.

x { 0 F } x f(x)

F |x, 0⟩ ⟶ |x, f(x)⟩

A remark: informally speaking, unitarity means that information cannot be lost. This means that the value f(x) cannot simply overwrite the 0 in the last qubit: those values (f(x) and 0) must be combined in a way that allows the recovery of both values. The exclusive-or function is commonly used for this purpose. In the Dirac notation, if the initial of the register is |x, b⟩ then the action of the F gate is actually

F |x, b⟩ = |x, b ⊕ f(x)⟩

Of course, if b = 0 then F |x, 0⟩ = |x, f(x)⟩, which is what we wanted. This property of non-destructive writing will be important later on.

Computing a function on an input is fine, but the rules of quantum mechanics allow much more. Recall that by linearity of quantum operations, if the input state is in quantum superposition \frac{1}{\sqrt{2}}(|x, 0⟩ + |y, 0⟩) then the F gate will compute the superposition of f on both values.

F (\frac{1}{\sqrt{2}}(|x, 0⟩ + |y, 0⟩)) = \frac{1}{\sqrt{2}}(|x, f(x)⟩ + |y, f(y)⟩)

Assume there is a way to unitarily generate (through some matrix S_{n}) a superposition of all possible values of an n qubit register. That is, if the initial state of the register is all zero, S_{n} transforms it in a superposition of all 2^{n} values of the first n qubits.

S_{n}| \underbrace{0 … 0}_{n}⟩ = \frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} |i⟩

We can see that by first applying S_{n} and then F, we can compute in one sweep all possible values for f in quantum superposition.

0^{n}{ 0 S_{n}  F

F S_{n}| \underbrace{0 … 0}_{n}, 0⟩ ⟶ F (\frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} |i, 0⟩) ⟶ \frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} |i, f(i)⟩

The reader should take careful note of what is meant by the above diagram. While the operator S_{n} acts on n qubits, its mathematical representation is a 2^{n} × 2^{n} unitary matrix. Also, in the expressions below the diagram, it would be more accurate to use S_{n} ⊗I (where I is the 2×2 identity matrix) since our gate array uses n+1 qubits. I trust the reader will be comfortable with this small abuse of notation throughout the text.

We now show how to implement an S_{n} gate to achieve this form of quantum parallelism. Consider the unitary matrix (and associated gate):

S_{1} = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ) ⇒  S_{1}

It is a simple matter to verify that S_{1} is indeed unitary. Note also that S_{1}^{−1} = S_{1}. An S_{1} gate is an elementary gate as it acts only on a single qubit: it sends |0⟩ to \frac{1}{\sqrt{2}}(|0⟩ + |1⟩) and |1⟩ to \frac{1}{\sqrt{2}}(|0⟩ − |1⟩). The desired S_{n} gate acts on a quantum register by sending each qubit individually into a separate S_{1} gate (an example on six qubits is shown here).

S_{6} ≡ ^{S_{1}}^{S_{1}}^{S_{1}}^{S_{1}}^{S_{1}}^{S_{1}}

The unitary transformation induced by an S_{n} gate is given by the formula S_{n} = ⨂_{n} S_{1}. This has a nice recursive definition^{5}: If n > 1 then

S_{n} = ( \begin{matrix}S_{n−1} & S_{n−1} \\ S_{n−1} & −S_{n−1} \end{matrix} )

In gate form: for any x ∈ {0, 1}^{n},

5Note: S_{n} is a special case of Hadamard matrices.

x { S_{n} } φ

S_{n}|x⟩ ⟶ |φ⟩ = \frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} (−1)^{x·i}|i⟩

where the operation x · i is the xor of the bitwise and of the strings x and i. Clearly, if x is set to 0^{n}, S_{n} performs the desired transformation. When outlining the proof of Simon’s theorem, the transformation induced by S_{n} will be more fully used.

With the conjunction of S_{n} and F gates, a single computation produces all possible values of the function f for each input. But these values are in quantum superposition and we have seen (by the sixth principle) that only an observable can obtain information from a superposition (and this act destroys the original superposition). If our aim is to compute various outputs ⟨x, f(x)⟩ for all x, then the only observable that could be used is the standard one, B (see definition 2.6).

0^{n}{ 0 S_{n}  F [figure: B]

But B will only produce a single pair ⟨x, f(x)⟩ where x is chosen randomly (uniformly). To obtain all values of f in this fashion would require (on average) an exponential number of such runs. This could have been done just as easily using a probabilistic Turing machine by choosing x randomly and computing f(x). Deutsch [Deu85] proved that quantum parallelism used in this simplistic way cannot produce that values of f any faster than classical machines. To get some form of benefit from superpositions, a more subtle use of quantum parallelism is needed.

Consider the following unitary transformation (and associated gate):

P = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) ⇒  P

If a qubit is set to 0 nothing happens but if it is set to 1 then the amplitude is multiplied by −1. This gate “encodes” the “value” of the qubit into the sign of the amplitude. Now consider the following gate array

0^{n}{ 0 S_{n}  F ^{P}  F [figure: D]

(where the observable D will be defined shortly). From our gate definitions, we know that the state |φ⟩ of the register just after the P gate is:

|φ⟩ = \frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} (−1)^{f(i)}|i, f(i)⟩

When that state goes through the final F gate, the values for f are again computed and non-destructively combined using (in our case) the xor function. Since f(i) ⊕ f(i) = 0 for all i ∈ {0, 1}^{n}, the final state before observation is

|φ⟩ = \frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} (−1)^{f(i)}|i, 0⟩

All the manipulations done so far had only one purpose: to transfer the values of f into the amplitudes relative to each of the basis states. The power of quantum computation resides in the interference of these amplitudes and the observable used to read the quantum states. We now define that observable. Consider D = {E_{a}, E_{b}} where the subspace E_{a} is the one-dimensional space spanned by

|ψ⟩ = \frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} |i, 0⟩

and E_{b} = (E_{a})^{⊥}, the orthogonal complement of E_{a}. Using D in the gate array above allows us to answer the mdjp, that is to determine without errors whether f is non-balanced or non-constant. To see this, recall that D will give the answer a or b with probabilities depending on the amplitudes of |φ⟩ in the subspaces E_{a} and E_{b}. We must find the expression of |φ⟩ in the basis defined by D. This is easy since D has only two subspaces, one being one-dimensional. Let α and β be the projections of |φ⟩ in E_{a} and E_{b}, then

|φ⟩ = α|ψ⟩ + β|ψ_{b}⟩

where |ψ_{b}⟩ is a vector in E_{b} and of course, |ψ⟩ ⊥ |ψ_{b}⟩. Observing the final state |φ⟩ with D will give the answer a or b with probability ∥α∥^{2} and ∥β∥^{2} respectively. Since the observable has only two possible answers, ∥β∥^{2} = 1 − ∥α∥^{2}. Also, finding the projection of |φ⟩ in the one-dimensional subspace E_{a} is simple. We now compute the exact expression for α, the projection of |φ⟩ along |ψ⟩.

α = ⟨ψ|φ⟩
= (\frac{1}{\sqrt{2^{n}}} ∑_{i=0}^{2^{n}−1} ⟨i, 0|) (\frac{1}{\sqrt{2^{n}}} ∑_{j=0}^{2^{n}−1} (−1)^{f(j)}|j, 0⟩)

= \frac{1}{2^{n}} ∑_{i=0}^{2^{n}−1} ∑_{j=0}^{2^{n}−1} (−1)^{f(j)}⟨i, 0|j, 0⟩

But since ⟨i, 0|j, 0⟩ = 1 if and only i = j and zero otherwise, the expression for α simplifies to

α = \frac{1}{2^{n}} ∑_{i=0}^{2^{n}−1} (−1)^{f(j)}

We now look at the value of α for different functions f. If f is a balanced function, the sum for α will contain exactly as many 1’s as −1’s, so in this case α = 0 and D will always give a b answer and never a. If f is a constant function, the value for α will either be 1 or −1, so in this case D always gives the answer a and never b. If f is of any other type, D will answer a or b with various probabilities.

To demonstrate that the above quantum gate array solves the mdjp, we need to take the above reasoning backwards. If the answer received from D is a, we know for certain that f could not have been a balanced function (since a is never given in that case), so answering “non-balanced” is correct. Similarly. if D gives the answer b, then we know for certain that f could not have been a constant function, so answering “non-constant” is correct. For cases where f is neither of these those case, D might give any of a and b, but this is not a problem since both answers “non-balanced” and “non-constant” are correct.

4 Separating Two Classes of Functions

The solution to the modified Deutsch-Jozsa problem, like most interesting quantum algorithms (or gate arrays) depends on the ability to evolve an nqubit register in superposition of all 2^{n} values. In the solution we presented, this operation was performed by the S_{n} gate. But the transformation induced by S_{n} is much more subtle. Recall that

S_{1} = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} )

and

S_{n} = S_{1} ⊗ S_{n−1} = ( \begin{matrix}S_{n−1} & S_{n−1} \\ S_{n−1} & −S_{n−1} \end{matrix} )

If an n-qubit register, initially set to x ∈ {0, 1}^{n}, goes through an S_{n} gate, the transformation will be as follow:

S_{n}|x⟩ = \frac{1}{\sqrt{2^{n}}} ∑_{i=1}^{2^{n}−1} (−1)^{x·i}|i⟩

Where x · i is the xor of the bitwise and of the two strings. We now show how Simon [Sim94] used this transformation to prove theorem 3.1.

Assume we have a computable function f : {0, 1}^{n} → {0, 1}^{m}, where m ≥ n. The Lecerf-Bennett theorem still applies, so there exists a quantum gate F that transforms |x, b⟩ into |x, b ⊕ f(x)⟩ for all x ∈ {0, 1}^{n} and b ∈ {0, 1}^{m}. Consider the following gate array:

0^{n}{^{0^{m}{} S_{n}  F S_{n}

S_{n}F S_{n}|0^{n}, 0^{m}⟩ ⟶ \frac{1}{2^{n}} ∑_{i=0}^{2^{n}−1} ∑_{j=0}^{2^{n}−1} (−1)^{i·j}|j, f(i)⟩

The first application of S_{n} allows all values of f to be computed using quantum superposition (with the F gate). The second application of S_{n} creates an elaborate entanglement of the states |j, f(i)⟩ whose phases are a function of both i and j. In fact, the output state of the gate array is a form of Fourier spectrum of the function f. With this gate array, Simon was able to distinguish efficiently two classes of function: 1-to-1 versus 2-to-1 with a mask.

A function f : {0, 1}^{n} → {0, 1}^{m} is said to be 2-to-1 with a mask s if there exists a non-trivial s ∈ {0, 1}^{n} such that for all x ≠ x′, f(x) = f(x′) if and only if x′ = x ⊕ s (where ⊕ is the bitwise xor). Suppose we are given a computable function f : {0, 1}^{n} → {0, 1}^{m} with a promise that it is either 1-to-1 or 2-to-1 with a mask. The task is to determine which of these hold for f and, in the second case, produce s. Simon proved that this problem can be solved in expected time O(nT_{f}(n) + G(n)), where T_{f}(n) is the time to compute f on inputs of size n and G(n) is the the required to solve an n × n linear system of equations over Z_{2}. The algorithm will call (on average) n times the following gate array:

0^{n}{^{0^{m}{} S_{n}  F S_{n} [figure: B]

To see how this gate array works, we must do a analysis similar to the one for the mdjp in section 3.1. Let |φ⟩ be the state of the register just before the observation.

|φ⟩ = \frac{1}{2^{n}} ∑_{i=0}^{2^{n}−1} ∑_{j=0}^{2^{n}−1} (−1)^{i·j}|j, f(i)⟩

If f is 1-to-1, then all |j, f(i)⟩ configurations are different, each with amplitude ±1/2^{n}. The observable B will yield any of those configurations with probability 1/2^{2n} and k repetitions of this subroutine will result in k configurations of |j, f(i)⟩ distributed uniformly and independently.

However, if there exists a non-trivial s such that for all x ∈ {0, 1}^{n}, f(x) = f(x′) if and only if x′ = x ⊕ s, then for all i, j ∈ {0, 1}^{n}, the configurations |j, f(i)⟩ and |j, f(i ⊕ s)⟩ are identical. Therefore, the amplitude α_{i,j} for a particular configuration is:

α_{i,j} = \frac{(−1)^{i·j} + (−1)^{(i⊕s)·j}}{2^{n}}

Two values are possible: if j · s = 0 then i · s = (i ⊕ s) · j so α_{i,j} = 1/2^{n−1}. Otherwise, α_{i,j} = 0. This means that when the register is observed, only configurations such that j · s = 0 can be seen. Repeating k times this subroutine will result in k configurations of this type chosen uniformly and independently.

In both of these cases, after an expected O(n) repetitions, we can find n configuration |j_{1}, f(i_{1})⟩, …, |j_{n}, f(i_{n})⟩ such that the equations j_{i} ·s = 0 are linearly independent. Solving this linear system yields a non-trivial s′. If f is 1-to-1, this s′ is a random string and if f is 2-to-1 with mask, s′ is that mask. Computing f(0^{n}) and f(s′) and comparing the values determines the status of f: if f(0^{n}) ≠ f(s′), then f is 1-to-1, otherwise f is 2-to-1 with s = s′ as the mask.

The proof of Simon’s theorem rests on the interaction of phases induced by the double application of S_{n} (with a relativized version of the above problem). Shor’s factoring algorithm uses the same trick, but with a refined version of S_{n}, called the quantum discrete Fourier transform, and more number theory. The next section will go over the quantum component of the factoring algorithm; the reader may consult [Sim94] to see how the relativized version of the above problem is used to prove Simon’s theorem.

5 Shor’s Factoring Algorithm

Every integer n has a unique decomposition in prime factors. However, finding this decomposition when n is large is a difficult computational problem. All known classical methods are resolutely inefficient (see [Adl94]) and even the best known classical algorithm, the number field sieve (see [LLMP90], [LL93]) requires time O(e^{c(log n)^{1/3}(log log n)^{2/3}}), which is exponential in the size (the number of digits, i.e., log n) of n. Whether the factoring problem is polynomial or not (classically) is still unknown. Yet the faith in hardness of this problem is such that the security of many classical cryptographic protocols is based of the impossibility of factoring efficiently.

Number theory offers another interesting problem: finding the order of an element. Given x and n, find r (called the order) such that x^{r} ≡ 1 (mod n). As with the factoring problem, no efficient algorithm is known for solving this problem. But while these problems appear very different, they are closely related. Miller [Mil76] has shown that, using randomization, one could solve the factoring problem if one had access to an oracle for finding the order of an element. His reduction works as follows: first, make sure that n is odd and not a prime (there are efficient primality testing algorithms). Then, use the following algorithm:

Program One-Factor (input: n odd integer) x ← random{0,…,n} r ← use the oracle to find the order of x (mod n) Output: if r is odd or x^{r/2} ≡ −1 (mod n) then fail

else return gcd(x^{r/2} − 1, n)

Choosing a random number in the range {0, …, n}, doing the modular exponentiation and finding the gcd (greatest common divisor) can all be done in polynomial time (see [Knu81]). Let k be the number of odd prime factors of n. One can prove that, provided n is odd and non-prime, the above algorithm will return a prime factor of n with probability at least 1 − 1/2^{k−1}. Repeating this algorithm a polynomial number of times will produce a complete factorization of n.

Shor’s breakthrough was to discover an efficient quantum algorithm to find the order of an element. The factoring algorithm is simply Miller’s reduction where the oracle call is replaced by a call to this quantum algorithm. The next section describes how to find the order of an element using quantum superpositions.

5.1 Finding the Order of an Element

We now describe Shor’s algorithm to find the order r of an element x (mod n). There are two distinct parts to algorithm: the first is the quantum component, described next, which produces a value c. Thanks to approprietly chosen amplitudes, this c has a relationship to r such that a little (purely classical) post-processing in the second part can efficiently determine r. We describe the quantum component using quantum gate arrays. First, we need to find m such that n^{2} ≤ 2^{m} ≤ 2n^{2}. The gate array operates on a 2m-qubit quantum register. Next, we need a gate such that on input |a, 0⟩, it computes |a, x^{a} mod n⟩. We known that modular exponentiation can be done classically in polynomial time. So by the Lecerf-Bennett theorem and corollary 3.3, there exists a quantum gate E_{n}^{x} that efficiently implements this operation. This E_{n}^{x} gate is shown below.

a {^{0^{m}{} E_{n}^{x} } a } x^{a} (mod n)

We only need one more quantum operation. Shor refined the S_{n} transformation used by [BV93] and [Sim94] in the following way: instead of using phases that were ±1/\sqrt{2^{m}}, we now make use of the full spectrum of complex amplitudes. The transformation A_{m} sends a m qubit register in basis state |a⟩ to

\frac{1}{\sqrt{2^{m}}} ∑_{c=0}^{2^{m}−1} e^{\frac{2πiac}{2^{m}}} |c⟩

(Recall that for any a + bi ∈ C of norm 1, there exists an angle θ ∈ [0, 2π] such that a + bi = cos θ + i sin θ = e^{iθ}.) This transformation is called the discrete quantum Fourier transform. The fact that one can efficiently implement such a quantum gate is not immediately clear, if only for the fact that the amplitudes seem to require increasing precision as m grows large. However, Deutsch and Coppersmith [Cop94] independently found an efficient solution based on the Fast Fourier Transform algorithm [Knu81], which only requires O(m^{2}) elementary quantum gates.

The gate array for Shor’s algorithm to find the order r of an element x (mod n) is:

0^{m}{^{0^{m}{} S_{m} E_{n}^{x} A_{m} [figure: B]

The S_{n} gate was defined in the previous section and only serves to generate a superposition of all possible values for the top half of the register. We then compute in quantum parallel the modular exponentiation of x for all these values and then apply the Fourier Transform A_{m}. The state of the register just prior the observation: is (omitting the (mod n) in the ket for clarity):

\frac{1}{2^{m}} ∑_{a=0}^{2^{m}−1} ∑_{c=0}^{2^{m}−1} e^{\frac{2πiac}{2^{m}}} |c, x^{a}⟩

Since we are using the standard observable, the observation will yield any basis state |c, x^{k}⟩ with probability

∥\frac{1}{2^{m}} ∑_{a:x^{a}≡x^{k}} e^{\frac{2πiac}{2^{m}}} ∥^{2}

Shor proves that this probability vanishes everywhere except for basis states |c, x^{k}⟩ such that there exists an integer d satisfying

|\frac{c}{2^{m}} − \frac{d}{r}| ≤ \frac{1}{2^{m+1}}

where the probability is at least 1/3r^{2}. This means that reading the final state of the register will yield with high probability a value c such that the fraction c/2^{m} is close to d/r. Because 2^{m} > n^{2}, there is only one fraction d/r that satisfies the above equality while keeping r < n. The algorithm for finding that fraction d/r from c/2^{m} is the post-processing we referred to earlier and can be done efficiently by continued fraction expansion (see [Knu81]). This produces the r we needed.

For a more detailed study of Shor’s algorithm including the necessary number theory which was left out here, see [Sho95] and [EJ96]. Shor’s algorithm and Simon’s theorem are two of the most important results in quantum complexity theory. Both are strong arguments in favor of the superiority of quantum computing models over classical ones. But if new efficient algorithms are developed on quantum machines, it would be nice to have actual quantum machines on which to run them! The next section considers the obstacles to building quantum mechanical computers.

6 Building a Quantum Computer

Quantum computers offer capabilities unmatched by classical Turing machines. But if quantum computing models could in principle be constructed, there are enormous practical issues still to overcome before reaching this goal. The most serious of these obstacles is the preparation and manipulation of macroscopic physical systems in quantum superposition. This section outlines the difficulties and possible solutions to this problems.

Qubits were defined in section 2.2 as any object having two distinct states whose evolution is considered according to the principles of quantum mechanics. Following those principles, it is possible to have this object in quantum superposition, which permits quantum parallelism. But while experimental physicists have been observing and manipulating atomic and sub-atomic particles in quantum superposition, no one has yet claimed to have observed a lamp-post exhibiting a similar behavior. Why? The explanation has to do with decoherence: the process by which a system in quantum superposition decays to a classical state because of interaction with the environment.

We illustrate the problem as follow: a qubit in state |φ⟩ = α|0⟩ + β|1⟩ is put inside a black box. If the box is perfectly sealed, sheilding its interior from the rest of the universe, the qubit remains in state |φ⟩ indefinitely. But perfect isolation is impossible: some energy in one form or another always leaks through the box, carrying traces of information of the box’s content. Consider a very simple case: a stray electron in state |e_{s}⟩ enters the box and interacts with the qubit. The interaction is such that the electron leaves the box in state either |e0⟩ or |e1⟩ depending whether the qubit was in basis state |0⟩ or |1⟩. In Dirac notation, this sequence of events is described as follows. Initially, we have two independent systems: a qubit in state |φ⟩ and the electron in state |e_{s}⟩. Since they are independent, their joint state is

|φ⟩ ⊗ |e_{s}⟩ = (α|0⟩ + β|1⟩) ⊗ |e_{s}⟩

However, once the electron enters the box, it interacts with the qubits. As it leaves the box, the joint state becomes

α(|0⟩ ⊗ |e0⟩) + β(|1⟩ ⊗ |e1⟩)

The qubit is still in the box and the electron is on its way yonder, but they now form an entangled system. If the state of the electron is now observed in any way (and here any interaction with an object in the lab is considered an observation), the states of the electron will collapse. For simplicity, assume the electron collapses to either |e0⟩ or |e1⟩. Since the electron and the qubit are entangled, the collapse of one causes the collapse of the other: the electron-qubit system will be in state |0⟩ ⊗ |e0⟩ with probability ∥α∥^{2} and in state |1⟩ ⊗ |e1⟩ with probability ∥β∥^{2}. The qubit spontaneously collapses to either |0⟩ or |1⟩ (in accordance with the electron’s collapse) and the quantum superposition lost.

No matter how well qubits are isolated, random energy exchanges between the environment and the qubits will cause some decoherence on a time scale that depends on the medium used for a qubit and the conditions under which it operates. In the best cases, coherence is kept for some 10^{4} seconds and in the worst cases, hardly 10^{−10} seconds. And these figures are for a single qubit only; some decoherence models show the decoherence time dropping exponentially as the number of qubits increases (see [Unr95] and [MSE95]). But keeping a qubit in quantum superposition is only part of the problem. A quantum computer will have to perform operations on that qubit. The time needed to perform an operation also depends on the medium used for a qubit and the conditions under which it operates. Unfortunately, the quick-action qubits are precisely those that interact easily with the environment, i.e. those having the shortest coherence time (see [DiV95]). The faster the operations can be performed, the less time there is to perform them!

Yet hope still remains. Shor’s discovery attracted enough attention that more and more breakthroughs are coming from experimental physics. Many proposals for constructing a quantum computer already exist, such as [Fey86],[SW94], [CY94], [Llo93] or [DiV95]. Currently, a proposal by Pellizzari, Gardener, Cirac and Zoller using trapped ions technology appears very promising [PGCZ95] and the authors even suggest a way to control to a certain extent the decoherence in their implementation. An alternative approach proposed by Deutsch could allow computation on a less than perfect quantum state through a stabilizing scheme (the scheme is outlined in [BDJ94] and a preliminary analysis is given in [Ber95]).

In view of this, it seems unlikely that a general purpose quantum computer will be available in the near future. But technological advances in this field are appearing at an increasing rate. Some researchers are already talking about controlling 3 or 4 qubits for a few operations within ten years. This may not be much of a computer, but it would still be quite an achievement! A more reasonable goal could be to have small special purpose quantum machines. For example, considering that cryptography plays such an important role in today’s world, a quantum factoring module would have important consequences. History does have a tendency to repeat itself; were not the first classical computers used for code breaking?

Acknowledgments: I would like to thank the many people who attended my seminar on quantum computation at CWI in the spring of 1995. Their questions and comments helped to put together the material for sections 2 and 3. I would also like to thank Janos Simon, Lance Fortnow, Stuart Kurtz, Amber Settle and Sophie Laplante for many interesting discussions as well as providing me with an office during my short visit to the computer science department of the University of Chicago, where part of this article was written. Also many thanks to Gilles Brassard, Paul Vitanyi, Jim Royer, Amber Settle, Sophie Laplante, Harry Buhrman, Jaap-Henk Hoepman, Barbara Terhal and Alain Tapp for their numerous comments and improvements on early drafts.

7 References

[Adl94] L. M. Adleman. Algorithmic number theory — the complexity contribution. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 88–113, 1994.

[BB92a] A. Berthiaume and G. Brassard. Oracle quantum computing. In Proceedings of the Workshop on Physics and Computation – Physcomp ’92, pages 195–199. IEEE Press, October 1992.

[BB92b] A. Berthiaume and G. Brassard. The quantum challenge to structural complexity. In Proceedings of the 7th Annual IEEE Conference on Structure in Complexity, pages 132–137, 1992.

[BB94] A. Berthiaume and G. Brassard. Oracle quantum computing. Journal of Modern Optics, 41(12):2521–2535, 1994.

[BBB^{+}92] C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin. Experimental quantum cryptography. Journal of Cryptology, 5(1):3–28, 1992.

[BBC^{+}95] A. Barenco, C. H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review Letters A, 1995.

[BBE92] C. H. Bennett, G. Brassard, and A Ekert. Quantum cryptography. Scientific American, pages 50–57, October 1992.

[BDJ94] A. Berthiaume, D. Deutsch, and R. Jozsa. The stabilisation of quantum computations. In Proceedings of the Workshop on Physics and Computation – Physcomp ’94, pages 60 – 62, 1994.

[Ben73] C. H. Bennett. Logical reversibility of computations. IBM Journal of Res. Develop., 17:525–532, 1973.

[Ben82] P. A. Benioff. Quantum mechanical hamiltonian models of turing machines. Journal of Statistical Physics, 29(3):515–546, 1982.

[Ben96] P. A. Benioff. Review of quantum computation. To appear in Trends in Statistical Physics by Council of Scientific Information, Trivandrum, India, 1996.

[Ber95] A. Berthiaume. L’ordinateur quantique: complexité et stabilisation des calculs. PhD thesis, Dept. d’informatique et de recherche opérationelle, Université de Montréal, 1995.

[BL85] C. H. Bennett and R. Landauer. Physical limits of computation. Scientific American, page 48, July 1985.

[Bra93] G. Brassard. Cryptology column — quantum cryptography: A bibliography. Sigact News, 24(3):16–20, 1993.

[BV93] E. Berstein and U. Vazirani. Quantum complexity theory. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computation, pages 11–20, 1993.

[Cop94] D. Coppersmith. An approximate fourier transform useful in quantum computing. Technical report, IBM Research Division, 1994.

[CY94] I. Chuang and Y. Yamamoto. A simple quantum computer, 1994. Submitted to Physical Review A.

[Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society, London, A400:97–117, 1985.

[Deu89] D. Deutsch. Quantum computational network. Proceedings of the Royal Society, London, A425:73–90, 1989.

[DiV95] D. P. DiVincenzo. Two-bit gates are universal for quantum computation. Physical Review Letters A, 50(1015), 1995.

[DJ92] D. Deutsch and R. Jozsa. Rapid solutions of problems by quantum computation. In Proceedings of the Royal Society, London, volume A439, pages 553–558, 1992.

[EJ96] A. Ekert and R. Jozsa. Shor’s quantum algorithme for factorising numbers. Review of Modern Physics, 1996. to appear.

[Fey82] R. P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6/7):467–488, 1982.

[Fey86] R. P. Feynman. Quantum mecanical computers. Foundation of Physics, 16(6):507–531, 1986.

[FLS64] R. P. Feynman, R. B. Leighton, and M. Sands. The Feynman Lectures on Physics, volume 3. Addison-Wesley, 1964.

[Knu81] D. E. Knuth. The Art of Computer Programming, volume 2. Addison-Wesley, 1981.

[Lan61] R. Landauer. Irreversability and heat generation in the computing process. IBM Journal of Research Development, 5(183), 1961.

[Lec63] Y. Lecerf. Machines de Turing réversibles. Récursive insolubilité en n ∈ N de l’équation u = θ^{n} où θ est un isomorphisme de codes. In Comptes rendus de l’Académie française des sciences, volume 257, pages 2597 – 2600, 1963.

[LL93] A. K. Lenstra and H. W. Lenstra, Jr. The devellopment of the number field sieve. Springer-Verlag’s Lecture Notes in Mathematics, (1554), 1993.

[LLMP90] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard. The number field sieve. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computation, pages 564–572, 1990.

[Llo93] S. Lloyd. A potentially realizable quantum computer. Science, 261:1569 – 1571, September 1993.

[Mil76] G. L. Miller. Riemann’s hypothesis and tests for primality. Journal of Computer Science, 13:300–317, 1976.

[MSE95] Palma G. M., K.-A. Suominen, and A. Ekert. Decoherence in quantum registers, 1995. preprint.

[PGCZ95] T. Pellizzari, S. A. Gardiner, J. I. Cirac, and P. Zoller. Decoherence, continuous observation and quantum computing: A cavity QED model, 1995. Submitted to Physical Review Letters.

[Sch95] B. Schumacher. On quantum coding. Physical Review Letters A, 1995. (in press to appear).

[Sho94] P. W. Shor. Algorithms for quantum computation: Discrete log and factoring. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 20–22, 1994.

[Sho95] P. W. Shor. Polynomial-time algorithms for prime factorisation and discrete laogarithms on a quantum computer. Submitted to SIAM Journal of Computing, 1995.

[Sim94] D. Simon. On the power of quantum computation. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 116–123, 1994.

[SW94] T. Sleator and H. Weinfurther. Realizable universal quantum logic gates, 1994. preprint.

[Unr95] W. G. Unruh. Maintaining coherence in quantum computers. Physical Review Letters A, 51:992–997, 1995.

[Yao93] A. C.-C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, page 352, 1993.

Index

Quantum Computation acyclic gate array, 14 building, 26 Deutsch-Jozsa Problem, 15 factoring, 24, 28 Fourier transform, 25 gate

array, 14

elementary, 14 Lecerf-Bennett theorem, 15 mdjp, 15 quantum Turing machine, 13 qubit, 7 register, 12 solution to mdjp, 19 solution to Simon’s problem,

22 Quantum Mechanics (QM)

amplitude, 3, 4 basis states, 4, 12 bracket notation, ⟨·|·⟩, 3 decoherence, 27 entanglement, 13, 27 event, 3, 10 Hilbert space, 6, 13 interference, 3, 20 observable, 8

standard, 8, 12 operator, see QM, unitary ma-

trix probability, 3, 6, 10 state vector, 6

collapse, 8

evolution, see QM, unitary

matrix joint state, 12

superposition, 6, 7, 17, 26 tensor product, 12 two-slit experiment, 2 unitary matrix, 10, 12, 15

Quantum Cryptography, 9