# Universality

- Entanglement
- $|00\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)=|\Phi^+\rangle$
- $|01\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)=|\Psi^+\rangle$
- $|10\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|00\rangle-|11\rangle)=|\Phi^-\rangle$
- $|11\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|01\rangle-|10\rangle)=|\Psi^-\rangle$
- Bell state are equivalent up to local unitary operations
- $|\Psi^+\rangle=X_1|\Phi^+\rangle=X_2|\Phi^+\rangle$
- $|\Phi^-\rangle=Z_1|\Phi^+\rangle=Z_2|\Phi^+\rangle$
> general property: Entanglement don't change under local unitary operations.
- $\frac{1}{\sqrt{2}}(|00\rangle+i|10\rangle)$ also called Bell state: **Local unitary equivalent**
with $S_1=\begin{pmatrix}1 & 0 \\ 0 & i\end{pmatrix}$

### Universality of quantum gates
- Classical:
- $\{AND, NOT\}$ and $\{NAND\}$ are sets of classical logic gate universal for **irreversible** computing
- $\{TOFFELI\}$ is a universal 3-bit logic gate for **reversible** computing
- Quantum computing: *what are the minimal sets for n-qubit computation $U$?*
- $T^4=S^2=Z$
- $HZH=X$
- $Y=iXZ$
> $H$-gate and $T$-gate can generate $X,Y,Z$
- Two-qubit
- **CNOT + arbitrary single rotation = universal gate set**
- example: $\{CNOT,H,T\}$
- Proof:
1. Arbitrary $n$-qubit gates can be decomposed into products of $n$-qubit unitary operations that act in a <ins>2-dim subspace</ins> only.
- decompose $U$ into a product of $\{V_k\}$
$$V_k=\begin{pmatrix}\\
1 & & & & & & & & & & \\
& \ddots & & & & & & & & & \\
& & 1 & & & & & & & & \\
& & & a & & & & b & & & \\
& & & & 1 & & & & & &\\
& & & & & \ddots & & & & & \\
& & & & & & 1 & & & & \\
& & & c & & & & d & & & \\
& & & & & & & & 1 & &\\
& & & & & & & & & \ddots & & \\
& & & & & & & & & & 1 \end{pmatrix}$$
- example: $d=3$
$$U=\begin{pmatrix} a&d&g\\ b&e&h\\ c&f&i\end{pmatrix}, U^\dagger U=\mathbb{I}$$
we will find $V_1,V_2,V_3$ such that $V_3V_2V_1U=\mathbb{I}$
(until decompose of $U$ into $2$-level unitary $V_k$)
thus $U^\dagger =V_3V_2V_1$
- if $b=0$, set $V_1=\begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1\end{pmatrix}$
- if $b\neq 0$, set $$V_1=\begin{pmatrix} \frac{a^*}{\sqrt{|a|^2+|b|^2}}&\frac{b^*}{\sqrt{|a|^2+|b|^2}}&0\\ \frac{b}{\sqrt{|a|^2+|b|^2}}&\frac{-a}{\sqrt{|a|^2+|b|^2}}&0\\ 0&0&1\end{pmatrix}$$
$V_1$ is a valid $2$-level unitary.
- for $d=2^n$, we need to construct
$(d-1)$ $2$-level unitaries for the first column
$(d-2)$ for the second column
- $U=V_1V_2...V_k$
$$k\leq\frac{d(d-1)}{2}$$
> This is **inefficient**
> There exists matrices for which $2$-level unitaries is needed
2. arbitrary $2$-level unitaries can be realized by $CNOT$-gate and single qubit rotations.
- if
$$V_k=\begin{pmatrix}a & 0 & \dots & b \\
0 & 1 & \dots & 0 \\
\vdots & & \ddots & \vdots\\
c & 0 & \dots & d\end{pmatrix}$$
- **Problem:** $V_k$ acts on the state, not a single qubit
- **Solution:** *Gray code* that connects state $|000\rangle$ and $|111\rangle$
- $000\rightarrow 001\rightarrow 011 \rightarrow 111$
all differs in one qubit only
- different controlled-controlled-$U$ ($3$-qubit):
- applies $U$ iff the first qubit is $|0\rangle$ and the second qubit is $|1\rangle$
- applies $X_1$ before and after controlled-controlled-$U$ (flips $|0\rangle$ to $|1\rangle$)
3. Arbitrary single-qubit rotation can be approximated by a finite set of single qubit gates, e.g. $H$ and $T$ gates
- arbitrary single-qubit rotation can be built up from rotations about **2-axis**
- $U=e^{i\alpha} R_n(\beta) R_m(\gamma) R_n(\delta)$
(can be built from $R_y,R_z$)
- **Solovay–Kitaev theorem**
A single-qubit gate $U$ can be approximately to accuracy $\varepsilon$ using $O(\log^2(1/\varepsilon))$ gates from the discrete gate set.
Poly-logarithmic increase $\Rightarrow$ growing very slow (not exponential increase in $1/\varepsilon$)
- overall resource count
- for one $2$-level unitary $(d=2^n)$, we need at most $2(n-1)$ controlled operations $C^{n-1}(X)$ to implement a **swap** according to the gray code.
- $O(n)$ toffeli-gate
- This amounts to $O(n)$ single-qubit gates and CNOT gates.
- We need $O(4^n)$ $2$-level unitaries $V_k$ to compose the $n$-qubit unitary $U$
> Result: Implementation of an arbitrary $n$-qubit unitary $U$ can be realized by a quantum circuit containing $O(n^24^n)$ single qubit gates and CNOT operations.

### $n$-qubit Pauli group
- $$P_n=\{e^{i\pi\cdot k/2}\sigma_{j_1}...\sigma_{j_n}|n=0,1,2,3\text{ and }j_k=0,1,2,3\}\\\text{where }\sigma_0=\mathbb{I},\sigma_1=X,\sigma_2=Y,\sigma_3=Z$$

### $n$-qubit Clifford group
- $$C_n=\{V P_n V^\dagger=P_n\}$$
- $n=1$ example:
- **Hadamard gate** $\in C_1$
- $HXH^\dagger=Z,HXH^\dagger=Z,HZH^\dagger=X,HYH^\dagger=-Y$
$\Rightarrow$ the 16 elements of $P_1$ are mapped onto $P_1$
- **T gate** $\notin C_1$
- $TXT^\dagger=1/\sqrt{2}(X+Y)\notin P_1$
- $n=2$ example:
- **CNOT gate** $\in C_2$
- $(C_1NOT_2)X_1(C_1NOT_2)=X_1X_2$
- **gottesman-knill theorem**
- Quantum circiuts of only Clifford gates can be perfectly simulated efficiently, i.e. in <ins>polynomial time</ins>, on classical computers.