A ROSETTA STONE FOR QUANTUM MECHANICS WITH AN INTRODUCTION TO QUANTUM COMPUTATION VERSION 1.5
arXiv:quantph/0007045v1 17 Jul 2000
SAMUEL J. LOMONACO, JR.
Abstract. The purpose of these lecture notes is to provide readers, who have some mathematical background but little or no exposure to quantum mechanics and quantum computation, with enough material to begin reading the research literature in quantum computation and quantum information theory. This paper is a written version of the ?rst of eight one hour lectures given in the American Mathematical Society (AMS) Short Course on Quantum Computation held in conjunction with the Annual Meeting of the AMS in Washington, DC, USA in January 2000, and will be published in the AMS PSAPM volume entitled “Quantum Computation.”. Part 1 of the paper is a preamble introducing the reader to the concept of the qubit, Part 2 gives an introduction to quantum mechanics covering such topics as Dirac notation, quantum measurement, Heisenberg uncertainty, Schr¨ odinger’s equation, density operators, partial trace, multipartite quantum systems, the Heisenberg versus the Schr¨ odinger picture, quantum entanglement, EPR paradox, quantum entropy. Part 3 gives a brief introduction to quantum computation, covering such topics as elementary quantum computing devices, wiring diagrams, the nocloning theorem, quantum teleportation, Shor’s algorithm, Grover’s algorithm. Many examples are given to illustrate underlying principles. A table of contents as well as an index are provided for readers who wish to “pick and choose.” Since this paper is intended for a diverse audience, it is written in an informal style at varying levels of di?culty and sophistication, from the very elementary to the more advanced.
Date : June 20, 2000. 2000 Mathematics Subject Classi?cation. Primary: 8101, 81P68. Key words and phrases. Quantum mechanics, quantum computation, quantum algorithms, entanglement, quantum information. This work was partially supported by ARO Grant #P38804PHQC and the LOOP Fund. The author gratefully acknowledges the hospitality of the University of Cambridge Isaac Newton Institute for Mathematical Sciences, Cambridge, England, where some of this work was completed. I would also like to thank the other AMS Short Course lecturers, Howard Brandt, Dan Gottesman, Lou Kau?man, Alexei Kitaev, Peter Shor, Umesh Vazirani and the many Short Course participants for their support. (Copyright 2000.)
1
2
SAMUEL J. LOMONACO, JR.
Contents Part 1. 1.
Preamble
4 4 5 5 5 6 6 7 7 8 8 8 10 12 13 15 16 17 18
Introduction
2. The classical world 2.1. Introducing the Shannon bit. 2.2. Polarized light: Part I. The classical perspective 3. The quantum world 3.1. Introducing the qubit – But what is a qubit? 3.2. Where do qubits live? – But what is a qubit? 3.3. A qubit is ... Part 2.
An Introduction to Quantum Mechanics
4. The beginnings of quantum mechanics 4.1. A Rosetta stone for Dirac notation: Part I. Bras, kets, and bra(c)kets 4.2. Quantum mechanics: Part I. The state of a quantum system 4.3. A Rosetta stone for Dirac notation: Part II. Operators 4.4. Quantum mechanics: Part II. Observables 4.5. Quantum mechanics: Part III. Quantum measurement – General principles 4.6. Polarized light: Part III. Three examples of quantum measurement 4.7. A Rosetta stone for Dirac notation: Part III. Expected values 4.8. Quantum Mechanics: Part IV. The Heisenberg uncertainty principle 4.9. Quantum mechanics: Part V. Dynamics of closed quantum systems: Unitary transformations, the Hamiltonian, and Schr¨ odinger’s equation 4.10. The mathematical perspective 5. The Density Operator 5.1. Introducing the density operator 5.2. Properties of density operators 5.3. Quantum measurement in terms of density operators 5.4. Some examples of density operators 5.5. The partial trace of a linear operator 5.6. Multipartite quantum systems 5.7. Quantum dynamics in density operator formalism 5.8. The mathematical perspective
19 19 20 20 21 22 23 24 26 27 27
A ROSSETTA STONE FOR QUANTUM MECHANICS
3
6.
The Heisenberg model of quantum mechanics
28
7. Quantum entanglement 31 7.1. The juxtaposition of two quantum systems 31 7.2. An example: An nqubit register Q consisting of the juxtaposition of n qubits. 32 7.3. An example of the dynamic behavior of a 2qubit register 33 7.4. De?nition of quantum entanglement 35 7.5. Einstein, Podolsky, Rosen’s (EPR’s) grand challenge to quantum mechanics. 36 7.6. Why did Einstein, Podolsky, Rosen (EPR) object? 37 7.7. Quantum entanglement: The Lie group perspective 39 8. Entropy and quantum mechanics 8.1. Classical entropy, i.e., Shannon Entropy 8.2. Quantum entropy, i.e., Von Neumann entropy 8.3. How is quantum entropy related to classical entropy? 8.4. When a part is greater than the whole – Ignorance = uncertainty 9. There is much more to quantum mechanics 43 43 44 46 46 48
Part of a Rosetta Stone for Quantum Computation
Part 3. 10. The Beginnings of Quantum Computation  Elementary Quantum Computing Devices 10.1. Embedding classical (memoryless) computation in quantum mechanics 10.2. Classical reversible computation without memory 10.3. Embedding classical irreversible computation within classical reversible computation 10.4. The unitary representation of reversible computing devices 10.5. Some other simple quantum computing devices 10.6. Quantum computing devices that are not embeddings 10.7. The implicit frame of a wiring diagram 11. 12. The NoCloning Theorem Quantum teleportation
48 48 49 49 51 51 53 54 54 55 57 60 61 62 62 64 65
13. Shor’s algorithm 13.1. Preamble to Shor’s algorithm 13.2. Number theoretic preliminaries 13.3. Overview of Shor’s algorithm 13.4. Preparations for the quantum part of Shor’s algorithm 13.5. The quantum part of Shor’s algorithm
4
SAMUEL J. LOMONACO, JR.
13.6. 13.7. 13.8. 13.9. 13.10.
Peter Shor’s stochastic source S A momentary digression: Continued fractions Preparation for the ?nal part of Shor’s algorithm The ?nal part of Shor’s algorithm An example of Shor’s algorithm
67 69 70 75 76 80 80 81 82 83 87 88 90 90 95
14. Grover’s Algorithm 14.1. Problem de?nition 14.2. The quantum mechanical perspective 14.3. Properties of the inversion Iψ 14.4. The method in Luv’s “madness” 14.5. Summary of Grover’s algorithm 14.6. An example of Grover’s algorithm 15. There is much more to quantum computation
References Index
Part 1.
Preamble
1. Introduction
These lecture notes were written for the American Mathematical Society (AMS) Short Course on Quantum Computation held 1718 January 2000 in conjunction with the Annual Meeting of the AMS in Washington, DC in January 2000. The notes are intended for readers with some mathematical background but with little or no exposure to quantum mechanics. The purpose of these notes is to provide such readers with enough material in quantum mechanics and quantum computation to begin reading the vast literature on quantum computation, quantum cryptography, and quantum information theory. The paper was written in an informal style. Whenever possible, each new topic was begun with the introduction of the underlying motivating intuitions, and then followed by an explanation of the accompanying mathematical ?nery. Hopefully, once having grasped the basic intuitions, the reader will ?nd that the remaining material easily follows. Since this paper is intended for a diverse audience, it was written at varying levels of di?culty and sophistication, from the very elementary to the more advanced. A large number of examples have been included. An
A ROSSETTA STONE FOR QUANTUM MECHANICS
5
index and table of contents are provided for those readers who prefer to “pick and choose.” Hopefully, this paper will provide something of interest for everyone. Because of space limitations, these notes are, of necessity, far from a complete overview of quantum mechanics. For example, only ?nite dimensional Hilbert spaces are considered, thereby avoiding the many pathologies that always arise when dealing with in?nite dimensional objects. Many important experiments that are traditionally part of the standard fare in quantum mechanics texts (such as for example, the SternGerlach experiment, Young’s two slit experiment, the Aspect experiment) have not been mentioned in this paper. We leave it to the reader to decide if these notes have achieved their objective. The ?nal version of this paper together with all the other lecture notes of the AMS Short Course on Quantum Computation will be published as a book in the AMS PSAPM Series entitled “Quantum Computation.”
2. The classical world 2.1. Introducing the Shannon bit. Since one of the objectives of this paper is to discuss quantum information, we begin with a brief discussion of classical information. The Shannon bit is so well known in our age of information that it needs little, if any, introduction. As we all know, the Shannon bit is like a very decisive individual. It is either 0 or 1, but by no means both at the same time. The Shannon bit has become so much a part of our every day lives that we take many of its properties for granted. For example, we take for granted that Shannon bits can be copied. 2.2. Polarized light: Part I. The classical perspective.
Throughout this paper the quantum polarization states of light will be used to provide concrete illustrations of underlying quantum mechanical principles. So we also begin with a brief discussion of polarized light from the classical perspective. Light waves in the vacuum are transverse electromagnetic (EM) waves with both electric and magnetic ?eld vectors perpendicular to the direction of propagation and also to each other. (See ?gure 1.)
6
SAMUEL J. LOMONACO, JR.
Figure 1. A linearly polarized electromagnetic wave. If the electric ?eld vector is always parallel to a ?xed line, then the EM wave is said to be linearly polarized. If the electric ?eld vector rotates about the direction of propagation forming a right(left)handed screw, it is said to be right (left) elliptically polarized. If the rotating electric ?eld vector inscribes a circle, the EM wave is said to be rightor leftcircularly polarized. 3. The quantum world 3.1. Introducing the qubit – But what is a qubit? Many of us may not be as familiar with the quantum bit of information, called a qubit. Unlike its sibling rival, the Shannon bit, the qubit can be both 0 and 1 at the same time. Moreover, unlike the Shannon bit, the qubit can not be duplicated1 . As we shall see, qubits are like very slippery, irascible individuals, exceedingly di?cult to deal with. One example of a qubit is a spin 1 2 particle which can be in a spinup state 1 which we label as “1”, in a spindown state 0 which we label as “0”, or in a superposition of these states, which we interpret as being both 0 and 1 at the same time. (The term “superposition” will be explained shortly.) Another example of a qubit is the polarization state of a photon. A photon can be in a vertically polarized state  . We assign a label of “1” to this state. It can be in a horizontally polarized state ? . We assign a label of “0” to this state. Or, it can be in a superposition of these states. In this case, we interpret its state as representing both 0 and 1 at the same time. Anyone who has worn polarized sunglasses is familiar with the polarization states of light. Polarized sunglasses eliminate glare by letting through only vertically polarized light, while ?ltering out the horizontally polarized
This is a result of the nocloning theorem of Wootters and Zurek[83]. A proof of the nocloning theorem is given in Section 10.8 of this paper.
1
A ROSSETTA STONE FOR QUANTUM MECHANICS
7
light. For that reason, they are often used to eliminate road glare, i.e., horizontally polarized light re?ected from the road. 3.2. Where do qubits live? – But what is a qubit? But where do qubits live? They live in a Hilbert space H. By a Hilbert space, we mean: A Hilbert space H is a vector space over the complex numbers C with a complex valued inner product (?, ?) : H × H →C which is complete with respect to the norm u = induced by the inner product. Remark 1. By a complex valued inner product, we mean a map (?, ?) : H × H →C from H × H into the complex numbers C such that: 1) (u, u) = 0 if and only if u = 0 2) (u, v ) = (v, u)? 3) (u, v + w) = (u, v ) + (u, w) 4) (u, λv ) = λ(u, v ) where ‘? ’ denotes the complex conjugate. Remark 2. Please note that (λu, v ) = λ? (u, v ). (u, u)
3.3. A qubit is ...
2
A qubit is a quantum system Q whose state lies in a two dimensional Hilbert space H.
2 Barenco et al in [1] de?ne a qubit as a quantum system with a two dimensional Hilbert space, capable of existing in a superposition of Boolean states, and also capable of being entangled with the states of other qubits. Their more functional de?nition will take on more meaning as the reader progresses through this paper.
8
SAMUEL J. LOMONACO, JR.
Part 2.
An Introduction to Quantum Mechanics
4. The beginnings of quantum mechanics 4.1. A Rosetta stone for Dirac notation: Part I. Bras, kets, and bra(c)kets . The elements of a Hilbert space H will be called ket vectors, state kets, or simply kets. They will be denoted as: where ‘label’ denotes some label.  label
Let H? denote the Hilbert space of all Hilbert space morphisms of H into the Hilbert space of all complex numbers C, i.e., The elements of H? will be called bra vectors, state bras, or simply bras. They will be denoted as: where once again ‘label’ denotes some label. label  H? = HomC (H, C) .
Also please note that the complex number will simply be denoted by label1  ( label2 ) label1  label2
and will be called the bra(c)ket product of the bra label1  and the ket  label2 .
There is a monomorphism (which is an isomorphism if the underlying Hilbert space is ?nite dimensional) H → H?  label ?→ (  label , ?)
?
de?ned by
A ROSSETTA STONE FOR QUANTUM MECHANICS
9
The bra (  label , ?) is denoted by label .
Hence, label1  label2 = ( label1 ,  label2 ) Remark 3. Please note that (λ  label )? = λ? label. The tensor product3 H ? K of two Hilbert spaces H and K is simply the “simplest” Hilbert space such that 1) (h1 + h2 ) ? k = h1 ? k + h2 ? k, for all h1 , h2 ∈ H and for all k ∈ K, and 2) h ? (k1 + k2 ) = h ? k1 + h ? k2 for all h ∈ H and for all k1 , k2 ∈ K. 3) λ (h ? k) ≡ (λh) ? k = h ? (λk) for all λ ∈ C, h ∈ H, k ∈ K. Remark 4. Hence, label ( label1 ,  label2 ) . = label  label and label1  label2 =
It follows that, if { e1 , e2 , . . . , em } and { f1 , f2 , . . . , fn } are respectively bases of the Hilbert spaces H and K, then { ei ? fj  1 ≤ i ≤ m, 1 ≤ j ≤ n } is a basis of H ? K. Hence, the dimension of the Hilbert space H ? K is the product of the dimensions of the Hilbert spaces H and K, i.e., Dim (H ? K) = Dim (H) · Dim (K) .
Finally, if  label1 and  label2 are kets respectively in Hilbert spaces H1 and H2 , then their tensor product will be written in any one of the following three ways:  label1 ?  label2  label1  label2  label1 , label2
3 Readers well versed in homological algebra will recognize this informal de?nition as a slightly disguised version of the more rigorous universal de?nition of the tensor product. For more details, please refer to [14], or any other standard reference on homological algebra.
10
SAMUEL J. LOMONACO, JR.
4.2. Quantum mechanics: Part I. The state of a quantum system.
The states of a quantum system Q are represented by state kets in a Hilbert space H. Two kets α and β represent the same state of a quantum system Q if they di?er by a nonzero multiplicative constant. In other words, α and β represent the same quantum state Q if there exists a nonzero λ ∈ C such that α = λ β Hence, quantum states are simply elements of the manifold H/? = CP n?1
where n denotes the dimension of H, and CP n?1 denotes complex projective (n ? 1)space . Convention: Since a quantum mechanical state is represented by a state ket up to a multiplicative constant, we will, unless stated otherwise, choose those kets α which are of unit length, i.e., such that α  α = 1 ?? α =1
4.2.1. Polarized light: Part II. The quantum mechanical perspective. As an illustration of the above concepts, we consider the polarization states of a photon. The polarization states of a photon are represented as state kets in a two dimensional Hilbert space H. One orthonormal basis of H consists of the kets  and 
which represent respectively the quantum mechanical states of left and rightcircularly polarized photons. Another orthonormal basis consists of the kets  and ?
representing respectively vertically and horizontally linearly polarized photons. And yet another orthonormal basis consists of the kets ? and ? for linearly polarized photons at the angles θ = π/4 and θ = ?π/4 o? the vertical, respectively.
A ROSSETTA STONE FOR QUANTUM MECHANICS
11
These orthonormal bases are related as follows: ? ? 1 ? ? ? = ? ? = √2 ( + ? ) ? ? ? ? ? ?  = = = = =
1 √ 2 1 √ 2
1+i 2 1?i 2
  ( (
+ +
1?i 2 1+i 2
  ) ) ? ?
(
? ? )
(? + ? )
?
? ? ? ? ? ?  ? ? 
1 √ (? ? ? ) 2 1 √ ( ? i ? ) 2 1 √ 2
(
+ i ? )
? ? ? = ? = ?  ?  =
? ? ? ? 
=
=
1 √ 2 i √ 2 1?i 2 1+i 2
+ ?
1+i 2 1?i 2
? + ? +
The bracket products of the various polarization kets are given in the table below:  ? ? ?   1 1 1 1 √ √ √ √  1 0 2 2 2 2 1 i 1 i √ √ √ √ ? 0 1 ? ? 2 2 2 2 ? ?  
1 √ 2 1 √ 2 1 √ 2 1 √ 2 1 √ 2 1 ?√ 2 i √ 2 i ?√ 2
1 0
0 1
1?i 2 1+i 2
1+i 2 1?i 2
1+i 2 1?i 2
1?i 2 1+i 2
1 0
0 1
In terms of the basis { , ? } and the dual basis {  , ?}, these kets and bras can be written as matrices as indicated below: ? 1 ? ? 1 0 ,  =  = ? ? 0 ? ? ? ? ? ? ? = ? ? ? ? = ? ? ? 0 1 , ? = 0 1
1 √ 2
1 1
,
? , ? 
=
1 √ 2
1 1 1 ?1
? ? ? ? ? ? = ? ? ?  = ? ? ? ? ? ? ? ?  =
1 √ 2 1 √ 2
1 ?1 1 i ,
= =
1 √ 2 1 √ 2
1 ?i 1 i
1 √ 2
1 ?i
,

=
1 √ 2
In this basis, for example, the tensor product ?
is
12
SAMUEL J. LOMONACO, JR.
?
=
1 √ 2 1 √ 2
?
1 √ 2 i ?√ 2
and the projection operator   1 = √ 2 1 i
 is: 1 ?√ 2 1 ?i
