summaryrefslogtreecommitdiff
path: root/source/know/concept/repetition-code/index.md
blob: fa039a34f7a2094c8a9a8e5aab90fb996ce4f2e0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
---
title: "Repetition code"
sort_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/):

{% include image.html file="bit-flip-encode.png" width="32%"
    alt="Bit flip code encoder" %}

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:

{% include image.html file="bit-flip-detect.png" width="62%"
    alt="Bit flip code decoder" %}

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}$$

{% include image.html file="phase-flip-encode.png" width="40%"
    alt="Phase flip code encoder" %}

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:

{% include image.html file="phase-flip-detect.png" width="70%"
    alt="Phase flip code decoder" %}

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:

{% include image.html file="shor-code-encode.png" width="55%"
    alt="Shor code 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.