Note: The Y gate is often represented in the alternate form where it maps |0〉 to i|1〉 and |1〉 to i|0〉, which in matrix form appears as
Some frequently used gates 1-qubit gates
The Hadamard gate, the phase gate, and the π/8 gate are frequently used gates. They are shown in Table 7.2. The Hadamard gate is frequently used in quantum computations as the first step in creating input data at the start of computations. It is a special case of the more general Fourier transform. It transforms a qubit in state |0〉 into the superposed state H|0〉 = (|0〉 + |1〉)/√2≡ |+〉 and likewise state |1〉 into H|1〉 = (|0〉 |1〉)/√2≡|-|〉.91 That is, H rotates the state of a qubit (remember unitary operators only rotate a state vector) such that the result may also be viewed as just a change in basis:
(|0〉, |1〉) → (|+〉, |-〉).91
The result is that if the qubit is measured in the basis, after being operated by the Hadamard gate, we will get |0〉 or |1〉 with equal probability, but if it is measured using the (|+〉, |-〉) basis, we will measure |+〉 if the qubit’s earlier state was |0〉 and |-〉 if the qubit’s earlier state was |1〉 . Note that H is its own inverse, or H<sup>2</sup> = I, that is, applying H twice to a state does nothing to it, and this is amazing; by applying a randomizing operation to a random state produces a deterministic outcome! Of course, only under the laws of quantum mechanics and not of classical mechanics. The (|0〉, |1〉) and (|+〉, |-〉) the bases are among the most frequently used bases in quantum computing, hence the reader should instinctively think about them when designing a new algorithm, especially as the first step in the algorithm for inputting all possible input data.
2-qubit controlled-not gate
The 2-qubit controlled-not gate, Cnot, is a generalization of the irreversible classical XOR gate. Here the state of the bit chosen as the control bit decides what happens to the other called the target bit as described below. Let |a〉⊕|b〉≡|a,b〉 represent a 2-qubit system on which it acts. Then, if the first bit is the control bit,
Cnot |a,b〉 = |a, a ⊗b〉
where ⊕ signifies the exclusive-or (XOR) operation (i.e., modulo 2 addition)93. It means that the output is “true” if and only if exactly one of the operands has a value “true”. This gate cannot be decomposed into a tensor product of two 1-qubit transformations, that is, one cannot find two unitary operators O1 and O2 such that Cnot = O1 ⊗ O2. The list of state changes shown in Table 7.3 is the analog of the truth table for a classical binary logic gate. Note that |00〉, |01〉, |10〉, |11〉 form an orthonormal basis for the state space of a 2-qubit system. By convention they are associated to the standard 4-tuple basis as shown in Table 7.3.
The resulting states are known as the Bell states (after John Bell) or sometimes as the EPR states or EPR pairs (after Einstein, Podolsky, and Rosen of the EPR-paradox fame; see Section 4.2). They are unique because they are all entangled states, i.e., in an unfactorizable state. When entangled particles are used to encode bits, their joint state represents an ebit.
Unlike a classical bit or a qubit, an ebit is, intrinsically, a shared resource. The information an ebit carries is always distributed between two particles. Hence the states of these particles are correlated, but undetermined until measured. An ebit therefore provides the basis for a restricted kind of quantum communication channel in the sense that once either particle comprising the ebit is measured, the state of both particles becomes definite. However, the channel is restricted in the sense that you cannot send an intentional message between two parties simply by having each party measure his or her members of a set of shared ebits, because, individually, the sequence of results (the decoded bits) would appear random.
The quantum Toffoli gate95 is a 3-qubit gate with three bits in and three bits out. A combination of 1-qubit unitary operations and a single 2-qubit operation (Cnot) is sufficient to build this gate. It can be viewed as a controlled-controlled-NOT gate, which negates the last of three bits if and only if the first two are 1, i.e., T |a, b, c〉 = | a, b, c⊕ ab〉. The Toffoli gate, applied twice to a set of bits has the effect (a, b, c) → (a, b, c⊕ ab) → (a, b, c). Thus, the Toffoli gate is reversible, since it is its own inverse. The use of three qubits is necessary to permit the whole operation to be unitary.
The 3-qubit Toffoli gate can be used to construct a complete set of Boolean connectives. In support of this statement, the AND and NOT operators are shown below:
T |x, y, 0〉 = |x, y, x ∧ y〉.
T |1, 1, x〉 = |1, 1,¬x〉.
The classical Toffoli gate is, therefore, a classical universal gate. The quantum version, which simply permutes computational basis states in the same way as the classical Toffoli gate, nevertheless cannot carry out the FANOUT operation because of the no-cloning theorem. The quantum Toffoli gate is not a universal gate in quantum computing, but it can implement all possible classical computations on a quantum computer. The Toffoli gate allows the irreversible classical gates to become reversible. This means that quantum computers can mimic the Universal Turing Machine despite being restricted to reversible, unitary gates.
7.6 Universal quantum gates
Classical computers compute using Boolean expressions. Any Boolean expression may be constructed from a non-unique set of universal logic gates. For example, the AND, OR, and NOT gates form a universal set. Alternatively, AND and NOT (also known as NAND), or OR and NOT or AND and XOR form three other possible universal sets. In addition to gates, one needs extra ancilla or working bits, to allow extra working space during computations. Muller’s theorem96 tells us that the choice of a universal set has little effect on the complexity of computing. Note that the operations of AND, OR, and XOR gates are many-to-one. Therefore, they are logically irreversible. Only the NOT gate is reversible since it is a one-to-one operation. Clearly then, the information content on the right-hand side of
(a, b) → NOT (a AND b)
is less than on the left-hand side.
Any unitary operation on n qubits can be implemented exactly by stringing together operations composed of single qubit and controlled-NOT gates97. For example, the Hadamard, phase98, controlled-NOT, and /8 gates provide a set of universal gates for which fault-tolerant constructions are known. This set is the standard set of universal gates. There is a second set of universal gates comprising the Hadamard, phase, controlled-NOT, and Toffoli gates, which may also be constructed in a fault-tolerant manner. We omit the proofs. In fact, there are many more choices for the universal quantum gate than in classical reversible computing due to the greater power of quantum computing. For example, DiVincenzo99 showed that two-qubit universal quantum gates are indeed possible and Barenco100 extended this knowledge to show that almost any two-qubit (within a certain restricted class) is universal. Subsequently, Lloyd101 and Deutsch, et al102, have shown that almost any two-qubit or n-qubit (n≥2) quantum gate is also universal.
Once Rolf Landauer,103 Charles Bennett104, Tommaso Toffoli,105 Edward Fredkin106 and others showed that reversible computing on a Turing machine was indeed possible and computationally economical, it was clear that quantum computers can simulate Turing machines by ensuring that they remain in a computational basis state at the end of each step, given that they start in one. To ensure unitarity, it is necessary and sufficient that the mapping from one state to another be bijective. In fact, the universal quantum computer can perfectly simulate107 any Turing machine and can simulate with arbitrary precision any quantum computer or simulator. In principle, any quantum particle, e.g., a photon or an electron, can function as a gate. The idea that quantum computers can be built to perform any computation reversibly both logically and thermodynamically by a physical apparatus dissipating arbitrarily little energy108 is no longer a fantasy.
8. Conclusion of Part I
Thus far we have explained certain fundamental differences between classical and quantum physics. We have emphasized that these differences require unusual approaches to algorithmic problem solving when using quantum computers. In Section 7 we concluded Part I by describing a set of core unitary quantum operators required to manipulate the state vector of a quantum computer. We will use these operators extensively in Part II to develop an array of quantum algorithms for general problem solving.
 A half-silvered mirror effects this transformation on a photon when it encounters the mirror.
 Braunstein (1995).
 In modulo 2 arithmetic, the following addition rules for adding two binary numbers are quite obvious:
