This is a very brief recap of the most important things you need to know about quantum mechanics for this lecture. You can find more in the script from intro to quantum computing.
Definition 2.1 (Quantum Systems) Quantum systems are described by a set \(\{1,\dots,N\}\) of labels, called classical possibilities or classical states.
A quantum system is in a certain state. We call this state a quantum state.
Definition 2.2 (Quantum State) A quantum state is a vector \(\psi \in \mathbb{C}^N\), \(\lVert\psi\rVert = 1\) \((\sqrt{\Sigma \lvert\psi_i\rvert^2} = 1)\). \(\psi_i\) is the “amplitude” of classical possibility i. \(\lvert\psi_i\rvert^2\) is the probability of classical possibility i.
In Ket-notation \(\ket{n}\) denotes the \(n\)-th entry being 1. E.g. \[ \ket {n} = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \leftarrow \text{1 at the $i$-th position}\] We also write \(\ket{\psi}\), to emphasize that \(\psi\) is a quantum state. Some often used states include: \[
\ket{0} := \begin{pmatrix} 1 \\ 0 \end{pmatrix}\quad
\ket{1} := \begin{pmatrix} 0 \\ 1 \end{pmatrix}\quad
\ket{+} := \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix}\quad
\ket{-} := \begin{pmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{pmatrix}
\]
These quantum states can have operators applied to them. These operators are matrices, more specifically unitaries.
Definition 2.3 (Unitary matrices) Unitary matrices describe the Evolution of a quantum system: \(\ket{\psi} \rightarrow \operatorname{U}\ket{\psi}\). Here U must be a unitary matrix. This means U is \(\in \mathbb{C}^{N \times N}\) and \(U^\dagger U = UU^{\dagger} = I\). \(U^{\dagger}\) is the conjugate transpose of \(U\) and \(I\) is the identity matrix. Unitary operations are length preserving, e.g. \(\lVert U \ket{\psi}\rVert = \lVert\ket{\psi}\rVert\).
After doing computations, you would naturally want to look at the results. To find out what state our system is in, we need to measure it.
Definition 2.4 (Complete Measurement) When we measure a state \(\psi\) in its entirety, we get outcome i with probability \(\lvert \psi_i \rvert ^2\). The post-measurement-state after measuring outcome i is \(\ket{i}\).
Instead of measuring the entire state, we might only want information about some of its components.
Measuring partially causes only the measured part of the system to collapse. This means the qubit(s) we measure decide what the partitions are.
Definition 2.5 (Partial Measurement) When we partially measure a state \(\psi\), we get one alternative \(A_j \subseteq \{1,\dots,N\}\), where each \(A_j\) forms a partition.
The state is then in partition \(A_j\) with probability \(\sum\limits_{x\in A_j}\lvert \psi_x\rvert^2\). This would result in the non-normalized post-measurement-state \(\tilde{\psi} = \begin{cases}\psi_i\text{ if i}\in A_j\\\text{ 0 if i}\notin A_j\end{cases}\). We can then get the normalized post-measurement state like this: \(\psi = \frac{\tilde{\psi}}{\lVert\tilde{\psi}\rVert}\).
What is the first bit of a two bit state?
\(A_0 = \{00,01\}, A_1 = \{10,11\}\)
The probability of outcome \(j\) would then be \(\sum\limits_{x\in A_j}\lvert \psi_x\rvert^2 = \begin{cases}\lvert\psi_{00}\rvert^2+\lvert\psi_{01}\rvert^2 (j= 0)\\\lvert\psi_{10}\rvert^2+\lvert\psi_{11}\rvert^2 (j= 1)\end{cases}\)
If we measured outcome 1, our state would be: \(\begin{pmatrix} 0 \\ 0 \\ \gamma \\ \delta \end{pmatrix}\), and after normalizing \(\begin{pmatrix} 0 \\ 0 \\ \frac{\gamma}{\sqrt{\lvert\gamma^2\rvert+\lvert\delta^2\rvert}} \\ \frac{\delta}{\sqrt{\lvert\gamma^2\rvert+\lvert\delta^2\rvert}} \end{pmatrix}\)
You can compose two quantum systems together. If we have quantum system A with classical possibilities \(\{1,\dots,N\}\) and quantum system B with possibilities \(\{1,\dots,M\}\), the composite system AB has the following classical possibilities \(\{(1,1),\dots,(1,M),(2,1),\dots,(N,M)\}\)
Similarly, we can compose quantum states. The states \(\phi\in\mathbb{C}^N\) and \(\psi\in\mathbb{C}^M\) of our systems A and B respectively can be composed as \(\phi \otimes \psi\).
\[\phi \otimes \psi = \begin{pmatrix} \phi_1\psi \\ \vdots \\ \phi_N\psi \end{pmatrix} = \begin{pmatrix} \phi_1\psi_1 \\ \vdots \\ \phi_1\psi_M \\ \phi_2\psi_1 \\ \phi_N\psi_M \end{pmatrix} \] The result vector then has \(N\times M\) entries.
While you can always tensor two states together, there are states of AB that cannot be written separately as \(\phi \otimes \psi\). These entangled states are the result of \(\phi\) and \(\psi\) having already interacted.
When writing down quantum operations, we do so using so-called quantum circuits.
In this example circuit, we have three qubits, A, B and C. We first apply the unitary U to the first qubit, but not to the second and third (this is written \(\operatorname{U} \otimes \operatorname{I} \otimes \operatorname{I}\)). Then, we apply the unitary V on qubit B and C, and finally we measure qubit B. Mathematically, the second operation can be written as \(\operatorname{I} \otimes \operatorname{V}\).
Measuring just the second wire would be the operation \(I\otimes M\otimes I\). Here, M is measuring a single qubit and thus the alternatives for that wire are \(M = \{\{0\},\{1\}\}\). The system then has either a 0 on wire B (\(A_0 = \{000,001,100,101\}\)) or a 1 (\(A_1 = \{010,011,110,111\}\)).
Common quantum transformations that are used often have names associated with them.
\[
X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \quad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} \quad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \quad H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}
\] \[
CNOT = \begin{psmallmatrix} 1 & 0&0 &0 \\ 0 & 1 &0 &0 \\ 0&0&0&1 \\0&0&1&0 \end{psmallmatrix}
\]
The X gate can be called a “bit flip”, because it flips the basis states: \[
X\ket{0} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \ket{1}
\]
Hadamard is useful because it switches the basis from computational to diagonal and back: \[
\operatorname{H}\ket{0} = \ket{+}, \operatorname{H}\ket{1} = \ket{-},
\operatorname{H}\ket{+} = \ket{0}, \operatorname{H}\ket{-} = \ket{1}
\]
Sometimes, large matrices are harder to visualize. A matrix such as CNOT can more easily be described by expressing what it does to an input. Like so: \(\operatorname{CNOT} \ket{x,y} \rightarrow \ket{x,y\oplus x}\). (E.g. \(\operatorname{CNOT} \ket{10} = \ket{1,0\oplus 1} = \ket{11}\)). This completely describes the behavior of an operator, since the computational basis states that you plug in to the equation form a basis of the vector space.
Visually, you would express \(\operatorname{CNOT}\) as the circuit displayed above. Here, the dot always represents the controlling wire, which flips the other connected wire depending on its state. Using more than one controlling wire makes a gate called a Toffoli.
With Toffoli, CNOT and X we can implement any classical function \(f: \{0,1\}^n\rightarrow\{0,1\}^m\) quantumly. Since functions work differently than the matrices we normally apply as operators when working in a quantum system, we need to represent this in a meaningful way. We use \(U_f\ket{x,y}\rightarrow\ket{x,y\oplus f(x)}\), with \(x\in \{0,1\}^n\) and \(y \in \{0,1\}^m\). Since quantum operations are always reversible, the output has to contain both the input and the output of f. Using Toffoli, CNOT and X, we can implement \(U_f\) with approximately twice the number of gates that a classical implementation of f would use.
We can also replace Toffoli, CNOT and X with other gates. Any set of gates that, together, can replace any gate at all, is called a universal set of gates. There is a constant factor in runtime, but otherwise it does not matter what universal set you use.
