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.
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.
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 Section 1.3, we introduced the circuit model of (classical) computation. We restricted attention to reversible circuits since they can simulate any non-reversible circuit with modest overhead. This model can be generalized to a model of quantum circuits. In the quantum circuit model, we have logical qubits carried along ‘wires’, and quantum gates that act on the qubits. A quantum gate acting on n qubits has the input qubits carried to it by n wires, and n other wires carry the output qubits away from the gate. A quantum circuit is often illustrated schematically by a circuit diagram as shown in Figure 4.1. The wires are shown as horizontal lines, and we imagine the qubits propagating along the wires from left to right in time. The gates are shown as rectangular blocks. For convenience, we will restrict attention to unitary quantum gates (which are also reversible). Recall from Section 3.5.3 that non-unitary (non-reversible) quantum operations can be simulated by unitary (reversible) quantum gates if we allow the possibility of adding an ancilla and of discarding some output qubits. A circuit diagram describing a superoperator being implemented using a unitary operator is illustrated in Figure 4.2. In the example of Figure 4.1, the 4-qubit state |ψi⟩= |0⟩⊗ |0⟩⊗ |0⟩⊗ |0⟩ enters the circuit at the left (recall we often write this state as |ψi⟩ = |0⟩|0⟩|0⟩|0⟩ or |ψi⟩ = |0000⟩.) These qubits are processed by the gates U1, U2, U3, and U4. At the output of the circuit we have the collective (possibly entangled) 4-qubit state |ψf⟩. A measurement is then made of the resulting state. The measurement will often be a simple qubit-by-qubit measurement in the computational basis, but in some cases may be a more general measurement of the joint state. A measurement of a single qubit in the computational basis is denoted on a circuit diagram by a small triangle, as shown in Figure 4.1 (there are other symbols used in the literature, but we adopt this one). The triangle symbol will be modified for cases in which there is a need to indicate different types of measurements.R50
Classical information processing is performed using bits , which are just two-state systems, with the two states called 0 and 1. By grouping bits togetherwe can represent arbitrary pieces of information, and by manipulating these bits we can perform arbitrary computations. The corresponding basic element used in quantum information is the quantum bit, or qubit . This is simply a quantum system with two orthonormal basis states, which we shall call |0⧽ and |1⧽. There are many possible physical implementations of a qubit, such as spin states of electrons or atomic nuclei, charge states of quantum dots, atomic energy levels, vibrational states of groups of atoms, polarization states of photons, or paths in an interferometer. At this stage the physical implementation is not important: the idea of a qubit is to abstract the discussion away from physical details. Taking the standard approach of quantum information theory, we shall begin by not worrying too much about the properties of these states, or even what their energies are; we shall simply assume that they are eigenstates of the system's Hamiltonian with known eigenvalues (that is, known energies). This approach allows us to concentrate on the fundamental properties of the system, without considering all the tedious details. We can in principle perform classical information processing on our quantum system by using the two states |0⧽ and |1⧽ as our logical states 0 and 1 and proceeding in the usual fashion, giving rise to the field of reversible computing , which will be explored briefly in Part II. This, however, misses the point.
Reversible computing has been studied since Rolf Landauer advanced the argument that has come to be known as Landauer's principle. This principle states that there is no minimum energy dissipation for logic operations in reversible computing, because it is not accompanied by reductions in information entropy. However, until now, no practical reversible logic gates have been demonstrated. One of the problems is that reversible logic gates must be built by using extremely energy-efficient logic devices. Another difficulty is that reversible logic gates must be both logically and physically reversible. Here we propose the first practical reversible logic gate using adiabatic superconducting devices and experimentally demonstrate the logical and physical reversibility of the gate. Additionally, we estimate the energy dissipation of the gate, and discuss the minimum energy dissipation required for reversible logic operations. It is expected that the results of this study will enable reversible computing to move from the theoretical stage into practical usage.
With the anticipated end of Moore’s law for integrated circuits [3, 4] fast approaching and continued advances in low-power electronics, interest in quantum computing has increased. This shifts the focus from deterministic logical circuits to potentially more powerful circuits based on controllable quantum systems. In this column, we present a mathematical tour of the quantum circuit model, beginning with reversible logic circuits and expanding to quantum circuits, gates, and measurement. We highlight quantum mechanical phenomena such as superposition, entanglement, and measurement, review the Gottesman-Knill theorem, which states that some subclasses of quantum operations can be simulated eciently on a classical computer, and describe sets of quantum gates that are universal for quantum computation.