Ouantum bits 15 Because la+2=1,we may rewrite Equation(1.1)as 1w)=e (0+ep） (1.3) where 0,and y are real numbers.In Chapter 2 we will see that we can ignore the factor of ei out the front,because it has no observable effects,and for that reason we can effectively write cos+el sin ) (1.4) The numbers 0 and o define a point on the unit three-dimensional sphere,as shown in Figure 1.3.This sphere is often called the Bloch sphere;it provides a useful means of visualizing the state of a single qubit,and often serves as an excellent testbed for ideas about quantum computation and quantum information.Many of the operations on single qubits which we describe later in this chapter are neatly described within the Bloch sphere picture.However,it must be kept in mind that this intuition is limited because there is no simple generalization of the Bloch sphere known for multiple qubits. 10》 1〉 Figure 1.3.Bloch sphere representation of a qubit. How much information is represented by a qubit?Paradoxically,there are an infinite number of points on the unit sphere,so that in principle one could store an entire text of Shakespeare in the infinite binary expansion of 0.However,this conclusion turns out to be misleading,because of the behavior of a qubit when observed.Recall that measurement of a qubit will give only either 0 or 1.Furthermore,measurement changes the state of a qubit,collapsing it from its superposition of 0)and 1)to the specific state consistent with the measurement result.For example,if measurement of +gives 0, then the post-measurement state of the qubit will be 0).Why does this type of collapse occur?Nobody knows.As discussed in Chapter 2,this behavior is simply one of the fundamental postulates of quantum mechanics.What is relevant for our purposes is that from a single measurement one obtains only a single bit of information about the state of the qubit,thus resolving the apparent paradox.It turns out that only if infinitely many
Quantum bits 15 Because |α| 2 + |β| 2 = 1, we may rewrite Equation (1.1) as |ψ = eiγ cos θ 2 |0 + eiϕ sin θ 2 |1 , (1.3) where θ, ϕ and γ are real numbers. In Chapter 2 we will see that we can ignore the factor of eiγ out the front, because it has no observable effects, and for that reason we can effectively write |ψ = cos θ 2 |0 + eiϕ sin θ 2 |1. (1.4) The numbers θ and ϕ define a point on the unit three-dimensional sphere, as shown in Figure 1.3. This sphere is often called the Bloch sphere; it provides a useful means of visualizing the state of a single qubit, and often serves as an excellent testbed for ideas about quantum computation and quantum information. Many of the operations on single qubits which we describe later in this chapter are neatly described within the Bloch sphere picture. However, it must be kept in mind that this intuition is limited because there is no simple generalization of the Bloch sphere known for multiple qubits. ϕ |ψ θ x y z Figure 1.3. Bloch sphere representation of a qubit. How much information is represented by a qubit? Paradoxically, there are an infinite number of points on the unit sphere, so that in principle one could store an entire text of Shakespeare in the infinite binary expansion of θ. However, this conclusion turns out to be misleading, because of the behavior of a qubit when observed. Recall that measurement of a qubit will give only either 0 or 1. Furthermore, measurement changes the state of a qubit, collapsing it from its superposition of |0 and |1 to the specific state consistent with the measurement result. For example, if measurement of |+ gives 0, then the post-measurement state of the qubit will be |0. Why does this type of collapse occur? Nobody knows. As discussed in Chapter 2, this behavior is simply one of the fundamental postulates of quantum mechanics. What is relevant for our purposes is that from a single measurement one obtains only a single bit of information about the state of the qubit, thus resolving the apparent paradox. It turns out that only if infinitely many
16 Introduction and overview identically prepared qubits were measured would one be able to determine o and B for a qubit in the state given in Equation(1.1). But an even more interesting question to ask might be:how much information is represented by a qubit if we do not measure it?This is a trick question,because how can one quantify information if it cannot be measured?Nevertheless,there is something conceptually important here,because when Nature evolves a closed quantum system of qubits,not performing any 'measurements',she apparently does keep track of all the continuous variables describing the state,like a and B.In a sense,in the state of a qubit, Nature conceals a great deal of 'hidden information'.And even more interestingly,we will see shortly that the potential amount of this extra 'information'grows exponentially with the number of qubits.Understanding this hidden quantum information is a question that we grapple with for much of this book,and which lies at the heart of what makes quantum mechanics a powerful tool for information processing 1.2.1 Multiple qubits Hilbert space is a big place. Carlton Caves Suppose we have two qubits.If these were two classical bits,then there would be four possible states,00,01,10,and 11.Correspondingly,a two qubit system has four com- putational basis states denoted 00),01),10),11).A pair of qubits can also exist in superpositions of these four states,so the quantum state of two qubits involves associating a complex coefficient-sometimes called an amplitude-with each computational basis state,such that the state vector describing the two qubits is b）=a00l00)+ao101)+a1ol10)+a11l11) (1.5) Similar to the case for a single qubit,the measurement result (=00,01,10 or 11)occurs with probability o2,with the state of the qubits after the measurement being )The condition that probabilities sum to one is therefore expressed by the normalization condition that1,where the notation0,1)2,means 'the set of strings of length two with each letter being either zero or one'.For a two qubit system,we could measure just a subset of the qubits,say the first qubit,and you can probably guess how this works:measuring the first qubit alone gives 0 with probability ooo+oo2,leaving the post-measurement state 1w）=a0l00+ao1l01 (1.6) VQ00+2012 Note how the post-measurement state is re-normalized by the factor so that it still satisfies the normalization condition,just as we expect for a legitimate quantum state. An important two qubit state is the Bell state or EPR pair, 100)+111) (1.7) V2 This innocuous-looking state is responsible for many surprises in quantum computation
16 Introduction and overview identically prepared qubits were measured would one be able to determine α and β for a qubit in the state given in Equation (1.1). But an even more interesting question to ask might be: how much information is represented by a qubit if we do not measure it? This is a trick question, because how can one quantify information if it cannot be measured? Nevertheless, there is something conceptually important here, because when Nature evolves a closed quantum system of qubits, not performing any ‘measurements’, she apparently does keep track of all the continuous variables describing the state, like α and β. In a sense, in the state of a qubit, Nature conceals a great deal of ‘hidden information’. And even more interestingly, we will see shortly that the potential amount of this extra ‘information’ grows exponentially with the number of qubits. Understanding this hidden quantum information is a question that we grapple with for much of this book, and which lies at the heart of what makes quantum mechanics a powerful tool for information processing. 1.2.1 Multiple qubits Hilbert space is a big place. – Carlton Caves Suppose we have two qubits. If these were two classical bits, then there would be four possible states, 00, 01, 10, and 11. Correspondingly, a two qubit system has four computational basis states denoted |00, |01, |10, |11. A pair of qubits can also exist in superpositions of these four states, so the quantum state of two qubits involves associating a complex coefficient – sometimes called an amplitude – with each computational basis state, such that the state vector describing the two qubits is |ψ = α00|00 + α01|01 + α10|10 + α11|11. (1.5) Similar to the case for a single qubit, the measurement result x (= 00, 01, 10 or 11) occurs with probability |αx| 2, with the state of the qubits after the measurement being |x. The condition that probabilities sum to one is therefore expressed by the normalization condition that x∈{0,1}2 |αx| 2 = 1, where the notation ‘{0, 1}2 ’ means ‘the set of strings of length two with each letter being either zero or one’. For a two qubit system, we could measure just a subset of the qubits, say the first qubit, and you can probably guess how this works: measuring the first qubit alone gives 0 with probability |α00| 2 +|α01| 2 , leaving the post-measurement state |ψ = α00|00 + α01|01 |α00| 2 + |α01| 2 . (1.6) Note how the post-measurement state is re-normalized by the factor |α00| 2 + |α01| 2 so that it still satisfies the normalization condition, just as we expect for a legitimate quantum state. An important two qubit state is the Bell state or EPR pair, |00 + |11 √ 2 . (1.7) This innocuous-looking state is responsible for many surprises in quantum computation
Ouantum computation 17 and quantum information.It is the key ingredient in quantum teleportation and super- dense coding,which we'll come to in Section 1.3.7 and Section 2.3,respectively,and the prototype for many other interesting quantum states.The Bell state has the property that upon measuring the first qubit,one obtains two possible results:0 with probability 1/2,leaving the post-measurement state )=00),and I with probability 1/2,leaving )=11).As a result,a measurement of the second qubit always gives the same result as the measurement of the first qubit.That is,the measurement outcomes are correlated. Indeed,it turns out that other types of measurements can be performed on the Bell state,by first applying some operations to the first or second qubit,and that interesting correlations still exist between the result of a measurement on the first and second qubit. These correlations have been the subject of intense interest ever since a famous paper by Einstein,Podolsky and Rosen,in which they first pointed out the strange properties of states like the Bell state.EPR's insights were taken up and greatly improved by John Bell,who proved an amazing result:the measurement correlations in the Bell state are stronger than could ever exist between classical systems.These results,described in de- tail in Section 2.6,were the first intimation that quantum mechanics allows information processing beyond what is possible in the classical world. More generally,we may consider a system of n qubits.The computational basis states of this system are of the form 2...n),and so a quantum state of such a system is specified by 2n amplitudes.For n=500 this number is larger than the estimated number of atoms in the Universe!Trying to store all these complex numbers would not be possible on any conceivable classical computer.Hilbert space is indeed a big place. In principle,however,Nature manipulates such enormous quantities of data,even for systems containing only a few hundred atoms.It is as if Nature were keeping 2500 hidden pieces of scratch paper on the side,on which she performs her calculations as the system evolves.This enormous potential computational power is something we would very much like to take advantage of.But how can we think of quantum mechanics as computation? 1.3 Quantum computation Changes occurring to a quantum state can be described using the language of quantum computation.Analogous to the way a classical computer is built from an electrical circuit containing wires and logic gates,a quantum computer is built from a quantum circuit containing wires and elementary quantum gates to carry around and manipulate the quantum information.In this section we describe some simple quantum gates,and present several example circuits illustrating their application,including a circuit which teleports qubits! 1.3.1 Single qubit gates Classical computer circuits consist of wires and logic gates.The wires are used to carry information around the circuit,while the logic gates perform manipulations of the infor- mation,converting it from one form to another.Consider,for example,classical single bit logic gates.The only non-trivial member of this class is the NOT gate,whose operation is defined by its truth table,in which 01 and 1-0,that is,the 0 and I states are interchanged. Can an analogous quantum Nor gate for qubits be defined?Imagine that we had some process which took the state 0)to the state 1),and vice versa.Such a process
Quantum computation 17 and quantum information. It is the key ingredient in quantum teleportation and superdense coding, which we’ll come to in Section 1.3.7 and Section 2.3, respectively, and the prototype for many other interesting quantum states. The Bell state has the property that upon measuring the first qubit, one obtains two possible results: 0 with probability 1/2, leaving the post-measurement state |ϕ = |00, and 1 with probability 1/2, leaving |ϕ = |11. As a result, a measurement of the second qubit always gives the same result as the measurement of the first qubit. That is, the measurement outcomes are correlated. Indeed, it turns out that other types of measurements can be performed on the Bell state, by first applying some operations to the first or second qubit, and that interesting correlations still exist between the result of a measurement on the first and second qubit. These correlations have been the subject of intense interest ever since a famous paper by Einstein, Podolsky and Rosen, in which they first pointed out the strange properties of states like the Bell state. EPR’s insights were taken up and greatly improved by John Bell, who proved an amazing result: the measurement correlations in the Bell state are stronger than could ever exist between classical systems. These results, described in detail in Section 2.6, were the first intimation that quantum mechanics allows information processing beyond what is possible in the classical world. More generally, we may consider a system of n qubits. The computational basis states of this system are of the form |x1x2 ...xn, and so a quantum state of such a system is specified by 2n amplitudes. For n = 500 this number is larger than the estimated number of atoms in the Universe! Trying to store all these complex numbers would not be possible on any conceivable classical computer. Hilbert space is indeed a big place. In principle, however, Nature manipulates such enormous quantities of data, even for systems containing only a few hundred atoms. It is as if Nature were keeping 2500 hidden pieces of scratch paper on the side, on which she performs her calculations as the system evolves. This enormous potential computational power is something we would very much like to take advantage of. But how can we think of quantum mechanics as computation? 1.3 Quantum computation Changes occurring to a quantum state can be described using the language of quantum computation. Analogous to the way a classical computer is built from an electrical circuit containing wires and logic gates, a quantum computer is built from a quantum circuit containing wires and elementary quantum gates to carry around and manipulate the quantum information. In this section we describe some simple quantum gates, and present several example circuits illustrating their application, including a circuit which teleports qubits! 1.3.1 Single qubit gates Classical computer circuits consist of wires and logic gates. The wires are used to carry information around the circuit, while the logic gates perform manipulations of the information, converting it from one form to another. Consider, for example, classical single bit logic gates. The only non-trivial member of this class is the gate, whose operation is defined by its truth table, in which 0 → 1 and 1 → 0, that is, the 0 and 1 states are interchanged. Can an analogous quantum gate for qubits be defined? Imagine that we had some process which took the state |0 to the state |1, and vice versa. Such a process
18 Introduction and overview would obviously be a good candidate for a quantum analogue to the NOT gate.However, specifying the action of the gate on the states 0)and |1)does not tell us what happens to superpositions of the states 0)and 1),without further knowledge about the properties of quantum gates.In fact,the quantum NOT gate acts linearly,that is,it takes the state a0)+31〉 (1.8) to the corresponding state in which the role of 0)and |1)have been interchanged, a1)+310) (1.9) Why the quantum NOT gate acts linearly and not in some nonlinear fashion is a very interesting question,and the answer is not at all obvious.It turns out that this linear behavior is a general property of quantum mechanics,and very well motivated empirically; moreover,nonlinear behavior can lead to apparent paradoxes such as time travel,faster- than-light communication,and violations of the second laws of thermodynamics.We'll explore this point in more depth in later chapters,but for now we'll just take it as given. There is a convenient way of representing the quantum NOT gate in matrix form, which follows directly from the linearity of quantum gates.Suppose we define a matrix X to represent the quantum NOT gate as follows: X (1.10) (The notation X for the quantum NOT is used for historical reasons.)If the quantum state a0)+B1)is written in a vector notation as [ (1.11) with the top entry corresponding to the amplitude for 0)and the bottom entry the amplitude for 1),then the corresponding output from the quantum NOT gate is x[]-[] (1.12) Notice that the action of the NOT gate is to take the state 0)and replace it by the state corresponding to the first column of the matrix X.Similarly,the state |1)is replaced by the state corresponding to the second column of the matrix X. So quantum gates on a single qubit can be described by two by two matrices.Are there any constraints on what matrices may be used as quantum gates?It turns out that there are.Recall that the normalization condition requires a2+B2=1 for a quantum state 0)+B1).This must also be true of the quantum state =a'0)+B 1)after the gate has acted.It turns out that the appropriate condition on the matrix representing the gate is that the matrix U describing the single qubit gate be unitary,that is UU=I, where Ut is the adjoint of U(obtained by transposing and then complex conjugating U),and I is the two by two identity matrix.For example,for the Nor gate it is easy to verify that XX =I. Amazingly,this unitarity constraint is the only constraint on quantum gates.Any unitary matrix specifies a valid quantum gate!The interesting implication is that in contrast to the classical case,where only one non-trivial single bit gate exists-the NOT
18 Introduction and overview would obviously be a good candidate for a quantum analogue to the gate. However, specifying the action of the gate on the states |0 and |1 does not tell us what happens to superpositions of the states |0 and |1, without further knowledge about the properties of quantum gates. In fact, the quantum gate acts linearly, that is, it takes the state α|0 + β|1 (1.8) to the corresponding state in which the role of |0 and |1 have been interchanged, α|1 + β|0. (1.9) Why the quantum gate acts linearly and not in some nonlinear fashion is a very interesting question, and the answer is not at all obvious. It turns out that this linear behavior is a general property of quantum mechanics, and very well motivated empirically; moreover, nonlinear behavior can lead to apparent paradoxes such as time travel, fasterthan-light communication, and violations of the second laws of thermodynamics. We’ll explore this point in more depth in later chapters, but for now we’ll just take it as given. There is a convenient way of representing the quantum gate in matrix form, which follows directly from the linearity of quantum gates. Suppose we define a matrix X to represent the quantum gate as follows: X ≡ 0 1 1 0 . (1.10) (The notation X for the quantum is used for historical reasons.) If the quantum state α|0 + β|1 is written in a vector notation as α β , (1.11) with the top entry corresponding to the amplitude for |0 and the bottom entry the amplitude for |1, then the corresponding output from the quantum gate is X α β = β α . (1.12) Notice that the action of the gate is to take the state |0 and replace it by the state corresponding to the first column of the matrix X. Similarly, the state |1 is replaced by the state corresponding to the second column of the matrix X. So quantum gates on a single qubit can be described by two by two matrices. Are there any constraints on what matrices may be used as quantum gates? It turns out that there are. Recall that the normalization condition requires |α| 2 + |β| 2 = 1 for a quantum state α|0 + β|1. This must also be true of the quantum state |ψ = α |0 + β |1 after the gate has acted. It turns out that the appropriate condition on the matrix representing the gate is that the matrix U describing the single qubit gate be unitary, that is U†U = I, where U† is the adjoint of U (obtained by transposing and then complex conjugating U), and I is the two by two identity matrix. For example, for the gate it is easy to verify that X†X = I. Amazingly, this unitarity constraint is the only constraint on quantum gates. Any unitary matrix specifies a valid quantum gate! The interesting implication is that in contrast to the classical case, where only one non-trivial single bit gate exists – the
Ouantum computation 19 10) ※ V2 Figure 1.4.Visualization of the Hadamard gate on the Bloch sphere,acting on the input state(0)+ gate-there are many non-trivial single qubit gates.Two important ones which we shall use later are the Z gate: (1.13) which leaves 0)unchanged,and flips the sign of 1)to give-1),and the Hadamard gate, a=} (1.14) This gate is sometimes described as being like a 'square-root of NOT'gate,in that it turns a 0)into (0)+1))/v2 (first column of H),'halfway'between 0)and |1),and turns 1)into (0)-1))/v2 (second column of H),which is also 'halfway'between 0)and 1).Note,however,that H2 is not a NoT gate,as simple algebra shows that H2=I,and thus applying H twice to a state does nothing to it. The Hadamard gate is one of the most useful quantum gates,and it is worth trying to visualize its operation by considering the Bloch sphere picture.In this picture,it turns out that single qubit gates correspond to rotations and reflections of the sphere.The Hadamard operation is just a rotation of the sphere about the axis by 90,followed by a rotation about the axis by 180,as illustrated in Figure 1.4.Some important single qubit gates are shown in Figure 1.5,and contrasted with the classical case. a1o)+31y X 310)+al1)》 a10)+31)y a0)-311〉 a10)+3I1)〉 H Figure 1.5.Single bit(left)and qubit(right)logic gates. There are infinitely many two by two unitary matrices,and thus infinitely many single
Quantum computation 19 x x x y y y z z z Figure 1.4. Visualization of the Hadamard gate on the Bloch sphere, acting on the input state (|0 + |1)/ √2. gate – there are many non-trivial single qubit gates. Two important ones which we shall use later are the Z gate: Z ≡ 1 0 0 −1 , (1.13) which leaves |0 unchanged, and flips the sign of |1 to give −|1, and the Hadamard gate, H ≡ 1 √ 2 1 1 1 −1 . (1.14) This gate is sometimes described as being like a ‘square-root of ’ gate, in that it turns a |0 into (|0 + |1)/ √ 2 (first column of H), ‘halfway’ between |0 and |1, and turns |1 into (|0−|1)/ √ 2 (second column of H), which is also ‘halfway’ between |0 and |1. Note, however, that H2 is not a gate, as simple algebra shows that H2 = I, and thus applying H twice to a state does nothing to it. The Hadamard gate is one of the most useful quantum gates, and it is worth trying to visualize its operation by considering the Bloch sphere picture. In this picture, it turns out that single qubit gates correspond to rotations and reflections of the sphere. The Hadamard operation is just a rotation of the sphere about the yˆ axis by 90◦, followed by a rotation about the xˆ axis by 180◦, as illustrated in Figure 1.4. Some important single qubit gates are shown in Figure 1.5, and contrasted with the classical case. Figure 1.5. Single bit (left) and qubit (right) logic gates. There are infinitely many two by two unitary matrices, and thus infinitely many single