14

Problems

Prove the pulse area theorem of (6.43). (Hint: See S. McCall and E. Hahn, Phys. Rev. Lett. 18, 908 (1967); Phys. Rev. 183, 457 (1969).)

Verify that for ?R = 0 the dark state |D(z, t)) of (6.54) is indeed the eigenstate of Hamiltonian (6.45) with the eigenvalue 0.

From (6.60), using the relations (6.62) and keeping in mind that the collective mixing angle ?¯(t) is a function of time, derive the dark ?eld prop- agation equation (6.63).


Part II













Quantum Information





Preamble











Information is represented, stored, processed, transmitted and readout by physical systems: “Information is physical,” as Rolf Landauer has summarized. Until recently, information has largely been thought of in classical terms, quan- tum mechanics having played a supportive role in designing the equipment to store and process it. With the tremendous progress in semiconductor technol- ogy and ever shrinking size of microelectronics, presently a single transistor in a PC processor is as small as ? 60 nm. According to Moore’s low, every 18 months computer chips double in density and power. If this trend continues during the next 15–20 years, we’ll have a single transistor represented by a sin- gle atom or molecule. Then quantum mechanical e?ects will begin playing an important role. This has in part motivated the birth of a new ?eld—Quantum Information Theory—based on quantum principles, which extends and gener- alizes classical information theory. Quantum information theory is currently attracting enormous interest in view of its fundamental nature and its poten- tially revolutionary applications to computation and secure communication.
This Part of the book is devoted to quantum information and computation. In Chap. 7 we brie?y outline the basic concepts of classical computation. This will prove useful in the description of the fundamental building blocks of quantum information in Chap. 8 and the principles of quantum computation in Chap. 9. We then conclude this Part and the whole book by Chap. 10, where we outline several representative quantum optical systems for quantum information processing.


7

Elements of Classical Computation











Computation is data processing. Computers process the input data, following a certain set of instructions called program, to proceed toward the result of computation contained in the output data. One distinguishes analog and digital computation. In analog computation, the computer basically imitates the physical process being simulated. In digital computation that most of us use on a daily basis, one “digitalizes” the parameters of the system to be modeled or analyzed and feeds this digital data into the computer input. The computation is then digital data processing.
In this chapter we review the basic concepts of classical computation. This is necessary in order to make the discussion on the theory of quantum informa- tion and computation more transparent. As will be seen in the chapters that follow, there are many parallels and analogies one can draw between classi- cal and quantum computers, but there are also striking di?erences associated with the superposition principle that results in quantum parallelism.


Bits and Memory

In a classical digital computer, the elementary unit of information—bit a—is represented by a classical two-state system a ? {0, 1}, e.g., charge state of a capacitance, magnetization of a ferromagnetic material, or current direction of a transistor circuit. A bit thus stores 0 or 1. An n-bit memory (register) of the computer can exist in 2n logical states
000 ... 0, 000 ... 1,..., 111 ... 1 .

Any integer number x, or a symbol associated with it, can be represented in binary units x ? x1x2 ... xn (xi ? {0, 1}) through
x = x12n?1 + x22n?2 + ... + xn20 . (7.1)


Thus, an 8-bit section of the memory, called byte, can store non-negative integer numbers in the range [0, 255], or if the ?rst bit is used to indicate sign, then the byte can store integer numbers in the range [?127, 127].
Fractions 0.y are represented by binary fractions 0.y ? 0.y1y2 ... yn (yi ?
{0, 1}) through
0.y = y12?1 + y22?2 + ... + yn2?n . (7.2)
A byte can then store fractional numbers in the range [0.1) with the precision of 2?8 = 1/256.


Circuits

Computation is a manipulation of the digital data according to a program which in turn reduces to a sequence of elementary arithmetic operations, ex- amples of which are be given below.


Wires and Gates

Operation of a digital computer can schematically be represented by circuits. Circuits consist of wires that carry bits in space or in time (or both), and logic gates. Logic gate is a function f : {0, 1}k ? {0, 1}l taking k input bits and returning l output bits. One usually distinguishes one-bit, two-bit or more-bit logic gates.


Unity a

a f(a)=a


NOT a a


f(a)=1 a


Fig. 7.1. Unity and not one-bit logic gates.


