Octopedia In order to understand quantum computing in terms of classical computations we need to represent classical bits and its operations as matrices and matrix operations. Iβm adding some elementary algebra for review purposes as itβs been over 2 decades since I last touched on these.
For a review on classical computing bit operations check out my notes on Boolean Algebra
Classical Bits as Matrices
One Bit with value 0 and 1
\[\displaylines{\ket{0} = \begin{bmatrix} 1\\0 \end{bmatrix}\\ \\ \ket{1} = \begin{bmatrix} 0\\1 \end{bmatrix} }\]This is similar to having an array starting from the 0 index with the top value of the matrix being the index to an array with [0, 1].
Algebra Review: Matrix Multiplication
\[\displaylines{ \begin{bmatrix} a & b\\ c & d \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix} = \begin{bmatrix} ax + by\\ cx + dy \end{bmatrix} \\ \\ \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \begin{bmatrix} x\\y\\z \end{bmatrix} = \begin{bmatrix} ax + by + cz\\ dx + ey + fz\\ gx + hy + iz \end{bmatrix} \\ \\ \begin{bmatrix} a & b\\ c & d \end{bmatrix} \begin{bmatrix} w & x\\ y & z \end{bmatrix} = \begin{bmatrix} aw + by & ax + bz\\ cw + dy & cz + dz\\ \end{bmatrix} }\]Algebra Review: Identity Matrix
In linear algebra, the identity matrix of size \(n\) is a \(n \times n\) square matrix filled with \(0\)s and \(1\)s going diagonally from \(x_{1,1}\) to \(x_{n,n}\)
\[{\displaystyle I_{1}={\begin{bmatrix}1\end{bmatrix}},\ I_{2}={\begin{bmatrix}1&0\\0&1\end{bmatrix}},\ I_{3}={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}},\ \dots ,\ I_{n}={\begin{bmatrix}1&0&0&\cdots &0\\0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\end{bmatrix}}.}\]Bit Flip using Identity Matrix
\[\displaylines{ \begin{bmatrix} \color{blue}{1} & 0 & 0 & 0\\ 0 & \color{blue}{1} & 0 & 0\\ 0 & 0 & \color{blue}{1} & 0\\ 0 & 0 & 0 & \color{blue}{1}\\ \end{bmatrix} \begin{bmatrix} a\\b\\c\\d \end{bmatrix} = \begin{bmatrix} a\\b\\c\\d \end{bmatrix}\\ \\ \begin{bmatrix} \color{blue}{1} & 0 & 0 & 0\\ 0 & 0 & \color{red}{1} & 0\\ 0 & \color{red}{1} & 0 & 0\\ 0 & 0 & 0 & \color{blue}{1}\\ \end{bmatrix} \begin{bmatrix} 0\\\color{red}{1}\\\color{red}{0}\\0 \end{bmatrix} = \begin{bmatrix} 0\\\color{blue}{0}\\\color{blue}{1}\\0 \end{bmatrix} }\]Classical Bit Operations on Matrices
Identity
\[f(x) = x\] \[\displaylines{ 0 & π΅ & \longrightarrow & π΅ & 0\\ 1 & π΅ & \longrightarrow & π΅ & 1\\ }\] \[\displaylines{ \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix}\\ \\ \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix}\\ \\ }\]Negation
\[f(x) = \lnot x\] \[\displaylines{ 0 & π΅ & \searrow & π΅ & 0\\ 1 & π΅ & \nearrow & π΅ & 1\\ }\] \[\displaylines{ \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix}\\ \\ \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix}\\ \\ }\]Constant-0
\[f(x) = 0\] \[\] \[\displaylines{ 0 & π΅ & \longrightarrow & π΅ & 0\\ 1 & π΅ & \nearrow & π΅ & 1\\ }\] \[\displaylines{ \begin{bmatrix} 1 & 1\\ 0 & 0 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix}\\ \\ \begin{bmatrix} 1 & 1\\ 0 & 0 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix}\\ \\ }\]Constant-1
\[f(x) = 1\] \[\displaylines{ 0 & π΅ & \searrow & π΅ & 0\\ 1 & π΅ & \longrightarrow & π΅ & 1\\ }\] \[\displaylines{ \begin{bmatrix} 0 & 0\\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix}\\ \\ \begin{bmatrix} 0 & 0\\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix}\\ \\ }\]Reversible Quantum Computing
- Given an operation and output value, you can find the input value
- For \(Ax = b\) given \(b\) and \(A\), you can find \(x\)
- Permutation operations are reversable. Overwriting and Erasing operations are not.
- Identity and Negation are reversible
- Constant-0 and Constant-1 are not
- All quantum operations are reversible as all operators are their own inverse.
- From all the classical bit operations the only thing that applies to Quantum computing are Negation and Identity
Tensor Product of Vectors
In Quantum Computing, multi bit states are written as the tensor product (x β y) of single bit vectors.
\[{\displaylines{\displaystyle {\begin{aligned}x\otimes y&=\left(\sum _{b\in B_{V}}x_{b}\,b\right)\otimes \left(\sum _{c\in B_{W}}y_{c}\,c\right)\\ \\ \\ &=\sum _{b\in B_{V}}\sum _{c\in B_{W}}x_{b}y_{c}\,b\otimes c.\end{aligned}}}\\ }\] \[\displaylines{ \begin{bmatrix} x_0\\x_1 \end{bmatrix}\otimes \begin{bmatrix} y_0\\y_1 \end{bmatrix}= \begin{bmatrix} x_0 \begin{bmatrix} y_0\\y_1 \end{bmatrix}\\ x_1 \begin{bmatrix} y_0\\y_1 \end{bmatrix} \end{bmatrix}= \begin{bmatrix} x_0 y_0\\ x_0 y_1\\ x_1 y_0\\ x_1 y_1\\ \end{bmatrix} }\] \[\displaylines{ \begin{bmatrix} x_0\\x_1 \end{bmatrix}\otimes \begin{bmatrix} y_0\\y_1 \end{bmatrix}\otimes \begin{bmatrix} z_0\\z_1 \end{bmatrix}= \begin{bmatrix} x_0 y_0 z_0\\ x_0 y_0 z_1\\ x_0 y_1 z_0\\ x_0 y_1 z_1\\ x_1 y_0 z_0\\ x_1 y_0 z_1\\ x_1 y_0 z_1\\ x_1 y_1 z_0\\ x_1 y_1 z_1\\ \end{bmatrix} }\] \[\displaylines{ \begin{bmatrix} 1\\2 \end{bmatrix}\otimes \begin{bmatrix} 3\\4 \end{bmatrix}= \begin{bmatrix} 3\\4\\6\\8 \end{bmatrix} }\] \[\displaylines{ \begin{bmatrix} 0\\1 \end{bmatrix}\otimes \begin{bmatrix} 0\\1 \end{bmatrix}\otimes \begin{bmatrix} 1\\0 \end{bmatrix}= \begin{bmatrix} 0\\0\\0\\0\\0\\0\\1\\0 \end{bmatrix} }\]Representing Multiple Clasical Bits Using Tensor Product
This tensored representation is called the product state which can be factored back into the individual state representation.
The product state of n bits is a vector of size 2n \(\displaylines{ \ket{0 0} = \begin{bmatrix} 1\\0 \end{bmatrix}\otimes \begin{bmatrix} 1\\0 \end{bmatrix}= \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} }\)
\[\displaylines{ \ket{1 0} = \begin{bmatrix} 0 \\1 \end{bmatrix}\otimes \begin{bmatrix} 1\\0 \end{bmatrix}= \begin{bmatrix} 0\\0\\1\\0 \end{bmatrix} }\] \[\displaylines{ \ket{0 1} = \begin{bmatrix} 1 \\0 \end{bmatrix}\otimes \begin{bmatrix} 0\\1 \end{bmatrix}= \begin{bmatrix} 0\\1\\0\\0 \end{bmatrix} }\] \[\displaylines{ \ket{1 1} = \begin{bmatrix} 0 \\0 \end{bmatrix}\otimes \begin{bmatrix} 1\\1 \end{bmatrix}= \begin{bmatrix} 0\\0\\0\\1 \end{bmatrix} }\] \[\displaylines{ \ket{4} = \ket{100} = \begin{bmatrix} 0 \\1 \end{bmatrix} \otimes \begin{bmatrix} 1\\0 \end{bmatrix} \otimes \begin{bmatrix} 1\\0 \end{bmatrix}= \begin{bmatrix} 0\\0\\0\\0\\1\\0\\0\\0 \end{bmatrix} }\]Operations on multiple classical bits: CNOT
- Works on a pair of bits:
- control bit
- target bit
- If the control bit is 0, the target bit is unchanged
- If the control bit is 1, the target bit is flipped
- The control bit remains unchanged
Example (MSB is control LSB is target)
\[\displaylines{ \begin{array}{ccc} 00 & π΅ &\longrightarrow & π΅ &00\\ 01 & π΅ &\longrightarrow & π΅ &01\\ 10 & π΅ & \searrow & π΅ & 10\\ 11 & π΅ &\nearrow & π΅ & 11 \end{array} }\]Matrix Representation
\[\displaylines{ C \lnot = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{bmatrix} }\]Reversible CNOT
\[\displaylines{ C\lnot\ket{10} = C\lnot \begin{bmatrix} \begin{bmatrix} 0\\1 \end{bmatrix} \otimes \begin{bmatrix} 1\\0 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0\\0\\1\\0 \end{bmatrix}= \begin{bmatrix} 0\\0\\0\\1 \end{bmatrix}= \begin{bmatrix} 0\\1 \end{bmatrix} \otimes \begin{bmatrix} 0\\1 \end{bmatrix}= \ket{11} }\] \[\displaylines{ C \lnot \ket{11} = C \lnot \begin{bmatrix} \begin{bmatrix} 0\\1 \end{bmatrix} \otimes \begin{bmatrix} 0\\1 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0\\0\\0\\1 \end{bmatrix}= \begin{bmatrix} 0\\0\\1\\0 \end{bmatrix}= \begin{bmatrix} 0\\1 \end{bmatrix} \otimes \begin{bmatrix} 1\\0 \end{bmatrix}= \ket{10} }\]CNOT along with the CCNOT (Toffoli Gate) are the building blocks of gate operations in Quantum Computers akin to how the NAND gate is a general purpose gate of classical computing which all other gates can be built in the most efficient way. CNOT and CCNOT are reversible because of their mathematical properties.
QBits and Superposition
QBits are represented by \(\begin{bmatrix}a\\b\end{bmatrix}\) where \(a\) and \(b\) are \(\mathbb{C}\) Complex numbers and \(\lVert a \rVert^2 + \lVert b\lVert^2 = 1\)
\[\displaylines{ \begin{array}{cccc} \begin{bmatrix} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} \end{bmatrix} & \begin{bmatrix} \frac{1}{\sqrt{2}}\\ \frac{\sqrt{3}}{2} \end{bmatrix} & \begin{bmatrix} -1\\ 0 \end{bmatrix} & \begin{bmatrix} \frac{1}{\sqrt{2}}\\ \frac{-1}{\sqrt{2}} \end{bmatrix} & \end{array} }\]Superposition allows for a QBit to be \(0\) and \(1\) at the same time and when we measure the value it collapses into an actual value of \(1\) or \(0\). If a QBit has value \(\begin{bmatrix}a\\b\end{bmatrix}\) then it collapses to \(0\) with a probability of \(\lVert a \rVert^{2}\) and \(0\) with a probability of \(\lVert b \rVert^{2}\).
For example, QBit \(\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{bmatrix}\) has a \(\bigl \lVert \frac{1}{\sqrt{2}} \bigr \rVert^2\) chance of collapsing to \(0\) or \(1\). The QBit \(\begin{bmatrix}1\\0\end{bmatrix}\) has a \(100\%\) chance of collapsing to \(0\) and \(\begin{bmatrix}0\\1\end{bmatrix}\) has a \(100\%\) chance of collapsing to \(1\).
Toffoli Gate and the Pigeonhole Principle
Quantum Logic Gates
Toffoli (CCNOT, CCX, TOFF)
\[\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}\]Swap
\[\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix}\]Controlled-Z
\[\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1\\ \end{bmatrix}\]Controlled-PHASE
\[\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & i\\ \end{bmatrix}\]Fredkin (Controlled-SWAP)
\[\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 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}\]Hadamard
\[\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1\\ 1 & -1\\ \end{bmatrix}\]Pauli-X
\[\begin{bmatrix} 0 & 1\\ 1 & 0\\ \end{bmatrix}\]Pauli-Y
\[\begin{bmatrix} 0 & -i\\ i & 0\\ \end{bmatrix}\]Pauli-Z
\[\begin{bmatrix} 1 & 0\\ 0 & -1\\ \end{bmatrix}\]Phase
The square root of the PAULI-Z gate
\[\begin{bmatrix} 1 & 0\\ 0 & i\\ \end{bmatrix}\]Ο/8
The square root of the phase gate
\[\begin{bmatrix} 1 & 0\\ 0 & \frac{e^{i\pi}}{4}\\ \end{bmatrix}\]