1 Qubits, Gates, and Circuits

      1.1 Bits and Qubits

      Digital systems that are most familiar are based on binary digits, or “bits.” Each bit can take on either the value “1” or “0,” and any arbitrary data can be represented by such a binary representation. In addition, any arbitrary logical operation can be implemented using bits. We will refer to these familiar systems as “classical” systems, since they are governed by the everyday laws of classical physics.

      Quantum computing is different from classical computing in a number of significant ways. The fundamental unit of information in quantum computing is the qubit (pronounced “KEW-bit”), short for quantum bit. The capabilities and behavior of qubits are quite different than bits, and we begin by pointing out and discussing the key differences as a launching point for our study of quantum computing.

      1.1.1 Circuits in Space vs. Circuits in Time

A simple classical logic circuit is represented by the NOT gate shown in Figure 1.1(a). The NOT gate turns a “0” into “1” and vice versa. In this circuit diagram the horizontal direction represents space, i.e., the input and output of the circuit are physically accessible from different points in the circuit, and they can be measured simultaneously.

      Figure 1.1 Interpretation of classical versus quantum NOT gates. (a) Classical NOT Circuit diagram. The horizontal direction represents space, i.e., the input and output of the circuit are physically accessible from different points in the circuit, and they can be measured simultaneously. (b) Quantum X gate circuit (quantum version of the NOT gate). The horizontal direction represents time, i.e., the input and output of the circuit represent the state of the same qubit after performing the X gate operation. The lower part of the Figure shows an alternate symbol for the quantum NOT gate.

      The quantum version of the NOT gate is the X gate shown in Figure 1.1(b). For qubits, the “0” and “1” states are normally written |0⟩, and |1⟩, respectively. We will discuss the meaning of this notation in more detail in a future section, but for now just consider them to be labels for the two states. In this case, the horizontal direction represents time, i.e., the input and output of the circuit represent the state of the same qubit after performing the X gate operation. In other words, unlike the usual structure of classical logic, a quantum gate represents an operation that you perform on a single qubit or set of qubits. The output effectively overwrites the input, and every time a gate is applied it changes the state of the qubit.

      1.1.2 Superposition

A classical bit must either be a “0” or a “1.” In contrast, a qubit can also be in a superposition state that is part “0” and part “1.” If the qubit is in a “1” or “0” state, we say the qubit is in a basis state.¹ For basis states, the state of the qubit can be measured any number of times without changing the state, much like measuring the state of a classical gate. A superposition state will also yield either a “0” or a “1” when measured, with a probability determined by the mixture. In this case the action of making the measurement will “collapse” the superposition state onto one of the constituent basis states, and the information stored in the superposition state will be lost. For example, if |ψ⟩ happens to represent a superposition state, then measuring the qubit at any time will collapse the state to either |0⟩ or |1⟩, destroying the information in the superposition state. From this point on, repeated measurement of the qubit will always yield the same result as the first measurement, just like a classical bit.

      Mathematically the superposition state can be written

      where α and β are complex constants.

      As mentioned, if such a superposition state is measured, it will always give either |0⟩ or |1⟩ but with probabilities of each determined by α and β. Specifically, the probabilities of measuring the two possible outcomes are given by

      If these are the only two possible outcomes of the measurement, then the probabilities must sum to 1, or

      This ability to represent superposition states is one of the secrets to the power of quantum computing: there is a sense in which the qubits are able to explore multiple possibilities in parallel.

      1.1.3 No Cloning

In a classical logic circuit we can measure the state of a bit at any time, and make as many copies of the state as we want. We can also do this for a qubit if it is known to be in one of the basis states; as described above, we can measure the |0⟩ or |1⟩ state without disturbing it, and we can make as many copies of |0⟩ or |1⟩ as needed.

      However, it turns out that it is not possible to create a precise, independent copy of an arbitrary quantum state. This is known as the no-cloning theorem. We’ll show a proof in Section 1.7, but for now let us consider the challenges this poses to the quantum programmer.

      For example, we can’t get estimates of α or β from running a circuit once. Cloning would allow me to run the circuit, make lots of copies of the result, and then measure each copy to estimate |α|² and |β|² by the probability of measuring |0⟩ or |1⟩. Without cloning, we can only measure the result once. To get many measurements, we must run the same computation many times to produce (hopefully!) the same result over and over.

      We cannot make copies of states for breakpoints, or to help with debugging or error recovery. It is also challenging to apply different operators to a single state during the course of a computation. Classical programmers take the ability to copy a state for granted, and this limitation requires some adjustment.

      It turns out that it is possible to copy a quantum state using entanglement (Section 1.1.5), but only by destroying the state being copied. This represents a transfer of state rather than a copy, and is referred to as teleportation.

      1.1.4 Reversibility

Classical NOT gates are reversible; i.e., two NOT gates in series returns the bit to its original state. However, the situation is different for classical logic gates with multiple inputs. As an example, consider the NAND Gate shown in Figure 1.2. It is not possible to uniquely determine the input bits from the output bit. Because of this, conventional multi-input logic is irreversible.²