One-bit logic gates are shown in Fig. 7.1. These are the Unity operation that does not change the bit and therefore coincides with the wire, and the not gate that ?ips the bit a ? a¯ changing 1 to 0, and 0 to 1.
Several two-bit logic gates are shown in Fig. 7.2. They take two input bits and return one output bit. The and gate returns 1 if both input bits are in state 1, otherwise it returns 0. The or gate returns 0 if both input bits are in state 0, otherwise it returns 1. The xor gate output is conveniently repre- sented by a ? b, where ? is addition modulo 2 operation that returns 0 if a = b and 1 if a ƒ= b. The action of the last two gates, nand and nor corresponds to applying the not gate to the output from the and and or gates, respectively. One can construct three- and more-bit gates as well. Examples of three-bit gates will be given in Sect. 7.4. As discussed at the end of this section, how- ever, just a few ?xed gates, supplemented by two additional operations, can


a
AND b

a
OR
b


a
XOR b

NAND a
(NOT AND) b

NOR a
(NOT OR) b


a AND b



a OR b



a XOR b


=


=


1 if a=b=1
f(a,b)= 0 otherwise

1 if a or b=1
f(a,b)= 0 if a=b=0



f(a,b)=a b


0 if a=b=1
f(a,b)=
1 otherwise

f(a,b)= 0 if a or b=1
1 if a=b=0

Fig. 7.2. and, or, xor, nand and nor two-bit logic gates.


compute any function, and therefore are said to implement the Universal cir- cuit construction. The two additional operations shown in Fig. 7.3 are the copying operation fanout and swapping operation crossover.

a

FANOUT a
a

a b

CROSSOVER
b a
Fig. 7.3. fanout bit-copying and crossover bit-swapping operations.




Circuit Examples

Programming is translating an algorithm for performing certain task into a sequence of instructions for a computer. Hence algorithms de?ne circuits to perform desired computations.
Let us consider now an example of circuit that can perform a useful oper- ation, add two single-digit binary numbers x and y. The circuit for doing this is called half–adder circuit shown in Fig. 7.4. The output of this circuit is a two-digit number representing the sum of x and y. This sum can take values


x z
H A =
y x y

Fig. 7.4. Half–Adder circuit and the corresponding truth-table.


from 00 = 0 to 10 = 2, while the largest value that a two-digit binary number can hold is 11 = 3. It is therefore capable of holding the result of addition of three binary numbers x, y and z, which is realized by the full–adder cir- cuit shown in Fig. 7.5. The circuit uses two half–adders and one or gate, all together ?ve two-bit gates.



x
H A
F A = y
H A
z


z’


x y z






Fig. 7.5. Full–Adder circuit and the corresponding truth-table.


It is not di?cult now to construct a circuit adding two binary n-digit numbers x = x1x2 ... xn and y = y1y2 ... yn, as shown in Fig. 7.6 for three- digit numbers. The generalization to arbitrary n is straightforward.


x1 z1

y1 F A

x2 z2

y2 F A

x3 z3
H A
y3 z4
Fig. 7.6. Circuit adding two three-digit numbers x = x1x2x3 and y = y1y2y3.


Elements of Universal Circuit Construction

One of the main tenets of classical computation theory is that just a few ?xed gates can be used to compute any function f : {0, 1}n ? {0, 1}m. It is easy to prove it for a Boolean function f : {0, 1}? {0, 1} taking one input bit and returning single output bit. There are four possible functions of this kind: the identity corresponding to a singe wire, the bit ?ip corresponding to a single not gate, the function returning 0 for any input, which can be implemented by applying the xor on two copies of the input bit, and the function returning 1 for any input, which can be implemented by applying the xor on two copies of the input bit followed by the not gate. The general proof for an arbitrary function f : {0, 1}n ? {0, 1}m relies on induction and can be found in many textbooks on the theory of computation.
There are ?ve basic elements in the Universal circuit construction:
1. Wires.
2. Ancilla (auxiliary) bits ak prepared in a standard state, e.g., ak = 0.
3. fanout copying operation.
4. crossover swapping operation.
5. Single bit not and two-bit and and xor gates.

In the last item, the required not, and and xor gates (as well as the or gate) can be implemented using just nand gate, as shown in Fig. 7.7. The nand gate is therefore said to be universal.


NOT =


AND =



OR =






XOR =


Fig. 7.7. Implementation of the not, and, or and xor gates using the nand gate.


Computational Resources