0 + 0 ≡ 0 (mod 2), 0 + 1 ≡ 1 (mod 2), 1 + 0 ≡ 1 (mod 2), 1 + 1 ≡ 0 (mod 2).
Analogously, the XOR (or Cnot) operation is: 0 ⊗ 0 = 0, 0 ⊗ 1 = 1, 1 ⊗ 0 = 1, 1 ⊗ 1 = 0.
 See Barenco, et al (1995).
 Toffoli (1980). It is named after Tommaso Toffoli, who in 1980 showed that the classical version is universal for classical reversible computation.
 Muller (1956).
 See, e.g., Nielsen and Chuang (2000), pp. 189 and 191.
 Though the phase gate, S = T2, it is included because of its natural role in the fault-tolerant constructions.
 DiVincenzo (1995).
 Barenco (1995).
 Lloyd (1995).
 Deutsch, Barenco & Ekert (1995), pp. 669-677.
 Landauer (1961).
 Bennett (1982).
 Toffoli (1980).
 Fredkin & Toffoli (1982).
Deutsch, D. (1985), p. 107.
 See, e.g., Landauer (1961), and Bennett (1973). Bennett, in particular, showed that a Turing machine “may be made logically reversible at every step, while retaining their simplicity and their ability to do general computations.” He also discussed the biosynthesis of messenger RNA as a physical example of reversible computation.