# Quantum Error Correction

- **Problem:** the quantum computer cannot be isolated from the environment, therefore, operations can be faulty.
This leads to errors in quantum gates, initial state preparation, measurements.

- *classical*: redundancy (by copying)
- but in quantum cases, by measuring $\alpha|0\rangle+\beta|1\rangle$ will lose the information about $\alpha$ and $\beta$
- even worse for entangled state $\alpha|000\rangle+\beta|111\rangle$
- *Quantum challenges*:
- not only bit flip error, but also phase flip or both
- errors continuous $U(t)=e^{-iHt}$
- **Effective error model**: Stochastic independently distributed $X,Y,Z$ errors with probability $p$

### $3$-qubit code
- Idea: distribute one qubit $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ over $3$ physical qubits.
- basis state / codewords $|0\rangle=|000\rangle,|1\rangle=|111\rangle$
- span codespace
$$\begin{aligned}|\psi\rangle_L&=\alpha|0\rangle+\beta|1\rangle\\
&=\alpha|000\rangle+\beta|111\rangle\end{aligned}$$

1. Encoding: $C_1NOT_2$ and $C_1NOT_3$ on $|\psi\rangle|0\rangle|0\rangle\rightarrow |\psi\rangle_L$
2. possible occurance of errors:
- e.g. bit flip error
$\alpha|000\rangle+\beta|111\rangle\xrightarrow[]{X_1}\alpha|100\rangle+\beta|011\rangle$
- by measuring: collapse onto $|011\rangle$ or $|100\rangle$ and lose the information about $\alpha$ and $\beta$
- **Solution** indirect measuremnt via ancilla qubits.
Apply $C_1NOT_3, C_2NOT_3$ on state $|a\rangle|b\rangle|0_C\rangle$ and measuring $|0_C\rangle$
where $|0_C\rangle$ is an ancilla state.
If $|ab\rangle=|00\rangle$ or $|ab\rangle=|11\rangle$, $|0_C\rangle$ will not change. $\Rightarrow$ even parity
If $|ab\rangle=|01\rangle$ or $|ab\rangle=|10\rangle$, $|0_C\rangle$ will change to $|1_C\rangle$. $\Rightarrow$ odd parity
- general consideration:
consider $n$-qubit operation $U$ with eigenvalues $\pm 1$
$$\begin{aligned}|0\rangle|\psi\rangle&\xrightarrow[]{H_1}&1/\sqrt{2}(|0\rangle+|1\rangle)|\psi\rangle\\
&\xrightarrow[]{Controlled-U}&1/\sqrt{2}|0\rangle|\psi\rangle+1/\sqrt{2}|1\rangle U|\psi\rangle\\
&\xrightarrow[]{H_1} & 1/2(|0\rangle+|1\rangle)|\psi\rangle+1/2(|0\rangle-|1\rangle) U|\psi\rangle \\
& &=|0\rangle (1/2)(\mathbb{I}+U)|\psi\rangle+|1\rangle (1/2)(\mathbb{I}-U)|\psi\rangle\end{aligned}$$
where $(1/2)(\mathbb{I}\pm U)$ is $P_\pm:$ projector operator on the $\pm 1$ eigenspace of $U$
$\Rightarrow$ realize a measuremnt of $U$
For $U=Z_1Z_2$
$\Rightarrow$ This is a contrast to measure $Z_1$ and $Z_2$ individually.
- Two ancilla qubits
$$\begin{aligned}|\psi\rangle|00\rangle\xrightarrow[]{error}&|\psi'\rangle|00'\rangle|00\rangle_{ancilla} \\
\xrightarrow[]{C_1NOT_4, C_2NOT_4, C_2NOT_5, C_3NOT5}&|\psi'\rangle|00'\rangle Z_1Z_2|0\rangle Z_2Z_3|0\rangle \\
\xrightarrow[]{correction}& |\psi''\rangle|00''\rangle\end{aligned}$$
| $Z_1Z_2$| $Z_2Z_3$ | error/correction |
|--| --|--|
|$1$ |$1$ | $\mathbb{I}$|
|$-1$| $1$| $X_1$ |
|$-1$| $-1$| $X_2$ |
|$1$| $-1$| $X_3$ |
> correct only **one** $X$-error on any of the gate
> If there are two $X$-errors, then QEC fails
> If there are three, then it cannot be detected
- *$3$-qubit code is not a complete code*
- <ins>Robustness</ins> $3$-qubit code better than one qubit?
- error model:
- bit flip error: $p$
- no error: $1-p$
- probability to correct:
$$p_{correct}=(1-p)^3+3p(1-p)^2$$
no error on $3$ qubits + the probability of one $X$ error
$$p_{fail}=3p^2(1-p)+p^3$$
- For $p<1/2$, $p_{correct}>(1-p)$
where $(1-p)$ is the probability of single qubit which successes.
$\Rightarrow$ $3$-qubit is better than single qubit.
- How to increase robustness?
1. $5$-qubit code
$p_{correct}^{(5)}\geq p_{correct}^{(3)}$ for small $p$
2. contatenation
Encode codes in codes in codes....
$$p_{fail}^{(n)}=3(p_{fail}^{(n-1)})^2-2(p_{fail}^{(n-1)})^3\leq 3 (p_{fail}^{(n-1)})^2$$
For $n$ layers of concatenation:
$$p_{fail}^{(n)}\leq\frac{1}{3}(3p)^{2^n}$$
$\Rightarrow p_{fail}\rightarrow 0\text{ for }p\leq 1/3$
> double-exponentially fast in the number of layers $n$
>

