Gates
Contents
Gates¶
Quantum Gates¶
A classical computer uses wires and logic gates. A Quantum Gate is an n by n unitary matrix. The Quantum Equivalent of a NOT gate is shown below.
\( \begin{align} X =& \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \end{align} \)
We can see how \(X\) works by applying it to a vector representing a quantum state. We apply of \(X\) to \(\qzero\). It acts like the NOT gate on \(\qzero\) and \(\qone\). More generally, it swaps the values of \(\alpha\) and \(\beta\).
\( \begin{align} \qzero =& 1 \qzero + 0 \qone \\ X =& \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \\ X \qzero =& \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} =\begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ \qone =& X \qzero = 0 \qzero + 1 \qone \end{align} \)
Properties of Single Qubit Gates¶
A gate must be a n by n unitary matrix. A Unitary Matrix means that \(U^{\dagger} U = \ident\). When we multiply the matrix by its Hermitian Conjugate we get the indentity. This means that any gate can be reversed to undo it’s calculation. This feature will be important to many algorithms.
There are infinitely many two by two unitary matrices, therefore infinitely many single qubit gates!
\( \begin{align} X^{\dagger} X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \end{align} \)
The \(X\) gate is it’s own Hermitian Conjugate. If we apply it twice, we get our original answer. Just like a double negative!
One Qubit Gates¶
The identity gate \(I\) makes no changes. It is unlikely you would ever explicity put this gate in a program, but it is used in the mathematics. If we want to use \(X\) on the second qubit and make no changes to the first, we are technically putting an \(I\) on the first qubit.
\( \begin{align} I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \end{align} \)
We have already seen the \(X\) gate. This is more formally called the Pauli-X Gate.
\( \begin{align} X =& \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \end{align} \)
The Pauli-\(Z\) gate flips the sign of \(\qone\).
\( \begin{align} Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \end{align} \)
The Pauli-\(Y\) gates applies a flip like the X gate, but also introduces an imaginary component.
\( \begin{align} Y=&\begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \end{align} \)
The Hadamard Gate puts the qubit into a halfway superposition.
\( \begin{align} H= \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \end{align} \)
The \(S\) or Phase gate multiplies the \(\qone\) position by \(i\).
\( \begin{align} S=&\begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix} \end{align} \)
The \(T\) or \(\frac{\pi}{8}\)-Gate turns the qubit at an angle. Yes this is called the \(\frac{\pi}{8}\) gate has \(\frac{\pi}{4}\) in the formula.
\( \begin{align} T=&\begin{bmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{bmatrix} \end{align} \)
Two Qubit Gates¶
There are also gates for multiple qubits. These allow us to create relationships between two gates.
The Controlled Not or CX gate works on two qubits. If the first qubit is set to \(\qone\) then an \(X\) is applied to the second qubit. You can think of this like an if statement. The value of the first qubit controls the value of the second qubit.
\( \begin{align} CX=& \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \end{align} \)
The Controlled Z gate (CZ) works like the CX gate. This time the first qubit controls application of the Z gate to the second qubit.
\( \begin{align} CZ=& \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix} \end{align} \)
The Swap gate swaps the values of two qubits.
\( \begin{align} SWAP=& \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{align} \)
Three Qubit Gate¶
The Toffoli Gate (CCX) is a three qubit gate. It takes three qubits as input. If the first two qubits are both \(\qone\) then it applies the \(X\) Gate to the third qubit. If we call the qubits \(q_0\), \(q_1\), and \(q_2\) then we can describe how the gate works.
The values of \(q_0\) and \(q_1\) are unchanged by the gate. It only reads them.
The value of \(q_2\) has the \(X\) gate applied if and only if \(q_0\) and \(q_1\) are both set to \(\qone\). In classic Boolean Logic we would describe it using XOR and AND.
\( \begin{align} q_2 =& q_2 \text{XOR} (q_0 \text{AND} q_1) \end{align} \)
This logical view does not convey everything that is going on. Since the qubit can be in states other that \(\qone\) or \(\qzero\). The matrix describes exaclty what is happening.
\( \begin{align} CCX=& \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \end{align} \)
Example¶
How do we use this to determine the outcome of a quantum system? Lets look at a simple 3 qubit system. It is based on the logic statement \(C=A \vee B\).
The circuit we will use as an example is shown below. This circuit has 3 qubits. We can also follow this circuit using vectors and matrixes.
When multiple gates are applied at the same time, we use the tensor product. If we wanted to apply the \(X\) gate to \(q_0\), but do nothing to \(q_1\). That means we apply \(I\) to \(q_1\). We would first build a 2-qubit system \(X \oplus I\).
If we wanted to apply \(X\) to \(q_0\), \(I\) to \(q_1\), and \(H\) to \(q_2\) then we need the tensor product of three matrixes. We compute \(X \oplus ( I \oplus H)\). The order in which we compute the tensor produces determines what gate is applied to which qubit. It is very important to keep the order correct.
We will now want through the circuit shown earlier. We have a 3-qubit system. That means there are 8 possible outcomes. We start with 1 in the 000 position and all others 0. We will show the binary value related to each vector position in parenthesis next to the number. The order of bits is \((q_0, q_1, q_2)\).
\( \begin{align} v=&\begin{bmatrix} 1 \text{ (000) }\\ 0 \text{ (001) }\\ 0 \text{ (010) } \\ 0 \text{ (011) }\\ 0 \text{ (100) }\\ 0 \text{ (101) }\\ 0 \text{ (110) }\\ 0 \text{ (111) } \end{bmatrix} \end{align} \)
We apply H to the first two qubits and identity to the last qubit. The 3 qubit matrix is \(H \otimes (H \otimes I)\) After the matrix is applied, we have an even split between four values 000, 010, 100, 110. The last bit is still always zero.
\( \begin{align} \begin{bmatrix} \frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & -\frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & -\frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & -\frac{1}{2} \\ \frac{1}{2} & 0 & -\frac{1}{2} & 0 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & -\frac{1}{2} & 0 & \frac{1}{2} \\ \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} \text{ (000) }\\ 0 \text{ (001) }\\ \frac{1}{2} \text{ (010) }\\ 0 \text{ (011) }\\ \frac{1}{2} \text{ (100) } \\ 0 \text{ (101) } \\ \frac{1}{2} \text{ (110) } \\ 0 \text{ (111) } \end{bmatrix} \end{align} \)
The probability of an answer being measured is \(|v_{i}|^2\). That means the probability of 100 is \(\left|\frac{1}{2}\right|^2=\frac{1}{4}\). There is a 25% chance of measuing the circuit at 100.
We next apply X to all 3 qubits. The 3 qubit matrix is \(X \otimes (X \otimes X)\) After applying the matrix we have an even split between 001, 011, 101, 111. Notice that now the last bit is always one.
\( \begin{align} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \text{ (000) } \\ \frac{1}{2} \text{ (001) } \\ 0 \text{ (010) } \\ \frac{1}{2} \text{ (011) } \\ 0 \text{ (100) } \\ \frac{1}{2} \text{ (101) } \\ 0 \text{ (110) } \\ \frac{1}{2} \text{ (111) } \end{bmatrix} \end{align} \)
Now, we apply the CCX Gate. This gate is on 3 qubits, so we don’t need to do anything to it. After applying the gate we even split between 001, 011, 101, 110. Notice the last case 110. When the first two qubits are 1, the last qubit is flipped!
\( \begin{align} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 0 \text{ (000) } \\ \frac{1}{2} \text{ (001) } \\ 0 \text{ (010) } \\ \frac{1}{2} \text{ (011) } \\ 0 \text{ (100) } \\ \frac{1}{2} \text{ (101) } \\ \frac{1}{2} \text{ (110) } \\ 0 \text{ (111) } \end{bmatrix} \end{align} \)
We now want to undo those \(X\) gates we applied earlier. We apply X to the first 2 qubits and Identity to the last qubit. The 3 qubit matrix is \(X \otimes (X \otimes I)\). After applying the matrix we have an even split between. 000, 011, 101, 111.
\( \begin{align} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \\ \frac{1}{2} \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} \text{ (000) } \\ 0 \text{ (001) } \\ 0 \text{ (010) } \\ \frac{1}{2} \text{ (011) } \\ 0 \text{ (100) } \\ \frac{1}{2} \text{ (101) } \\ 0 \text{ (110) } \\ \frac{1}{2} \text{ (111) } \\ \end{bmatrix} \end{align} \)
We now have the final vector of the quantum circuit. Each position has a 25% probability. There is an equal split between 000, 011, 101, 111. This is the truth table table for an OR gate! We have built a circuit that generates all possible truth tables for the OR gate in Boolean Logic.
\( \begin{align} \begin{bmatrix} \frac{1}{2} \text{ (000) } \\ 0 \text{ (001) } \\ 0 \text{ (010) } \\ \frac{1}{2} \text{ (011) } \\ 0 \text{ (100) } \\ \frac{1}{2} \text{ (101) } \\ 0 \text{ (110) } \\ \frac{1}{2} \text{ (111) } \\ \end{bmatrix} \end{align} \)
If we simulate the system using IBM’s qiskit library the result appear as \((q_2, q_1, q_0)\) which the the reverse of the order in our vectors above. \(q_0\) is the last bit instead of the first. Qiskit tells us the solution to this system is {‘101’: 523, ‘000’: 515, ‘111’: 481, ‘110’: 529}
The split on a real circuit is not exactly 25% to each. Each time we measure, we get a different answer. The probability is 25% from each answer, but that is not exactly what we get.
Imagine you had a coin. The change of heads and tails is 50%. If you flip the coin exactly 4 times, there is no guarantee you will get 2 heads and 2 tails. If you did enough tests the answer would trend toward 50/50, but any one test is random. the same thing is happening with out circuit.