An important part of the analysis of computational problems is an estima- tion of the resources required to solve a given problem. The computational resources include the space, or memory (number of bits), required to hold and manipulate the data, and time, or complexity of the circuit (number of elementary steps) required to process the data. The vital question then is: What are the minimal resources needed to solve a given computational prob- lem? The answer to this question ranks the problem among one or another complexity class.
Consider a problem of size N , where N is the number of bits containing the input and, possibly, the associated data required to process it. If the problem can be solved using resources which are bounded by a polynomial in N , then the problem can be solved e?ciently. This means that if the problem is resized to N r > N , then the computational resources grow modestly (polynomially) with N , and the problem is said to be an easy or tractable problem. If, on the other hand, the problem requires resources which grow with N faster than any polynomial in N (e.g., exponentially), the problem cannot be solved e?ciently on a computer, and it is said to be a hard or intractable problem.
Ranking the computational problems as easy or hard is rather coarse. While there are hard problems for which it is rigorously proven that the best algorithm needs resources growing exponentially in the problem size, for other cases there may exist e?cient algorithms that are simply not known yet. Many algorithms are frequently used to solve moderate size problems that may be ranked as hard according the de?nition above. On the other hand, an easy problem of enormous size may be intractable and very costly for present-day computers. As expressed by Papadimitriou, however, “adopting polynomial worst-case performance as our criterion of e?ciency results in an elegant and useful theory that says something meaningful about practical computation, and would be impossible without this simpli?cation.” The detailed study of complexity classes of computational problems is an important part of com- puter science and applied mathematics, which is beyond the scope of the present text.


Reversible Computation

The model of computation discussed until now is intrinsically irreversible. This is because the two-bit gates used to construct circuits are irreversible as they involve two input bits and only one output bit. Thus one cannot deduce the input of the gate from its output. Consider, as an example, the and gate. The possible inputs are {00}, {01},{10} and {11}, and the outputs are 0 for the ?rst three inputs and 1 for the last input. Thus with a 0 at the output, one cannot determine which of the three possible inputs were fed into the gate; this information is lost. Another example is the xor gate, for which the

7.4 Reversible Computation 209

inputs {00} and {11} yield 0, and inputs {01} and {10} yield 1 at the output. Conversely, ?nding a 0 at the output can not disclose whether the input was
{00} or {11} and similarly, ?nding a 1 at the output can not disclose whether the input was {01} or {10}.
In these examples, the number of input bits to the circuit is less then the number of output bits. The information carried by the excess bits is dis- carded which inevitably leads to energy dissipation according to the Lan- dauer’s principle: Erasing a single bit of information leads to dissipation of at least kB T ln 2 Joule of energy into the environment with temperature T . Alternatively one may say that the entropy of the environment increases by at least kB ln 2, as required by thermodynamics. This determines the funda- mental lower limit of energy consumed and dissipated by the computer in the course of operation. Therefore if one realizes a reversible computation, which is not accompanied by bit erasure, one would reduce the energy dissipation. We should note, however, that present day computers consume more than 100kB T ln 2 Joule of energy per dissipated bit, which is quite far from the fundamental lower limit. Semiconductor nanotechnology is, however, evolving with enormous pace and perhaps in the not-very-distant future, the funda- mental lower limit may be approached, in which case the construction of a reversible computer will become an important technological objective.


Toffoli (CCNOT) gate

Fredkin (CSWAP) gate




a a


b b


c c ab

a a’


b b’


c c




Fig. 7.8. To?oli (Controlled-Controlled-not) gate and Fredkin (Controlled-swap) gate.


It turns out that employing the universal three-bit To?oli or Fredkin gates, shown in Fig. 7.8, one can realize reversible circuit construction capable of universal computation. The action of the To?oli gate is to ?ip the target bit c conditional upon the states of the two control bits a and b; the target bit is ?ipped c ? c¯ if a = b = 1, otherwise it is unchanged. The Fredkin gate interchanges the target bits a and b conditional upon the state of the control bit c; the target bits are swapped a ? b if c = 1, otherwise they are unchanged. It is easy to see that the output of either To?oli or Fredkin gate uniquely determines the corresponding input and therefore no information is lost.


a
NAND
a
b b

a FANOUT 1 1
a
b a = a a a

1 1 ab=ab 0 a

Fig. 7.9. Implementation of the nand and fanout operations using the To?oli gate.


