cheatsheet.tex

\section{Cheatsheet}\label{sec:cheatsheet}
% Local formatting for the cheatsheet
\begingroup
\setlength{\parindent}{0pt}
\setlength{\parskip}{0pt plus 0.5ex}
\raggedright
\footnotesize

\makeatother

\begin{multicols}{3}

\section*{Linear Algebra Notation}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Bra-Ket}: Ket $|\psi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$, Bra $\langle\psi| = [\alpha^* \; \beta^*]$
    \item \textbf{Inner Product}: $\langle\phi|\psi\rangle = \phi^\dagger\psi = \sum_i \phi_i^*\psi_i$
    \item \textbf{Norm}: $\|\psi\|^2 = \langle\psi|\psi\rangle = \sum_i |\psi_i|^2$
    \item \textbf{Outer Product}: $|\psi\rangle\langle\phi| = \begin{bmatrix} \psi_1\phi_1^* & \psi_1\phi_2^* \\ \psi_2\phi_1^* & \psi_2\phi_2^* \end{bmatrix}$
    \item \textbf{Tensor Product}: $|\psi\rangle \otimes |\phi\rangle = \begin{bmatrix} \psi_1\phi_1 \\ \psi_1\phi_2 \\ \psi_2\phi_1 \\ \psi_2\phi_2 \end{bmatrix}$
    \item \textbf{Matrix Mult}: $(AB)_{ij} = \sum_k A_{ik}B_{kj}$
    \item \textbf{Unitary}: $U^\dagger U = UU^\dagger = I$, preserves norms and inner products
    \item \textbf{Hermitian}: $H = H^\dagger$, eigenvalues are real
    \item \textbf{Magnitude}: Real: $\|v\| = \sqrt{\sum_i v_i^2}$, Complex: $\|v\| = \sqrt{\sum_i |v_i|^2}$
\end{itemize}

\conceptbox{Important Property}{Tensor products are \textit{not commutative}: $A \otimes B \neq B \otimes A$ generally}

\section*{Qubit Representation}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Dirac Notation}: $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, where $\alpha,\beta \in \mathbb{C}$ and $|\alpha|^2 + |\beta|^2 = 1$
    \item \textbf{Computational Basis}: $|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$
\end{itemize}

\section*{Universal Bases}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Computational}: $\{|0\rangle, |1\rangle\}$ \\
        $(\theta=0, \phi=0; \theta=\pi, \phi=0)$
    \item \textbf{Hadamard}: $\{|+\rangle, |-\rangle\}$ where\\
        $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$\\
        $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$\\
        $(\theta=\frac{\pi}{2}, \phi=0; \theta=\frac{\pi}{2}, \phi=\pi)$
    \item \textbf{Phase}: $\{|+i\rangle, |-i\rangle\}$ where\\
        $|+i\rangle = \frac{1}{\sqrt{2}}(|0\rangle + i|1\rangle)$\\
        $|-i\rangle = \frac{1}{\sqrt{2}}(|0\rangle - i|1\rangle)$\\
        $(\theta=\frac{\pi}{2}, \phi=\frac{\pi}{2}; \theta=\frac{\pi}{2}, \phi=-\frac{\pi}{2})$
\end{itemize}

\section*{Bloch Sphere}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Equation}: $|\psi\rangle = \cos\frac{\theta}{2}|0\rangle + e^{i\phi}\sin\frac{\theta}{2}|1\rangle$\\
    where $\theta \in [0,\pi]$, $\phi \in [0,2\pi)$
    \item \textbf{Cartesian Projection}:
    \begin{align*}
        x &= \sin\theta\cos\phi\\
        y &= \sin\theta\sin\phi\\
        z &= \cos\theta
    \end{align*}
\end{itemize}

\section*{Quantum Measurement}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Probability}: For measuring state $|\psi\rangle$ in basis $|b\rangle$:
    \begin{align*}
        P(b) = |\langle b|\psi\rangle|^2
    \end{align*}
    \item \textbf{Post-measurement state}:
    \begin{align*}
        |\psi_{\text{new}}\rangle = \frac{|b\rangle\langle b|\psi\rangle}{\sqrt{P(b)}}
    \end{align*}
    \item For $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$:
    \begin{align*}
        P(0) = |\alpha|^2, \quad P(1) = |\beta|^2
    \end{align*}
