{ "cells": [ { "cell_type": "markdown", "id": "78d88306", "metadata": {}, "source": [ "---\n", "title: Classical repetition codes\n", "description: A free IBM course on quantum information and computation\n", "---\n", "\n", "{/* cspell:ignore mapsto */}\n", "\n", "# Repetition codes\n", "\n", "We'll begin the lesson with a discussion of *repetition codes.*\n", "Repetition codes don't protect quantum information against every type of error that can occur on qubits, but they do form the basis for the 9-qubit Shor code, which we'll see in the next lesson, and they're also useful for explaining the basics of error correction.\n", "\n", "## Classical encoding and decoding\n", "\n", "Repetition codes are extremely basic examples of error correcting codes.\n", "The idea is that we can protect bits against errors by simply repeating each bit some fixed number of times.\n", "\n", "In particular, let's first consider the 3-bit repetition code, just in the context of classical information to start.\n", "This code encodes one bit into three by repeating the bit three times, so $0$ is encoded as $000$ and $1$ is encoded as $111.$\n", "\n", "$$\n", "\\begin{aligned}\n", "0 & \\mapsto 000\\\\\n", "1 & \\mapsto 111\n", "\\end{aligned}\n", "$$\n", "\n", "If nothing goes wrong, we can obviously distinguish the two possibilities for the original bit from their encodings.\n", "The point is that if there was an error and one of the three bits flipped, meaning that a 0 changes into a 1 or a 1 changes to a 0, then we can still figure out what the original bit was by determining which of the two binary values appears twice.\n", "Equivalently, we can *decode* by computing the majority value (that is, the binary value that appears most frequently).\n", "\n", "$$\n", "a b c \\mapsto \\operatorname{majority}(a,b,c)\n", "$$\n", "\n", "Of course, if 2 or 3 bits of the encoding flip, then the decoding won't work properly and the wrong bit will be recovered, but if at most 1 of the 3 bits flip, the decoding will be correct.\n", "This is a typical property of error correcting codes in general: they may allow for the correction of errors, but only if there aren't too many of them.\n", "\n", "### Noise reduction for the binary symmetric channel\n", "\n", "For an example of a situation in which the chances of making an error can be decreased using a repetition code,\n", "suppose that our goal is to communicate a single bit to a hypothetical receiver, and we're able to transmit bits through a so-called *binary symmetric channel*, which flips each bit sent through it independently with some probability $p.$\n", "That is, with probability $1-p,$ the receiver gets whatever bit was sent through the channel, but with probability $p,$ the bit-flips and the receiver gets the opposite bit value.\n", "\n", "So, if we choose not to use the 3-bit repetition code, and simply send whatever bit we have in mind through the channel, the receiver therefore receives the wrong bit with probability $p.$\n", "On the other hand, if we first encode the bit we want to send using the 3-bit repetition code, and then send each of the three bits of the encoding through the channel, then each one of them flips independently with probability $p.$\n", "The chances of a bit-flip are now greater because there are now three bits that might flip rather than one, but if at most one of the bits flips, then the receiver will decode correctly.\n", "An error therefore persists after decoding only if two or more of the bits flip during transmission.\n", "\n", "The probability that two bits flip during transmission is $3p^2(1-p),$ which is $p^2(1-p)$ for each of the three choices for the bit that doesn't flip, while the probability that all three bits flip is $p^3.$\n", "The total probability of two or three bit-flips is therefore\n", "\n", "$$\n", "3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.\n", "$$\n", "\n", "For values of $p$ smaller than one-half, this results in a decrease in the probability that the receiver ends up with the wrong bit.\n", "There will still be a chance of an error in this case, but the code *decreases* the likelihood.\n", "(For values of $p$ *greater* than one-half, on the other hand, the code actually *increases* the likelihood that the receiver gets the wrong bit.)\n", "\n", "![Error probability graph for the 3 bit repetition code for a binary symmetric channel](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/binary-symmetric-error.svg)\n", "\n", "{/* cspell:ignore mapsto */}\n", "\n", "## Encoding qubits\n", "\n", "The 3-bit repetition code is a classical error correcting code, but we can consider what happens if we try to use it to protect *qubits* against errors.\n", "As we'll see, it's not a very impressive quantum error correcting code, because it actually makes some errors more likely.\n", "It is, however, the first step toward the Shor code, and will serve us well from a pedagogical viewpoint.\n", "\n", "To be clear, when we refer to the 3-bit repetition code being used for qubits, we have in mind an encoding of a qubit where *standard basis states* are repeated three times, so that a single-qubit state vector is encoded as follows.\n", "\n", "$$\n", "\\alpha \\vert 0\\rangle + \\beta \\vert 1\\rangle \\mapsto \\alpha \\vert 000\\rangle + \\beta \\vert 111\\rangle\n", "$$\n", "\n", "This encoding is easily implemented by the following quantum circuit, which makes use of two initialized workspace qubits and two controlled-NOT gates.\n", "\n", "![Encoding circuit for the 3-bit repetition code](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/repetition-encoder.svg)\n", "\n", "Notice, in particular, that this encoding is not the same as repeating the quantum state three times, as in a given qubit state vector being encoded as $\\vert\\psi\\rangle \\mapsto \\vert\\psi\\rangle\\vert\\psi\\rangle\\vert\\psi\\rangle.$\n", "Such an encoding cannot be implemented for an unknown quantum state $\\vert\\psi\\rangle$ by the no cloning theorem.\n", "\n", "### Bit-flip errors\n", "\n", "Now suppose that an error takes place after the encoding has been performed.\n", "Specifically, let's suppose that an $X$ gate, or in other words a bit-flip, occurs on one of the qubits.\n", "For instance, if the middle qubit experiences a bit-flip, the state of the three qubits is transformed into this state:\n", "\n", "$$\n", "\\alpha \\vert 010\\rangle + \\beta \\vert 101\\rangle.\n", "$$\n", "\n", "Of course, this isn't the only sort of error that could occur — and it's also reasonable to question the assumption that an error takes the form of a perfect, unitary operation.\n", "We'll return to these issues in the last section of the lesson, and for now we can view an error of this form as being just one possible type of error (albeit a fundamentally important one).\n", "\n", "We can see clearly from the mathematical expression for the state above that the middle bit is the one that's different inside of each ket.\n", "But suppose that we had the three qubits in our possession and didn't know their state.\n", "If we suspected that a bit-flip may have occurred, one option to verify that a bit flipped would be to perform a standard basis measurement, which, in the case at hand, would cause us to see $010$ or $101$ with probabilities $\\vert\\alpha\\vert^2$ and $\\vert\\beta\\vert^2,$ respectively.\n", "In either case, our conclusion would be that the middle bit flipped — but, unfortunately, we would lose the original quantum state $\\alpha\\vert 0\\rangle + \\beta \\vert 1\\rangle.$\n", "This is the state we're trying to protect, so measuring in the standard basis is an unsatisfactory option.\n", "\n", "What we can do instead is to use the following quantum circuit, feeding the encoded state into the top three qubits.\n", "This circuit nondestructively measures the *parity* of the standard basis states of the top two qubits as well as the bottom two qubits of the three-qubit encoding.\n", "\n", "![Error detection circuit for the 3-bit repetition code](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/repetition-error-detection.svg)\n", "\n", "Under the assumption that at most one bit flipped, one can easily deduce from the measurement outcomes the location of the bit-flip (or the absence of one).\n", "In particular, as the following four circuit diagrams illustrate, the measurement outcome $00$ indicates that no bit-flip occurred, while the three other possibilities indicate which qubit experienced a bit-flip.\n", "\n", "![Error detection for the 3-bit repetition code (no errors)](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/repetition-decode-no-error.svg)\n", "\n", "![Error detection for the 3-bit repetition code (error on qubit 0)](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/repetition-decode-e0.svg)\n", "\n", "![Error detection for the 3-bit repetition code (error on qubit 1)](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/repetition-decode-e1.svg)\n", "\n", "![Error detection for the 3-bit repetition code (error on qubit 2)](https://quantum.cloud.ibm.com/learning/images/courses/foundations-of-quantum-error-correction/correcting-quantum-errors/repetition-decode-e2.svg)\n", "\n", "Crucially, the state of the top three qubits does not collapse in any of the cases, which allows us to correct a bit-flip error if one has occurred — by simply applying the same bit-flip again with an $X$ gate.\n", "The following table summarizes the states we obtain from at most one bit-flip, the measurement outcomes (which are called the *syndrome* in the context of error correction), and the correction needed to get back to the original encoding.\n", "\n", "| State | Syndrome | Correction |\n", "| :-----------------------------------------------: | :------: | :--------------------------------------------: |\n", "| $\\alpha\\vert 000\\rangle + \\beta \\vert 111\\rangle$ | $00$ | $\\mathbb{I}\\otimes\\mathbb{I}\\otimes\\mathbb{I}$ |\n", "| $\\alpha\\vert 001\\rangle + \\beta \\vert 110\\rangle$ | $01$ | $\\mathbb{I}\\otimes\\mathbb{I}\\otimes X$ |\n", "| $\\alpha\\vert 010\\rangle + \\beta \\vert 101\\rangle$ | $11$ | $\\mathbb{I}\\otimes X\\otimes\\mathbb{I}$ |\n", "| $\\alpha\\vert 100\\rangle + \\beta \\vert 011\\rangle$ | $10$ | $X\\otimes\\mathbb{I}\\otimes\\mathbb{I}$ |\n", "\n", "Once again, we're only considering the possibility that at most one bit-flip occurred.\n", "This wouldn't work correctly if two or three bit-flips occurred, and we also haven't considered other possible errors besides bit-flips.\n", "\n", "### Phase-flip errors\n", "\n", "In the quantum setting, bit-flip errors aren't the only errors we need to worry about.\n", "For instance, we also have to worry about *phase-flip errors*, which are described by $Z$ gates.\n", "Along the same lines as bit-flip errors, we can think about phase-flip errors as representing just another possibility for an error that can affect a qubit.\n", "\n", "However, as we will see in the last section of the lesson, which is on the so-called *discretization of errors* for quantum error correcting codes, a focus on bit-flip errors and phase-flip errors turns out to be well-justified.\n", "Specifically, the ability to correct a bit-flip error, a phase-flip error, or both of these errors simultaneously automatically implies the ability to correct an arbitrary quantum error on a single qubit.\n", "\n", "Unfortunately, the 3-bit repetition code doesn't protect against phase-flips at all.\n", "For instance, suppose that a qubit state $\\alpha\\vert 0\\rangle + \\beta\\vert 1\\rangle$ has been encoded using the 3-bit repetition code, and a phase-flip error occurs on the middle qubit.\n", "This results in the state\n", "\n", "$$\n", "(\\mathbb{I} \\otimes Z \\otimes \\mathbb{I}) ( \\alpha \\vert 000\\rangle + \\beta \\vert 111\\rangle)\n", "= \\alpha \\vert 000\\rangle - \\beta \\vert 111\\rangle,\n", "$$\n", "\n", "which is exactly the state we would have obtained from encoding the qubit state $\\alpha\\vert 0\\rangle - \\beta\\vert 1\\rangle.$\n", "Indeed, a phase-flip error on any one of the three qubits of the encoding has this same effect, which is equivalent to a phase-flip error occurring on the original qubit prior to encoding.\n", "Under the assumption that the original quantum state is an unknown state, there's therefore no way to detect that an error has occurred, because the resulting state is a perfectly valid encoding of a different qubit state.\n", "In particular, running the error detection circuit from before on the state $\\alpha \\vert 000\\rangle - \\beta \\vert 111\\rangle$ is certain to result in the syndrome $00,$ which wrongly suggests that no errors have occurred.\n", "\n", "Meanwhile, there are now three qubits rather than one that could potentially experience phase-flip errors.\n", "So, in a situation in which phase-flip errors are assumed to occur independently on each qubit with some nonzero probability $p$ (similar to a binary symmetric channel except for phase-flips rather than bit-flips), this code actually increases the likelihood of a phase-flip error after decoding for small values of $p.$\n", "To be more precise, we'll get a phase-flip error on the original qubit after decoding whenever there are an odd number of phase-flip errors on the three qubits of the encoding, which happens with probability\n", "\n", "$$\n", "3 p (1 - p)^2 + p^3.\n", "$$\n", "\n", "This value is larger than $p$ when $0