Using a single ancilla bit, the To?oli gate can implement the universal nand and fanout operations, as shown in Fig. 7.9. Similarly, it is a simple exercise to show that the Fredkin gate can also be con?gured to simulate the not, and, crossover and fanout operations (see Prob. 7.5). Therefore either of the three-bit reversible gates can be cascaded to simulate any classical circuit. In general, with a small resource overhead due to the use of ancilla bits, any irreversible circuit computing a function f (x) can be e?ciently simulated by a reversible circuit with the action (x, y) ? (x, y ? f (x)). Then reversal of the computation can be achieved by repeated application of the circuit (x, y ? f (x)) ? (x, y ? f (x) ? f (x)) = (x, y).


Problems

What is the largest positive integer number that can be stored in a 8, 16 or 32 bit register?

What is the smallest positive real number that can be stored in a 8, 16 or 32 bit register?
Compose a circuit to add two 5 digit binary numbers.

Verify the implementations of the not, and, or and xor gates using the nand gates of Fig. 7.7. Compose a di?erent implementation of the xor gate using 6 nand gates. (Hint: Combine the nand gates with the or and and gates implemented by nand gates.)

Implement the not, and, fanout and crossover operations using the Fredkin gate.


8

Fundamentals of Quantum Information











We turn now to the description of the building blocks of quantum informa- tion theory. We introduce the quantum analog of the bit—qubit, single- and multiple-qubit logic gates and quantum circuits performing information pro- cessing. Any introduction to quantum information theory would be incomplete if it did not contain a discussion on the peculiar properties of the entangle- ment, which results, on the one hand, in the notorious non-locality of quantum mechanics, and on the other hand, in decoherence already studied in previous chapters in the general framework of a small quantum system coupled to a large reservoir. A signi?cant part of this chapter is therefore devoted to the analysis of the role of entanglement in the fundamental tests of quantum me- chanics, as well as its quantum information applications such as cryptography, teleportation and dense coding.


Quantum Bits and Memory

In quantum information theory, the elementary unit of information is a quan- tum bit—qubit. A qubit is represented by a quantum mechanical system with two orthogonal states conventionally denoted by |0) and |1). These states form the computational basis { |0), |1)}, whereas their orthogonality implies (0|1) = 0. A qubit can be not only in one of the basis states, but also in any superposition state of the form
|?1) = ? |0) + ? |1) , (8.1) where the coe?cients ? and ? are arbitrary complex numbers normalized to
unity according to |?|2 + |?|2 = 1. Hence, unlike the classical bit which can
only store a discrete variable taking two real values, the qubit can represent a continuum of states spanned by a unit vector in a two-dimensional complex vector space. Thus, when both coe?cients of superposition (8.1) are nonzero, the qubit, in a sense, simultaneously contains both possible values of classical


bit 0 and 1, each having the corresponding probability amplitude ? and ?. As discussed in detail in Chap. 9, this fact is at the heart of all quantum algorithms that explore the superposition principle, combined with quantum interference to achieve the massive parallelism in solving certain computa- tional problems that are otherwise intractable on classical computers.
A pair of qubits can exist is any state of the form
|?2) = c00 |00) + c01 |01) + c10 |10) + c11 |11) , (8.2)
where the complex coe?cients cx (x = 00,..., 11) are normalized as .x |cx|2 =
1. In general, the compound state |?2) is an entangled state of two qubits, meaning that it can not be factorized into a product state of the qubits (? |0) + ? |1)) ? (?r |0) + ?r |1)). Only when the coe?cients of (8.2) satisfy c00 = ??r, c01 = ??r, c10 = ??r and c11 = ??r, is the decomposition into the product state possible, in which case the state is factorisable. Important examples of two-qubit (bipartite) entangled states are the Bell states, also known as Einstein–Podolsky–Rosen (EPR) states
|B00) = 1 ( |00) + |11)) , |B01) = 1 ( |01) + |10)) , (8.3a)
?2 ?2
|B10) = 1 ( |00)? |11)) , |B11) = 1 ( |01)? |10)) . (8.3b)
?2 ?2

These are maximally entangled states in the sense that if we discard the information pertaining to one of the qubits, the measurement performed on the other qubit of the pair would yield completely random result, as discussed in more detail in Sect. 8.5. The Bell states are widely employed in quantum communication protocols such as teleportation and dense coding, as well as in fundamental tests of the locality of quantum mechanics, described later in this chapter.
In general, an n-qubit register has 2n mutually orthogonal states which, in the computational basis, are of the form |x1x2 ... xn), where xk ? {0, 1} for 1 ? k ? n. Any state of the register can therefore be speci?ed by 2n complex amplitudes cx, x ? x1x2 ... xn, via
|?n) = . cx |x) , . |cx|2 =1 . (8.4)
x x

