Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Подождите немного. Документ загружается.

16.1 Quantum bits 307

therefore,

|q=







|0+







|1, (16.5)

where α



,β



are any complex numbers.

To provide an illustration, let us come back to the analogy of the closed box containing

a coin, and tell the story again with the qubit formalism. The box has been shaken to the

point that it is impossible to tell on which side, heads or tails, the coin may be found.

We can assume without loss of generality that the coin is “fair,” and that it must rest on

either side at the bottom of the box, so that the probabilities of the coin being on heads

or on tails are strictly equal. This deﬁnes two equiprobable “coin states;” call them here

|H  and



. As long as we don’t open the box, the coin remains in the superposition of

states corresponding to the qubit:

|q=

√

|H +

√



(16.6)

with the amplitudes satisfying |α|

=|β|

=(1/

√

≡ 1/2. Thus, from the quantum

viewpoint, the coin inside the closed box does exist in both heads and tails states. The

action of opening the box and checking the physical position of the coin yields the qubit

projection |H  or



, which corresponds to either of the classical bits 0 = heads or 1

= tails, respectively, with equal probabilities. This measurement is seen to collapse the

coin state |q into one of its elementary states |H or



, which yields the observable

value referred to as heads or tails. The counterintuitive, or nonclassical, conclusion

is that as long as no measurement (or state collapse) is effected, the coin dwells in

the superposition of states deﬁned by Eq. (16.6). Note that this superposition is often

referred to as



, or “cat state,” as I shall explain.

It is possible to think of many other examples of superpositions of states. For instance,

consider a toddler in her room on an early Sunday morning. Is she still sleeping (state

|S) or is she awake and playing (state |A)? By 8 a.m. the parents know that there

is a fair chance that she must be asleep, say 90%. By 9 a.m., they know that the

odds are 50%. But if the parents don’t get up and check, the quantum view is that

by 8 a.m., the child must be in the state |S/

√

0.9 +|A/

√

0.1 and by 9 a.m. in the

state (|S+|A)/

√

2, which we have called the state |+. Only by opening the child’s

bedroom door can the actual measurement be made, which results in the state collapse

into |S or |A, giving the classical information 0 =sleeping or 1 = awake. As uncanny

as this example may sound, it illustrates the quantum concept of “superposition of

states,” now with the notion of a time evolution from the initial pure state |S to the

ﬁnal pure state |A. One may view our example as a gentler, yet conceptually equivalent,

version of the Schr

odinger’s cat thought experiment.

The stories of the tossed coin,

In a thought experiment, Schr

odinger imagines a cat that is placed inside a sealed box. The box contains a

can of poison gas, a radioactive substance, and a Geiger counter. The decay rate of the radioactive substance

is such that after one hour, there is a 50% chance that one atom decays, which is recorded by the Geiger

counter. In this event, the counter activates the opening of the poison-gas can, resulting in the cat’s instant

death. At any time, the (poor) cat’s state can be viewed as a superposition of the pure states |deador |alive,

308 Quantum bits and quantum gates

of the sleeping toddler, and of Schr

odinger’s cat illustrate the same paradox: does the

state of a macroscopic object or system require an outside observer to be deﬁned, or is

it self-deﬁned independent of outside observation? Our intuition tells us that such an

object or system cannot exist in two states at the same time, and, therefore, it must be its

own “observer.” The quantum-mechanics viewpoint breaks with intuition and afﬁrms

the contrary: that objects or systems can, indeed, exist in multiple states, and that only

the observer intervention deﬁnes what the actual state turns out to be. About elementary

information, our classical mind training requires that a bit is absolutely deﬁned as either

being 0 or 1 (regardless of possible measurement mistakes). With the qubit, we must

now retrain our mind to accept the fact that a quantum of information (the qubit) is in

a0/1 superposition state, whose outcome in observed reality remains undeﬁned until

some measurement is performed. The next two chapters will clarify and further develop

such a most intriguing notion!

To summarize the above description so far, a qubit must be conceived as a two-

dimensional bit, whose coordinates in that space represent probability amplitudes. Since

two coordinates deﬁne the qubit, it is possible to represent it as a unique point on the sur-

face of a sphere of unity radius, called a Bloch sphere, which is described in Appendix M.

In this appendix, it is shown that the most general deﬁnition of the qubit, within an unob-

servable phase factor, is

|q=cos

|0+sin

iϕ

|1. (16.7)

The two angles θ,ϕ, thus, uniquely deﬁne the position of a point on the surface of a

sphere, just like latitude and longitude on the Earth, and as illustrated in Fig. 16.1.It

is seen from the ﬁgure that the pure qubits |0 or |1 correspond to the cases θ = 0or

θ = π , respectively, which occupy the north and south poles of the Bloch sphere. The

key conclusion is that the qubit information corresponds to an inﬁnite number of states,

which are continuously distributed onto the surface of the Bloch sphere.

The above description concerned single qubits, corresponding to single classical bits.

It is possible to deﬁne higher-order qubits, which correspond to two classical bits or

to even longer binary codewords. Since there exist four possible pairs of classical bits,

which begins from a certain |alive and evolves over time towards a certain |dead. After the 1-hour delay,

the probabilities of the two states are equal, and the cat dwells in the state superposition

|+ =

|dead+|alive

√

hence, the name “cat state.” At any time, one cannot be sure if the cat is dead or alive, and this infor-

mation requires one to make a measurement by opening the box. Such a measurement results into the

collapse of the cat’s state into either of the pure states |dead or |alive. The initial purpose of Schr

odinger’s

though experiment was to illustrate that such a quantum view must be incomplete: the cat cannot be both

dead and alive at the same time! And there is no need for someone to open the box to deﬁne in which

state the cat actually exists. Yet such a view is consistent with the so-called “Copenhagen interpreta-

tion,” according to which systems can exist in such a superposition of states until reaching state collapse

through physical observation. A ﬁne argument, which reconciles this interpretation with Schr

odinger’s

cat paradox, is the fact that a cat is a macroscopic or classical system, and, therefore, the microscopic

quantum interpretation may not apply. See discussion, and more puzzling arguments in (for instance):

http://en.wikipedia.org/wiki/Schr%C3%B6dinger’s_cat.

16.1 Quantum bits 309

Figure 16.1 Representation of qubit |q by a point on the surface of the Bloch sphere, as deﬁned

by the “colatitude” angle θ and the “longitude” angle ϕ. The north and south poles correspond to

the pure qubit states |0 and |1, respectively.

namely 00, 01, 10, and 11, we can call the corresponding elementary two-qubit (or

2-qubit) states |00, |01, |10, and |11, and, similarly to Eq. (16.3), we obtain the most

general deﬁnition for any 2-qubit state:

|q=α

|00+α

|01+α

|10+α

|11. (16.8)

In this deﬁnition, the complex amplitudes α

must satisfy the property



= 1. (16.9)

From the previous description concerning 1-qubits, it is clear that each of the terms

|α

in the above summation represents the probability of ﬁnding the 2-qubit in the

state |ij, or, equivalently, of measuring the classical bit pair ij. We shall note here that

concept of tensor state, which is explained in the last section of this chapter.

We can even simplify the picture of a 2-qubit by looking at it as a “four-sided die,” such

as a tetrahedron, hidden in the box. Such a die has four classically measurable outcomes

(00, 01, 10, and 11), but in the quantum world there exist an inﬁnity of superpositions

of 2-qubit pairs, as I shall now establish.

Indeed, the 2-qubit state deﬁned in Eq. (16.8) can also be rewritten in the form

|q=



|α

+|α

|00+α

|01



|α

+|α



|α

+|α

|10+α

110

|11



|α

+|α

(16.10)

≡ β

+β

,

310 Quantum bits and quantum gates

with β



|α

+|α

and β



|α

+|α

, and











=



|α

+|α

(

|00+α

|01

)

≡ γ

|00+γ

|01

=



|α

+|α

(

|10+α

|11

)

≡ γ

|10+γ

|11.

(16.11)

The development in Eq. (16.11) illustrates that any 2-qubit state can be conceived as the

superposition of two 2-qubits, which we call here



(a 2-qubit with the ﬁrst bit 0),

and



(a 2-qubit with the ﬁrst bit being 1), respectively. According to all expectation,

should we have fully assimilated the earlier story of the 1-qubit measurement, if we

attempt to measure only the ﬁrst bit of any 2-qubit state, the latter must collapse into



, according to the outcome of the measurement being the 0 or 1 classical bits,

with associated probabilities

and

, respectively. The resulting states



, which represent superposition of 2-qubit states (with either 0 or 1 as the ﬁrst bit),

are referred to as post-measurement states.

The above has shown that any 2-qubit state can actually be decomposed into a variety

of possible superposition of 2-qubit pairs, as selected from the family {|00, |01, |10,

|11}. Of particular interest is the speciﬁc subgroup of 2-qubit pair superpositions

|ij±|kl, where i = k or j = l, conventionally deﬁned according to:











|β

≡

√

[

|00+|11

]

|β

≡

√

[

|01+|10

]

|β

≡

√

[

|00−|11

]

|β

≡

√

[

|01−|10

]

(16.12)

The family of 2-qubit superpositions deﬁned in the above inventory is referred to as Bell

states or EPR pairs, the EPR acronym being short for the names Einstein, Podolsky, and

Rosen. The Bell or EPR states exhibit quite intriguing and useful properties for quantum

computing, as will be described in Chapter 18.

The key lesson we have learnt so far is that, unlike classical bits, qubits are not

physically observable. But, as I shall describe next, qubits can be physically manipu-

lated! Such a manipulation, which transforms the qubit state, is of consequence in the

measurable or experimental domain. Hence, we may conceive of a quantum computer,

a machine that processes information not from bits but from qubits. The fact that qubits

are a probabilistic superposition of states introduces new dimensions and perspectives

in computing power, which represents a key justiﬁcation for QIT.

16.2 Basic computations with 1-qubit quantum gates

In Chapter 15, we have described the principles of reversible-logic gates, as based on

classical bit inputs and controls. Here, we shall explore how such gates can perform

16.2 Basic computations with 1-qubit quantum gates 311

elementary computations by exclusive use of qubits, instead of classical bits. As we

will discover, quantum computation based on these two principles is quite different in

nature and in power, when compared with classical computation obtained from mere

Boolean-logic gates. We shall ﬁrst consider operations with single qubit states, and then

move to more complex ones involving two and three qubit states.

As we have seen earlier in this chapter, a single qubit (or 1-qubit), |q, is deﬁned

through its complex amplitudes (α, β) with respect to a given orthonormal base or pure

states (|0, |1), also referred to as computational basis. A quantum gate, call it A, has

the effect of transforming an input qubit state |q into an output qubit state |q



,using

predeﬁned control qubits. Thus, the relation between the input and output states can be

expressed in the equivalent matrix-vector relation:



=A|q. (16.13)

In quantum vocabulary, the entity A that transforms |q into |q



 is referred to as an

operator. Since the vector |q



 must remain on the Bloch sphere surface (so that its

squared amplitudes correspond to actual probabilities), it must be a unitary vector. For

this reason, the transformation from |q to |q



is called unitary, and A must be a unitary

operator. We shall now further develop the notion of unitary transformation and the

relation between unitary operator and matrix.

For simplicity and to escape any further conceptual burden, so far we have assumed

that qubits are equivalent to vectors in a 2D space. This view is simplistic, but accurate.

Consistently, we may assume that the transformation operator A may be deﬁned through

a2× 2 matrix, whose coefﬁcients are deﬁned by four complex numbers, a

.Fromthe

deﬁnitions Eq. (16.3) and Eq. (16.13), we, thus, obtain the matrix-vector equation in the

|0, |1 base:



=A|q









α + a



≡

(

α + a

)

|0+

(

α + a

)

|1

≡ α



|0+β



|1.

(16.14)

Such a relation between the input (α, β) and output (α



,β



) amplitudes does not account

for the control qubits in the quantum gate, but for the time being this will sufﬁce for our

description.

The result in Eq. (16.14) shows that the action of the quantum gate, or that of

the quantum operator A, modiﬁes the state amplitudes of the initial superposition,

according to the transformations α → α



= a

α + α

β and β → α

α + α

β. Since

the output state amplitudes (α



,β



) must correspond to probabilities, it is required that

312 Quantum bits and quantum gates

|α



+|β



= 1. As I have mentioned earlier, such a transformation and the associated

operator/matrix, must be unitary.

In the following, we shall consider ﬁve examples of 2 ×2 unitary operators or matrices

and their effect on qubit transformation, namely: the Pauli matrices (called I, X, Y, and

Z-gates) and the Hadamard matrix (also called a H-gate).

Pauli matrices or I, X, Y, Z-gates

The Pauli matrices (named after the physicist W. Pauli) or I, X, Y, Z-gates are deﬁned

as:

I ≡ σ





X ≡ σ

= σ





Y ≡ σ

= σ



0 −i

i 0



Z ≡ σ

= σ



0 −1



(16.15)

The different notations I = σ

, X = σ

= σ

, Y = σ

= σ

and Z = σ

= σ

are usually

found in the related literature for historical reasons. It is easily established that the squares

of all the above matrices are equal to unity or X

= Y

= Z

= (σ

)

= I

= I .

The ﬁrst matrix I is the identity matrix, which corresponds to the classical REPEAT

gate and leaves the input qubit |q=α|0+β|1 invariant, according to



=I |q











≡ α|0+β|1≡|q.

(16.16)

The second matrix X (or X-Pauli) corresponds to the classical NOT gate. Indeed, we

obtain



=X |q







(16.17)





≡ β|0+α|1,

A transformation and associated matrix A is unitary if the following identity is satisﬁed A

−1

= ( A

)

∗

≡ A

In this deﬁnition, A

−1

is the inverse matrix of A (such that A

−1

A = AA

−1

= I ), A

is the transposed matrix

of A (with coefﬁcients a

→ a

), and

∗

denotes complex conjugation (a

→ a

∗

). The symbol

stands

for Hermitian conjugation, which combines both transposition and complex conjugation (a

→ a

∗

), i.e.,

is the Hermitian conjugate of the matrix A.

16.2 Basic computations with 1-qubit quantum gates 313

showing that the elementary qubits |0, |1 are switched into their counterparts |1, |0,

which for a state superposition |q=α|0+β|1 amounts to swapping the amplitude

probabilitie according to (α, β) → (β, α). Thus, if the input |q is in the pure state, for

instance |q=|0 (or α = 1,β = 0), the output state is |q



=|1, and the reverse with

|q=|1, which gives |q



=|0. In these two limiting cases, this operation, indeed,

corresponds to that of a classical NOT gate. But generally, it is also correct to call

X,σ

,σ

a quantum NOT gate.

The action of the Y-gate is both to swap the amplitudes and to introduce a π phase

shift between the two states of the initial superposition,

according to



=Y |q



0 −i

i 0







−i β

i α



=−i (β|0−α|1) ≡ e

iγ

(β|0+e

iπ

α|1),

(16.18)

where γ =−π/2 is an immeasurable, or “unobservable” phase constant.

Finally, the action of the Z -gate is only to introduce a π phase shift between the two

states of the initial superposition, according to



=Z|q



0 −1







−β



≡ α|0−β|1≡α|0+e

iπ

β|1.

(16.19)

As can also be easily checked, the three Pauli matrices X, Y, Z exhibit the following

properties:











= i σ

=−σ

(i = j).

(16.20)

One deﬁnes the commutator of two operators or matrices A, B as [A, B] = AB − BA.

Two operators or matrices are said to commute if [ A, B] = 0. Then we observe from

the last equation in Eq. (16.20) that for i = j the Pauli matrices do not commute, i.e.,

σ

,σ

=σ

− σ

= 2σ

, and, in the general case

σ

,σ

=2δ

, (16.21)

where δ

is the Kronecker symbol.

We,thus,have[σ

,σ

] = 2σ

= 2iσ

,[σ

,σ

] =

2σ

= 2iσ

and [σ

,σ

] = 2σ

= 2iσ

. The commutator between any two Pauli

With complex numbers, a change of sign corresponds to a phase shift of ±π , or a multiplying factor of

±iπ

=−1, since e

±iπ

= cos(±π ) + isin(±π ) =−1.

Namely: δ

= 1fori = j,andδ

= 0fori = j.

314 Quantum bits and quantum gates

matrices can be generalized in the formula

[σ

,σ

] = 2iε

ijk

, (16.22)

where ε

ijk

is the Levi–Civita symbol.

Likewise, using the property (σ

)

= I , we can

generalize Eq. (16.20) in the formula:

= iε

ijk

+ δ

I. (16.23)

These properties of the Pauli matrices or I, X, Y, Z-gates are used extensively in quantum

computing, as will be illustrated. In Appendix N, I show that the Pauli matrices constitute

a universal base, making it possible to generate any unitary 2 ×2 matrices or unitary

operators U , which represent the universal building blocks for 2-qubit quantum gates

and circuits.

Hadamard matrix gate or H-gate

The Hadamard matrix gate,orH-gate, is deﬁned as:

H =

√



1 −1



≡

√

(X + Z ). (16.24)

Using results in Eqs. (16.17) and (16.19), we can interpret the action of the Hadamard

gate as follows:



=H |q

√

(X + Z )|q

√

(X |q+Z |q)

√

[(β|0+α|1) +(α|0−β|1)]

= α

|0+|1

√

+ β

|0−|1

√

≡ α|+ + β|−.

(16.25)

It is seen from the above that the Hadamard gate transforms any input qubit |q=

α|0+β|1 into the superposition |q=α|+ + β|−, where |+, |− represent a new

pure states basis. As we shall see later, the two pure-state bases |0, |1 and |+, |−

play a fundamental role in quantum computing.

The action of the above 2 ×2 quantum gates on input qubits is summarized in

Table 16.1.

With the following deﬁnition (see http://en.wikipedia.org/wiki/Levi-Civita_symbol)

ijk







+1if(i, j, k)is(1, 2, 3), (2, 3, 1) or (3, 1, 2),

−1if(i, j, k)is(3, 2, 1), (1, 3, 2) or (2, 1, 3),

0 otherwise: i = j or j = k or k = i.

16.3 Quantum gates with multiple inputs and outputs 315

Table 16.1 Action of the elementary 2 × 2 quantum gates on input qubit |q=α|0+β|1.

Gate U Output |q



=U|q Action

Identity, I,σ

α|0+β|1 Invariant

X,σ

,σ

β|0+α|1 Swaps amplitudes

Y,σ

,σ

β|0+e

iπ

α|1 Swaps amplitudes and π shift between amplitudes

Z,σ

,σ

α|0+e

iπ

β|1 π shift between amplitudes

Hadamard, H α|+ + β|− Switches to |+, |− basis

For illustration purposes, consider two examples showing the action of cascades of

2 × 2 quantum gates:

U = XZX →

U |q=XZX(α|0+β|1)

= XZ(β|0+α|1)

= X (β|0+e

iπ

α|1)

= e

iπ

α|0+β|1

= e

iπ

(α|0+e

−iπ

β|1)

≡ α|0−β|1,

(16.26)

U = HX →

U |q=HX(α|0+β|1)

= H (β|0+α|1)

≡ β|+ + α|−.

(16.27)

Finally, we must note that the 2 ×2 Pauli and Hadamard matrix gates correspond

to reversible 1-qubit computations. Indeed, any input qubit can be retrieved through

the double operations X

= Y

= Z

= H

= I

= I . More generally, any gate cor-

responding to a unitary matrix or operator U is reversible by the application of the

Hermitian conjugate U

, since, by deﬁnition, U

U = I . This property also applies to

gate cascades UVW ...of unitary operators, which have for their Hermitian conjugate

(UVW ...)

=···W

, thus,

(UVW ...)

UVW =···W

VW =···W

W =···I.

16.3 Quantum gates with multiple qubit inputs and outputs

With the background from the previous section on 2 × 2 quantum gates and that

from reversible logic gates introduced in Chapter 15, we can now describe the matrix

representation and operation of various higher-order quantum gates, which have two

or more 1-qubit inputs and outputs. The elementary gates of this type are called

CNOT, CROSSOVER, controlled-U, controlled-SWAP, Toffoli, and CCNOT, which

I shall review in the following.

316 Quantum bits and quantum gates

CNOT

10´ +=

|a> |x> |a

>|x

0101

110

011

Figure 16.2 CNOT gate with control qubit



and target qubit |x, with truth table and gate

output |a, |x



 resulting from target qubit superposition |x=α|0+β|1.

CNOT gate

Consider ﬁrst the CNOT gate, whose diagram is shown in Fig. 16.2. The gate has a

control qubit |a=|0 or |a=|1, and a target qubit |x=α|0+β|1. Here, we

shall assume that the control qubits are in pure states, namely, |0, |1.Theﬁgure

shows the action of the CNOT gate with the corresponding truth table. It is seen

from the ﬁgure that the target qubit |x is left unchanged when the control qubit is

as we have seen in the previous section, represents the quantum NOT version of a

qubit.

But how can we deﬁne the CNOT gate matrix, since here we have a control qubit?

To answer this, recall that in the case of 1-qubit gates, the matrix is deﬁned in the

computational base |0, |1. In the case of the CNOT gate, the matrix must be deﬁned in

the extended computational base, noted {|a|x} = {|0|0, |0|1, |1|0, |1|1}, which

covers all possible gate inputs according to the truth table shown in Fig. 16.2, with |a=

|0 or |a=|1 and |x=|0 or |x=|1 (the matrix applying to any superposition

thereof). As will be described further on in this chapter, the state |a|x is referred to as

the tensor product of the kets |a and |x. In the computational base {|0|1}, the input

tensor state |a|x is represented by a four-dimensional column-vector with coordinates

, u



|x=













, (16.28)

which satisﬁes |u

+|u

= 1. The output state of the gate is then

given by the matrix-vector relation |a



|x



=A|a|x, where A is the gate’s 4 ×

4 matrix. In the case of the CNOT gate, and as expressed in the tensor base