\end{itemize}

\section*{Single-Qubit Gates}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Properties}:
    \begin{itemize}[nosep]
        \item Reversible: $U^\dagger U = UU^\dagger = I$
        \item Preserve norm: $\|U|\psi\rangle\| = \||\psi\rangle\|$
        \item Linear: $U(\alpha|\psi\rangle + \beta|\phi\rangle) = \alpha U|\psi\rangle + \beta U|\phi\rangle$
    \end{itemize}
\end{itemize}

\section*{Pauli Gates}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Pauli-X (NOT)}: $X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$
        \begin{itemize}[nosep]
            \item $X|0\rangle = |1\rangle$, $X|1\rangle = |0\rangle$
            \item $X|+\rangle = |+\rangle$, $X|-\rangle = -|-\rangle$
        \end{itemize}

    \item \textbf{Pauli-Y}: $Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}$
        \begin{itemize}[nosep]
            \item $Y|0\rangle = i|1\rangle$, $Y|1\rangle = -i|0\rangle$
        \end{itemize}

    \item \textbf{Pauli-Z (Phase Flip)}: $Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$
        \begin{itemize}[nosep]
            \item $Z|0\rangle = |0\rangle$, $Z|1\rangle = -|1\rangle$
            \item $Z|+\rangle = |-\rangle$, $Z|-\rangle = |+\rangle$
        \end{itemize}
\end{itemize}

\section*{Rotation Gates}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{X-rotation}: $R_X(\theta) = e^{-i\theta X/2} = \begin{bmatrix} \cos\frac{\theta}{2} & -i\sin\frac{\theta}{2} \\ -i\sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{bmatrix}$

    \item \textbf{Y-rotation}: $R_Y(\theta) = e^{-i\theta Y/2} = \begin{bmatrix} \cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ \sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{bmatrix}$

    \item \textbf{Z-rotation}: $R_Z(\theta) = e^{-i\theta Z/2} = \begin{bmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{bmatrix}$
\end{itemize}

\section*{Other Important Gates}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Hadamard}: $H = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$
    \begin{itemize}[nosep]
        \item $H|0\rangle = |+\rangle$, $H|1\rangle = |-\rangle$
        \item $H|+\rangle = |0\rangle$, $H|-\rangle = |1\rangle$
        \item $H^2 = I$
    \end{itemize}

    \item \textbf{Phase (S)}: $S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}$
    \begin{itemize}[nosep]
        \item $S|+\rangle = |+i\rangle = \frac{1}{\sqrt{2}}(|0\rangle + i|1\rangle)$
        \item $S^2 = Z$
    \end{itemize}

    \item \textbf{T Gate}: $T = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{bmatrix}$
    \begin{itemize}[nosep]
        \item $T|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\pi/4}|1\rangle)$
        \item $T^2 = S$, $T^4 = Z$
    \end{itemize}

    \item \textbf{General Phase}: $P(\theta) = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{bmatrix}$
    \begin{itemize}[nosep]
        \item $S = P(\pi/2)$, $T = P(\pi/4)$, $Z = P(\pi)$
    \end{itemize}
\end{itemize}

\section*{Circuit Notation}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Elements}:
    \begin{itemize}[nosep]
        \item Qubit: Horizontal line
        \item Gates: Boxes with labels
        \item Measurement: Meter symbol (if available)
        \item Time: Left $\to$ Right
        \item Controlled operations: Vertical line with dot
        \item Control on $|1\rangle$: Filled dot $\bullet$
        \item Control on $|0\rangle$: Empty dot $\circ$
    \end{itemize}
    \item \textbf{Important}: Matrix order in circuit is opposite to mathematical notation
    \begin{itemize}[nosep]
        \item $U_1 U_2$ in circuit $=$ $U_2 U_1$ in matrix form
    \end{itemize}
\end{itemize}