? 1 1 ? ?i ? ? = ? 2? 1 ? ?i = 1 2 1 ?i i 1
?
4.3. A Rosetta stone for Dirac notation: Part II. Operators. An (linear) operator or transformation O on a ket space H is a Hilbert space morphism of H into H, i.e., is an element of HomC (H, H) The adjoint O? of an operator O is that operator such that O?  label1 ,  label2 for all kets  label1 and  label2 . In like manner, an (linear) operator or transformation on a bra space H? is an element of HomC (H? , H? ) Moreover, each operator O on H can be identi?ed with an operator, also denoted by O, on H? de?ned by label1  ?→ label1  O where label1  O is the bra de?ned by ( label1  O) ( label2 ) = label1  (O  label2 ) (This is sometimes called Dirac’s associativity law.) Hence, the expression label1  O  label2 is unambiguous. Remark 5. Please note that (O  label )? = label O? = ( label1 , O  label2 )
A ROSSETTA STONE FOR QUANTUM MECHANICS
13
4.4. Quantum mechanics: Part II. Observables. In quantum mechanics, an observable is simply a Hermitian (also called selfadjoint) operator on a Hilbert space H, i.e., an operator O such that An eigenvalue a of an operator A is a complex number for which there is a ket label such that O? = O .
The ket label is called an eigenket of A corresponding to the eigenvalue a. An important theorem about observables is given below: Theorem 1. The eigenvalues ai of an observable A are all real numbers. Moreover, the eigenkets for distinct eigenvalues of an observable are orthogonal. De?nition 1. An eigenvalue is degenerate if there are at least two linearly independent eigenkets for that eigenvalue. Otherwise, it is nondegenerate . Notational Convention: If all the eigenvalues ai of an observable A are nondegenerate, then we can and do label the eigenkets of A with the corresponding eigenvalues ai . Thus, we can write: for each eigenvalue ai . A ai = ai ai
A label = a label .
Convention: In this paper, unless stated otherwise, we assume that the eigenvalues of observables are nondegenerate. One notable exception to the above convention is the measurement operator for the eigenvalue ai , which is the outer product of ket ai with its adjoint the bra ai , where we have assumed that ai (and hence, ai ) is of unit length. It has two eigenvalues 0 and 1. 1 is a nondegenerate eigenvalue with eigenket ai . 0 is a degenerate eigenvalue with corresponding eigenkets { aj }j =i . An observable A is said to be complete if its eigenkets ai form a basis of the Hilbert space H. Since by convention all the eigenkets are chosen to ai ai 
14
SAMUEL J. LOMONACO, JR.
be of unit length, it follows that the eigenkets of a complete nondegenerate observable A form an orthonormal basis of the underlying Hilbert space. Moreover, given a complete nondegenerate observable A, every ket ψ in H can be written as: ψ =
i
ai ai  ψ
Thus, for a complete nondegenerate observable A, we have the following operator equation which expresses the completeness of A, ai ai  = 1
i
In this notation, we also have A=
i
ai ai ai  ,
where once again we have assumed that ai and ai  are of unit length for all i.
Example 1. The Pauli spin matrices σ1 = 0 1 1 0 , σ2 = 0 ?i i 0 , σ3 = 1 0 0 ?1
are examples of observables that frequently appear in quantum mechanics and quantum computation. Their eigenvalues and eigenkets are given in the following table: Pauli Matrices σ1 = 0 1 1 0 Eigenvalue/Eigenket 1 + 1 1 =√ +1 0 √ 2 2 1 1 0 √ ?1 1 =√ 1 2 2 ?1 +1 1
0 +i1 √ 2 0 √ ?i1 2
σ2 =
0 ?i i 0
= =
1 √ 2 1 √ 2
1 i
σ3 =
1 0 0 ?1
+1 0 = 1 1 =
1 0 0 1
1 ?i
A ROSSETTA STONE FOR QUANTUM MECHANICS
15
4.5. Quantum mechanics: Part III. Quantum measurement – General principles. In this section, A will denote a complete nondegenerate observable with eigenvalues ai and eigenkets ai . We will, on occasion, refer to {ai } as the frame (or the basis) of the observable A. According to quantum measurement theory, the measurement of an observable A of a quantum system Q in the state ψ produces the eigenvalue ai as the measured result with probability P rob (Value ai is observed) = ai  ψ
2
,
and forces the state of the quantum system Q into the state of the corresponding eigenket ai . Since quantum measurement is such a hotly debated topic among physicists, we (in selfdefense) quote P.A.M. Dirac[25]: “A measurement always causes the (quantum mechanical) system to jump into an eigenstate of the dynamical variable that is being measured.” Thus, the result of the above mentioned measurement of observable A of a quantum system Q which is in the state ψ before the measurement can be diagrammatically represented as follows: First Meas. of A =? P rob = aj  ψ Second Meas. of A =? P rob = 1
ψ =
i ai
ai  ψ
2
aj aj
≈
aj
aj
Please note that the measured value is the eigenvalue aj with probability 2 aj  ψ . If the same measurement is repeated on the quantum system Q after the ?rst measurement, then the result of the second measurement is no longer stochastic. It produces the previous measured value aj and the state of Q remains the same, i.e., aj . The observable ai ai  is frequently called a selective measurement operator (or a ?ltration) for ai . As mentioned earlier, it has two eigenvalues 0 and 1. 1 is a nondegenerate eigenvalue with eigenket aj , and 0 is a degenerate eigenvalue with eigenkets {aj }j =i .
16
SAMUEL J. LOMONACO, JR.
Thus, ψ but for j = i, Meas. of ai ai  =? P rob = aj  ψ 2 Meas. of ai ai  =? P rob = ai  ψ 2 1 · ai = ai ,
ψ
0 · aj = 0
The above description of quantum measurement is not the most general possible. For the more advanced quantum measurement theory of probabilistic operator valued measures (POVMs) (a.k.a., positive operator valued measures), please refer to such books as for example [43] and [72]. 4.6. Polarized light: Part III. surement. Three examples of quantum mea
We can now apply the above general principles of quantum measurement to polarized light. Three examples are given below:4 Example 2. Vertical Polaroid ?lter =? Measurement op.   =? P rob =
1 2
Rt. Circularly polarized photon  =
1 √ 2
P rob = =?
1 2
Vertically polarized photon  0 No photon
(
+ i ? )
Example 3. A vertically polarized ?lter followed by a horizontally polarized ?lter.
The last two examples can easily be veri?ed experimentally with at most three pair of polarized sunglasses.
4
A ROSSETTA STONE FOR QUANTUM MECHANICS
17
photon α + β ? =?
Vert. polar. ?lter .
P rob = α =?
2
Vert. polar. photon =? 
Horiz. polar. ?lter
No photon P rob = 1 =? . 0
Normalized so that α 2+ β 2=1


? ?
Example 4. But if we insert a diagonally polarized ?lter (by 45o o? the vertical) between the two polarized ?lters in the above example, we have:
α ?  
2

=
1 √ 2
(? + ? ) ? ?
1 2
?
? =
1 √ 2
(
+ ? ) ? ?
1 2
?
?
where the input to the ?rst ?lter is α 
+ β ? .
4.7. A Rosetta stone for Dirac notation: Part III. Expected values. The average value (expected value) of a measurement of an observable A on a state α is: For, since A = α A α
i
ai ai  = 1 ,
we have ? ?
A = α A α = α But on the other hand,
i
ai ai  A ?
j
aj
aj ? α =
i,j
α  ai ai  A aj
aj  α
ai  A aj = aj ai  aj = ai δij
18
SAMUEL J. LOMONACO, JR.
Thus, A =
i
α  ai ai ai  α =
ai
i
ai  α
2
Hence, we have the standard expected value formula, A =
i
ai P rob (Observing ai on input α ) .
4.8. Quantum Mechanics: Part IV. The Heisenberg uncertainty principle. There is, surprisingly enough, a limitation of what we can observe in the quantum world. From classical probability theory, we know that one yardstick of uncertainty is the standard deviation, which measures the average ?uctuation about the mean. Thus, the uncertainty involved in the measurement of a quantum observable A is de?ned as the standard deviation of the observed eigenvalues. This standard deviation is given by the expression U ncertainty (A) = where △A = A ? A (△A)2
Two observables A and B are said to be compatible if they commute, i.e., if AB = BA. Otherwise, they are said to be incompatible. Let [A, B ], called the commutator of A and B , denote the expression [A, B ] = AB ? BA In this notation, two operators A and B are compatible if and only if [A, B ] = 0.
The following principle is one expression of how quantum mechanics places limits on what can be observed:
A ROSSETTA STONE FOR QUANTUM MECHANICS
19
Heisenberg’s Uncertainty Principle5 (△A)2 (△B )2 ≥ 1  [A, B ] 2 4
Thus, if A and B are incompatible, i.e., do not commute, then, by measuring A more precisely, we are forced to measure B less precisely, and vice versa. We can not simultaneously measure both A and B to unlimited precision. Measurement of A somehow has an impact on the measurement of B , and vice versa. 4.9. Quantum mechanics: Part V. Dynamics of closed quantum systems: Unitary transformations, the Hamiltonian, and Schr¨ odinger’s equation. An operator U on a Hilbert space H is unitary U ? = U ?1 . if
Unitary operators are of central importance in quantum mechanics for many reasons. We list below only two: ? Closed quantum mechanical systems transform only via unitary transformations ? Unitary transformations preserve quantum probabilities Let ψ (t) denote the state as a function of time t of a closed quantum mechanical system Q . Then the dynamical behavior of the state of Q is determined by the Schr¨ odinger equation ? ψ (t) = H ψ (t) , ?t where ? denotes Planck’s constant divided by 2π , and where H denotes an observable of Q called the Hamiltonian. The Hamiltonian is the quantum mechanical analog of the Hamiltonian of classical mechanics. In classical physics, the Hamiltonian is the total energy of the system. i? 4.10. The mathematical perspective. From the mathematical perspective, Schr¨ odinger’s equation is written as: ? i U (t) = ? H (t)U (t) , ?t ? where ψ (t) = U ψ (0) ,
5
We have assumed units have been chosen such that ? = 1.
20
SAMUEL J. LOMONACO, JR.
i and where ? ? H (t) is a skewHermitian operator lying in the Lie algebra of the unitary group. The solution is given by a multiplicative integral, called the pathordered integral,
U (t) =
t
0
e? ? H (t)dt ,
i
i H (t) in the Lie algebra of the unitary group. which is taken over the path ? ? The pathordered integral is given by:
t
e? ? H (t)dt = lim 0
i
0 n→∞ n→∞ k =n
i
e? ? H (k n ) n
t i t i t i t
i
t
t
= lim e? ? H (n· n ) · e? ? H ((n?1)· n ) · · · · · e? ? H (1· n ) · e? ? H (0· n )
Remark 6. The standard notation for the above pathordered integral is ? ? t i H (t)dt? P exp ?? ?
0
If the Hamiltonian H (t) = H is independent of time, then all matrices commute and the above pathordered integral simpli?es to
t
e? ? Hdt = e 0
i
t 0
i Hdt ??
= e? ? Ht
i
Thus, in this case, U (t) is nothing more than a one parameter subgroup of the unitary group.
5. The Density Operator 5.1. Introducing the density operator. John von Neumann suggested yet another way of representing the state of a quantum system. Let ψ be a unit length ket (i.e., ψ  ψ = 1) in the Hilbert space H representing the state of a quantum system6 . The density operator ρ associated with the state ket ψ is de?ned as the outer product of the ket
6 Please recall that each of the kets in the set { λ ψ  λ ∈ C, λ = 0 } represent the same state of a quantum system. Hence, we can always (and usually do) represent the state of a quantum system as a unit normal ket, i.e., as a ket such that ψ  ψ = 1 .
A ROSSETTA STONE FOR QUANTUM MECHANICS
21
ψ (which can be thought of as a column vector) with the bra ψ  (which can be thought of as a row vector), i.e., The density operator formalism has a number of advantages over the ket state formalism. One advantage is that the density operator can also be used to represent hybrid quantum/classical states, i.e., states which are a classical statistical mixture of quantum states. Such hybrid states may also be thought of as quantum states for which we have incomplete information. For example, consider a quantum system which is in the states (each of unit length) with probabilities respectively, where p1 + p2 + . . . + pn = 1 (Please note that the states ψ1 , ψ2 , . . . , ψn need not be orthogonal.) Then the density operator representation of this state is de?ned as ρ = p1 ψ1 ψ1  + p2 ψ2 ψ2  + . . . + pn ψn ψn  If a density operator ρ can be written in the form it is said to represent a pure ensemble . Otherwise, it is said to represent a mixed ensemble . 5.2. Properties of density operators. It can be shown that all density operators are positive semide?nite Hermitian operators of trace 1, and vice versa. As a result, we have the following crisp mathematical de?nition: De?nition 2. An linear operator on a Hilbert space H is a density operator if it is a positive semide?nite Hermitian operator of trace 1. It can be shown that a density operator represents a pure ensemble if and only if ρ2 = ρ, or equivalently, if and only if T race(ρ2 ) = 1. For all ensembles, both pure and mixed, T race(ρ2 ) ≤ 1. From standard theorems in linear algebra, we know that, for every density operator ρ, there exists a unitary matrix U which diagonalizes ρ, i.e., such that U ρU ? is a diagonal matrix. The diagonal entries in this matrix are, ρ = ψ ψ  , ψ1 , ψ2 , . . . , ψn p 1 , p 2 , . . . , pn ρ = ψ ψ 
22
SAMUEL J. LOMONACO, JR.
of course, the eigenvalues of ρ. These are nonnegative real numbers which all sum to 1. Finally, if we let D denote the set of all density operators for a Hilbert space H, then iD is a convex subset of the Lie algebra of the unitary group associated with H. 5.3. Quantum measurement in terms of density operators. Let {ai } denote the set of distinct eigenvalues ai of an observable A. Let Pai denote the projection operator that projects the underlying Hilbert space onto the eigenspace determined by the eigenvalue ai . For example, if ai is a nondegenerate eigenvalue, then Pai = ai ai  Finally, let Q be a quantum system with state given by the density operator ρ.
If the quantum system Q is measured with respect to the observable A, then with probability pi = T race (Pai ρ) the resulting measured eigenvalue is ai , and the resulting state of Q is given by the density operator ρi = Pai ρPai . T race (Pai ρ)
Moreover, for an observable A, the averaged observed eigenvalue expressed in terms of the density operator is: A = trace(ρA) Thus, we have extended the de?nition of A so that it applies to mixed as well as pure ensembles, i.e., generalized the following formula to mixed ensembles: A = ψ  A  ψ = trace (ψ ψ  A) = trace(ρA) .
A ROSSETTA STONE FOR QUANTUM MECHANICS
23
5.4. Some examples of density operators. For example, consider the following mixed ensemble of the polarization state of a photon: Example 5. Ket Prob. 
3 4
?
1 4
In terms of the basis ? ,  of the two dimensional Hilbert space H, the density operator ρ of the above mixed ensemble can be written as: ρ = =
3 4 3 4
 1 0
+ 1 4 ? ? 1 0 +
1 4
√ 1/√2 1/ 2 ?
7 8 1 8
√ √ 1/ 2 1/ 2
1 8 1 8
=
3 4
1 0 0 0
+
1 8
1 1 1 1
? =?
? ? ?
Example 6. The following two preparations produce mixed ensembles with the same density operator: Ket Prob. 
1 2
?
1 2
Ket and Prob.
?
1 2
?
1 2
For, for the left preparation, we have
ρ = =
1 2 1 2
 1 0
+ 1 2 ? ? 1 0 +
1 2
0 1
0 1
=
1 2
1 0 0 1
And for the right preparation, we have
24
SAMUEL J. LOMONACO, JR.
ρ = =
1 2
1 ? ? + 2 ? ?
1 1√ 2 2
1 1 1 1 1 1
1 √ 2
1 1
1 4
+
1 1√ 2 2
1 ?1
1 2
1 √ 2
1 ?1
=
1 4
+
1 ?1 ?1 1
=
1 0 0 1
There is no way of physically distinquishing the above two mixed ensembles which were prepared in two entirely di?erent ways. For the density operator represents all that can be known about the state of the quantum system.
5.5. The partial trace of a linear operator. In order to deal with a quantum system composed of many quantum subsystems, we need to de?ne the partial trace. Let be a linear operator on the Hilbert space H. O : H ?→ H ∈ HomC (H, H)
where we recall that
Since Hilbert spaces are free algebraic objects, it follows from standard results in abstract algebra7 that HomC (H, H) ? = H ? H? , H? = HomC (H, C) .
Hence, such an operator O can be written in the form O=
α
aα hα ? kα  ,
where the kets hα lie in H and the bras kα  lie in H? . Thus, the standard trace of a linear operator T race : HomC (H, H) ?→ C
7
See for example [55].
A ROSSETTA STONE FOR QUANTUM MECHANICS
25
is nothing more than a contraction, i.e., T race(O) =
α
aα kα  hα
,
i.e., a replacement of each outer product hα ? kα  by the corresponding bracket kα  hα . We can generalize the T race as follows: Let H now be the tensor product of Hilbert spaces H1 , H2 , . . . ,Hn , i.e.,
n
H=
j =1
Hj .
Then it follows once again from standard results in abstract algebra that
n
HomC (H, H) ? =
j =1
? Hj ? Hj
.
Hence, the operator O can be written in the form
n
O=
aα
α j =1
hα,j ? kα,j  ,
? for where, for each j , the kets hα,j lie in Hj and the bras kα,j  lie in Hj all α.
Next we note that for every subset I of the set of indices J = {1, 2, . . . , n}, we can de?ne the partial trace over I , written ? ? ? ? as the contraction on the indices I , i.e., ? T raceI (O) =
α
T raceI : HomC ?
j ∈J
Hj ,
j ∈J
Hj ? ?→ HomC ? kα,j  hα,j ? ?
j ∈J ?I
Hj ,
j ∈J ?I
Hj ?
aα ?
j ∈I
j ∈J ?I
 hα,j