Thus, even for a modest number of qubits n < 100, the number of ampli- tudes cx specifying the state of quantum system is very large. Storing and manipulating such an amount of complex numbers with classical computers is an enormously costly task. Hence the ine?ciency of classical computers in simulating quantum mechanics, as discussed in more detail in Sect. 9.3
Let us ?nally present the many qubit “analogs” of Bell states. One family of such fully-entangled multiqubit states is known as the Greenberger–Horne– Zeilinger states, or GHZ for short,
|GHZ) = 1 ( |000 ... 0)± |111 ... 1)) . (8.5)


As discussed in Sect. 8.8.3, such states are even more compelling than the Bell states in revealing the non-local nature of quantum mechanics. Another family of multiqubit entangled states is called the W states, having the form
1
|Wn) = ?N ( |00 ... 01) + |00 ... 10) + ... + |01 ... 00) + |10 ... 00)) . (8.6)

Thus a W state of n qubits consists of an equally weighted superposition of n states, each of which has exactly one qubit in state |1) and all the others in state |0).


Quantum Circuits

As in classical computers, the operation of quantum computers can be rep- resented by circuits consisting of quantum wires that carry qubits and quan- tum logic gates. One distinguishes one-qubit and multiple-qubit logic gates, acting, respectively on one and many qubits. Since quantum computation is reversible, in any quantum logic gate the number of input and output qubits must be the same. In addition, only the quantum logic gates that preserve the
norm .x |cx|2 = 1 of the register’s wavevector |?n) for all times are allowed
in quantum circuits. Therefore the logic gates can be represented by quantum mechanical unitary operators acting on the state of the register.


One Qubit Gates
Consider ?rst single-qubit logic gates. A general one-qubit logic gate is de-
. ? ? .

scribed by a 2 × 2 unitary matrix U =

? ? that transforms the qubit state

|0) to ? |0) + ? |1) and state |1) to ? |0) + ? |1). Examples of one-qubit logic gates are shown in Fig. 8.1. These are the Unity I, Hadamard H, Pauli X, Y and Z, and Phase S gates. The matrix representation of operators corre- sponding to these gates is shown on the right of each gate. The action of the gate is therefore equivalent to the action of the corresponding operator on the input state of the qubit. For the Unity gate we have I |?1) = |?1) which leaves the qubit state unchanged being thus equivalent to the wire. The Hadamard gate transforms the initial state of the qubit |0) or |1) to an evenly weighted superposition of its two basis states
1
H |0)? ?2 ( |0) + |1)) ? |+) ,
1
H |1)? ?2 ( |0)? |1)) ? |?) .
We can cast this in a compact form, obtaining a very useful expression



Unity I I = 0 1




Hadamard

H = 1 1 1

2 1 ?1


0 1
Pauli X X =
1 0


Pauli Y Y Y = i 0



Pauli Z Z

Z =
0 ?1



Phase S S = 0 i

Fig. 8.1. Unity I, Hadamard H, Pauli X, Y and Z, and Phase S one-qubit logic gates.


xz
. ? | )
?


, (8.7)

z 2

where x, z ? {0, 1}. Consequently, an arbitrary qubit state |?1) given by (8.1) is transformed according to
1 . 1 1
| 1) ?

. . ? .

1 . ? + ? .
? ?

1
= ? [(? + ?) |0) + (? ? ?) |1)] .

2 ? ? ? 2

2 1 ?1 ?

(8.8)

The X, Y and Z gates are equivalent to the Pauli spin- 1

operators ?x, ?y ,

?z , respectively. The X gate ?ips the qubit state according to
X |0)? |1) ,
X |1)? |0) ,

. 0 1 . . ? .

. ? .

X |?1) = 10

? ? ?

= (? |0) + ? |1)) , (8.9)


which is the quantum analog of the not gate. Similarly for the Y gate we have


Y |0)? i |1) , Y |1)? ?i |0) ,

. 0 ?i . . ? .

. ?i? .

Y |?1) = i 0

? ? i?

= ?i(? |0)? ? |1)) . (8.10)


The Z gate introduces the phase-shift ? to the qubit state |1) while leaving state |0) unchanged

Z |0)? |0) , Z |1)? ? |1) ,