\section*{Multi-Qubit Gates}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{CNOT} (Controlled-NOT):
    \begin{align*}
        \text{CNOT} = \begin{bmatrix}
            1 & 0 & 0 & 0 \\
            0 & 1 & 0 & 0 \\
            0 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{bmatrix}
    \end{align*}
    \begin{itemize}[nosep]
        \item Effect: $|c,t\rangle \rightarrow |c, t \oplus c\rangle$
        \item $|00\rangle \to |00\rangle$, $|01\rangle \to |01\rangle$
        \item $|10\rangle \to |11\rangle$, $|11\rangle \to |10\rangle$
    \end{itemize}

    \item \textbf{Controlled-Z}:
    \begin{align*}
        \text{CZ} = \begin{bmatrix}
            1 & 0 & 0 & 0 \\
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            0 & 0 & 0 & -1
        \end{bmatrix}
    \end{align*}
    \begin{itemize}[nosep]
        \item Effect: $|x,y\rangle \to (-1)^{xy}|x,y\rangle$
        \item Only changes $|11\rangle \to -|11\rangle$
        \item Symmetric: Either qubit can be control
    \end{itemize}

    \item \textbf{Toffoli} (CCNOT):
    \begin{itemize}[nosep]
        \item Effect: $|x,y,z\rangle \to |x,y,z \oplus (x \cdot y)\rangle$
        \item Flips target only if both controls are $|1\rangle$
    \end{itemize}

    \item \textbf{SWAP}:
    \begin{align*}
        \text{SWAP} = \begin{bmatrix}
            1 & 0 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            0 & 1 & 0 & 0 \\
            0 & 0 & 0 & 1
        \end{bmatrix}
    \end{align*}
    \begin{itemize}[nosep]
        \item Effect: $|a,b\rangle \to |b,a\rangle$
        \item Implementation: $\text{CNOT}_{1,2} \cdot \text{CNOT}_{2,1} \cdot \text{CNOT}_{1,2}$
    \end{itemize}

    \item \textbf{Flipped CNOT}:
    \begin{align*}
        (H \otimes H) \cdot \text{CNOT} \cdot (H \otimes H) = \begin{bmatrix}
            1 & 0 & 0 & 0 \\
            0 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0 \\
            0 & 1 & 0 & 0
        \end{bmatrix}
    \end{align*}
\end{itemize}

\section*{Key Quantum Properties}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Reversibility}: All quantum gates are reversible
    \begin{itemize}[nosep]
        \item To reverse a circuit, apply $U^\dagger$ gates in reverse order
    \end{itemize}

    \item \textbf{No-Cloning Theorem}: Cannot create an identical copy of an unknown quantum state
    \begin{align*}
        \nexists U: U(|\psi\rangle \otimes |0\rangle) = |\psi\rangle \otimes |\psi\rangle
    \end{align*}

    \item \textbf{Entanglement}: States that cannot be factored as tensor products of individual states
    \begin{itemize}[nosep]
        \item E.g., Bell state: $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$
    \end{itemize}
\end{itemize}

\section*{Bell Pair}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Bell States} (maximally entangled):
    \begin{align*}
        |\Phi^+\rangle &= \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\\
        |\Phi^-\rangle &= \frac{1}{\sqrt{2}}(|00\rangle - |11\rangle)\\
        |\Psi^+\rangle &= \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle)\\
        |\Psi^-\rangle &= \frac{1}{\sqrt{2}}(|01\rangle - |10\rangle)
    \end{align*}
\end{itemize}

\section*{Grover's Algorithm}
\begin{itemize}[leftmargin=*,nosep,topsep=0pt]
    \item \textbf{Purpose}: Search unstructured database of $N$ items in $O(\sqrt{N})$ time

    \item \textbf{Algorithm}:
    \begin{enumerate}[nosep]
        \item Initialize: $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$
        \item Repeat $O(\sqrt{N})$ times:
        \begin{itemize}[nosep]
            \item Oracle ($O$): $O|x\rangle = (-1)^{f(x)}|x\rangle$ where $f(x)=1$ for solution
            \item Diffusion ($D$): $D = 2|s\rangle\langle s| - I$
        \end{itemize}
        \item Measure to find solution with high probability
    \end{enumerate}
\end{itemize}

\conceptbox{Important Insight}{Grover's algorithm provides quadratic speedup over classical search, which is proven to be optimal for quantum algorithms}

\end{multicols}
\endgroup