kα,j  .
For example, let H1 and H0 be two dimensional Hilbert spaces with selected orthonormal bases {01 , 11 } and {00 , 10 }, respectively. Thus, {01 00 , 01 10 , 11 00 , 11 10 } is an orthonormal basis of H = H1 ? H0 .
26
SAMUEL J. LOMONACO, JR.
Let ρ ∈ HomC (H, H) be the operator ρ= = 01 00 ? 11 10 √ 2 ?
01 00  ? 11 10  √ 2
where the rows and columns are listed in the order 01 00 , 01 10 , 11 00 , 11 10 The partial trace T race0 with respect to I = {0} of ρ is
1 (01 00 01 00  ? 01 00 11 10  ? 11 10 01 00  + 11 10 11 10 ) 2 which in terms of the basis {01 00 , 01 10 , 11 00 , 11 10 } can be written as the matrix ? ? 1 0 0 ?1 1? 0 0 0 0 ? ? , ρ= ? 0 ? 2? 0 0 0 ?1 0 0 1
ρ1 = T race0 (ρ) 1 = T race0 (01 00 01 00  ? 01 00 11 10  ? 11 10 01 00  + 11 10 11 10 ) 2 1 = ( 00  00 01 01  ? 10  00 01 11  ? 00  10 11 01  + 10  10 11 11 ) 2 1 = (01 01  ? 01 11 ) 2 which in terms of the basis {01 , 11 } becomes ρ1 = T race0 (ρ) = 1 2 1 0 0 1 ,
where the rows and columns are listed in the order 01 , 11 . 5.6. Multipartite quantum systems. One advantage density operators have over kets is that they provide us with a means for dealing with multipartite quantum systems. De?nition 3. Let Q1 , Q2 , . . . , Qn be quantum systems with underlying Hilbert spaces H1 , H2 , . . . , Hn , respectively. The global quantum system Q consisting of the quantum systems Q1 , Q2 , . . . , Qn is called a multipartite quantum system. Each of the quantum systems Qj (j = 1, 2, . . . , n) is called a constituent “part” of Q . The underlying Hilbert space H of Q is the tensor product of the Hilbert spaces of the constituent “parts,” i.e.,
n
H=
j =1
Hj .
A ROSSETTA STONE FOR QUANTUM MECHANICS
27
If the density operator ρ is the state of a multipartite quantum system Q, then the state of each constituent “part” Qj is the density operator ρj given by the partial trace ρj = T raceJ ?{j } (ρ) , where J = {1, 2, . . . , n} is the set of indices. Obviously, much more can be said about the states of multipartite systems and their constituent parts. However, we will forego that discussion until after we have had an opportunity introduce the concepts of quantum entanglement and von Neumann entropy. 5.7. Quantum dynamics in density operator formalism. Under a unitary transformation U , a density operator ρ transforms according to the rubric: ρ ?→ U ρU ?
Moreover, in terms of the density operator, Schr¨ odinger’s equation8 becomes: ?ρ = [H, ρ] , i? ?t where [H, ρ] denotes the commutator of H and ρ, i.e., [H, ρ] = Hρ ? ρH 5.8. The mathematical perspective.
From the mathematical perspective, one works with iρ instead of ρ because iρ lies in the Lie algebra of the unitary group. Thus, the density operator transforms under a unitary transformation U according to the rubric: iρ ?→ AdU (iρ) , where AdU denotes the big adjoint representation. From the mathematical perspective, Schr¨ odinger’s equation is in this case more informatively written as: ? (iρ) 1 = ? adiH (iρ) , ?t ?
8 Schr¨ odinger’s equation determines the dynamics of closed quantum systems. However, nonclosed quantum systems are also of importance in quantum computation and quantum information theory. See for example the Schumacher’s work on superoperators, e.g., [76].
28
SAMUEL J. LOMONACO, JR.
where ad? i H denotes the little adjoint representation . Thus, the solu? tion to the above form of Schr¨ odinger’s equation is given by the path ordered integral: ρ=
t 0
e? ? (adiH (t) )dt
1
ρ0
where ρ0 denotes the density operator at time t = 0.
6. The Heisenberg model of quantum mechanics
Consider a computing device with inputs and outputs for which we have no knowledge of the internal workings of the device. We are allowed to probe the device with inputs and observe the corresponding outputs. But we are given no information as to how the device performs its calculation. We call such a device a blackbox computing device. For such blackboxes, we say that two theoretical models for blackboxes are equivalent provided both predict the same input/output behavior. We may prefer one model over the other for various reasons, such as simplicity, aesthetics, or whatever meets our fancy. But the basic fact is that each of the two equivalent models is just as “correct” as the other. In like manner, two theoretical models of the quantum world are said to be equivalent if they both predict the same results in regard to quantum measurements. Up to this point, we have been describing the Schr¨ odinger model of quantum mechanics. However, shortly after Schr¨ odinger proposed his model for the quantum world, called the Schr¨ odinger picture, Heisenberg proposed yet another, called the Heisenberg picture. Both models were later proven to be equivalent. In the Heisenberg picture, state kets remain stationary with time, but observables move with time. While state kets, and hence density operators, remain ?xed with respect to time, the observables A change dynamically as: A ?→ U ? AU under a unitary transformation U = U (t), where the unitary transformation is determined by the equation i? ?U = HU ?t
A ROSSETTA STONE FOR QUANTUM MECHANICS
29
It follows that the equation of motion of observables is according to the following equation
i?
?A = [A, H ] ?t
One advantage the Heisenberg picture has over the Schr¨ odinger picture is that the equations appearing in it are similar to those found in classical mechanics.
30
SAMUEL J. LOMONACO, JR.
In summary, we have the following table which contrasts the two pictures:
Schr¨ odinger Picture Moving State ket ψ0 ?→ ψ = U ψ0 Moving ρ0 ?→ ρ = U ρ0 U ? = AdU (ρ0 ) Stationary Observable Observable Eigenvalues A0 Stationary aj
Heisenberg Picture Stationary ψ0 Stationary ρ0 Moving A0 ?→ A = U ? A0 U = AdU ? (A0 ) Stationary aj Moving A0 =
j
Density Operator
Observable Frame
Stationary A0 =
j
aj aj ?→
0
aj 0
aj aj
0
aj 0
At =
j
aj aj
t
t
aj t
0
where aj
(S ) U i? ?U ?t = H ? i? ?t ψ = H (S ) ψ
= U ? aj
Dynamical Equations
(H ) U i? ?U ?t = H (H ) i? ?A ?t = A, H
Measurement
Measurement of observable A0 produces eigenvalue aj with probability aj 0 ψ
2
Measurement of observable A produces eigenvalue aj with probability aj t ψ0
2
=
aj 0 ψ
2
=
aj 0 ψ
2
where H (H ) = U ? H (S ) U
A ROSSETTA STONE FOR QUANTUM MECHANICS
31
It follows that the Schr¨ odinger Hamiltonian H (S ) and the Heisenberg Hamiltonian are related as follows: ?H (H ) ? ?H (S ) =U U , ?t ?t
?U where terms containing ?U ?t and ?t have cancelled out as a result of the Schr¨ odinger equation. We should also mention that the Schr¨ odinger and Heisenberg pictures can be transformed into one another via the mappings:
?
S ?→ H ψ (S ) ?→ ψ (H ) = U ? ψ (S ) ρ(S ) ?→ ρ(H ) = U ? ρ(S ) U A(S ) ?→ A(H ) = U ? A(S ) U A(S ) ?→ A(H ) = U ? A(S ) U
H ?→ S ψ (H ) ?→ ψ (S ) = U ψ (H ) ρ(H ) ?→ ρ(S ) = U ρ(H ) U ? A(H ) ?→ A(S ) = U A(H ) U ? A(H ) ?→ A(S ) = U A(H ) U ?
Obviously, much more could be said on this topic. For quantum computation from the perspective of the Heisenberg model, please refer to the work of Deutsch and Hayden[23], and also to Gottesman’s “study of the ancient Hittites” :) [31]. 7. Quantum entanglement 7.1. The juxtaposition of two quantum systems. Let Q1 and Q2 be two quantum systems that have been separately prepared respectively in states ψ1 and ψ2 , and that then have been united without interacting. Because Q1 and Q2 have been separately prepared without interacting, their states ψ1 and ψ2 respectively lie in distinct Hilbert spaces H1 and H2 . Moreover, because of the way in which Q1 and Q2 have been prepared, all physical predictions relating to one of these quantum systems do not depend in any way whatsoever on the other quantum system. The global quantum system Q consisting of the two quantum systems Q1 and Q2 as prepared above is called a juxtaposition of the quantum systems Q1 and Q2 . The state of the global quantum system Q is the tensor product of the states ψ1 and ψ2 . In other words, the state of Q is: ψ1 ? ψ2 ∈ H1 ? H2
32
SAMUEL J. LOMONACO, JR.
7.2. An example: An nqubit register Q consisting of the juxtaposition of n qubits. Let H be a two dimensional Hilbert space, and let {0 , 1 } denote an arbitrarily selected orthonormal basis9 . Let Hn?1 , Hn?2 , . . . ,H0 be distinct Hilbert spaces, each isomorphic to H, with the obvious induced orthonormal bases { 0n?1 , 1n?1 } , { 0n?2 , 1n?2 } , . . . , { 00 , 10 }
respectively.
Consider n qubits Qn?1 , Qn?2 , . . . , Q0 separately prepared in the states 1 1 1 √ (0n?1 + 1n?1 ) , √ (0n?2 + 1n?2 ) , . . . , √ (00 + 10 ) , 2 2 2 respectively. Let Q denote the global system consisting of the separately prepared (without interacting) qubits Qn?1 , Qn?2 , . . . , Q0 . Then the state ψ of Q is: 1 1 1 ψ = √ (0n?1 + 1n?1 ) ? √ (0n?2 + 1n?2 ) ? . . . ? √ (00 + 10 ) 2 2 2 1 n (0n?1 0n?2 . . . 01 00 + 0n?1 0n?2 . . . 01 10 + . . . + 1n?1 1n?2 . . . 11 10 ) = √ 2 which lies in the Hilbert space H = Hn?1 ? Hn?2 ? . . . ? H0 . Notational Convention: We will usually omit subscripts whenever they can easily be inferred from context. Thus, the global system Q consisting of the n qubits Qn?1 , Qn?2 , . . . , Q0 is in the state ψ = 1 √ 2
n
(00 . . . 00 + 00 . . . 01 + . . . + 11 . . . 11 ) ∈
n?1 0
H
The reader should note that the nqubit register Q is a superposition of kets with labels consisting of all the binary ntuples. If each binary ntuple bn?1 bn?2 . . . b0 is identi?ed with the integer bn?1 2n?1 + bn?2 2n?2 + . . . + b0 20 ,
9
We obviously have chosen to label the basis elements in a suggestive way.
A ROSSETTA STONE FOR QUANTUM MECHANICS
33
i.e., if we interpret each binary ntuple as the radix 2 representation of an integer, then we can rewrite the state as 1 n √ (0 + 1 + 2 + . . . + 2n ? 1 ) . 2 In other words, this nqubit register contains all the integers from 0 to 2n ? 1 in superposition. But most importantly, it contains all the integers 0 to 2n ? 1 simultaneously ! ψ = This is an example of the massive parallelism that is possible within quantum computation. However, there is a downside. If we observe (measure) the register, then all the massive parallelism disappears. On measurement, the quantum world selects for us one and only one of the 2n integers. The probability of observing any particular one of the integers is √ n2 n = (1 1/ 2 2 ) . The selection of which integer is observed is unfortunately not made by us, but by the quantum world. Thus, harnessing the massive parallelism of quantum mechanics is no easy task! As we will see, a more subtle approach is required. 7.3. An example of the dynamic behavior of a 2qubit register. We now consider the previous nqubit register for n = 2. bases described in the previous section, we have: ? ? 1 ? ? ? ? ? 1 1 0 ? ? 0 = 00 = ? = ? ? ? ? 0 0 0 ? ? ? ? 0 ? ? ? ? ? ? ? ? ? 0 ? ? ? ? ? 1 0 1 ? ? 1 = 01 = ? = ? ? ? ? 0 0 1 ? ? ? ? 0 ? = ? ? ? 0 ? ? ? ? 0 ? 0 1 ? ? 2 = 10 = ? = ? ? ? ? 1 1 0 ? ? ? ? 0 ? ? ? ? ? ? ? ? ? 0 ? ? ? ? ? 0 0 0 ? ? 3 = 11 = ? = ? ? ? ? 1 0 1 ? ? ? 1 In terms of the ? ? ? ? ? ? ? ?
? ? ? ?
? ? ? ?
34
SAMUEL J. LOMONACO, JR.
Let us assume that the initial state ψ ψ = 0 ? 1 √ 2
t=0
where the rows and the columns are listed in the order 00 , 01 , 10 , 11 , i.e., in the order 0 , 1 , 2 , 3 . Then, as a consequence of Schr¨ odinger’s equation, the Hamiltonian H determines a unitary transformation UCN OT =
t 0
Let us also assume that from time t = 0 to time t = 1 the dynamical behavior of the above 2qubit register is determined by a constant Hamiltonian H , which when written in terms of the basis {00 , 01 , 10 , 11 } = {0 , 1 , 2 , 3 } is given by ? ? 0 0 0 0 π? ? 0 0 ? ? 0 0 ? , H= ? 0 0 1 ?1 ? 2 0 0 ?1 1
? 1 1 1 ? 0 ? 1 ? ? 0 = √ (00 ? 10 ) = √ (0 ? 2 ) = √ ? 2 2 2 ? ?1 ? 0
t=0
of our 2qubit register is ?
e? ? Hdt = e 0 1 0 0 0 0 0 1
i
1 0
i Hdt ??
= e? ? H
i
which moves the 2qubit register from the initial state ψ t=0 at time t = 0 to ψ t=1 = UCN OT ψ t=0 at time t = 1. Then ? ? ? ? 1 1 0 0 0 ? 0 1 0 0 ? 1 ? 0 ? ? ? ? ψ t=1 = UCN OT ψ t=0 = ? ? 0 0 0 1 ? · √2 ? ?1 ? 0 0 0 1 0 ? ? 1 ? 1 1 1 0 ? ?= √ =√ ? (00 ? 11 ) = √ (0 ? 3 ) ? ? 0 2 2 2 ?1 The resulting state (called an EPR pair of qubits for reasons we shall later explain) can no longer be written as a tensor product of two states. Consequently, we no longer have the juxtaposition of two qubits.
1 ? 0 =? ? 0 0
?
? 0 0 ? ? = 0 0 + 1 1 + 2 3 + 3 2 1 ? 0
A ROSSETTA STONE FOR QUANTUM MECHANICS
35
Somehow, the resulting two qubits have in some sense “lost their separate identities.” Measurement of any one of the qubits immediately impacts the other. For example, if we measure the 0th qubit (i.e., the rightmost qubit), the EPR state in some sense “jumps” to one of two possible states. Each of the 1 , as indicated in the table below: two possibilities occurs with probability 2
1 √ 2
(01 00 ? 11 10 ) Meas. 0th Qubit
1 2
??? P rob = 01 00
???
1 2
P rob = 11 10
Thus we see that a measurement of one of the qubits causes a change in the other.
7.4. De?nition of quantum entanglement. The above mentioned phenomenon is so unusual and so nonclassical that it warrants a name. De?nition 4. Let Q1 , Q2 , . . . , Qn be quantum systems with underlying Hilbert spaces H1 , H2 , . . . , Hn , respectively. Then the global quantum system Q consisting of the quantum systems Q1 , Q2 , . . . , Qn is said to be entangled if its state ψ ∈ H = n j =1 Hj can not be written in the form
n
ψ =
j =1
ψj , We
where each ket ψj lies in the Hilbert space Hj for, j = 1, 2, . . . , n. also say that such a state ψ is entangled. Thus, the state ψ
t=1
1 = √ (00 ? 11 ) 2
of the 2qubit register of the previous section is entangled.
36
SAMUEL J. LOMONACO, JR.
Remark 7. In terms of density operator formalism, a pure ensemble ρ is entangled if it can not be written in the form
n
ρ=
j =1
ρj ,
where the ρj ’s denote density operators. Please note that we have de?ned entanglement only for pure ensembles. For mixed ensembles, entanglement is not well understood10 . As a result, the “right” de?nition of entanglement of mixed ensembles is still unresolved. We give one de?nition below: De?nition 5. A density operator ρ on a Hilbert space H is said to be entangled with respect to the Hilbert space decomposition
n
H= if it can not be written in the form
?
j =1
Hj ?
ρ=
k =1
for some positive integer ?, where the λk ’s are positive real numbers such that
?
λk ?
?
n j =1
ρ(j,k) ? ,
λk = 1 .
k =1
and where each ρ(j,k) is a density operator on the Hilbert space Hj . Readers interested in pursuing this topic further should refer to the works of Bennett , the Horodecki’s, Nielsen, Smolin, Wootters , and others[6], [45], [59], [67]. 7.5. Einstein, Podolsky, Rosen’s (EPR’s) grand challenge to quantum mechanics. Albert Einstein was skeptical of quantum mechanics, so skeptical that he together with Podolsky and Rosen wrote a joint paper[26] appearing in 1935 challenging the very foundations of quantum mechanics. Their paper hit the scienti?c community like a bombshell. For it delivered a direct frontal attack at the very heart and center of quantum mechanics.
10
Quantum entanglement is not even well understood for pure ensembles.
A ROSSETTA STONE FOR QUANTUM MECHANICS
37
At the core of their objection was quantum entanglement. Einstein and his colleagues had insightfully recognized the central importance of this quantum phenomenon. Their argument centered around the fact that quantum mechanics violated either the principle of nonlocality11 or the principle of reality12 . They argued that, as a result, quantum mechanics must be incomplete, and that quantum entanglement could be explained by missing hidden variables. For many years, no one was able to conceive of an experiment that could determine which of the two theories, i.e., quantum mechanics or EPR’s hidden variable theory, was correct. In fact, many believed that the two theories were not distinguishable on physical grounds. It was not until Bell developed his famous inequalities [3],[4], [13], that a physical criterion was found to distinquish the two theories. Bell developed inequalities which, if violated, would clearly prove that quantum mechanics is correct, and hidden variable theories are not. Many experiments were performed. Each emphatically supported quantum mechanics, and clearly demonstrated the incorrectness of hidden variable theory. Quantum mechanics was the victor! 7.6. Why did Einstein, Podolsky, Rosen (EPR) object? But why did Einstein and his colleagues object so vehemently to quantum entanglement? As a preamble to our answer to this question, we note that Einstein and his colleagues were convinced of the validity of the following two physical orinciples: 1) The principle of local interactions , i.e., that all the known forces of nature are local interactions, 2) The principle of nonlocality, i.e., that spacelike separated regions of spacetime are physically independent of one another. Their conviction in regard to principle 1) was based on the fact that all four known forces of nature, i.e., gravitational, electromagnetic, weak, and strong forces, are local interactions. By this we mean: i) They are mediated by another entity, e.g., graviton, photon, etc. ii) They propagate no faster than the speed c of light iii) Their strength drops o? with distance
We will later explain the principle of nonlocality. For an explanation of the principle of reality as well as the principle of nonlocalty, please refer, for example, to [72], [13].
12 11
38
SAMUEL J. LOMONACO, JR.
Their conviction in regard to principle 2) was based on the following reasoning: Two points in spacetime P1 = (x1 , y1 , z1 , t1 ) and P2 = (x2 , y2 , z2 , t2 ) are separated by a spacelike distance provided the distance between (x1 , y1 , z1 ) and (x2 , y2 , z2 ) is greater than c t2 ? t1 , i.e., where c denotes the speed of light. In other words, no signal can travel between points that are said to be separated by a spacelike distance unless the signal travels faster than the speed of light. But because of the basic principles of relativity, such superluminal communication is not possible. Hence we have: The principle of nonlocality: Spacelike separated regions of spacetime are physically independent. In other words, spacelike separated regions can not in?uence one another. 7.6.1. EPR’s objection. We now are ready to explain why Einstein and his colleagues objected so vehemently to quantum entanglement. We explain Bohm’s simpli?ed version of their argument.
13
Distance ((x1 , y1 , z1 ) , (x2 , y2 , z2 )) > c t2 ? t1  ,
Consider a two qubit quantum system that has been prepared by Alice in her laboratory in the state 1 ψ = √ (01 00 ? 11 10 ) . 2 After the preparation, she decides to keep qubit #1 in her laboratory, but enlists Captain James T. Kirk of the Starship Enterprise to transport qubit #0 to her friend Bob 14 who is at some far removed distant part of the universe, such as at a Federation outpost orbiting about the double star Alpha Centauri in the constellation Centaurus. After Captain Kirk has delivered qubit #0, Alice’s two qubits are now separated by a spacelike distance. Qubit #1 is located in her Earth based laboratory. Qubits #0 is located with Bob at a Federation outpost orbiting Alpha Centauri. But the two qubits are still entangled, even in spite of the fact that they are separated by a spacelike distance. If Alice now measures qubit #1 (which is located in her Earth based laboratory), then the principles of quantum mechanics force her to conclude that instantly, without any time lapse, both qubits are “e?ected.” As a
13 Alice is a well known personality in quantum computation, quantum cryptography, and quantum information theory. 14 Bob is another well known personality in quantum computation, quantum cryptography, and quantum information theory.
A ROSSETTA STONE FOR QUANTUM MECHANICS
39
result of the measurement, both qubits will be either in the state 01 00 or the state 11 10 , each possibility occurring with probability 1/2. This is a nonlocal “interaction.” For, ? The “interaction” occurred without the presence of any force. It was not mediated by anything. ? The measurement produced an instantaneous change, which was certainly faster than the speed of light. ? The strength of the “e?ect” of the measurement did not drop o? with distance. No wonder Einstein was highly skeptical of quantum entanglement. Yet puzzlingly enough, since no information is exchanged by the process, the principles of general relativity are not violated. As a result, such an “e?ect” can not be used for superluminal communication. For a more indepth discussion of the EPR paradox and the foundations of quantum mechanics, the reader should refer to [13]. 7.7. Quantum entanglement: The Lie group perspective. Many aspects of quantum entanglement can naturally be captured in terms of Lie groups and their Lie algebras. Let H = Hn?1 ? Hn?2 ? . . . ? H0 =
n?1 0
Hj
be a decomposition of a Hilbert space H into the tensor product of the Hilbert spaces Hn?1 , Hn?2 , . . . ,H0 . Let U = U(H), Un?1 = U(Hn?1 ), Un?2 = U(Hn?2 ), . . . ,U0 = U(H0 ), denote respectively the Lie groups of all unitary transformations on H, Hn?1 , Hn?2 , . . . ,H0 . Moreover, let u = u(H), un?1 = un?1 (Hn?1 ), un?2 = un?2 (Hn?2 ), . . . , u0 = u0 (H0 ) denote the corresponding Lie algebras. De?nition 6. The local subgroup L = L(H) of U = U(H) is de?ned as the subgroup L = U n?1 ? U n?2 ? . . . ? U 0 =
n?1 0
Uj .
The elements of L are called local unitary transformations . Unitary transformations which are in U but not in L are called global unitary transformations. The corresponding lie algebra ? = un?1 ? un?2 ? . . . ? u0
40
SAMUEL J. LOMONACO, JR.
is called the local Lie algebra, where ‘?’ denotes the Kronecker sum15 .
Local unitary transformations can not entangle quantum systems with respect to the above tensor product decomposition. However, global unitary transformations are those unitary transformations which can and often do produce interactions which entangle quantum systems. This leads to the following de?nition: De?nition 7. Two states ψ1 and ψ2 in H are said to be locally equivalent ( or, of the same entanglement type) , written ψ1
local
? ψ2 ,
if there exists a local unitary transformation U ∈ L such that The equivalence classes of local equivalence ? are called the entanglelocal
U ψ1 = ψ2 .
ment classes of H. Two density operators ρ1 and ρ2 , (and hence, the corresponding two skew Hermitian operators iρ1 and iρ2 lying in u) are said to be locally equivalent ( or, of the same entanglement type), written ρ1 ? ρ2 ,
local
if there exists a local unitary transformation U ∈ L such that AdU (ρ1 ) = ρ2 , where AdU denotes the big adjoint representation, i.e., AdU (iρ) = U (iρ)U ? . The equivalence classes under this relation are called entanglement classes of the Lie algebra u(H). Thus, the entanglement classes of the Hilbert space H are just the orbits of the group action of L(H) on H. In like manner, the entanglement classes of the Lie algebra u(H) are the orbits of the big adjoint action of L(H) on u(H). Two states are entangled in the same way if and only if they lie in the same entanglement class, i.e., the same orbit. For example, let us assume that Alice and Bob collectively possess two qubits QAB which are in the entangled state ? ? 1 1 ? 0B 0A + 1B 1A 0 ? ? , √ =√ ? ψ1 = ? 0 ? 2 2 1
15
The Kronecker sum A ? B is de?ned as
A?B =A?1+1?B , where 1 denotes the identity transformation.
A ROSSETTA STONE FOR QUANTUM MECHANICS
41
and moreover that Alice possesses qubit labeled A, but not the qubit labeled B , and that Bob holds qubit B , but not qubit A. Let us also assume that Alice and Bob are also separated by a spacelike distance. As a result, they can only apply local unitary transformations to the qubits that they possess. Alice could, for example, apply the local unitary transformation ? ? 0 0 1 0 ? 0 0 1 1 0 0 0 1 ? ? UA = ? =? ? ?1 0 0 1 ?1 0 0 0 ? 0 ?1 0 0
to her qubit to move Alice’s and Bob’s qubits A and B respectively into the state ? ? 0 1 ? 1 ? 0B 1A ? 1B 0A ? , √ =√ ? ψ2 = 2 2 ? ?1 ? 0 Bob also could accomplish the same by applying the local unitary transformation ? ? 0 ?1 0 0 ? 1 1 0 0 0 0 ? 0 ?1 ? UB = ? =? ? 0 0 1 0 0 ?1 ? 1 0 0 0 1 0 By local unitary transformations, Alice and Bob can move the state of their two qubits to any other state within the same entanglement class. But with local unitary transformations, there is no way whatsoever that Alice and Bob can transform the two qubits into a state lying in a di?erent entanglement class (i.e., a di?erent orbit), such as ψ3 = 0B 0A . The only way Alice and Bob could transform the two qubits from state ψ1 to the state ψ3 is for Alice and Bob to come together, and make the two qubits interact with one another via a global unitary transformation such as ? ? 1 0 0 1 1 ? 0 1 1 0 ? ? UAB = √ ? 2 ? 0 ?1 1 0 ? ?1 0 0 1 The main objective of this approach to quantum entanglement is to determine when two states lie in the same orbit or in di?erent orbits? In other words, what is needed is a complete set of invariants, i.e., invariants that
to his qubit.
42
SAMUEL J. LOMONACO, JR.
completely specify all the orbits ( i.e., all the entanglement classes). save this topic for another lecture[61].
We
At ?rst it would seem that state kets are a much better vehicle than density operators for the study of quantum entanglement. After all, state kets are much simpler mathematical objects. So why should one deal with the additional mathematical luggage of density operators? Actually, density operators have a number of advantages over state kets. The most obvious advantage is that density operators certainly have an upper hand over state kets when dealing with mixed ensembles. But their most important advantage is that the orbits of the adjoint action are actually manifolds, which have a very rich and pliable mathematical structure. Needless to say, this topic is beyond the scope of this paper. Remark 8. It should also be mentioned that the mathematical approach discussed in this section by no means captures every aspect of the physical phenomenon of quantum entanglement. The use of ancilla and of classical communication have not been considered. For an indepth study of the relation between quantum entanglement and classical communication (including catalysis), please refer to the work of Jonathan, Nielson, and others[67]. In regard to describing the locality of unitary operations, we will later have need for a little less precision than that given above in the above de?nitions. So we give the following (unfortunately rather technical) de?nitions: De?nition 8. Let H, Hn?1 , Hn?2 , . . . ,H0 be as stated above. Let P = {Bα } be a partition of the set of indices {0, 1, 2, . . . , n ? 1}, i.e., P is a collection of disjoint subsets Bα of {0, 1, 2, . . . , n ? 1}, called blocks, such that α Bα = {0, 1, 2, . . . , n ? 1}. Then the P tensor product decomposition of H is de?ned as H= where
Bα ∈P
HBα , Hj ,
HBα =
for each block Bα in P . Also the subgroup of P local unitary transformations LP (H) is de?ned as the subgroup of local unitary transformations of H corresponding to the P tensor decomposition of H. We de?ne the ?neness of a partition P , written f ineness(P ), as the maximum number of indices in a block of P . We say that a unitary transformation U of H is su?ciently local if there exists a partition P with suf?ciently small f ineness(P ) (e.g., f ineness(P ) ≤ 3) such that U ∈ LP (H).
j ∈Bα
A ROSSETTA STONE FOR QUANTUM MECHANICS
43
Remark 9. The above lack of precision is needed because there is no way to know what kind (if any) of quantum computing devices will be implemented in the future. Perhaps we will at some future date be able to construct quantum computing devices that locally manipulate more than 2 or 3 qubits at a time?
8. Entropy and quantum mechanics
8.1. Classical entropy, i.e., Shannon Entropy.
Let S be a probability distribution on a ?nite set {s1 , s2 , . . . , sn } of elements called symbols given by Prob (sj ) = pj , where n j =1 pj = 1. Let s denote the random variable (i.e., ?nite memoryless stochastic source) that produces the value sj with probability pj .
De?nition 9. The classical entropy (also called the Shannon entropy) H (S ) of a probability distribution S (or of the source s) is de?ned as:
n
H (S ) = H (s) = ?
pj lg(pj ) ,
j =1
where ‘lg’ denotes the log to the base 2 .
Classical entropy H (S ) is a measure of the uncertainty inherent in the probability distribution S . Or in other words, it is the measure of the uncertainty of an observer before the source s “outputs” a symbol sj . One property of such classical stochastic sources we often take for granted is that the output symbols sj are completely distinguishable from one another. We will see that this is not necessarily the case in the strange world of the quantum.
44
SAMUEL J. LOMONACO, JR.
8.2. Quantum entropy, i.e., Von Neumann entropy. Let Q be a quantum system with state given by the desity operator ρ. Then there are many preparations
Preparation
ψ1 p1
ψ2 p2
... ...
ψn pn
which will produce the same state ρ. These preparations are classical stochastic sources with classical entropy given by H=? pj lg(pj ) .
Unfortunately, the classical entropy H of a preparation does not necessarily re?ect the uncertainty in the resulting state ρ. For two di?erent preparations P1 and P2 , having di?erent entropies H (P1 ) and H (P2 ), can (and often do) produce the same state ρ. The problem is that the states of the preparation my not be completely physically distinguishable from one another. This happens when the states of the preparation are not orthogonal. (Please refer to the Heisenberg uncertainty principle.) John von Neumann found that the true measure of quantum entropy can be de?ned as follows: De?nition 10. Let Q be a quantum system with state given by the density operator ρ. Then the quantum entropy (also called the von Neumann entropy) of Q, written S (Q), is de?ned as where ‘lg ρ’ denotes the log to the base 2 of the operator ρ. Remark 10. The operator lg ρ exists and is an analytic map ρ ?→ lg ρ given by the power series lg ρ = 1 ln 2
∞
S (Q) = ?T race (ρ lg ρ) ,
n=1
(?1)n+1
(ρ ? I )n n
provided that ρ is su?ciently close to the identity operator I , i.e., provided where ρ?I <1 , A = sup
v∈H
Av . v
It can be shown that this is the case for all positive de?nite Hermitian operators of trace 1. For Hermitian operators ρ of trace 1 which are not positive de?nite, but only positive semide?nite (i.e., which have a zero eigenvalue), the logarithm
A ROSSETTA STONE FOR QUANTUM MECHANICS
45
lg(ρ) does not exist. However, there exists a sequence ρ1 , ρ2 , ρ3 , . . . of positive de?nite Hermitian operators of trace 1 which converges to ρ, i.e., such that ρ = lim ρk It can then be shown that the limit
k ?→∞
exists. Hence, S (ρ) is de?ned and exists for all density operators ρ. Quantum entropy is a measure of the uncertainty at the quantum level. As we shall see, it is very di?erent from the classical entropy that arises when a measurement is made. One important feature of quantum entropy S (ρ) is that it is invariant under the adjoint action of unitary transformations, i.e., S ( AdU (ρ) ) = S U ρU ? = S (ρ) . It follows that, for closed quantum systems, it is a dynamical invariant. As the state ρ moves according to Schr¨ odinger’s equation, the quantum entropy S (ρ) of ρ remains constant. It does not change unless measurement is made, or, as we shall see, unless we ignore part of the quantum system. Because of unitary invariance, the quantum entropy can be most easily computed by ?rst diagonalizing ρ with a unitary transformation U , i.e., ? → U ρU ? = △( λ ) , ? → ? → where △( λ ) denotes the diagonal matrix with diagonal λ = (λ1 , λ2 , . . . , λn ). Once ρ has been diagonalized , we have ? → ? → S (ρ) = ?T race △( λ ) lg △( λ ) = ?T race ( △(λ1 lg λ1 , λ2 lg λ2 , . . . , λn lg λn ) )
n
k ?→∞
lim ρk lg ρk
=?
λj lg λj ,
j =1
where the λj ’s are the eigenvalues of ρ, and where 0 lg 0 ≡ 0. Please note that, because ρ is positive semide?nite Hermitian of trace 1, all the eigenvalues of ρ are nonnegative real numbers such that
n
λj = 1 .
j =1
46
SAMUEL J. LOMONACO, JR.
As an immediate corollary we have that the quantum entropy of a pure ensemble must be zero, i.e., ρ pure ensemble =? S (ρ) = 0 There is no quantum uncertainty in a pure ensemble. However, as expected, there is quantum uncertainty in mixed ensembles. 8.3. How is quantum entropy related to classical entropy? But how is classical entropy H related to quantum entropy S ? Let A be an observable of the quantum system Q. Then a measurement of A of Q produces an eigenvalue ai with probability pi = T race (Pai ρ) , where Pai denotes the projection operator for the eigenspace of the eigenvalue ai . For example, if ai is a nondegenerate eigenvalue, then Pai = ai ai  . In other words, measurement of A of the quantum system Q in state ρ can be identi?ed with a classical stochastic source with the eigenvalues ai as output symbols occurring with probability pi . We denote this classical stochastic source simply by (ρ, A) . The two entropies S (ρ) and H (ρ, A) are by no means the same. One is a measure of quantum uncertainty before measurement, the other a measure of the classical uncertainty that results from measurement. The quantum entropy S (ρ) is usually a lower bound for the classical entropy, i.e., S (ρ) ≤ H (ρ, A) . If A is a complete observable (hence, nondegenerate), and if A is compatible with ρ, i.e., [ρ, A] = 0, then S (ρ) = H (ρ, A). 8.4. When a part is greater than the whole – Ignorance = uncertainty. Let Q be a multipartite quantum system with constituent parts Qn?1 , . . . ,Q1 , Q0 , and let the density operator ρ denote the state of Q. Then from section 5.6 of this paper we know that the state ρj of each constituent
A ROSSETTA STONE FOR QUANTUM MECHANICS
47
“part” Qj is given by the partial trace over all degrees of freedom except Qj , i.e., by ρj = T race (ρ) . 0≤k ≤n?1 k=j
By applying the above partial trace, we are focusing only on the quantum system Qj , and literally ignoring the remaining constituent “parts” of Q. By taking the partial trace, we have done nothing physical to the quantum system. We have simply ignored parts of the quantum system. What is surprising is that, by intentionally ignoring “part” of the quantum system, we can in some cases create more quantum uncertainty. This happens when the constituent “parts” of Q are quantum entangled.
For example, let Q denote the bipartite quantum system consisting of two qubits Q1 and Q0 in the entangled state 01 00 ? 11 10 √ . 2 The corresponding density operator ρQ is 1 ρQ = (01 00 01 00  ? 01 00 11 10  ? 11 10 01 00  + 11 10 11 10 ) 2? ? 1 0 0 ?1 1? 0 0 0 0 ? ? = ? ? 0 0 0 0 ? 2 ?1 0 0 1 ΨQ = Since ρQ is a pure ensemble, there is no quantum uncertainty, i.e., S ( ρQ ) = 0 . Let us now focus on qubit #0 (i.e., Q0 ). The resulting density operator ρ0 for qubit #0 is obtained by tracing over Q1 , i.e., ρ0 = T race1 (ρQ ) = 1 1 ( 0 0 + 1 1 ) = 2 2 S (ρ0 ) = 1 . Something most unusual, and nonclassical, has happened. Simply by ignoring part of the quantum system, we have increased the quantum uncertainty. The quantum uncertainty of the constituent “part” Q0 is greater 1 0 0 1 .
Hence, the quantum uncertainty of qubit #0 is
48
SAMUEL J. LOMONACO, JR.
than that of he whole quantum system Q. This is not possible in the classical world, i.e., not possible for Shannon entropy. (For more details, see [15].)
9. There is much more to quantum mechanics
There is much more to quantum mechanics. For more indepth overviews, there are many outstanding books. Among such books are [13], [16], [25], [28], [40], [41], [43], [46], [48], [64], [68], [70], [72], [74], [75], and many more.
Part 3.
Part of a Rosetta Stone for Quantum Computation
10. The Beginnings of Quantum Computation  Elementary Quantum Computing Devices
We begin this section with some examples of quantum computing devices. By a quantum computing device16 we mean a unitary transformation U that is the composition of ?nitely many su?ciently local unitary transformations, i.e., U = Un?1 Un?2 . . . U1 U0 , where Un?1 , Un?2 , . . . ,U1 ,U0 are su?ciently local17 unitary transformations. Each Uj is called a computational step of the device. Our ?rst examples will be obtained by embedding classical computing devices within the realm of quantum mechanics. We will then look at some other quantum computing devices that are not the embeddings of classical devices.
Unfortunately, Physicists have “stolen” the akronym QCD. :) See De?nition 8 in Section 7.7 of this paper for a de?nition of the term ‘su?ciently local’.
17 16
A ROSSETTA STONE FOR QUANTUM MECHANICS
49
10.1. Embedding classical (memoryless) computation in quantum mechanics. One objective in this section is to represent18 classical computing computing devices as unitary transformations. Since unitary transformations are invertible, i.e., reversible, it follows that the only classical computing devices that can be represented as such transformations must of necessity be reversible devices. Hence, the keen interest in reversible computation. For a more in depth study of reversible computation, please refer to the work of Bennett and others. 10.2. Classical reversible computation without memory. ? ? ? ? ? ? ? Input ? ? ? ? ? ? xn ? 1 xn ? 1 . . . x1 x0 ?→ ?→ . . . ?→ ?→ ?→ ?→ . . . y n?1 y n?1 . . . ? ? ? ? ? ? ? ? ? ? ? ? ?
CRCDn
Output
?→ y1 ?→ y0
Each classical ninput/noutput (binary memoryless) reversible computing device (CRCDn ) can be identi?ed with a bijection on the set {0, 1}n of all binary ntuples. Thus, we can in turn identify each CRCDn with an element of the permutation group S2n on the 2n symbols → → { ? a  ? a ∈ {0, 1}n } . Let Bn = B x0 , x1 , . . . , xn?1 π : {0, 1}n ?→ {0, 1}n
denote the free Boolean ring on the symbols x0 , x1 , . . . , xn?1 . Then → the binary ntuples ? a ∈ {0, 1}n are in onetoone correspondence with the minterms of Bn , i.e.,
? → ? → a ←→ x a = n?1 j =0
xj j ,
a
where
? 0 ? xj = xj ?
x1 j = xj
Since there is a onetoone correspondence between the automorphisms of Bn and the permutations on the set of minterms, it follows that CRCDn ’s
18
Double meaning is intended.
50
SAMUEL J. LOMONACO, JR.
can also be identi?ed with the automorphism group Aut (Bn ) of the free Boolean ring Bn . Moreover, since the set of binary ntuples {0, 1}n is in onetoone correspondence with the set of integers {0, 1, 2, . . . , 2n ? 1} via the radix 2 representation of integers, i.e., (bn?1 , bn?2 , . . . , b1 , b0 ) ←→
n?1 j =0
bj 2j ,
we can, and frequently do, identify binary ntuples with integers. For example, consider the ControlledNOT gate, called CNOT , which is de?ned by the following wiring diagram: c CNOT = b ?→ ⊕ ?→  ?→ ? ?→ b+c b a ,
a ?→?→?→
where we have used the following indexing conventions: ? ? First=Right=Bottom ? Last=Left=Top
where ‘?’ and ‘⊕’ denote respectively a control bit and a target bit, and where ‘a + b’ denotes the exclusive ‘or’ of bits a and b. This corresponds to the permutation π = (26)(37), i.e., ? 0 = 000 ?→ 000 = 0 ? ? ? ? 1 = 001 ?→ 001 = 1 ? ? ? ?  2 = 010 ?→ 110 = 6 ? ? ? ? ? 3 = 011 ?→ 111 = 7 , ? ?  4 =  100 ?→  100 =  4 ? ? ? ? 5 = 101 ?→ 101 = 5 ? ? ? ?  6 = 110 ?→ 010 = 2 ? ? ? 7 = 111 ?→ 011 = 3
As another example, consider the To?oli gate , which is de?ned by the following wiring diagram: c ?→ ⊕ ?→ c + ab  b ?→ ? ?→ b  a ?→ ? ?→ a
To?oli =
,
A ROSSETTA STONE FOR QUANTUM MECHANICS
51
where ‘ab’ denotes the logical ‘and’ of a and b. As before, ‘+’ denotes exclusive ‘or’. This gate corresponds to the permutation π = (67). In summary, we have:
n = Aut (B ) { CRCDn } = S2 n
10.3. Embedding classical irreversible computation within classical reversible computation. A classical 1input/noutput (binary memoryless) irreversible computing device can be thought of as a Boolean function f = f (xn?2 , . . . , x1 , x0 ) in Bn?1 = B x0 , x1 , . . . , xn?2 . Such irreversible computing devices can be transformed into reversible computing devices via the monomorphism where ι(f ) is the automorphism in Aut(Bn ) de?ned by ι : Bn?1 ?→ Aut(Bn ),
and where ‘⊕’ denotes exclusive ‘or’. Thus, the image of each Boolean function f is a product of disjoint transpositions in S2n . As an additive group (ignoring ring structure), Bn?1 is the abelian group 2(n?1) ?1 Z2 , where Z2 denotes the cyclic group of order two. j =0 Classical Binary Memoryless Computation is summarized in the table below: Summary Classical Binary Memoryless Computation B n?1 =
2(n?1) ?1 Z2 j =0
(xn?1 , xn?2 , . . . , x1 , x0 ) ?→ (xn?1 ⊕ f, xn?2 , . . . , x1 , x0 ) ,
?→ S2n = Aut(Bn )
ι
10.4. The unitary representation of reversible computing devices. It is now a straight forward task to represent CRCDn ’s as unitary transformations. We simply use the standard unitary representation
n ?→ U(2n ; C) ν : S2
of the symmetric group S2n into the group of 2n × 2n unitary matrices U(2n ; C). This is the representation de?ned by π ?→ (δk,πk )2n ×2n ,
52
SAMUEL J. LOMONACO, JR.
We think of such unitary transformations as quantum computing devices. For example, consider the controlledNOT gate CNOT′ = (45)(67) ∈ S8 given by the wiring diagram ?→ ? ?→ c  b ?→?→?→ b  a ?→ ⊕ ?→ a + c c 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 ? ? ? ? ? ? ? ? ? ? ? ?
where δk? denotes the Kronecker delta, i.e., ? ? 1 if k = ? δk? = ? 0 otherwise
CNOT′ =
This corresponds to the unitary transformation ? 1 0 0 ? 0 1 0 ? ? 0 0 1 ? ? 0 0 0 ′ UCNOT′ = ν (CNOT ) = ? ? 0 0 0 ? ? 0 0 0 ? ? 0 0 0 0 0 0
Moreover, consider the To?oli gate To?oli′ = (57) ∈ S8 given by the wiring diagram ?→ ? ?→ c  b ?→ ⊕ ?→ b + ac  a ?→ ? ?→ a c 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 ? ? ? ? ? ? ? ? ? ? ? ?
To?oli′ =
This corresponds to the unitary transformation ? 1 0 0 0 ? 0 1 0 0 ? ? 0 0 1 0 ? ? 0 0 0 1 ′ ′ UTo?oli = ν (To?oli ) = ? ? 0 0 0 0 ? ? 0 0 0 0 ? ? 0 0 0 0 0 0 0 0
A ROSSETTA STONE FOR QUANTUM MECHANICS
53
Abuse of Notation and a Caveat: Whenever it is clear from context, we will use the name of a CRCDn to also refer to the unitary transformation corresponding to the CRCDn . For example, we will denote ν (CN OT ) and ν (T of f oli) simply by CN OT and T of f oli. Moreover we will also use the wiring diagram of a CRCDn to refer to the unitary transformation corresponding to the CRCDn . For quantum computation beginners, this can lead to some confusion. Be careful! 10.5. Some other simple quantum computing devices. After CRCDn ’s are embedded as quantum computing devices, they are no longer classical computing devices. After the embedding, they suddenly have acquired much more computing power. Their inputs and outputs can be a superposition of many states. They can entangle their outputs. It is misleading to think of their input qubits as separate, for they could be entangled. As an illustration of this fact, please note that the device CNOT′′ given by the wiring diagram ? 1 b ?→ ? ?→ a + b ? 0  =? CNOT′′ = ? 0 a ?→ ⊕ ?→ a 0 quantum computing 0 1 0 0 0 0 0 1 ? 0 0 ? ? 1 ? 0
is far from classical. It is more than a permutation. It is a linear operator that respects quantum superposition. For example, CNOT′′ can take two nonentangled qubits as input, and then produce two entangled qubits as output. This is something no classical computing device can do. For example, 1 1 0 ? 1 √ ? 0 = √ (00 ? 10 ) ?→ √ (00 ? 11 ) 2 2 2
For completeness, we list two other quantum computing devices that are embeddings of CRCDn ’s, NOT and SWAP: NOT = and SWAP = ?→ ? ?→ ?→ ⊕ ?→ ?→ ? ?→ a    a ?→ ⊕ ?→ ?→ ? ?→ ?→ ⊕ ?→ b b a ?→ NOT ?→ a + 1 = 0 1 1 0 ? = σ1 ? 0 0 ? ? 0 ? 1
1 ? 0 =? ? 0 0
0 0 1 0
0 1 0 0
54
SAMUEL J. LOMONACO, JR.
10.6. Quantum computing devices that are not embeddings. We now consider quantum computing devices that are not embeddings of CRCDn ’s.
The Hadamard gate H is de?ned as: H= ?→ H ?→ 1 =√ 2 1 1 1 ?1 . √
Another quantum gate is the square root of NOT, i.e., is given by √ √ 1?i 1+i i 1 NOT = ?→ NOT ?→ = = 1 i 2 2 There is also the square root of swap √ SWAP = ?→ √ SWAP ?→
NOT, which .
1 ?i ?i 1
√ SWAP which is de?ned as: ? ? 1 0 0 0 ? 0 1+i 1?i 0 ? 2 2 ? =? ? 0 1?i 1+i 0 ? . 2 2 0 0 0 1 = eiθσ1 = eiθσ2 = eiθσ3
Three frequently used unary quantum gates are the rotations: ?→ eiθσ1 ?→ ?→ eiθσ2 ?→ ?→ eiθσ3 ?→ = cos θ i sin θ i sin θ cos θ cos θ sin θ ? sin θ cos θ = eiθ 0 0 e?iθ
=
10.7. The implicit frame of a wiring diagram. Wiring diagrams have the advantage of being a simple means of describing some rather complicated unitary transformations. However, they do have their drawbacks, and they can, if we are not careful, be even misleading. One problem with wiring diagrams is that they are not frame (i.e., basis) independent descriptions of unitary transformations. Each wiring diagram describes a unitary transformation using an implicitly understood basis.
A ROSSETTA STONE FOR QUANTUM MECHANICS
55
For example, consider CNOT′′ given by the wiring diagram: CNOT =
′′
?→ ? ?→ a + b  a ?→ ⊕ ?→ a b
.
The above wiring diagram de?nes CNOT′′ in terms of the implicitly understood basis 1 0 0 = , 1 = . 0 1 This wiring diagram suggests that qubit #1 controls qubit #0, and that qubit #1 is not e?ected by qubit #0. But this is far from the truth. For, CNOT′′ transforms 0 ? 1 0 + 1 √ ? √ 2 2 into 0 ? 1 0 ? 1 √ ? √ , 2 2 where we have used our indexing conventions ? ? First=Right=Bottom . ? Last=Left=Top In fact, in the basis 0 + 1 0 ? 1 √ , 1′ = √ 2 2 the wiring diagram of the same unitary transformation CNOT′′ is: 0′ = b ?→ ⊕ ?→ a + b  a ?→ ? ?→ a The roles of the target and control qubits appeared to have switched! 11. The NoCloning Theorem
In this section, we prove the nocloning theorem of Wootters and Zurek [83]. The theorem states that there can be no device that produces exact replicas or copies of a quantum state. (See also [83] for an elegant proof using the creation operators of quantum electrodynamics.) The proof is an amazingly simple application of the linearity of quantum mechanics. The key idea is that copying is an inherently quadratic
56
SAMUEL J. LOMONACO, JR.
transformation, while the unitary transformations of quantum mechanics are inherently linear. Ergo, copying can not be a unitary transformation. But what do we mean by a quantum replicator? De?nition 11. Let H be a Hilbert space. Then a quantum replicator consists of an auxiliary Hilbert space HA , a ?xed state ψ0 ∈ HA (called the initial state of replicator), and a unitary transformation such that, for some ?xed state blank ∈ H, U : HA ? H ⊕ H ?→ HA ? H ⊕ H U ψ0 a blank = ψa a a ,
for all states a ∈ H, where ψa ∈ HA (called the replicator state after replication of a ) depends on a . Since a quantum state is determined by a ket up to a multiplicative nonzero complex number, we can without loss of generality assume that ψ0 , a , blank are all of unit length. From unitarity, it follows that ψa is also of unit length. Let a , b be two kets of unit length in H such that Then 0< ab <1. ? ? U ψ0 a blank ? U ψ0 b blank
= ψa a a = ψb b b
Hence,
blank a ψ0  U ? U ψ0 b blank = blank a ψ0  ψ0 b blank = ab On the other hand,
blank a ψ0  U ? U ψ0 b blank = a a ψa  ψb b b = ab ab =1.
2
ψa  ψb
Thus, And so, ab
2
ψa  ψb
=
.
ab
ψa  ψb
A ROSSETTA STONE FOR QUANTUM MECHANICS
57
But this equation can not be satis?ed since  ab <1 and  ψa  ψb  ≤ ψa ψb =1
Hence, a quantum replicator cannot exist.
12. Quantum teleportation
We now give a brief description of quantum teleportation, a means possibly to be used by future quantum computers to bus qubits from one location to another. As stated earlier, qubits can not be copied as a result of the nocloning theorem. (Please refer to the previous section.) However, they can be teleported, as has been demonstrated in laboratory settings. Such a mechanism could be used to bus qubits from one computer location to another. It could be used to create devices called quantum repeaters.
But what do we mean by teleportation? Teleportation is the transferring of an object from one location to another by a process that: 1) Firstly dissociates (i.e., destroys) the object to obtain information. – The object to be teleported is ?rst scanned to extract su?cient information to reassemble the original object. 2) Secondly transmits the acquired information from one location to another. 3) Lastly reconstructs the object at the new location from the received information. – An exact replicas reassembled at the destination out of locally available materials. Two key e?ects of teleportation should be noted: 1) The original object is destroyed during the process of teleportation. Hence, the nocloning theorem is not violated. 2) An exact replica of the original object is created at the intended destination.
58
SAMUEL J. LOMONACO, JR.
Scotty of the Starship Enterprise was gracious enough to loan me the following teleportation manual. So I am passing it on to you.
Quantum Teleportation Manual
Step. 1 .(Location A): Preparation: At location A, construct an EPR pair of qubits (qubits #2 and #3) in H2 ? H3 . 00 ?→ H2 ? H3 Unitary Matrix ?→ ?→
01 ?10 √ 2
Step 2. Transport: Physically transport entangled qubit #3 from location A to location B. Step 3. : The qubit to be teleported, i.e., qubit #1, is delivered to location A in an unknown state a 0 + b 1 As a result of Steps 1  3, we have: ? Locations A and B share an EPR pair, i.e. – The qubit which is to be teleported, i.e., qubit #1, is at Location A – Qubit #2 is at Location A – Qubit #3 is at Location B – Qubits #2 & #3 are entangled ? The current state Φ of all three qubits is: Φ = (a 0 + b 1 ) 01 ? 10 √ 2 ∈ H1 ? H2 ? H3
H2 ? H3
To better understand what is about to happen, we reexpress the state Φ of the three qubits in terms of the following basis (called the Bell basis) of H1 ? H2 : ? ?01 ΨA = 10 √ ? ? 2 ? ? ? ? ? ? 10 √ +01 ? ? ? ΨB = 2 ? ? ? ΨC ? ? ? ? ? ? ? ?  ΨD =
00 ?11 √ 2
=
00 √ +11 2
A ROSSETTA STONE FOR QUANTUM MECHANICS
59
The result is:
1 2[
Φ
=
where, as you might have noticed, we have written the expression in a suggestive way. Remark 11. Please note that since the completion of Step 3, we have done nothing physical. We have simply performed some algebraic manipulation of the expression representing the state Φ of the three qubits. Let U : H1 ? H2 ?→ H1 ? H2 be the unitary transformation de?ned by ? ? ΨA ?→ 00 ? ? ? ? ? ? ? ΨB ?→ 01 ? ΨC ? ? ? ? ? ? ? ΨD ?→ 10 ?→ 11
ΨA + ΨB + ΨC + ΨD
(?a 0 ? b 1 ) (?a 0 + b 1 ) (a 1 + b 0 ) (a 1 ? b 0 ) ]
,
Step 4. (Location A): 19 Apply the local unitary transformation U ? I : H1 ? H2 ? H3 ?→ H1 ? H2 ? H3 to the three qubits (actually more precisely, to qubits #1 and #2). Thus, under U ? I the state Φ of all three qubits becomes
1 2[
 Φ′
=
00 (?a 0 ? b 1 ) + 01 (?a 0 + b 1 ) + 10 (a 1 + b 0 ) + 11 (a 1 ? b 0 ) ]
Step 5. (Location A): Measure qubits #1 and #2 to obtain two bits of classical information. The result of this measurement will be one of the bit pairs {00, 01, 10, 11} . Step 6.: Send from location A to location B (via a classical communication channel) the two classical bits obtained in Step 6.
19 Actually, there is no need to apply the unitary transformation U . We could have instead made a complete Bell state measurement, i.e., a measurement with respect to the compatible observables ΨA ΨA , ΨB ΨB , ΨC ΨC , ΨD ΨD . We have added the additional step 4 to make quantum teleportation easier to understand for quantum computation beginners. Please note that a complete Bell state measurement has, of this writing, yet to be achieved in a laboratoy setting.
60
SAMUEL J. LOMONACO, JR.
As an intermediate summary, we have: 1) Qubit #1 has been disassembled, and 2) The information obtained during disassembly (two classical bits) has been sent to location B.
Step 7. (Location B): The two bits (i, j ) received from location A are used to select from the following table a unitary transformation U (i,j ) of H3 , (i.e., a local unitary transformation I4 ? U (i,j ) on H1 ? H2 ? H3 ) Rec. Bits 00 01 10 11 U (i,j ) ?1 U (00) = 0 ?1 U (01) = 0 0 U (10) = 1 0 U (11) = ?1 Future e?ect on qubit #3 0 ?1 0 1 1 0 1 0 ?a 0 ? b 1 ?→ a 0 + b 1 ?a 0 + b 1 ?→ a 0 + b 1 a 1 + b 0 ?→ a 0 + b 1 a 1 ? b 0 ?→ a 0 + b 1
Step 8. (Location B): The unitary transformation U (i,j ) selected in Step 7 is applied to qubit #3. As a result, qubit #3 is at location B and has the original state of qubit #1 when qubit #1 was ?rst delivered to location A, i.e., the state a 0 + b 1
It is indeed amazing that no one knows the state of the quantum teleported qubit except possibly the individual that prepared the qubit. Knowledge of the actual state of the qubit is not required for teleportaton. If its state is unknown before the teleportation, it remains unknown after the teleportation. All that we know is that the states before and after the teleportation are the same.
13. Shor’s algorithm The following description of Shor’s algorithm is based on [27], [47], [50], [53], and [77] .
A ROSSETTA STONE FOR QUANTUM MECHANICS
61
13.1. Preamble to Shor’s algorithm. There are cryptographic systems (such as RSA20 ) that are extensively used today (e.g., in the banking industry) which are based on the following questionable assumption, i.e., conjecture: Conjecture(Assumption). Integer factoring is computationally much harder than integer multiplication. In other words, while there are obviously many polynomial time algorithms for integer multiplication, there are no polynomial time algorithms for integer factoring. I.e., integer factoring computationally requires superpolynomial time. This assumption is based on the fact that, in spite of the intensive e?orts over many centuries of the best minds to ?nd a polynomial time factoring algorithm, no one has succeeded so far. As of this writing, the most asymptotically e?cient classical algorithm is the number theoretic sieve [56], [57], which factors an integer N in time O exp (lg N )1/3 (lg lg N )2/3 . Thus, this is a superpolynomial time algorithm in the number O (lg N ) of digits in N .
However, ... Peter Shor suddenly changed the rules of the game. Hidden in the above conjecture is the unstated, but implicitly understood, assumption that all algorithms run on computers based on the principles of classical mechanics, i.e., on classical computers. But what if a computer could be built that is based not only on classical mechanics, but on quantum mechanics as well? I.e., what if we could build a quantum computer? Shor, starting from the works of Benio?, Bennett, Deutsch , Feynman, Simon, and others, created an algorithm to be run on a quantum computer, i.e., a quantum algorithm, that factors integers in polynomial time! Shor’s algorithm takes asymptotically O (lg N )2 (lg lg N ) (lg lg lg N ) steps on a quantum computer, which is polynomial time in the number of digits O (lg N ) of N .
RSA is a public key cryptographic system invented by Rivest, Shamir, Adleman. Hence the name. For more information, please refer to [79].
20
62
SAMUEL J. LOMONACO, JR.
13.2. Number theoretic preliminaries. Since the time of Euclid, it has been known that every positive integer N can be uniquely (up to order) factored into the product of primes. Moreover, it is a computationally easy (polynomial time) task to determine whether or not N is a prime or composite number. For the primality testing algorithm of MillerRabin[66] makes such a determination at the cost of O (s lg N ) arithmetic operations [O s lg3 N bit operations] with probability of error P robError ≤ 2?s . However, once an odd positive integer N is known to be composite, it does not appear to be an easy (polynomial time) task on a classical computer to determine its prime factors. As mentioned earlier, so far the most asymptotically e?cient classical algorithm known is the number theoretic sieve [56], [57], which factors an integer N in time O exp (lg N )1/3 (lg lg N )2/3 . Prime Factorization Problem. Given a composite odd positive integer N , ?nd its prime factors. It is well known[66] that factoring N can be reduced to the task of choosing at random an integer m relatively prime to N , and then determining its modulo N multiplicative order P , i.e., to ?nding the smallest positive integer P such that mP = 1 mod N . It was precisely this approach to factoring that enabled Shor to construct his factoring algorithm.
13.3. Overview of Shor’s algorithm. But what is Shor’s quantum factoring algorithm?
Let N = {0, 1, 2, 3, . . . } denote the set of natural numbers.
Shor’s algorithm provides a solution to the above problem. His algorithm consists of the ?ve steps (steps 1 through 5), with only STEP 2 requiring the use of a quantum computer. The remaining four other steps of the algorithm are to be performed on a classical computer. We begin by brie?y describing all ?ve steps. After that, we will then focus in on the quantum part of the algorithm, i.e., STEP 2.
A ROSSETTA STONE FOR QUANTUM MECHANICS
63
Step 1. Choose a random positive even integer m. Use the polynomial time Euclidean algorithm21 to compute the greatest common divisor gcd (m, N ) of m and N . If the greatest common divisor gcd (m, N ) = 1, then we have found a nontrivial factor of N , and we are done. If, on the other hand, gcd (m, N ) = 1, then proceed to STEP 2. STEP 2. Use a quantum computer to determine the unknown period P of the function
N N ?→ N a ?→ ma mod N
f
Step 3. If P is an odd integer, then goto Step 1. [The probability of P being 1 k ) , where k is the number of distinct prime factors of N .] If odd is ( 2 P is even, then proceed to Step 4.
Step 4. Since P is even, mP/2 ? 1 mP/2 + 1 = mP ? 1 = 0 mod N .
If mP/2 + 1 = 0 mod N , then goto Step 1. If mP/2 + 1 = 0 mod N , then proceed to Step 5. It can be shown that the probability that k ?1 , where k denotes the number mP/2 + 1 = 0 mod N is less than ( 1 2) of distinct prime factors of N . Step 5. Use the Euclidean algorithm to compute d = gcd mP/2 ? 1, N . Since mP/2 +1 = 0 mod N , it can easily be shown that d is a nontrivial factor of N . Exit with the answer d.
Thus, the task of factoring an odd positive integer N reduces to the following problem: Problem. Given a periodic function ?nd the period P of f . f : N ?→ N ,
The Euclidean algorithm is O lg2 N . For a description of the Euclidean algorithm, see for example [20] or [19].
21
64
SAMUEL J. LOMONACO, JR.
13.4. Preparations for the quantum part of Shor’s algorithm. Choose a power of 2 Q = 2L such that N 2 ≤ Q = 2L < 2N 2 , and consider f restricted to the set SQ = {0, 1, . . . , Q ? 1} which we also denote by f , i.e., f : SQ ?→ SQ . In preparation for a discussion of STEP 2 of Shor’s algorithm, we construct two Lqubit quantum registers, Register1 and Register2 to hold respectively the arguments and the values of the function f , i.e., Reg1 Reg2 = a f (a) = a b = a0 a1 · · · aL?1 b0 b1 · · · bL?1 In doing so, we have adopted the following convention for representing integers in these registers: Notation Convention. In a quantum computer, we represent an integer a with radix 2 representation a=
L?1 j =0
aj 2j ,
as a quantum register consisting of the 2n qubits a = a0 a1 · · · aL?1 =
L?1 j =0
aj
For example, the integer 23 is represented in our quantum computer as n qubits in the state: 23 = 10111000 · · · 0
Before continuing, we remind the reader of the classical de?nition of the Qpoint Fourier transform.
A ROSSETTA STONE FOR QUANTUM MECHANICS
65
De?nition 12. Let ω be a primitive Qth root of unity, e.g., ω = e2πi/Q . Then the Qpoint Fourier transform is the map M ap(SQ , C) ?→ M ap(SQ , C) [f : SQ ?→ C] ?→ f : SQ ?→ C where 1 f (x)ω xy f (y ) = √ Q x∈S
Q
F
We implement the Fourier transform F as a unitary transformation, which in the standard basis is given by the Q × Q unitary matrix 1 F = √ (ω xy ) . Q 0 , 1 , . . . , Q ? 1
This unitary transformation can be factored into the product of O lg2 Q = O lg2 N su?ciently local unitary transformations. (See [77], [47].)
13.5. The quantum part of Shor’s algorithm. The quantum part of Shor’s algorithm, i.e., STEP 2, is the following: STEP 2.0 Initialize registers 1 and 2, i.e.,
22 Apply
ψ0 = Reg1 Reg2 = 0 0 = 00 · · · 0 0 · · · 0 the Qpoint Fourier transform F to Register1.
F?I
STEP 2.1
ψ0 = 0 0 ?→ ψ1
1 =√ Q
Q ?1 x=0
ω
0·x
1 x 0 = √ Q
Q ?1 x=0
x 0
Remark 12. Hence, Register1 now holds all the integers 0, 1, 2, . . . , Q ? 1 in superposition.
22 In this step we could have instead applied the Hadamard transform to Register1 with the same result, but at the computational cost of O (lg N ) su?ciently local unitary transformations.
66
SAMUEL J. LOMONACO, JR.
STEP 2.2 Let Uf be the unitary transformation that takes x 0 to x f (x) . Apply the linear transformation Uf to the two registers. The result is: ψ1 1 =√ Q
Q ?1 x=0
x 0 ?→ ψ2
Uf
1 =√ Q
Q ?1 x=0
x f (x)
Remark 13. The state of the two registers is now more than a superposition of states. In this step, we have quantum entangled the two registers.
STEP 2.3. Apply the Qpoint Fourier transform F to Reg1. The resulting state is: ψ2 =
1 √ Q Q ?1 x=0
x f (x)
F?I
?→ ψ3 =
1 Q
Q?1Q?1 x=0 y =0 Q ?1 y =0
ω xy y f (x)
= where Υ(y ) =
Q ?1 x=0
1 Q
Υ(y )
· y
Υ(y ) Υ(y )
,
ω xy f (x) .
STEP 2.4. Measure Reg1, i.e., perform a measurement with respect to the orthogonal projections 0 0 ? I, 1 1 ? I, 2 2 ? I, . . . , Q ? 1 Q ? 1 ? I , where I denotes the identity operator on the Hilbert space of the second register Reg2. As a result of this measurement, we have, with probability P rob (y0 ) = moved to the state y0 and measured the value Υ(y0 ) Υ(y0 ) Υ(y0 ) Q2
2
,
y0 ∈ {0, 1, 2, . . . , Q ? 1} .
A ROSSETTA STONE FOR QUANTUM MECHANICS
67
If after this computation, we ignore the two registers Reg1 and Reg2, we see that what we have created is nothing more than a classical probability distribution S on the sample space {0, 1, 2, . . . , Q ? 1} . In other words, the sole purpose of executing STEPS 2.1 to 2.4 is to create a classical ?nite memoryless stochastic source S which outputs a symbol y0 ∈ {0, 1, 2, . . . , Q ? 1} with the probability P rob(y0 ) = Υ(y0 ) Q2
2
.
(For more details, please refer to section 8.1 of this paper.)
As we shall see, the objective of the remander of Shor’s algorithm is to glean information about the period P of f from the just created stochastic source S . The stochastic source was created exactly for that reason.
13.6. Peter Shor’s stochastic source S .
Before continuing to the ?nal part of Shor’s algorithm, we need to analyze the probability distribution P rob (y ) a little more carefully.
Proposition 1. Let q and r be the unique nonnegative integers such that Q = P q + r , where 0 ≤ r < P ; and let Q0 = P q . Then ? ? ? ? ? ? ? ? ?
r sin2
πP y · Q Q0 +1 P
+(P ?r ) sin2
πP y Q
πP y Q0 · P Q
P rob (y ) =
Q2 sin2 r (Q0 +P )2 +(P ?r )Q2 0 Q2 P 2
if P y = 0 mod Q
if P y = 0 mod Q
68
SAMUEL J. LOMONACO, JR.
Proof. We begin by deriving a more usable expression for Υ(y ) . Υ(y ) =
Q ?1 x=0 P ?1
ω xy
f (x) =
Q 0 ?1 x=0
ω xy
f (x) +
Q ?1
x =Q 0
ω xy f (x)
=
Q0 ?1 P
x0 =0 x1 =0 P ?1
ω (P x1 +x0 )y f (P x1 + x0 ) + ?Q ?
0 ?1 P
r ?1
ω
P
Q0 P
+x 0 y
x0 =0
f (P x1 + x0 )
=
x0 =0
? ω x0 y · ?
x1 =0
Q0 P
? ω P yx1 f (x ? ?
?
0)
+
r ?1
x0 =0
ω x0 y · ω
Py
Q0 P
f (x0 ) ?
=
r ?1
x0 =0
where we have used the fact that f is periodic of period P .
? ω x0 y · ?
x1 =0
? ω P yx1 ? f (x0 ) +
P ?1 x 0 =r
? ω x0 y · ?
?Q
0 ?1 P
x1 =0
? ω P yx1 ? f (x0 )
Since f is onetoone when restricted to its period 0, 1, 2, . . . , P ? 1, all the kets f (0) , f (1) , f (2) , . . . , f (P ? 1) , are mutually orthogonal. Hence,
Q0 P
2
Υ(y )  Υ(y ) = r
ω P yx1
x1 =0
+ (P ? r )
Q0 ?1 P
2
ω P yx1
.
x1 =0
If P y = 0 mod Q, then since ω is a Qth root of unity, we have Υ(y )  Υ(y ) = r Q0 +1 P
2
+ (P ? r )
Q0 P
2
.
On the other hand, if P y = 0 mod Q, then we can sum the geometric series to obtain Υ(y )  Υ(y ) = ω
P y·
Q0 +1 P
2
ωP y ? 1
2πi ·P y · Q
?1
+ (P ? r ))
2
ω
P y·
?1 P y ω ?1
2πi ·P y · Q Q0 P
Q0 P
2
=
e
Q0 +1 P
2
e
2πi ·P y Q
?1
?1
+ (P ? r ))
e
e
2πi ·P y Q
?1
?1
A ROSSETTA STONE FOR QUANTUM MECHANICS
69
where we have used the fact that ω is the primitive Qth root of unity given by ω = e2πi/Q . The remaining part of the proposition is a consequence of the trigonometric identity 2 θ . eiθ ? 1 = 4 sin2 2
As a corollary, we have Corollary 1. If P is an exact divisor of Q, then ? ? 0 if P y = 0 mod Q P rob (y ) = ? 1 if P y = 0 mod Q P 13.7. A momentary digression: Continued fractions. We digress for a moment to review the theory of continued fractions. (For a more indepth explanation of the theory of continued fractions, please refer to [42] and [58].) Every positive rational number ξ can be written as an expression in the form 1 , ξ = a0 + 1 a1 + 1
a2 +
1 a3 + ···+ 1 aN
where a0 is a nonnegative integer, and where a1 , . . . , aN are positive integers. Such an expression is called a (?nite, simple) continued fraction , and is uniquely determined by ξ provided we impose the condition aN > 1. For typographical simplicity, we denote the above continued fraction by [a0 , a1 , . . . , aN ] . The continued fraction expansion of ξ can be computed with the following recurrence relation, which always terminates if ξ is rational: ? ? a0 = ?ξ ? ? ? an+1 = ?1/ξn ? , and if ξn = 0, then ? ? ξ 1 ξ0 = ξ ? a0 n+1 = ξn ? an+1
70
SAMUEL J. LOMONACO, JR.
The nth convergent (0 ≤ n ≤ N ) of the above continued fraction is de?ned as the rational number ξn given by ξn = [a0 , a1 , . . . , an ] .
n Each convergent ξn can be written in the for, ξn = p qn , where pn and qn are relatively prime integers ( gcd (pn , qn ) = 1). The integers pn and qn are determined by the recurrence relation
p0 = a0 , p1 = a1 a0 + 1, pn = an pn?1 + pn?2 , q0 = 1, q1 = a1 , qn = an qn?1 + qn?2 .
13.8. Preparation for the ?nal part of Shor’s algorithm. De?nition 13. 23 For each integer a, let {a}Q denote the residue of a modulo Q of smallest magnitude. In other words, {a}Q is the unique integer such that ? ? a = {a}Q mod Q . ? ?Q/2 < {a}Q ≤ Q/2 Proposition 2. Let y be an integer lying in SQ . Then ? 4 1 2 1 ? if 0 < {P y }Q ≤ ? π2 · P · 1 ? N P rob (y ) ≥ ? ? 1 1 2 if {P y }Q = 0 P · 1? N
π {P y }Q Q P 2 1 N
· 1?
Proof. We begin by noting that ·
Q0 P
+1
≤ ≤
π Q π 2
·
P 2
· 1?
1 N
1 N
·
Q 0 +P P P Q
≤
π 2
π 2
· 1?
1 N
1 N
·
Q +P Q N N2
· 1?
· 1+
≤
· 1?
· 1+
<
π 2
,
where we have made use of the inequalities N 2 ≤ Q < 2N 2 and 0 < P ≤ N . It immediately follows that π {P y }Q Q0 π < · . Q P 2
23
{a}Q = a ? Q · round
a Q
=a?Q·
a Q
+
1 2
.
A ROSSETTA STONE FOR QUANTUM MECHANICS
71
As a result, we can legitimately use the inequality π 4 2 θ ≤ sin2 θ ≤ θ 2 , for θ  < π2 2 to simplify the expression for P rob (y ). Thus,
r sin2
P rob (y ) =
π {P y }Q · Q
Q0 +1 P
+(P ?r ) sin2
πP y Q
π {P y }Q Q · P0 Q
Q2 sin2
π {P y }Q · Q 2
≥
r·
4 · π2
Q0 +1 P
+(P ?r )·
π {P y }Q Q 2
4 · π2
π {P y }Q Q · P0 Q
2
Q2
2
≥ =
4 π2 4 π2
· ·
P·
Q0 P Q2
=
r Q
4 π2 2
·
1 P
· ·
Q ?r Q 1 P
2
1 P
· 1?
≥
4 π2
· 1?
1 2 N
The remaining case, {P y }Q = 0 is left to the reader. Lemma 1. Let Y = y ∈ SQ  {P y }Q ≤ Y y P 2 and SP = { d ∈ SQ  0 ≤ d < P } .
Then the map ?→ SP ?→ d = d(y ) = round Q ·d P
P Q
·y
is a bijection with inverse y = y (d) = round .
Hence, Y and SP are in onetoone correspondence. Moreover, {P y }Q = P · y ? Q · d(y ) . Remark 14. Moreover, the following two sets of rationals are in onetoone correspondence y y∈Y Q ←→ d 0≤d<P P
72
SAMUEL J. LOMONACO, JR.
As a result of the measurement performed in STEP 2.4, we have in our possession an integer y ∈ Y . We now show how y can be use to determine the unknown period P . We now need the following theorem24 from the theory of continued fractions: Theorem 2. Let ξ be a real number, and let a and b be integers with b > 0. If 1 a ≤ 2 , ξ? b 2b then the rational number a/b is a convergent of the continued fraction expansion of ξ . As a corollary, we have: Corollary 2. If {P y }Q ≤ Proof. Since P y ? Qd(y ) = {P y }Q , we know that P y ? Qd(y ) ≤ which can be rewritten as y d(y ) 1 ? . ≤ Q P 2Q But, since Q ≥ N 2 , it follows that 1 d(y ) y ≤ ? . Q P 2N 2 P , 2
P 2,
then the rational number
y Q.
d(y ) P
is a convergent
of the continued fraction expansion of
1 Finally, since P ≤ N (and hence 21 N ≤ 2P 2 ), the above theorem can be d(y ) applied. Thus, P is a convergent of the continued fraction expansion of y . ξ=Q y) Since d( P is a convergent of the continued fraction expansion of follows that, for some n, y Q,
it
d(y ) pn = , P qn
24
See [42, Theorem 184, Section 10.15].
A ROSSETTA STONE FOR QUANTUM MECHANICS
73
where pn and qn are relatively prime positive integers given by a recurrence relation found in the previous subsection. So it would seem that we have found a way of deducing the period P from the output y of STEP 2.4, and so we are done. Not quite! We can determine P from the measured y produced by STEP 2.4, only if ? ? pn = d(y ) , ? qn = P
which is true only when d(y ) and P are relatively prime.
So what is the probability that the y ∈ Y produced by STEP 2.4 satis?es the additional condition that gcd (P, d(y )) = 1 ?
Proposition 3. The probability that the random y produced by STEP 2.4 is such that d(y ) and P are relatively prime is bounded below by the following expression P rob {y ∈ Y  gcd(d(y ), P ) = 1} ≥ 1 4 φ(P ) · · 1? 2 π P N
2
,
where φ(P ) denotes Euler’s totient function, i.e., φ(P ) is the number of positive integers less than P which are relatively prime to P . The following theorem can be found in [42, Theorem 328, Section 18.4]: Theorem 3. lim inf φ(N ) = e?γ , N/ ln ln N
where γ denotes Euler’s constant γ = 0.57721566490153286061 . . . , and where e?γ = 0.5614594836 . . . . As a corollary, we have: Corollary 3. P rob {y ∈ Y  gcd(d(y ), P ) = 1} ≥ e?γ ? ? (P ) 1 4 · · 1? 2 π ln 2 lg lg N N
2
,
74
SAMUEL J. LOMONACO, JR.
where ? (P ) is a monotone decreasing sequence converging to zero. In terms of asymptotic notation, P rob {y ∈ Y  gcd(d(y ), P ) = 1} = ? 1 lg lg N .
Thus , if STEP 2.4 is repeated O(lg lg N ) times, then the probability of success is ? (1). Proof. From the above theorem, we know that φ(P ) ≥ e?γ ? ? (P ) . P/ ln ln P where ? (P ) is a monotone decreasing sequence of positive reals converging to zero. Thus, e?γ ? ? (P ) e?γ ? ? (P ) e?γ ? ? (P ) e?γ ? ? (P ) 1 φ(P ) ≥ ≥ = ≥ · P ln ln P ln ln N ln ln 2 + ln lg N ln 2 lg lg N
1 Remark 15. ?( lg lg Readers not N ) denotes an asymptotic lower bound. familiar with the bigoh O(?) and bigomega ? (?) notation should refer to [19, Chapter 2] or [11, Chapter 2].
Remark 16. For the curious reader, lower bounds LB (P ) of e?γ ? ? (P ) for 3 ≤ P ≤ 841 are given in the following table: P 3 4 5 7 13 31 61 211 421 631 841 LB (P ) 0.062 0.163 0.194 0.303 0.326 0.375 0.383 0.411 0.425 0.435 0.468
Thus, if one wants a reasonable bound on the P rob {y ∈ Y  gcd(d(y ), P ) = 1} before continuing with Shor’s algorithm, it would pay to ?rst use a classical algorithm to verify that the period P of the randomly chosen integer m is not too small.
A ROSSETTA STONE FOR QUANTUM MECHANICS
75
13.9. The ?nal part of Shor’s algorithm. We are now prepared to give the last step in Shor’s algorithm. This step can be performed on a classical computer. Step 2.5 Compute the period P from the integer y produced by STEP 2.4.
? ? –
Loop for each n from n = 1 Until ξn = 0.
Use the recurrence relations given in subsection 13.7, to comy n pute the pn and qn of the nth convergent p qn of Q . Test to see if qn = P by computing25 mq n =
i
?
–
m2
i
qn,i
mod N ,
where qn = i qn,i 2i is the binary expansion of qn . If mqn = 1 mod N , then exit with the answer P = qn , and proceed to Step 3. If not, then continue the loop.
? ?
End of Loop
If you happen to reach this point, you are a very unlucky quantum computer scientist. You must start over by returning to STEP 2.0. But don’t give up hope! The probability that the integer y produced by STEP 2.4 will lead to a successful completion of Step 2.5 is bounded below by e?γ ? ? (P ) 1 4 · · 1? 2 π ln 2 lg lg N N
2
>
0.232 1 · 1? lg lg N N
2
,
provided the period P is greater than 3. constant.]
[ γ denotes Euler’s
The indicated algorithm for computing mqn mod N requires O(lg qn ) arithmetic operations.
25
76
SAMUEL J. LOMONACO, JR.
13.10. An example of Shor’s algorithm.
Let us now show how N = 91 (= 7 · 13) can be factored using Shor’s algorithm. We choose Q = 214 = 16384 so that N 2 ≤ Q < 2N 2 . Step 1 Choose a random positive integer m, say m = 3. Since gcd(91, 3) = 1, we proceed to STEP 2 to ?nd the period of the function f given by f (a) = 3a mod 91 Remark 17. Unknown to us, f has period P = 6. For, a f (a) 0 1 2 3 4 5 6 7 ···
1 3 9 27 81 61 1 3 · · · ∴ Unknown period P = 6
STEP 2.0 Initialize registers 1 and 2. Thus, the state of the two registers becomes: ψ0 = 0 0
STEP 2.1 Apply the Qpoint Fourier transform F to register #1, where F k = √ 1 16384
16383 x=0
ω kj x ,
2πi
and where ω is a primitive Qth root of unity, e.g., ω = e 16384 . Thus the state of the two registers becomes: ψ1 = √ 1 16384
16383 x=0
x 0
A ROSSETTA STONE FOR QUANTUM MECHANICS
77
STEP 2.2 Apply the unitary transformation Uf to registers #1 and #2, where Uf x ? = x  f (x) ? ? mod 91 .
2 = I .) Thus, the state of the two registers becomes: (Please note that Uf
ψ2
= =
√ 1 16384 √ 1 ( 16384
16383 x=0 x
3x mod 91
 0 1 +  1 3 +  2 9 +  3 27 +  4 81 +  5 61 +  6 1 +  7 3 +  8 9 +  9 27 + 10 81 + 11 61 + 12 1 + 13 3 + 14 9 + 15 27 + 16 81 + 17 61 + ... + 16380 1 + 16381 3 + 16382 9 + 16383 27
)
Remark 18. The state of the two registers is now more than a superposition of states. We have in the above step quantum entangled the two registers.
STEP 2.3 Apply the Qpoint F again to register #1. Thus, the state of the system becomes: ψ3 = = = where
16383 √ 1 16384 1 16384 1 16384 16383 √ 1 x=0 16384 16383 x=0 16383 x=0 16383 xy y =0 ω
y 3x mod 91
y
16383 x=0
ω xy 3x mod 91
y Υ (y ) ,
Υ (y ) =
x=0
ω xy 3x mod 91
78
SAMUEL J. LOMONACO, JR.
Thus, Υ (y ) = 1 + ω y 3 + ω 2y 9 + ω 3y 27 + ω 4y 81 + ω 5y 61 + ω 6y 1 + ω 7y 3 + ω 8y 9 + ω 9y 27 + ω 10y 81 + ω 11y 61 + ω 12y 1 + ω 13y 3 + ω 14y 9 + ω 15y 27 + ω 16y 81 + ω 17y 61 + ... + ω 16380y 1 + ω 16381y 3 + ω 16382y 9 + ω 16383y 27
STEP 2.4 Measure Reg1. The result of our measurement just happens to turn out to be y = 13453 Unknown to us, the probability of obtaining this particular y is: Moreover, unknown to us, we’re lucky! prime to P , i.e., 0.3189335551 × 10?6 . The corresponding d is relatively P · y) = 5 Q
d = d(y ) = round(
However, we do know that the probability of d(y ) being relatively prime to P is greater than 1 0.232 · 1? lg lg N N and we also know that
2
≈ 8.4% (provided P > 3),
d(y ) P is a convergent of the continued fraction expansion of y 13453 ξ= = Q 16384 So with a reasonable amount of con?dence, we proceed to Step 2.5. Step 2.5 Using the recurrence relations found in subsection 13.7 of this paper, we successively compute (beginning with n = 0) the an ’s and qn ’s for the continued fraction expansion of 13453 y = . ξ= Q 16384
A ROSSETTA STONE FOR QUANTUM MECHANICS
79
For each nontrivial n in succession, we check to see if 3qn = 1 mod 91. If this is the case, then we know qn = P , and we immediately exit from Step 2.5 and proceed to Step 3. ? In this example, n = 0 and n = 1 are trivial cases. ? For n = 2, a2 = 4 and q2 = 5 . We test q2 by computing 3q2 = 35 = 32 Hence, q2 = P . ? We proceed to n = 3, and compute a3 = 1 and q3 = 6. We then test q3 by computing 3q3 = 36 = 32
0 0
1
· 32
1
0
· 32
0
1
= 61 = 1 mod 91 .
0
· 32
1
1
· 32
0
1
= 1 mod 91 .
Hence, q3 = P . Since we now know the period P , there is no need to continue to compute the remaining an ’s and qn ’s. We proceed immediately to Step 3. To satisfy the reader’s curiosity we have listed in the table below all the values of an , pn , and qn for n = 0, 1, . . . , 14. But it should be mentioned again that we need only to compute an and qn for n = 0, 1, 2, 3, as indicated above. n an pn qn 0 0 0 1 1 1 1 1 2 4 4 5 3 4 5 6 7 8 9 10 11 12 13 14 1 1 2 3 1 1 3 1 1 1 1 3 5 9 23 78 101 179 638 817 1455 2272 3727 13453 6 11 28 95 123 218 777 995 1772 2767 4539 16384
Step 3. Since P = 6 is even, we proceed to Step 4. Step 4. Since 3P/2 = 33 = 27 = ?1 mod 91, we goto Step 5.
80
SAMUEL J. LOMONACO, JR.
Step 5. With the Euclidean algorithm, we compute gcd 3P/2 ? 1, 91 = gcd 33 ? 1, 91 = gcd (26, 91) = 13 . We have succeeded in ?nding a nontrivial factor of N = 91, namely 13. We exit Shor’s algorithm, and proceed to celebrate!
14. Grover’s Algorithm The the following description of Grover’s algorithm is based on [34], [35], and [49]. 14.1. Problem de?nition. We consider the problem of searching an unstructured database of N = 2n records for exactly one record which has been speci?cally marked. This can be rephrased in mathematical terms as an oracle problem as follows: Label the records of the database with the integers and denote the label of the unknown marked record by x0 . We are given an oracle which computes the n bit binary function de?ned by f : {0, 1}n ?→ {0, 1} ? ? 1 if x = x0 ? 0, 1, 2, . . . , N ? 1 ,
f (x) =
0 otherwise
We remind the readers that, as a standard oracle idealization, we have no access to the internal workings of the function f . It operates simply as a blackbox function, which we can query as many times as we like. But with each such a query comes an associated computational cost. Search Problem for an Unstructured Database. Find the record labeled as x0 with the minimum amount of computational work, i.e., with the minimum number of queries of the oracle f . From probability theory, we know that if we examine k records, i.e., if we compute the oracle f for k randomly chosen records, then the probability of ?nding the record labeled as x0 is k/N . Hence, on a classical computer it takes O(N ) = O(2n ) queries to ?nd the record labeled x0 .
A ROSSETTA STONE FOR QUANTUM MECHANICS
81
14.2. The quantum mechanical perspective. However, as Luv Grover so astutely observed, on a quantum√ computer the search of an unstructured database can be accomplished in O ( N ) steps, or √ more precisely, with the application of O( N lg N ) su?ciently local unitary transformations. Although this is not exponentially faster, it is a signi?cant speedup.
Let H2 be a 2 dimensional Hilbert space with orthonormal basis {0 , 1 } ; and let {0 , 1 , . . . , N ? 1 } denote the induced orthonormal basis of the Hilbert space H=
N ?1 0
H2 .
From the quantum mechanical perspective, the oracle function f is given as a blackbox unitary transformation Uf , i.e., by H ? H2 x ? y ?→
Uf
H ? H2
?→ x ? f (x) ⊕ y
where ‘⊕’ denotes exclusive ‘OR’, i.e., addition modulo 2.26
That Ix0 is computationally equivalent to Uf follows from the easily veri?able fact that 0 ? 1 0 ? 1 , = Ix0 (x ) ? √ Uf x ? √ 2 2
26
Instead of Uf , we will use the computationally equivalent unitary transformation ? ? ? x0 if x = x0 f (x) Ix0 (x ) = (?1) x = ? x otherwise
Please note that Uf = (ν ? ι) (f ), as de?ned in sections 10.3 and 10.4 of this paper.
82
SAMUEL J. LOMONACO, JR.
and also from the fact that Uf can be constructed from a controlledIx0 and two one qubit Hadamard transforms. (For details, please refer to [51], [53].)
The unitary transformation Ix0 is actually an inversion [2] in H about the hyperplane perpendicular to x0 . This becomes evident when Ix0 is rewritten in the form Ix0 = I ? 2 x0 x0  , where ‘I ’ denotes the identity transformation. More generally, for any unit length ket ψ , the unitary transformation Iψ = I ? 2 ψ ψ  is an inversion in H about the hyperplane orthogonal to ψ .
14.3. Properties of the inversion Iψ . We digress for a moment to discuss the properties of the unitary transformation Iψ . To do so, we need the following de?nition. De?nition 14. Let ψ and χ be two kets in H for which the bracket product ψ  χ is a real number. We de?ne SC = SpanC (ψ , χ ) = {α ψ + β χ ∈ H  α, β ∈ C} as the subHilbert space of H spanned by ψ and χ . We associate with the Hilbert space SC a real inner product space lying in SC de?ned by SR = SpanR (ψ , χ ) = {a ψ + b χ ∈ H  a, b ∈ R} , where the inner product on SR is that induced by the bracket product on H. If ψ and χ are also linearly independent, then SR is a 2 dimensional real inner product space (i.e., the 2 dimensional Euclidean plane) lying inside of the complex 2 dimensional space SC .
Proposition 4. Let ψ and χ be two linearly independent unit length kets in H with real bracket product; and let SC = SpanC (ψ , χ ) and SR = SpanR (ψ , χ ). Then
A ROSSETTA STONE FOR QUANTUM MECHANICS
83
1) Both SC and SR are invariant under the transformations Iψ , Iχ , and hence Iψ ? Iχ , i.e., Iψ (SC ) = SC Iχ (SC ) = SC Iψ Iχ (SC ) = SC and and and Iψ (SR ) = SR Iχ (SR ) = SR Iψ Iχ (SR ) = SR
2) If Lψ⊥ is the line in the plane SR which passes through the origin and which is perpendicular to ψ , then Iψ restricted to SR is a re?ection in (i.e., a M¨ obius inversion [2] about) the line Lψ⊥ . A similar statement can be made in regard to χ . 3) If ψ ⊥ is a unit length vector in SR perpendicular to ψ , then ?Iψ = Iψ⊥ . (Hence, ψ ⊥  χ is real.)
Finally we note that, since Iψ = I ? 2 ψ ψ , it follows that Proposition 5. If ψ is a unit length ket in H, and if U is a unitary transformation on H, then U Iψ U ?1 = IU ψ .
14.4. The method in Luv’s “madness”. Let H : H ?→ H be the Hadamard transform, i.e., H= where H (2) = with respect to the basis 0 , 1 . 1 1 1 ?1
n?1 0
H (2) ,
84
SAMUEL J. LOMONACO, JR.
We begin by using the Hadamard transform H to construct a state ψ0 which is an equal superposition of all the standard basis states 0 , 1 ,. . . ,N ? 1 (including the unknown state x0 ), i.e., 1 ψ0 = H 0 = √ N
N ?1 k =0
k .
Both ψ0 and the unknown state x0 lie in the Euclidean plane SR = SpanR (ψ0 , x0 ). Our strategy is to rotate within the plane SR the state ψ0 about the origin until it is as close as possible to x0 . Then a measurement with respect to the standard basis of the state resulting from rotating ψ0 , will produce x0 with high probability. To achieve this objective, we use the oracle Ix0 to construct the unitary transformation Q = ?HI0 H ?1 Ix0 , which by proposition 2 above, can be reexpressed as Q = ?Iψ0 Ix0 .
⊥ Let x⊥ 0 and ψ0 denote unit length vectors in SR perpendicular to x0 and ψ0 , respectively. There are two possible choices for each of x⊥ 0 ⊥ respectively. To remove this minor, but nonetheless annoying, and ψ0 ⊥ so that the orientation of the plane S ambiguity, we select x⊥ R 0 and ψ0 induced by the ordered spanning vectors ψ0 , x0 is the same orientation ⊥ as that induced by each of the ordered bases x⊥ 0 , x0 and ψ0 , ψ0 . (Please refer to Figure 2.)
Remark 19. The removal of the above ambiguities is really not essential. However, it does simplify the exposition given below.
A ROSSETTA STONE FOR QUANTUM MECHANICS
85
Figure 2. The linear transformation QSR is re?ection in the line Lx⊥ 0 followed by re?ection in the line Lψ0 which is the same as rotation by the angle 2β . Thus, QSR rotates ψ0 by the angle 2β toward x0 .
We proceed by noting that, by the above proposition 1, the plane SR lying in H is invariant under the linear transformation Q, and that, when Q is restricted to the plane SR , it can be written as the composition of two inversions, i.e., QSR = Iψ⊥ Ix0 . 0 In particular, QSR is the composition of two inversions in SR , the ?rst in the line Lx⊥ in SR passing through the origin having x0 as normal, the
⊥ as normal.27 second in the line Lψ0 through the origin having ψ0
0
We can now apply the following theorem from plane geometry:
Theorem 4. If L1 and L2 are lines in the Euclidean plane R2 intersecting at a point O; and if β is the angle in the plane from L1 to L2 , then the operation of re?ection in L1 followed by re?ection in L2 is just rotation by angle 2β about the point O.
is the same as the angle from x⊥ 0 to ψ0 , which in turn is the same as the ⊥ angle from x0 to ψ0 . Then by the above theorem QSR = Iψ⊥ Ix0 is 0 a rotation about the origin by the angle 2β .
Let β denote the angle in SR from Lx⊥ to Lψ0 , which by plane geometry
0
The key idea in Grover’s algorithm is to move ψ0 toward the unknown state x0 by successively applying the rotation Q to ψ0 to rotate it around to x0 . This process is called amplitude ampli?cation. Once this process is completed, the measurement of the resulting state (with respect to the standard basis) will, with high probability, yield the unknown state x0 . This is the essence of Grover’s algorithm.
27
The line Lx⊥ is the intersection of the plane SR with the hyperplane in H orthogonal
0
to x0 . A similar statement can be made in regard to Lψ0 .
86
SAMUEL J. LOMONACO, JR.
But how many times K should we apply the rotation Q to ψ0 ? If we applied Q too many or too few times, we would over or undershoot our target state x0 .
We determine the integer K as follows: Since ψ0 = sin β x0 + cos β x⊥ 0 the state resulting after k applications of Q is ψk = Qk ψ0 = sin [(2k + 1) β ] x0 + cos [(2k + 1) β ] x⊥ 0 sin [(2k + 1) β ] is as close as possible to 1. In other words, we seek to ?nd the smallest positive integer K = k such that (2k + 1) β is as close as possible to π/2. It follows that28 K = k = round π 1 ? 4β 2 , . ,
Thus, we seek to ?nd the smallest positive integer K = k such that
where “round” is the function that rounds to the nearest integer.
We can determine the angle β by noting that the angle α from ψ0 and x0 is complementary to β , i.e., α + β = π/2 , and hence, π 1 √ = x0  ψ0 = cos α = cos( ? β ) = sin β . 2 N Thus, the angle β is given by β = sin?1 and hence, ? 1 √ N 1 (for large N ) , ≈√ N ? π√ 1 N? 4 2
K = k = round ?
28
π 4 sin?1
1 √ N
The reader may prefer to use the f loor function instead of the round function.
1 ? ? ≈ round 2
(for large N ).
A ROSSETTA STONE FOR QUANTUM MECHANICS
87
14.5. Summary of Grover’s algorithm. In summary, we provide the following outline of Grover’s algorithm: Grover’s Algorithm STEP 0. (Initialization) ψ ←? H 0 = k STEP 1. ←? 0
π √ 4 sin?1 (1/ N ) 1 √ N N ?1 j =0
j
Loop until k = round
?
1 2
≈ round
π 4
√ N?
1 2
ψ ←? Q ψ = ?HI0 HIx0 ψ k STEP 2. ←? k + 1 Measure ψ with respect to the standard basis 0 , 1 , . . . , N ? 1 to obtain the marked unknown 1 . state x0 with probability ≥ 1 ? N
We complete our summary with the following theorem: Theorem 5. With a probability of error29 1 P robE ≤ , N Grover’s algorithm ?nds the unknown state x0 at a computational cost of √ N lg N O Proof. Part 1. The probability of error P robE of ?nding the hidden state x0 is given by P robE = cos2 [(2K + 1) β ] , where ? ?1 ? ? ? β = sin
1 √ N
If the reader prefers to use the f loor function rather than the round function, then 4 4 ?N probability of error becomes P robE ≤ N 2.
29
? ? ? K = round
,
π 4β
?
1 2
88
SAMUEL J. LOMONACO, JR.
where “round” is the function that rounds to the nearest integer. Hence,
π 4β
?1 ≤ K ≤ Thus,
π 4β
=?
π 2
? β ≤ (2K + 1) β ≤
π 2
π 2
+β
π 2
=? sin β = cos
? β ≥ cos [(2K + 1) β ] ≥ cos 1 √ N = 1 N
+ β = ? sin β
P robE = cos2 [(2K + 1) β ] ≤ sin2 β = sin2 sin?1
n?1 Part 2. The computational cost of the Hadamard transform H = 0 H (2) is O(n) = O(lg N ) single qubit operations. The transformations ?I0 and Ix0 each carry a computational cost of O(1). STEP 1 is the computationally dominant step. In STEP 1 there are √ N iterations. In each iteration, the Hadamard transform is apO plied twice. The transformations ?I0 and Ix0 are each applied once. Hence, each iteration comes with √ a computational cost of O (lg N ), and so the total cost of STEP 1 is O( N lg N ).
14.6. An example of Grover’s algorithm. As an example, we search a database consisting of N = 2n = 8 records for an unknown record with the unknown label x0 = 5. The calculations for this example were made with OpenQuacks , which is an open source quantum simulator Maple package developed at UMBC and publically available.
We are given a blackbox computing device In → that implements as an oracle the ? 1 ? 0 ? ? 0 ? ? 0 ? Ix0 = I5 = ? ? ? 0 ? ? 0 ? ? 0 0 I? → Out
unknown unitary transformation ? 0 0 0 0 0 0 0 1 0 0 0 0 0 0 ? ? 0 1 0 0 0 0 0 ? ? 0 0 1 0 0 0 0 ? ? ? ? 0 0 0 ?1 0 0 0 ? ? 0 0 0 0 1 0 0 ? ? 0 0 0 0 0 1 0 ? 0 0 0 0 0 0 1
A ROSSETTA STONE FOR QUANTUM MECHANICS
89
We cannot open up the blackbox →
I?
→ to see what is inside.
So we do not know what Ix0 and x0 are. The only way that we can glean some information about x0 is to apply some chosen state ψ as input, and then make use of the resulting output.
Using of the blackbox → a computing device → operator
I?
→ as a component device, we construct → which implements the unitary ?1 ?1 ?1 ?1 1 1 1 1 1 1 1 1 1 1 1 1 ?
?HI0 HI? ?
Q = ?HI0 HIx0
? ? ? ? ? 1? = ? 4? ? ? ? ? ?
?3 1 1 1 1 ?3 1 1 1 1 ?3 1 1 1 1 ?3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 1 ?1 ?3 1 ?1 1 ?3 ?1 1 1
? ? ? ? ? ? ? ? 1 ? ? 1 ? ? 1 ? ?3
We do not know what unitary transformation Q is implemented by the device → ?HI0 HI? → because the blackbox → I? → is one
of its essential components. STEP 0. We begin by preparing the known state ψ0 = H 0 = STEP 1. We proceed to loop K = round π 4 sin
?1 1 √ 8
(1, 1, 1, 1, 1, 1, 1, 1) transpose
1 √ ? 2 1/ 8
=2
times in STEP 1. Iteration 1. On the ?rst iteration, we obtain the unknown state ψ1 = Q ψ0 =
1 √ 4 2
(1, 1, 1, 1, 5, 1, 1, 1) transpose
90
SAMUEL J. LOMONACO, JR.
Iteration 2. On the second iteration, we obtain the unknown state ψ2 = Q ψ1 =
1 √ 8 2
(?1, ?1, ?1, ?1, 11, ?1, ?1, ?1) transpose
and branch to STEP 2. STEP 2. We measure the unknown state ψ2 to obtain either with probability 5
P robSuccess = sin2 ((2K + 1) β ) = or some other state with probability P robF ailure = cos2 ((2K + 1) β ) = and then exit.
121 = 0.9453 128 7 = 0.0547 128
15. There is much more to quantum computation
Needles to say, there is much more to quantum computation. I hope that you found this introductory paper useful.
References
[1] Barenco, A, C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J.A. Smolin, and H. Weinfurter, Elementary gates for quantum computation, Phys. Rev. A, 52, (1995), pp 3475  3467. [2] Beardon, Alan F., “The Geometry of Discrete Groups,” SpringerVerlag, (1983). [3] Bell, J.S., Physics, 1, (1964), pp 195  200. [4] Bell, J.S., “Speakable and Unspeakable in Quantum Mechanics,” Cambridge University Press (1987). [5] Bennett, C.H. et al., Phys. Rev. Lett. 70, (1995), pp 1895. [6] Bennett, C.H., D.P. DiVincenzo, J.A. Smolin, and W.K. Wootters, Ohys. Rev. A, 54, (1996), pp 3824. [7] Berman, Gennady, Gary D. Doolen, Ronnie Mainieri, and Vladimir I. Tsifrinovich, “Introduction to Quantum Computation,” World Scienti?c (1999). [8] Bernstein, Ethan, and Umesh Vazirani, Quantum complexity theory, Siam J. Comput., Vol. 26, No.5 (1997), pp 1411  1473. [9] Brandt, Howard E., Qubit devices and the issue of quantum decoherence, Progress in Quantum Electronics, Vol. 22, No. 5/6, (1998), pp 257  370.
A ROSSETTA STONE FOR QUANTUM MECHANICS
91
[10] Brandt, Howard E., Qubit devices, Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000,” to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) [11] Brassard, Gilles, and Paul Bratley, “Algorithmics: Theory and Practice,” PrinticeHall, (1988). [12] Brooks, Michael (Ed.), “Quantum Computing and Communications,” SpringerVerlag (1999). [13] Bub, Je?rey, “Interpreting the Quantum World,” Cambridge University Press (1997). [14] Cartan, Henri, and Samuel Eilenberg, “Homological Algebra,” Princeton University Press, Princeton, New Jersey, (1956) [15] Cerf, Nicholas J. and Chris Adami, “Quantum information theory of entanglement and measurement,” in Proceedings of Physics and Computation, PhysComp’96, edited by J. Leao T. To?oli, pp 65  71. See also quantph/9605039 . [16] CohenTannoudji, Claude, Bernard Diu, and Frank Lalo¨ e, “Quantum Mechanics,” Volumes 1 & 2, John Wiley & Sons (1977) [17] D’Espagnat, Bernard, “Veiled Reality: Analysis of Present Day Quantum Mechanical Concepts,” AddisonWesley (1995) [18] D’Espagnat, Bernard, “Conceptual Foundations of Quantum Mechanics,” (Second Edition), AddisonWesley (1988) [19] Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest, “Introduction to Algorithms,” McGrawHill, (1990). [20] Cox, David, John Little, and Donal O’Shea, “Ideals, Varieties, and Algorithms,” (second edition), SpringerVerlag, (1996). [21] Davies, E.B., “Quantum Theory of Open Systems,” Academic Press, (1976). [22] Deutsch, David, “The Fabric of Reality,” Penguin Press, New York (1997). [23] Deutsch, David, and Patrick Hayden, Information ?ow in entangled quantum systems, quantph/9906007. [24] Deutsch, David, Quantum theory, the ChurchTuring principle and the universal quantum computer, Proc. Royal Soc. London A, 400, (1985), pp 97  117. [25] Dirac, P.A.M., “The Principles of Quantum Mechanics,” (Fourth edition). Oxford University Press (1858). [26] Einstein, A., B. Podolsky, N. Rosen, Can quantum, mechanical description of physical reality be considered complete?, Phys. Rev. 47, 777 (1935); D. Bohm “Quantum Theory”, PrenticeHall, Englewood Cli?s, NJ (1951). [27] Ekert, Artur K.and Richard Jozsa, Quantum computation and Shor’s factoring algorithm, Rev. Mod. Phys., 68,(1996), pp 733753. [28] Feynman, Richard P., Robert B. Leighton, and Matthew Sands, “The Feyman Lectures on Physics: Vol. III. Quantum Mechanics,” AddisonWesley Publishing Company, Reading, Massachusetts (1965). [29] Feynman, Richard P., “Feynman Lectures on Computation,” (Edited by Anthony J.G. Hey and Robin W. Allen), AddisonWesley, (1996). [30] Gilmore, Robert, “Alice in Quantumland,” SpringerVerlag (1995). [31] Gottesman, Daniel, The Heisenberg representation of quantum computers, quantph/9807006. [32] Gottesman, Daniel, An introduction to quantum error correction, Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000,” to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) (quantph/0004072) [33] Gottfreid, “Quantum Mechanics: Volume I. Fundamentals,” AddisonWesley (1989).
92
SAMUEL J. LOMONACO, JR.
[34] Grover, Lov K., Quantum computer can search arbitrarily large databases by a single querry, Phys. Rev. Letters (1997), pp 47094712. [35] Grover, Lov K., A framework for fast quantum mechanical algorithms, quantph/9711043. [36] Grover, L., Proc. 28th Annual ACM Symposium on the Theory of Computing, ACM Press, New Yorkm (1996), pp 212  219. [37] Grover, L., Phys. Rev. Lett. 78, (1997), pp 325  328. [38] Gruska, Jozef, “Quantum Computing,” McGrawHill, (1999) [39] Gunther, Ludwig, “An Axiomatic Basis for Quantum Mechanics: Volume I. Derivation of Hilbert Space Structure,” SpringerVerlag (1985). [40] Haag, R., “Local Quantum Physics: Fields, Particles, Algebras,” (2nd revised edition), SpringerVerlag. [41] Heisenberg, Werner, “The Physical Principles of Quantum Theory,” translated by Eckart and Hoy, Dover. [42] Hardy, G.H., and E.M. Wright, “An Introduction to the Theory of Numbers,” Oxford Press, (1965). [43] Helstrom, Carl W., “Quantum Detection and Estimation Theory,” Academic Press (1976). [44] Hey, Anthony J.G. (editor), “Feynman and Computation,” Perseus Books, Reading, Massachusetts, (1998). [45] Horodecki, O., M. Horodecki, and R. Horodecki, Phys. Rev. Lett. 82, (1999), pp 1056. [46] Holevo, A.S., “Probabilistic and Statistical Aspects of Quantum Theory,” NorthHolland, (1982). [47] Hoyer, Peter, E?cient quantum transforms, quantph/9702028. [48] Jauch, Josef M., “Foundations of Quantum Mechanics,” AddisonWesley Publishing Company, Reading, Massachusetts (1968). [49] Jozsa, Richard, Searching in Grover’s Algorithm, quantph/9901021. [50] Jozsa, Richard, Quantum algorithms and the Fourier transform, quantph preprint archive 9707033 17 Jul 1997. [51] Jozsa, Richard, Proc. Roy. Soc. London Soc., Ser. A, 454, (1998), 323  337. [52] Kau?man, Louis H., Quantum topology and quantum computing, Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000,” to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) [53] Kitaev, A., Quantum measurement and the abelian stabiliser problem, (1995), quantph preprint archive 9511026. [54] Kitaev, Alexei, Quantum computation with anyons, Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000,” to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) [55] Lang, Serge, “Algebra,” Addison Wesley (1971). [56] Lenstra, A.K., and H.W. Lenstra, Jr., eds., “The Development of the Number Field Sieve,” Lecture Notes in Mathematics, Vol. 1554, SpringerVelag, (1993). [57] Lenstra, A.K., H.W. Lenstra, Jr., M.S. Manasse, and J.M. Pollard, The number ?eld sieve. Proc. 22nd Annual ACM Symposium on Theory of ComputingACM, New York, (1990), pp 564  572. (See exanded version in Lenstra & Lenstra, (1993), pp 11  42.) [58] LeVeque, William Judson, “Topics in Number Theory: Volume I,” AddisonWesley, (1958). [59] Linden, N., S. Popescu, and A. Sudbery, Nonlocal properties of multiparticle density matrices, quantph/9801076.
A ROSSETTA STONE FOR QUANTUM MECHANICS
93
[60] Lo, HoiKwong, Tim Spiller & Sandu Popescu(editors), “Introduction to Quantum Computation & Information,” World Scienti?c (1998). [61] Lomonaco, Samuel J., Jr., “A tangled tale of quantum entanglement: Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000,” to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) [62] Lomonaco, Samuel J., Jr., A quick glance at quantum cryptography, Cryptologia, Vol. 23, No. 1, January,1999, pp 141. (quantph/9811056) [63] Lomonaco, Samuel J., Jr., A talk on quantum cryptography: How Alice Outwits Eve, in “Coding Theory and Cryptography: From Enigma and Geheimsschreiber to Quantum Theory,” edited by David Joyner, SpringerVerlag, (2000), pp 144  174. [64] Mackey, George W., “Mathematical Foundations of Quantum Mechanics,” AddisonWesley (1963). [65] Milburn, Gerald J., “The Feynman Processor,” Perseus Books, Reading, Massachusetts (1998) [66] Miller, G.L., Riemann’s hypothesis and tests for primality, J. Comput. System Sci., 13, (1976), pp 300  317. [67] Nielsen, M.A., Continuity bounds on entanglement, Phys. Rev. A, Vol. 61, 064301, pp 14. [68] Omn` es, Roland, “An Interpretation of Quantum Mechanics,” Princeton University Press, Princeton, New Jersey, (1994). [69] Omn` es, Roland, “Understanding Quantum Mechanics,” Princeton University Press (1999). [70] von Neumann, John, “Mathematical Foundations of Quantum Mechanics,” Princeton University Press. [71] Penrose, Roger, “The Large, the Small and the Human Mind,” Cambridge University Press, (1997). [72] Peres, Asher, “Quantum Theory: Concepts and Methods,” Kluwer Academic Publishers, Boston, (1993). [73] Raymond, Pierre, “Field Theory: A Modern Primer,” AddisonWesley (1989). [74] Piron, C., “Foundations of Quantum Physics,” AddisonWesley, (1976). [75] Sakurai, J.J., “Modern Quantum Mechanics,” (Revised edition), AddisonWesley Publishing Company, Reading, Massachusetts (1994). [76] Schumacher, Benjamin, Sending entanglement through noisy quantum channels, (22 April 1996), quantph/9604023. [77] Shor, Peter W., Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. on Computing, 26(5) (1997), pp 1484  1509. (quantph/9508027) [78] Shor, Peter W., Introduction to quantum algorithms, Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000,” to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) (quantph/0005003) [79] Stinson, Douglas R., “Cryptography: Theory and Practice,” CRC Press, Boca Raton, (1995). [80] Vazirani, Umesh, Quantum complexity theory, Lecture Notes for the AMS Short Course on Quantum Computation, Washington, DC, January 2000, to appear in “Quantum Computation,” edited by S.J. Lomonaco, AMS PSAPM Series. (To appear) [81] Williams, Collin P., and Scott H. Clearwater, “Explorations in Quantum Computation,” SpringerVerlag (1997). [82] Williams, Colin, and Scott H. Clearwater, “Ultimate Zero and One,” Copernicus, imprint by SpringerVerlag, (1998).
94
SAMUEL J. LOMONACO, JR.
[83] Wootters, W.K., and W.H. Zurek, A single quantum cannot be cloned, Nature, Vol. 299, 28 October 1982, pp 982  983.
Index
Adjoint, 12 Big, 27 Little, 27 Alice, 37, 39 Ancilla, 41 Automorphism Group, 49 Bennett, 35, 48 Blackbox, 79, 87 Bob, 37, 39 Bra, 8 Bracket, 8 CNOT, see also ControlledNOT Commutator, 18, 27 Complex Projective Space CP n?1 , 10 Computation Irreversible, 50 Reversible, 48 Computational Step, 47 Computing Device Classical, 47 Quantum, 47 Constituent “Part”, 26 Continued Fraction, 68 Convergent of, 69 ControlledNOT, 49, 51, 52 Convergent, see also Continued Fraction CRCD, see also Computing Device, Classlical Reversible Density Operator, 20–27 Deutsch, 30, 60 Diagonalization, 21, 44 Dirac Notation, 8–12, 17 Dynamic Invariants, 44 Eigenket, 13 Eigenvalue, 13 Degenerate, 13 Nondegenerate, 13 Einstein, 35 Embedding, 47, 50 Ensemble Mixed, 21–23 Pure, 21, 45 Entangled, Quantum, 30, 42 Entanglement Classes, 39 Quantum, 34 Type, 39 Entropy, Classical, 42, 43
95
Entropy, Shannon, 42 Entropy, von Neumann, 43, 45 EPR, 33, 35, 38 Euler’s constant, 72 Expected Value, 17 Filtration, 15 Fourier Transform, 64 γ , see also Euler’s Constant Global Quantum System, 26 Global Unitary Transformation, 38 Gottesman, 30 Grover’s Algorithm, 78, 89 Hamiltonian, 19 Heisenberg Uncertainty Principle, 18 Heisenberg, Picture, 28, 30 Hermitian Operator, 13 Hilbert Space, 7 Inversion, 80 Juxtaposition, 30 Ket, 8 Kronecker Sum, 39 lg, 42 Lie Group, 38 Local Su?ciently, 41 Local Equivalence, 39 Local Interaction, 36 Local Lie Algebra, 39 Local Subgroup, 38 Local Unitary Transformation, 38 Measurement, 14, 17, 22 Mobius Inversion, 80 Multipartite Quantum System, 26 Nielsen, 35 NoCloning Theorem, 54, 56 NonLocality, 36, 37 NOT gate, 52 Observable, 13 Complete, 13 Incompatible Operators, 18 Selective Measurement, 15 Observable, Measurement, 13 Observables
96
SAMUEL J. LOMONACO, JR.
Compatible Operators, 18 OpenQuacks Public Domain Software, 87 Operator Compatible, 18 Hermitian, 13 Incompatible, 18 Measurement, 13 SelfAdjoint, 13 Unitary, 19 Orbits, 39 Partial Trace, 24, 26 Partition, 41 PathOrdered Integral, 20 Pauli Spin Matrices, 14 Permutation Group, 48 Planck’s Constant, 19 Podolsky, 35 Polarized Light, 5, 6 Positive Operator Valued Measure, 16 POVM, 16 Primality Testing, 61 Principle of NonLocality, 36, 37 Probabilistic Operator Valued Measure, 16 Probability Distribution, 42 Projection Operator, 45 Quantum Repeater, 56 Replicator, 55 Quantum Entangled, 30, 34, 42 Quantum Register, 31, 32 Qubit, 6, 7 Radix 2 Representation, 63 Reality Principle of, 36 Repeater Quantum, 56 Replicator Quantum, 55 Reversible Computation, 48 Rosen, 35 Rotation, 53 round function, 84 Schrodinger Picture, 28 Selective Measurement Operator, 15 SelfAdjoint Operator, 13 Shor, 59 Shor’s Algorithm, 60, 78 Spacelike Distance, 37 Square Root of
NOT, 53 SWAP, 53 Standard Deviation, 18 Standard Unitary Representation, 50 Stochastic Source, 42 Su?ciently Local Unitary Transformation, see also Unitary Superluminal Communication, 37 Superposition, 6, 31, 32 SWAP Gate, 52 Symbols Output, 42, 45 Symmetric Group, 50 Teleportation, 56 Teleportation, Quantum, 56, 59 Tensor Product, 9 To?oli Gate, 49, 51 Trace, 24 Unitary Operator, 19 Su?ciently Local, 41 Transformation, 19 ?(?), asymptotic lower bound, 73 Wiring Diagram, 49–54 Wiring Diagrams Implicit Frame, 53 Wootters, 35, 54 Zurek, 54
A ROSSETTA STONE FOR QUANTUM MECHANICS
97
Dept. of Comp. Sci. & Elect. Engr., University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, MD 21250 Email address : EMail: Lomonaco@UMBC.EDU URL: WebPage: http://www.csee.umbc.edu/~lomonaco