Z |?1) =

. 1 0
0 ?1

. . ? .
?

. ? .
? ??

= (? |0)? ? |1)) . (8.11)


Note that if the qubit is prepared in either |+) or |?) states (using, e.g., the Hadamard gate), the action of the Z gate is to interchange these states, Z |±) ? |?). Finally, the Phase gate S introduces the phase-shift ?/2 to state
|1) and leaves state |0) unchanged,

S |0)? |0) , S |1)? i |1) ,

. 1 0 . . ? .

. ? .

S |?1) = 0 i

? ? i?

= (? |0) + i? |1)) . (8.12)


Its action can thus be thought of as “half-way” or square-root of the action of Z gate, as it is easy to check that SS = Z. Other useful relations between the single-qubit gates are HH = XX = YY = ZZ = I, H = 1 (X + Z),
2
XY = iZ, XZ = ?iY , YZ = iX, etc.
More generally, an arbitrary single qubit transformation U can be decom- posed into the product of the rotation operators Ry (?) and Rz (?r) and an overall phase factor given by ei?. The expressions for the rotation operators and their physical meaning are given in Sect. 8.4.


Two and More Qubit Gates

Consider now examples of two-qubit logic gates W shown in Fig. 8.2. These are the controlled-not (cnot), swap, controlled-Z (cz) and a general controlled- U gates, where U is any single-qubit unitary transformation. The cnot is a quantum analog of the classical reversible xor gate, |a) |b) ? |a) |a ? b) (a, b ? {0, 1}), whereby the target (lower) qubit b is ?ipped if the control (upper) qubit a is in state |1), and is left unchanged if the control qubit state is |0). The swap is analogous to the classical crossover transformation,
|a) |b)? |b) |a), it interchanges the states of the two qubits. The swap gate can be implemented by triple application of the cnot as shown on the second line of Fig. 8.2. Another example of a two-qubit gate is the controlled-Z gate,





CNOT (XOR)


WCNOT =








SWAP =

1 0 0 0










Controlled?Z WCZ =

1 0 0 0

Z 0 0


0 ?1



1 0 0 0

Controlled?U W =
U 0 0

Fig. 8.2. cnot (controlled-not), swap, controlled-Z and controlled-U two-qubit logic gates.


|a) |b) ? (?1)ab |a) |b), where the Z operator is applied to the target qubit conditional upon the state of the control qubit. More generally, any controlled- U transformation is realized by a circuit shown on the last line of Fig. 8.2, where the application of the U operator to the target qubit is triggered by the control qubit if its state is |1).
As in the case of one-qubit gates, the operators W corresponding to the two-qubit gates have convenient matrix representation shown on the right of each gate in Fig. 8.2. There we use the usual convention for numbering the rows and columns of the matrix, |00), |01), |10) and |11), where the ?rst symbol in the kets indicates the state of the control qubit and the second symbol indicates the state of the target. The result of application of, e.g., the cnot to the general two-qubit state (8.2) can be calculated via

? 100 0 ? ? c00 ?

? c00 ?

Wcnot |?2) = ? 010 0 ? ? c01 ? = ? c01 ? , (8.13)

? 000 1 ? ? c10 ?

? c11 ?

? ? ?
0010

?
c11

? ?
c10


which shows that the coe?cients of states |10) and |11) are interchanged. The same procedure is used to calculate the action of any two-qubit gate.




a H 2
Bab b



Fig. 8.3. Circuit generating the four Bell states |Bab) and the corresponding truth table.


As an example of a simple circuit, we show in Fig. 8.3 the generation of the four Bell states |Bab) from the the initially unentangled pair of qubits
|a)? |b) using the Hadamard and cnot gates (see Prob. 8.1).


CCNOT
(Toffoli)


UCCNOT =





Fig. 8.4. ccnot (controlled-controlled-not) or quantum To?oli logic gate.


Next, in Fig. 8.4 we depict the three-qubit ccnot (controlled-controlled- not) logic gate, which is the quantum analog of the classical universal To?oli gate, |a) |b) |c)? |a) |b) |ab ? c), whereby the target (lower) qubit c is ?ipped if both control (upper) qubits a and b are in state |1), and is left unchanged otherwise. As discussed in Sect. 9.1.1, any multiqubit unitary transforma- tion, including the quantum To?oli gate, can be e?ciently simulated by an appropriate circuit that involves only single- and two-qubit operations. In par-