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.2
Figure 1.2 NAND circuit diagram.
In contrast, quantum gates are reversible. As a result, even though the output overwrites the input, the input is not lost since the effect of a series of gate operations can be reversed by applying the appropriate inverse operations.
1.1.5 Entanglement
The fact that we can only calculate the probability of measurement results—not the precise results—on qubits in superposition states allows for a phenomenon that has no classical analog: entanglement. If two qubits are entangled, then the states are correlated even though the outcome of a measurement on either of the qubits can only be predicted by its probability. For example, if two qubits are entangled, then a measurement on one of the qubits will give a result with probability determined by its superposition state, just as would happen with an isolated qubit. However, once the state of one of the qubits has been collapsed by a measurement, the entanglement means that we know exactly what we will get if we measure the second qubit.
It is a bit like flipping two coins at the same time, and having them always come up the same, i.e., both heads or both tails. Or alternatively, having them always come up opposite—one heads and the other tails. Prior to making a measurement, the states of both of the qubits have not yet been determined. However, when the state of one is collapsed by a measurement, the second qubit somehow instantaneously “knows” the result. This is true regardless of how far apart the qubits are. For example, suppose we entangle two qubits, send one to New York and the other to Tokyo, then make prior arrangements to measure both at the same time. We will discover that the results of the measurements will be correlated even though there was not enough time for a signal traveling the speed of light to travel between the qubits. Einstein called this “spooky action at a distance.”
If it were possible to control the result of the first measurement, then it would appear that we could communicate faster than the speed of light—violating the principle of special relativity. However, the fact that we cannot control the result of the first measurement means that we cannot actually send any information using this mechanism.3 So we can rest comfortably knowing that relativity has not been violated.
We will see that the phenomena of superposition and entanglement give quantum computing its unusual and powerful capabilities.
1.2 Single-Qubit States
Since there are two components in a qubit’s state, we can represent the state as a two-dimensional vector, referred to as a state vector. The basis states can be written
It follows that we can express a general superposition state as a weighted sum of the basis states:
The notation |ψ⟩ is called a “ket.” The transpose complex conjugate4 of a ket is denoted ⟨ψ| and is called a “bra”:
where the † superscript indicates the transpose complex conjugate, also referred to as the Hermitian conjugate, or adjoint. The “bra” and “ket” terminology may seem strange until you multiply them together to form a “bra-ket.” For example,
(Note that when written as a bra-ket, only a single vertical bar is used in the center.) The bra-ket operation (i.e., multiplying a bra and ket) is also referred to as an “inner product.” Referring to (1.8), we see that the inner product of a state vector with itself gives the sum of the probabilities that each of the basis states will be obtained in a measurement. Since the sum of the probabilities of all possible outcomes must equal 1, we see that the state vectors must be properly normalized to a length of unity.
1.3 Measurement and the Born Rule
We have previously stated that the probability of measuring a given component of a superposition state is given by the magnitude squared of its coefficient. The act of measuring requires an apparatus that interacts with the qubit in order to extract information. The rules of quantum mechanics tell us that the apparatus can only give partial information, related to a set of basis states. For now, we will assume that measurement is always with respect to the standard basis states, |0⟩ and |1⟩, which is the case for most quantum computing systems. However, it is possible
