This chapter makes us walk a few preliminary, but decisive, steps towards quantum information theory (QIT), which will be the focus of the rest of this book. Here, we shall remain in the classical world, yet getting a hint that it is possible to think of a different world where computations may be reversible, namely, without any loss of information. One key realization through this paradigm shift is that “information is physical.” As we shall see, such a nonintuitive and striking conclusion actually results from the age-long paradox of Maxwell's demon in thermodynamics, which eventually found an elegant conclusion in Landauer's principle. This principle states that the erasure of a single bit of information requires one to provide an energy that is proportional to log 2, which, as we know from Shannon's theory, is the measure of information and also the entropy of a two-level system with a uniformly distributed source. This consideration brings up the issue of irreversible computation. Logic gates, used at the heart of the CPU in modern computers, are based on such computation irreversibility. I shall then describe the computers' von Newman's architecture, the intimate workings of the ALU processing network, and the elementary logic gates on which the ALU is based. This will also provide some basics of Boolean logic, expanding on Chapter 1, which is the key to the following logic-gate concepts.
This chapter makes us walk a few preliminary, but decisive, steps towards quantum information theory (QIT), which will be the focus of the rest of this book. Here, we shall remain in the classical world, yet getting a hint that it is possible to think of a different world where computations may be reversible, namely, without any loss of information. One key realization through this paradigm shift is that “information is physical.” As we shall see, such a nonintuitive and striking conclusion actually results from the age-long paradox of Maxwell's demon in thermodynamics, which eventually found an elegant conclusion in Landauer's principle. This principle states that the erasure of a single bit of information requires one to provide an energy that is proportional to log 2, which, as we know from Shannon's theory, is the measure of information and also the entropy of a two-level system with a uniformly distributed source. This consideration brings up the issue of irreversible computation. Logic gates, used at the heart of the CPU in modern computers, are based on such computation irreversibility. I shall then describe the computers' von Newman's architecture, the intimate workings of the ALU processing network, and the elementary logic gates on which the ALU is based. This will also provide some basics of Boolean logic, expanding on Chapter 1, which is the key to the following logic-gate concepts.
In the last chapter, we saw that it is theoretically possible to switch a logically reversible gate without dissipating any energy at all (recall the proof of the Landauer-Shannon result). If there is no dissipation, then no information is ever being discarded; therefore, if we know the state of the system completely at any instant of time, we should be able to infer its state at any previous instant. This is consistent with the equations of quantum mechanics (e.g., the Schro¨dinger equation, or the Pauli Equation) which are reversible in time. This property of quantum mechanical systems, known as ‘time reversal symmetry’, guarantees that if we know the state of a system at a time t0, we can tell what the state was at any time t < t0. Because of this fundamental connection between physical reversibility, logical reversibility, and the equations of quantum mechanics, we would expect logically reversible gates to behave as non-classical (quantum mechanical) computing machinery∗. This will bring us to the topic of quantum computing and quantum logic gates, but before we get there, let us explore reversible logic in a little more detail.
In the last chapter, we saw that it is theoretically possible to switch a logically reversible gate without dissipating any energy at all (recall the proof of the Landauer-Shannon result). If there is no dissipation, then no information is ever being discarded; therefore, if we know the state of the system completely at any instant of time, we should be able to infer its state at any previous instant. This is consistent with the equations of quantum mechanics (e.g., the Schro¨dinger equation, or the Pauli equation) which are reversible in time. This property of quantum mechanical systems, known as “time reversal symmetry”, guarantees that if we know the state of a system at a time t0, we can tell what the state was at any time t < t0. Because of this fundamental connection between physical reversibility, logical reversibility, and the equations of quantum mechanics, we would expect logically reversible gates to behave as non-classical (quantum mechanical) computing machinery.∗ This will bring us to the topic of quantum computing and quantum logic gates, but before we get there, let us explore reversible logic in a little more detail.
From the intrinsic evidence of his creation, the Great Architect of the Universe now begins to appear as a pure mathematician. Sir James Jeans, Mysterious Universe Now that we have the mathematical and physical preliminaries under our belt, we can move on to the nuts and bolts of quantum computing. At the heart of a classical computer is the notion of a bit and at the heart of quantum computer is a generalization of the concept of a bit called a qubit, which shall be discussed in Section 5.1. In Section 5.2, classical (logical) gates, which manipulate bits, are presented from a new and different perspective. From this angle, it is easy to formulate the notion of quantum gates, which manipulate qubits. As mentioned in Chapters 3 and 4, the evolution of a quantum system is reversible, i.e., manipulations that can be done must also be able to be undone. This “undoing” translates into reversible gates, which are discussed in Section 5.3. We move on to quantum gates in Section 5.4. Reader Tip . Discussion of the actual physical implementation of qubits and quantum gates is dealt with in Chapter 11. BITS AND QUBITS What is a bit ? Definition 5.1.1 A bit is a unit of information describing a two-dimensional classical system . There are many examples of bits: ▪ A bit is electricity traveling through a circuit or not (or high and low). ▪ A bit is a way of denoting “true” or “false.” […]
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〉, respectively. 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 physically transformed by the action of unitary matrices , which are also called operators . I show that such qubit transformations, resulting from any qubit manipulation, can be described by rotations on a 2D surface, which is referred to as the Bloch sphere . The Pauli matrices are shown to generate all such unitary transformations. These transformations are reversible , because they are characterized by unitary matrices ; this property always makes it possible to trace the input information carried by qubits. I will then describe different types of elementary quantum computations performed by elementary quantum gates, forming a veritable “zoo” of unitary operators, called I , X , Y , Z , H , CNOT, CCNOT, CROSSOVER or SWAP, controlled- U , and controlled-controlled- U . These gates can be used to form quantum circuits , involving any number of qubits, and of which several examples and tools for analysis are provided. Finally, the concept of tensor product , as progressively introduced through the above description, is eventually formalized.
The relation between entropy and information has great significance for computation. Based on the strict reversibility of the laws of microphysics, Landauer (1961), Bennett (1973), Priese (1976), Fredkin and Toffoli (1982), Feynman (1985) and others envisioned a reversible computer that cannot allow any ambiguity in backward steps of a calculation. It is this backward capacity that makes reversible computing radically different from ordinary, irreversible computing. The proposal aims at a higher kind of computer that would give the actual output of a computation together with the original input, with the absence of a minimum energy requirement. Hence, information retrievability and energy efficiency due to diminished heat dissipation are the exquisite tasks of quantum computer technology.
Except for the NOT gate, all the other familiar classical gates are irreversible in the sense that we cannot uniquely reconstruct the input states from the output states. For example, OR, AND, NAND, NOR, etc. are irreversible. They all map a two-bit input state into a single bit output state. Thus one bit is erased during operation of each of these gates, and according to Landauer’s principle that requires dissipation of a minimum amount of energy. Now a simple question arises in our curious mind: Is it possible to avoid this loss of energy? The answer is yes. If we don’t erase any bit then we can circumvent this energy loss. Thus we need to map n bit input states to n bit output states. In addition, if a one-toone correspondence exists between the input states and the output states then only we will be able to uniquely reconstruct the input states from the output states. In such a case the gate is called reversible. For example, if we have f(00) = 00, f(01) = 10, f(10) = 01, f(11) = 11 then f represents a reversible gate. Quantum evolution operators are unitary so for every operator U we have an inverse operator U−1 = U†. Therefore, quantum evolution operators are the natural choice for the construction of energy efficient reversible gates. However, it is not the only choice. We can have classical reversible gates, too. Usually by reversible gates we refer to classical reversible gates, and quantum gates are specifically referred to as quantum gates. Reversible gates and quantum gates are similar but there exists a fundamental difference that reversible gates cannot accept superposition states (e.g. α|0〉 + β|1〉) as input states, whereas quantum gates can. Thus all quantum gates are essentially reversible but the converse is not true.