From 6ce0bb9a8f9fd7d169cbb414a9537d68c5290aae Mon Sep 17 00:00:00 2001 From: Prefetch Date: Fri, 14 Oct 2022 23:25:28 +0200 Subject: Initial commit after migration from Hugo --- .../concept/repetition-code/bit-flip-detect.png | Bin 0 -> 8481 bytes .../concept/repetition-code/bit-flip-encode.png | Bin 0 -> 4453 bytes source/know/concept/repetition-code/index.md | 343 +++++++++++++++++++++ .../concept/repetition-code/phase-flip-detect.png | Bin 0 -> 12371 bytes .../concept/repetition-code/phase-flip-encode.png | Bin 0 -> 6112 bytes .../concept/repetition-code/shor-code-encode.png | Bin 0 -> 15043 bytes 6 files changed, 343 insertions(+) create mode 100644 source/know/concept/repetition-code/bit-flip-detect.png create mode 100644 source/know/concept/repetition-code/bit-flip-encode.png create mode 100644 source/know/concept/repetition-code/index.md create mode 100644 source/know/concept/repetition-code/phase-flip-detect.png create mode 100644 source/know/concept/repetition-code/phase-flip-encode.png create mode 100644 source/know/concept/repetition-code/shor-code-encode.png (limited to 'source/know/concept/repetition-code') diff --git a/source/know/concept/repetition-code/bit-flip-detect.png b/source/know/concept/repetition-code/bit-flip-detect.png new file mode 100644 index 0000000..4928dc1 Binary files /dev/null and b/source/know/concept/repetition-code/bit-flip-detect.png differ diff --git a/source/know/concept/repetition-code/bit-flip-encode.png b/source/know/concept/repetition-code/bit-flip-encode.png new file mode 100644 index 0000000..e1afe96 Binary files /dev/null and b/source/know/concept/repetition-code/bit-flip-encode.png differ diff --git a/source/know/concept/repetition-code/index.md b/source/know/concept/repetition-code/index.md new file mode 100644 index 0000000..0e992c4 --- /dev/null +++ b/source/know/concept/repetition-code/index.md @@ -0,0 +1,343 @@ +--- +title: "Repetition code" +date: 2021-05-07 +categories: +- Quantum information +layout: "concept" +--- + +A **repetition code** is a simple approach to error correction: +to protect a bit $x$, make two copies: + +$$\begin{aligned} + 0 \to 000 + \qquad \quad + 1 \to 111 +\end{aligned}$$ + +If a single-bit error occurs, e.g. $000 \to 100$, +a majority vote resets the minority bit. +Clearly, this does not protect against multi-bit errors, +but that is usually not necessary. + +In quantum computing, where error correction is much more important, +repetition codes can also be used, +albeit with some complications, +as discussed below. + + +## Bit flip code + +Suppose that we want to detect errors in +the following arbitrary qubit state $\Ket{\psi}$: + +$$\begin{aligned} + \Ket{\psi} + = \alpha \Ket{0} + \beta \Ket{1} +\end{aligned}$$ + +For now, let us limit ourselves to detecting **bit flips**, +where $\alpha$ and $\beta$ get switched: + +$$\begin{aligned} + \alpha \Ket{0} + \beta \Ket{1} + \quad \to \boxed{\mathrm{Error}} \to \quad + \beta \Ket{0} \!+\! \alpha \Ket{1} +\end{aligned}$$ + +One way to defend against this is +the quantum version of a classical repetition code: + +$$\begin{aligned} + \Ket{\psi} + \quad \to \boxed{\mathrm{Encoder}} \to \quad + \ket{\overline{\psi}} + = \alpha \Ket{000} + \beta \Ket{111} +\end{aligned}$$ + +In other words, a *logical* $\Ket{0}$ (written $\ket{\overline{0}}$) +is represented by 3 *physical* qubits, and vice versa: + +$$\begin{aligned} + \boxed{ + \Ket{0} + \to + \ket{\overline{0}} + = \Ket{000} + \qquad \quad + \Ket{1} + \to + \ket{\overline{1}} + = \Ket{111} + } +\end{aligned}$$ + +Such a transformation is easy to achieve with the following sequence +of [quantum gates](/know/concept/quantum-gate/): + + + + + +So, a little while after encoding the state $\Ket{\psi}$ like that, +a bit flip occurs on the 2nd qubit: + +$$\begin{aligned} + \ket{\overline{\psi}} + \quad \to \boxed{\mathrm{Error}} \to \quad + \alpha \Ket{010} + \beta \Ket{101} +\end{aligned}$$ + +But now there is a problem: how do we detect this error? +We could measure the state, but that would make it collapse, +which is probably not what we want. + +The trick is to use operators called **stabilizers**, +in this case for example $ZZI = Z_1 \otimes Z_2 \otimes I_3$, +where $I$ is identity and $Z$ is the Pauli-$Z$ gate. +The 3-qubit basis states are its eigenvectors: + +$$\begin{alignedat}{2} + ZZI \Ket{000} + &= + \Ket{000} + \qquad + ZZI \Ket{001} + &&= + \Ket{001} + \\ + ZZI \Ket{010} + &= - \Ket{010} + \qquad + ZZI \Ket{011} + &&= - \Ket{011} + \\ + ZZI \Ket{100} + &= - \Ket{100} + \qquad + ZZI \Ket{101} + &&= - \Ket{101} + \\ + ZZI \Ket{110} + &= + \Ket{110} + \qquad + ZZI \Ket{111} + &&= + \Ket{111} +\end{alignedat}$$ + +We could measure $ZZI$ for $\ket{\overline{\psi}}$, +and if the eigenvalue is $-1$, +we know that a bit flip has occurred, +whereas if the eigenvalue is $+1$, +there is *maybe* no error ($\Ket{001}$ and $\Ket{110}$ are false negatives). + +These false negatives are fixed by including another stabilizer $IZZ$, +with these eigenvectors: + +$$\begin{alignedat}{2} + IZZ \Ket{000} + &= + \Ket{000} + \qquad + IZZ \Ket{001} + &&= - \Ket{001} + \\ + IZZ \Ket{010} + &= - \Ket{010} + \qquad + IZZ \Ket{011} + &&= + \Ket{011} + \\ + IZZ \Ket{100} + &= + \Ket{100} + \qquad + IZZ \Ket{101} + &&= - \Ket{101} + \\ + IZZ \Ket{110} + &= - \Ket{110} + \qquad + IZZ \Ket{111} + &&= + \Ket{111} +\end{alignedat}$$ + +In which case $\Ket{100}$ and $\Ket{011}$ are false negatives. +In other words, $IZZ$ cannot detect if the 1st qubit was flipped, +while $ZZI$ cannot protect the 3rd qubit. +But by using both, we know exactly which qubit was flipped +thanks to the eigenvalues: + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Error$ZZI$$IZZ$
$I$$+1$$+1$
$X_1$$-1$$+1$
$X_2$$-1$$-1$
$X_1$$+1$$-1$
+ +Where e.g. $X_3$ denotes that the 3rd qubit was flipped. +The measurement outcomes on the last three rows are called **error syndromes**, +and are obtained by a **syndrome measurement**. + +Fortunately, we can measure $ZZI$ and $IZZ$ +without affecting $\ket{\overline{\psi}}$ itself, +by applying $\mathrm{CNOT}$s to some ancillary qubits +and then measuring those: + + + + + +The two measurements, respectively representing $ZZI$ and $IZZ$, +yield $\Ket{1}$ if a bit flip definitely occurred, +and $\Ket{0}$ otherwise. +There is no entanglement, +so the input is untouched. + + +## Phase flip code + +The above system protects us against all single-qubit bit flips. +Unfortunately, that is not enough: +qubits can also experience a **phase flip**: + +$$\begin{aligned} + \alpha \Ket{0} + \beta \Ket{1} + \quad \to \boxed{\mathrm{Error}} \to \quad + \alpha \Ket{0} - \beta \Ket{1} +\end{aligned}$$ + +How to detect that? +If we want to protect against phase flips *instead of* bit flips, +we can simply do the same as before, +but along the $X$-axis intead of the $Z$-axis: + +$$\begin{aligned} + \boxed{ + \Ket{0} + \to + \ket{\overline{0}} + = \Ket{+\!+\!+} + \qquad \quad + \Ket{1} + \to + \ket{\overline{1}} + = \Ket{-\!-\!-} + } +\end{aligned}$$ + +Such that an arbitrary state $\Ket{\psi}$ is encoded as follows, +by the circuit shown below: + +$$\begin{aligned} + \Ket{\psi} + \quad \to \boxed{\mathrm{Encoder}} \to \quad + \ket{\overline{\psi}} + = \alpha \Ket{+\!+\!+} + \beta \Ket{-\!-\!-} +\end{aligned}$$ + + + + + +A phase flip along the $Z$-axis +corresponds to a bit flip along the $X$-axis $\Ket{+} \to \Ket{-}$. +In this case, the stabilizers are $XXI$ and $IXX$, +and the error detection circuit is as follows: + + + + + +This system protects us against all single-qubit phase flips, +but not against bit flips. + + +## Shor code + +What kind of repetition code would we need +if we want to detect both bit flips *and* phase flips? +The most straightforward option is the **Shor code**. +Starting from a phase flip encoding: + +$$\begin{aligned} + \Ket{0} \to + \ket{\overline{0}} + &= \Ket{+\!+\!+} + = \bigg( \frac{\Ket{0} + \Ket{1}}{\sqrt{2}} \bigg)^{\otimes 3} + \\ + \Ket{1} \to + \ket{\overline{1}} + &= \Ket{-\!-\!-} + = \bigg( \frac{\Ket{0} - \Ket{1}}{\sqrt{2}} \bigg)^{\otimes 3} +\end{aligned}$$ + +We add protection against bit flips +by using a repetition code for each physical qubit: + +$$\begin{aligned} + \boxed{ + \ket{\overline{0}} + = \bigg( \frac{\Ket{000} + \Ket{111}}{\sqrt{2}} \bigg)^{\otimes 3} + \qquad \quad + \ket{\overline{1}} + = \bigg( \frac{\Ket{000} - \Ket{111}}{\sqrt{2}} \bigg)^{\otimes 3} + } +\end{aligned}$$ + +This encoding is achieved by the following quantum circuit, +which simply consists of the phase flip encoder, +followed by 3 copies of the bit flip encoder: + + + + + +We thus use 9 physical qubits to store 1 logical qubit. +Fortunately, more efficient schemes exist. + +The bit flip stabilizers $ZZI$ and $IZZ$ +are applied on a per-block basis, like so: + +$$\begin{aligned} + ZZI \: III \: III \qquad\quad III \: ZZI \: III \qquad\quad III \: III \: ZZI + \\ + IZZ \: III \: III \qquad\quad III \: IZZ \: III \qquad\quad III \: III \: IZZ +\end{aligned}$$ + +Whereas the phase flip stabilizers $XXI$ and $IXX$ +are applied to entire blocks at once: + +$$\begin{aligned} + XXX \: XXX \: III + \qquad \quad + III \: XXX \: XXX +\end{aligned}$$ + + + +## References +1. J.S. Neergaard-Nielsen, + *Quantum information: lectures notes*, + 2021, unpublished. +2. S. Aaronson, + *Introduction to quantum information science: lecture notes*, + 2018, unpublished. + diff --git a/source/know/concept/repetition-code/phase-flip-detect.png b/source/know/concept/repetition-code/phase-flip-detect.png new file mode 100644 index 0000000..f43e706 Binary files /dev/null and b/source/know/concept/repetition-code/phase-flip-detect.png differ diff --git a/source/know/concept/repetition-code/phase-flip-encode.png b/source/know/concept/repetition-code/phase-flip-encode.png new file mode 100644 index 0000000..0a4f04c Binary files /dev/null and b/source/know/concept/repetition-code/phase-flip-encode.png differ diff --git a/source/know/concept/repetition-code/shor-code-encode.png b/source/know/concept/repetition-code/shor-code-encode.png new file mode 100644 index 0000000..d112f9b Binary files /dev/null and b/source/know/concept/repetition-code/shor-code-encode.png differ -- cgit v1.2.3