and (A, B) -> (A, AB), respectively, can be performed using the properties A x B mod (A+A++A) mod m, (15.9) times AB mod =(AxAx... A) mod m, (15.10) B times which apply given any modulus m. Modular algebra is the key to solving quantum- computation problems, such as the factorization of integers into primes (see Chapter 20). In the forthcoming chapters, reversible-logic gates and their networks will not be used with "classical bits," but rather with "quantum bits," or qubits, which hold more interesting properties and surprises. Exercises 15.1 (B): Prove the following alternative definitions for XOR gates: =(ab) 15.2 (B): Prove De Morgan's law: (avb)=anb. 19 M.A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press, 2000); V. Vedral and M.B. Plenio, Basics of quantum computation. Prog. Quant. Electron., 22 (1998), 1-39. 15.4 Exercises 15.3 (T): Prove by Boolean algebra that the definition of XOR ab=(ab)(avb) is formally equivalent to any of the following three definitions: (Clue: use the distributive property according to which a 1(bvc)=(arb) (a \ c)). 15.4 (B): What is the Boolean function of the gate circuit? 15.5 (B): Through Boolean logic, show that the circuit arrangement of three successive CNOT gates, ACNOT BCNOT, ACNOT, ACNOT ACNOT is equivalent to a SWAP gate. Quantum bits and quantum gates This chapter represents our first step into quantum information theory (QIT). The key to operating such a transition is to become familiar with the concept of the quantum bit, or qubit, which is a probabilistic superposition of the classical 0 and 1 bits. In the quantum world, the classical 0 and 1 bits become the pure states |0) and |1), respec- tively. It is as if a coin can be classically in either heads or tails states, but is now allowed to exist in a superposition of both! Then I show that qubits can be physi- cally transformed by the action of unitary matrices, which are also called operators. I show that such qubit transformations, resulting from any qubi