### Stabilize Formalism
- Idea: Fix and describe quantum state by set of commuting observations rather than explicit quantum state vector.
- allows us to describe a larger class of multi-qubit states.
- Example:
- Stabilizer state: $|\Phi^+\rangle=1/\sqrt{2}(|00\rangle+|11\rangle)$
- Stabilizer: $S_1=Z_1Z_2, S_2=X_1X_2$
- $S_1S_2=S_2S_1$, they can commute with each other
i.e. $[S_1,S_2]=0$
- $|\Phi^+\rangle$ has unique eigenstate $|\psi\rangle$
$S_1|\psi\rangle=|\psi\rangle\\S_2|\psi\rangle=|\psi\rangle$
- $S_1, S_2$ generates a $2^2=4$ Abelian group:
$$\{\mathbb{I},Z_1Z_2,X_1X_2,-Y_1Y_2\}$$
- Generalization of $n$-qubit
- $n$ generators $S_1,...,S_n$
- $2^n$ stabilizer operators
- $S_i|\psi\rangle=|\psi\rangle,\ \forall\ i$
- Stabilizer QEC code:
- $\{S_i\}$ with $[S_i,S_j] = 0,\ \forall\ i,j$
- $O_L$: logical operatoers $Z_L, X_L$, with $[O_L,S_i]=0$
- $\{Z_L,X_L\}=0$
- Quantum hamming bound:
- How large must a $\mathcal{H}$ space be, so that we can accomadate QEC codes:
- $n$-qubit, $k$ encoded for up to $t$ errors.
- if $j$ errors, $j\leq t$
$$\sum_{j=0}^t{n\choose j}3^j\cdot 2^k\leq 2^n\\\text{ called Quantum Hamming Bound}$$
${n\choose j}:j$ errors occur in $n$-qubits
$3^j:$ $X,Y,Z$ errors
$2^k:$ error codespace to an $2^k$ dimension orthogonal subspace
- for 1 logical qubit $k=1$, 1 arbitrary correctable error $t=1$
$$2(1+3n)\leq2^n$$
$\Rightarrow n\geq 5$ qubits needed for smallest <ins>complete</ins> code.
- *9*-qubit shor code:
- $$\begin{aligned}|\psi\rangle_L&=\alpha(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)/\sqrt{8}\\
&+\beta(|000\rangle-|111\rangle)(|000\rangle-|111\rangle)(|000\rangle-|111\rangle)/\sqrt{8}\end{aligned}$$
- Bit flip errors $X_i$
can be detected by $\{Z_1Z_2, Z_2Z_3,Z_4Z_5,Z_5Z_6,Z_7Z_8,Z_8Z_9\}$
- phase flip errors $Z_i$
can be detected by $\{X_1X_2X_3X_4X_5X_6,X_4X_5X_6X_7X_8X_9\}$
detect the sign of any of three qubits.
- after detecting a phase flip in the first block, we don't know which qubit
but we can applying $Z_1$-correction
we get the same correct state.
- **Property:**
- complete code
- <ins>degenerate code</ins>: several errors have the same effect on logic state e.g. $Z_1, Z_2$
- Correction works: $$\text{attempt + error = identity or stabilizer}$$

### Quantum Fault Tolerance
- **Problem:** Errors can occur before encoding or during encoding
- <ins>uncontrolled error propagation</ins>
- example $(C_1NOT_2)X_1=X_1X_2(C_1NOT_2)$
$X$ error propagates from a controlled qubit through $CNOT$ gate onto a target qubit
( propagate errors from $X_1$ to $X_2$)
- Fault Tolerant quantum circuit construction: avoid error spread, infection
- $7$-qubit scheme code
- possible, but requires non-local gates, resource overhead

### Topological QEC
- idea: quantum information spread out **globally**, to protect against **local** errors.
- no concatenation
- increase the size of lattice to increase robustness
- no braiding for gates

### Kitaev's toric code
- $L\times L$ square lattice with physical qubits located on the edges
- Codespace: $S_Z^{(i)}|\psi\rangle=S_X^{(j)}|\psi\rangle=|\psi\rangle$
- Periodic boundry conditions: lattice is embedded on the surface of a torus. $\Rightarrow$ Toric code
- number of qubits and operatoins:
- $L^2$ plaquette $\Rightarrow$ $2L^2$ physics qubits
- $L^2$ plaquette $\Rightarrow$ $L^2$ $Z$-stabalizer
- $L^2$ plaquette $\Rightarrow$ $L^2$ $X$-stabalizer
- not all stabilizers are independent:
$$\prod_i S_Z^{(i)}=\mathbb{I}\Rightarrow\prod_i^{L^2-1} S_Z^{(i)}=S_Z^{(L^2)}$$
- only $L^2-1$ independent $Z(X)$-stabalizers.
- $k=$ number of logic qubits$=(\#$physical qubits$)-(\#$independent stabalizer constrains$)=2$ (encoded qubits)
> Topological property: independent of size, lattice structure
- minimum-weight perfect matching (MWPM)
- logic quantum computations: transversal gates
- **Transversality:** logic operations = bitwise physical operations (local operations)
$$H^{\otimes n}=H_1\otimes H_2\otimes...\otimes H_n$$
if one $H_i$ is wrong, only effect one qubit $\Rightarrow$ Fault Tolerant