{ "cells": [ { "cell_type": "markdown", "id": "bd74fbe8", "metadata": {}, "source": [ "---\n", "title: CSS codes\n", "description: A free IBM course on quantum information and computation\n", "---\n", "\n", "{/* cspell:ignore subseteq */}\n", "\n", "{/* cspell:ignore mapsto */}\n", "\n", "# CSS Codes\n", "\n", "## Classical linear codes\n", "\n", "Classical error correcting codes were first studied in the 1940s, and many different codes are now known, with the most commonly studied and used codes falling into a category of codes known as *linear codes.*\n", "We'll see exactly what the word \"linear\" means in this context in just a moment, but a very simple way to express what linear codes are at this point is that they're stabilizer codes that happen to be classical.\n", "CSS codes are essentially *pairs* of classical linear codes that are combined together to create a quantum error correcting code.\n", "So, for the sake of the discussion that follows, we're going to need to understand a few basic things about classical linear codes.\n", "\n", "Let $\\Sigma$ be the binary alphabet for this entire discussion.\n", "When we refer to a *classical linear code*, we mean a non-empty set $\\mathcal{C}\\subseteq\\Sigma^n$ of binary strings of length $n,$ for some positive integer $n,$ which must satisfy just one basic property:\n", "if $u$ and $v$ are binary strings in $\\mathcal{C},$ then the string $u\\oplus v$ is also in $\\mathcal{C}.$\n", "Here, $u\\oplus v$ refers to the bitwise exclusive-OR of $u$ and $v,$ as we encountered multiple times in the\n", "\"Fundamentals of quantum algorithms\" course.\n", "\n", "In essence, when we refer to a classical error correcting code as being *linear,* we're thinking about binary strings of length $n$ as being $n$-dimensional vectors, where the entries are all either $0$ or $1,$ and demanding that the code itself forms a linear subspace.\n", "Instead of ordinary vector addition over the real or complex numbers, however, we're using addition modulo $2,$ which is simply the exclusive-OR.\n", "That is, if we have two *codewords* $u$ and $v,$ meaning that $u$ and $v$ are binary strings in $\\mathcal{C},$ then $u + v$ modulo 2, which is to say $u\\oplus v,$ must also be a codeword in $\\mathcal{C}.$\n", "Notice, in particular, that this implication must be true even if $u = v.$\n", "This implies that $\\mathcal{C}$ must include the all-zero string $0^n,$ because the bitwise exclusive-OR of any string with itself is the all-zero string.\n", "\n", "### Example: the 3-bit repetition code\n", "\n", "The 3-bit repetition code is an example of a classical linear code.\n", "In particular, we have $\\mathcal{C} = \\{000,111\\},$ so, with respect to the linearity condition, there are just two possible choices for $u$ and two possible choices for $v.$\n", "It's a trivial matter to go through the four possible pairs to see that we always get a codeword when we take the bitwise exclusive-OR:\n", "\n", "$$\n", "000 \\oplus 000 = 000, \\quad\n", "000 \\oplus 111 = 111, \\quad\n", "111 \\oplus 000 = 111, \\quad\n", "111 \\oplus 111 = 000.\n", "$$\n", "\n", "### Example: the $[7,4,3]$-Hamming code\n", "\n", "Here's another example of a classical linear code called the $[7,4,3]$-Hamming code.\n", "It was one of the very first classical error correcting codes ever discovered, and it consists of these 16 binary strings of length 7.\n", "(Sometimes the $[7,4,3]$-Hamming code is understood to mean the code with these strings reversed, but we'll take it to be the code containing the strings shown here.)\n", "\n", "$$\n", "\\begin{array}{cccc}\n", "0000000 & 1100001 & 1010010 & 0110011\\\\[1mm]\n", "0110100 & 1010101 & 1100110 & 0000111\\\\[1mm]\n", "1111000 & 0011001 & 0101010 & 1001011\\\\[1mm]\n", "1001100 & 0101101 & 0011110 & 1111111\n", "\\end{array}\n", "$$\n", "\n", "There is very simple logic behind the selection of these strings, but it's secondary to the lesson and won't be explained here.\n", "For now, it's enough to observe that this is a classical linear code: XORing any two of these strings together will always result in another string in the code.\n", "\n", "The notation $[7,4,3]$ (in single square brackets) means something analogous to the double square bracket notation for stabilizer codes mentioned in the previous lesson, but here it's for classical linear codes.\n", "In particular, codewords have $7$ bits, we can encode $4$ bits using the code (because there are $16 = 2^4$ codewords), and it happens to be a distance $3$ code, which means that any two distinct codewords must differ in at least $3$ positions — so at least $3$ bits must be flipped to change one codeword into another.\n", "The fact that this is a distance $3$ code implies that it can correct for up to one bit-flip error.\n", "\n", "### Describing classical linear codes\n", "\n", "The examples just mentioned are very simple examples of classical linear codes, but even the $[7,4,3]$-Hamming code looks somewhat mysterious when the codewords are simply listed.\n", "There are better, more efficient ways to describe classical linear codes, including the following two ways.\n", "\n", "1. *Generators*. One way to describe a classical linear code is with a minimal list of codewords that *generates* the code, meaning that by taking all of the possible subsets of these codewords and XORing them together, we get the entire code.\n", "\n", " In greater detail, the strings $u_1,\\ldots,u_m\\in\\Sigma^n$ generate the classical linear code $\\mathcal{C}$ if\n", "\n", " $$\n", " \\mathcal{C} = \\bigl\\{\\alpha_1 u_1 \\oplus \\cdots \\oplus \\alpha_m u_m\\,:\\,\\alpha_1,\\ldots,\\alpha_m\\in\\{0,1\\}\\bigr\\},\n", " $$\n", "\n", " with the understanding that $\\alpha u = u$ when $\\alpha = 1$ and $\\alpha u = 0^n$ when $\\alpha = 0,$\n", " and we say that this list is *minimal* if removing one of the strings generates a smaller code.\n", " A natural way to think about such a description is that the collection $\\{u_1,\\ldots,u_m\\}$ forms a *basis* for $\\mathcal{C}$ as a subspace, where we're thinking about strings as vectors with binary-valued entries, keeping in mind that we're working in a vector space where arithmetic is done modulo $2.$\n", "\n", "2. *Parity checks*.\n", " Another natural way to describe a classical linear code is by *parity checks* — meaning a minimal list of binary strings for which the strings in the code are precisely the ones whose *binary dot product* with every one of these parity check strings is zero. (Similar to the bitwise exclusive-OR, the binary dot product appeared several times in \"Fundamentals of quantum algorithms.\")\n", "\n", " That is, the strings $v_1,\\ldots,v_r\\in\\Sigma^n$ are parity check strings for the classical linear code $\\mathcal{C}$ if\n", "\n", " $$\n", " \\mathcal{C} = \\bigl\\{ u\\in \\Sigma^n\\,:\\, u\\cdot v_1 = \\cdots = u \\cdot v_r = 0 \\bigr\\},\n", " $$\n", "\n", " and this set of strings is *minimal* if removing one results in a larger code.\n", " These are called parity check strings because $u$ has binary dot product equal to zero with $v$ if and only if the bits of $u$ in positions where $v$ has 1s have even parity.\n", " So, to determine if a string $u$ is in the code $\\mathcal{C},$ it suffices to check the parity of certain subsets of the bits of $u.$\n", "\n", " An important thing to notice here is that the binary dot product is not an inner product in a formal sense. In particular, when two strings have binary dot product equal to zero, it doesn't mean that they're orthogonal in the usual way we think about orthogonality. For example, the binary dot product of the string $11$ with itself is zero — so it is possible that a parity check string for a classical linear code is itself in the code.\n", "\n", "Classical linear codes over the binary alphabet always include a number of strings that's a power of $2$ — and for a single classical linear code described in the two different ways just described, it will always be the case that $n = m + r.$\n", "In particular, if we have a minimal set of $m$ generators, then the code encodes $m$ bits and we'll necessarily have $2^m$ codewords;\n", "and if we have a minimal set of $r$ parity check strings, then we'll have $2^{n-r}$ codewords.\n", "So, each generator doubles the size of the code space while each parity check string halves the size of the code space.\n", "\n", "For example, the 3-bit repetition code is a linear code, so it can be described in both of these ways.\n", "In particular, there's only one choice for a generator that works: $111.$\n", "We can alternatively describe the code with two parity check strings, such as $110$ and $011$ — which should look familiar from our previous discussions of this code — or we could instead take the parity check strings to be $110$ and $101,$ or $101$ and $011.$ (Generators and parity check strings are generally not unique for a given classical linear code.)\n", "\n", "For a second example, consider the $[7,4,3]$-Hamming code.\n", "Here's one choice for a list of generators that works.\n", "\n", "$$\n", "\\begin{array}{c}\n", "1111000\\\\[1mm]\n", "0110100\\\\[1mm]\n", "1010010\\\\[1mm]\n", "1100001\n", "\\end{array}\n", "$$\n", "\n", "And here's a choice for a list of parity checks for this code.\n", "\n", "$$\n", "\\begin{array}{c}\n", "1111000\\\\[1mm]\n", "1100110\\\\[1mm]\n", "1010101\n", "\\end{array}\n", "$$\n", "\n", "Here, by the way, we see that *all* of our parity check strings are themselves in the code.\n", "\n", "One final remark about classical linear codes, which connects them to the stabilizer formalism, is that parity check strings are equivalent to stabilizer generators that only consist of $Z$ and identity Pauli matrices.\n", "For instance, the parity check strings $110$ and $011$ for the 3-bit repetition code correspond precisely to the stabilizer generators $Z\\otimes Z\\otimes \\mathbb{I}$ and $\\mathbb{I}\\otimes Z\\otimes Z,$ which is consistent with the discussions of Pauli observables from the previous lesson.\n", "\n", "## Definition of CSS codes\n", "\n", "CSS codes are stabilizer codes obtained by combining together certain *pairs* of classical linear codes.\n", "This doesn't work for two arbitrary classical linear codes — the two codes must have a certain relationship.\n", "Nevertheless, this construction opens up many possibilities for quantum error correcting codes, based in part on over 75 years of classical coding theory.\n", "\n", "In the stabilizer formalism, stabilizer generators containing only $Z$ and identity Pauli matrices are equivalent to parity checks, as we just observed for the 3-bit repetition code.\n", "For another example, consider the following parity check strings for the $[7,4,3]$-Hamming code.\n", "\n", "$$\n", "\\begin{array}{c}\n", "1111000\\\\[1mm]\n", "1100110\\\\[1mm]\n", "1010101\n", "\\end{array}\n", "$$\n", "\n", "These parity check strings correspond to the following stabilizer generators (written without tensor product symbols), which we obtain by replacing each $1$ by a $Z$ and each $0$ by an $\\mathbb{I}.$\n", "These are three of the six stabilizer generators for the 7-qubit Steane code.\n", "\n", "$$\n", "\\begin{array}{ccccccc}\n", "Z & Z & Z & Z & \\mathbb{I} & \\mathbb{I} & \\mathbb{I} \\\\[1mm]\n", "Z & Z & \\mathbb{I} & \\mathbb{I} & Z & Z & \\mathbb{I} \\\\[1mm]\n", "Z & \\mathbb{I} & Z & \\mathbb{I} & Z & \\mathbb{I} & Z\n", "\\end{array}\n", "$$\n", "\n", "Let us give the name *$Z$ stabilizer generators* to stabilizer generators like this, meaning that they only have Pauli $Z$ and identity tensor factors — so $X$ and $Y$ Pauli matrices never occur in $Z$ stabilizer generators.\n", "\n", "We can also consider stabilizer generators where only $X$ and identity Pauli matrices appear as tensor factors.\n", "Stabilizer generators like this can be viewed as being analogous to $Z$-stabilizer generators, except that they describe parity checks in the $\\{\\vert+\\rangle,\\vert-\\rangle\\}$ basis rather than the standard basis.\n", "Stabilizer generators of this form are called *$X$ stabilizer generators* — so no $Y$ or $Z$ Pauli matrices are allowed this time.\n", "\n", "For example, consider the remaining three stabilizer generators from the 7-qubit Steane code.\n", "\n", "$$\n", "\\begin{array}{ccccccc}\n", "X & X & X & X & \\mathbb{I} & \\mathbb{I} & \\mathbb{I} \\\\[1mm]\n", "X & X & \\mathbb{I} & \\mathbb{I} & X & X & \\mathbb{I} \\\\[1mm]\n", "X & \\mathbb{I} & X & \\mathbb{I} & X & \\mathbb{I} & X\n", "\\end{array}\n", "$$\n", "\n", "They follow exactly the same pattern from the $[7,4,3]$-Hamming code as the $Z$-stabilizer generators, except this time we substitute $X$ for $1$ rather than $Z.$\n", "What we obtain from just these three stabilizer generators is a code that includes the 16 states shown here, which we get by applying Hadamard operations to the standard basis states that correspond to the strings in the $[7,4,3]$-Hamming code.\n", "(Of course, the code space for this code also includes linear combinations of these states.)\n", "\n", "$$\n", "\\begin{array}{cccc}\n", " \\vert {+++++++} \\rangle \\quad & \\vert {--++++-} \\rangle \\quad & \\vert {-+-++-+} \\rangle \\quad & \\vert {+--++--} \\rangle \\\\\n", " \\vert {+--+-++} \\rangle \\quad & \\vert {-+-+-+-} \\rangle \\quad & \\vert {--++--+} \\rangle \\quad & \\vert {++++---} \\rangle \\\\\n", " \\vert {----+++} \\rangle \\quad & \\vert {++--++-} \\rangle \\quad & \\vert {+-+-+-+} \\rangle \\quad & \\vert {-++-+--} \\rangle \\\\\n", " \\vert {-++--++} \\rangle \\quad & \\vert {+-+--+-} \\rangle \\quad & \\vert {++----+} \\rangle \\quad & \\vert {-------} \\rangle\n", "\\end{array}\n", "$$\n", "\n", "We can now define CSS codes in very simple terms.\n", "\n", "
\n", " A CSS code is a stabilizer code that can be expressed using only $X$ and $Z$ stabilizer generators.\n", "
\n", "\n", "That is, CSS codes are stabilizer codes for which we have stabilizer generators in which no Pauli $Y$ matrices appear, and for which $X$ and $Z$ never appear in the *same* stabilizer generator.\n", "\n", "To be clear, by this definition, a CSS code is one for which it is *possible* to choose just $X$ and $Z$ stabilizer generators — but we must keep in mind that there is freedom in how we choose stabilizer generators for stabilizer codes.\n", "Thus, there will generally be different choices for the stabilizer generators of a CSS code that don't happen to be $X$ or $Z$ stabilizer generators (in addition to at least one choice for which they are).\n", "\n", "Here's a very simple example of a CSS code that includes both a $Z$ stabilizer generator and an $X$ stabilizer generator:\n", "\n", "$$\n", "\\begin{array}{cc}\n", "Z & Z \\\\[1mm]\n", "X & X\n", "\\end{array}\n", "$$\n", "\n", "It's clear that this is a CSS code, because the first stabilizer generator is a $Z$ stabilizer generator and the second is an $X$ stabilizer generator.\n", "Of course, a CSS code must also be a valid stabilizer code — meaning that the stabilizer generators must commute, form a minimal generating set, and fix at least one quantum state vector.\n", "These requirements happen to be simple to observe for this code.\n", "As we noted in the previous lesson, the code space for this code is the one-dimensional space spanned by the $\\vert\\phi^+\\rangle$ Bell state.\n", "The fact that both stabilizer generators fix this state is apparent by considering the following two expressions of an e-bit, together with an interpretation of these stabilizer generators as parity checks in the $\\{\\vert 0\\rangle, \\vert 1\\rangle\\}$ and\n", "$\\{\\vert +\\rangle, \\vert -\\rangle\\}$ bases.\n", "\n", "$$\n", "\\vert\\phi^+\\rangle\n", "= \\frac{\\vert 0\\rangle\\vert 0\\rangle + \\vert 1\\rangle\\vert 1\\rangle}{\\sqrt{2}}\n", "= \\frac{\\vert +\\rangle\\vert +\\rangle + \\vert -\\rangle\\vert -\\rangle}{\\sqrt{2}}\n", "$$\n", "\n", "The 7-qubit Steane code is another example of a CSS code.\n", "\n", "$$\n", "\\begin{array}{ccccccc}\n", "Z & Z & Z & Z & \\mathbb{I} & \\mathbb{I} & \\mathbb{I} \\\\[1mm]\n", "Z & Z & \\mathbb{I} & \\mathbb{I} & Z & Z & \\mathbb{I} \\\\[1mm]\n", "Z & \\mathbb{I} & Z & \\mathbb{I} & Z & \\mathbb{I} & Z \\\\[1mm]\n", "X & X & X & X & \\mathbb{I} & \\mathbb{I} & \\mathbb{I} \\\\[1mm]\n", "X & X & \\mathbb{I} & \\mathbb{I} & X & X & \\mathbb{I} \\\\[1mm]\n", "X & \\mathbb{I} & X & \\mathbb{I} & X & \\mathbb{I} & X\n", "\\end{array}\n", "$$\n", "\n", "Here we have three $Z$ stabilizer generators and three $X$ stabilizer generators, and we've already verified that this is a valid stabilizer code.\n", "\n", "And the 9-qubit Shor code is another example.\n", "\n", "$$\n", "\\begin{array}{ccccccccc}\n", "Z & Z & \\mathbb{I} &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I}\\\\[1mm]\n", "\\mathbb{I} & Z & Z &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I}\\\\[1mm]\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "Z & Z & \\mathbb{I} &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I}\\\\[1mm]\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "\\mathbb{I} & Z & Z &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I}\\\\[1mm]\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "Z & Z & \\mathbb{I}\\\\[1mm]\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I} &\n", "\\mathbb{I} & Z & Z\\\\[1mm]\n", "X & X & X & X & X & X &\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I}\\\\[1mm]\n", "\\mathbb{I} & \\mathbb{I} & \\mathbb{I}&\n", "X & X & X & X & X & X\n", "\\end{array}\n", "$$\n", "\n", "This time we have six $Z$ stabilizer generators and just two $X$ stabilizer generators.\n", "This is fine, there doesn't need to be a balance or a symmetry between the two types of generators (though there often is).\n", "\n", "Once again, it is critical that CSS codes are valid stabilizer codes, and in particular each $Z$ stabilizer generator must commute with each $X$ stabilizer generator.\n", "So, not every collection of $X$ and $Z$ stabilizer generators defines a valid CSS code.\n", "\n", "## Error detection and correction\n", "\n", "With regard to error detection and correction, CSS codes in general have a similar characteristic to the 9-qubit Shor code, which is that $X$ and $Z$ errors can be detected and corrected completely independently; the $Z$ stabilizer generators describe a code that protects against bit flips, and the $X$ stabilizer generators describe a code that independently protects against phase flips.\n", "This works because $Z$ stabilizer generators necessarily commute with $Z$ errors, as well as $Z$ operations that are applied as corrections, so they're completely oblivious to both, and likewise for $X$ stabilizer generators, errors, and corrections.\n", "\n", "As an example, let's consider the 7-qubit Steane code.\n", "\n", "$$\n", "\\begin{array}{ccccccc}\n", "Z & Z & Z & Z & \\mathbb{I} & \\mathbb{I} & \\mathbb{I} \\\\[1mm]\n", "Z & Z & \\mathbb{I} & \\mathbb{I} & Z & Z & \\mathbb{I} \\\\[1mm]\n", "Z & \\mathbb{I} & Z & \\mathbb{I} & Z & \\mathbb{I} & Z \\\\[1mm]\n", "X & X & X & X & \\mathbb{I} & \\mathbb{I} & \\mathbb{I} \\\\[1mm]\n", "X & X & \\mathbb{I} & \\mathbb{I} & X & X & \\mathbb{I} \\\\[1mm]\n", "X & \\mathbb{I} & X & \\mathbb{I} & X & \\mathbb{I} & X\n", "\\end{array}\n", "$$\n", "\n", "The basic idea for this code is now apparent: it's a $[7,4,3]$-Hamming code for bit-flip errors and a $[7,4,3]$-Hamming code for phase-flip errors.\n", "The fact that the $X$ and $Z$ stabilizer generators commute is perhaps good fortune, for this wouldn't be a valid stabilizer code if they didn't.\n", "But there are, in fact, many known examples of classical linear codes that yield a valid stabilizer code when used in a similar way.\n", "\n", "In general, suppose we have a CSS code for which the $Z$ stabilizer generators allow for the correction of up to $j$ bit-flip errors, and the $X$ stabilizer generators allow for the correction of up to $k$ phase-flip errors.\n", "For example, $j = 1$ and $k = 1$ for the Steane code, given that the $[7,4,3]$-Hamming code can correct one bit flip.\n", "It then follows, by the discretization of errors, that this CSS code can correct for *any error* on a number of qubits up to the *minimum* of $j$ and $k.$\n", "This is because, when the syndrome is measured, an arbitrary error on this number of qubits effectively collapses probabilistically into some combination of $X$ errors, $Z$ errors, or both — and then the $X$ errors and $Z$ errors are detected and corrected independently.\n", "\n", "In summary, provided that we have two classical linear codes (or two copies of a single classical linear code) that are compatible, in that they define $X$ and $Z$ stabilizer generators that commute, the CSS code we obtain by combining them inherits the error correction properties of those two codes, in the sense just described.\n", "\n", "Notice that there is a price to be paid though, which is that we can't *encode* as many qubits as we could bits with the two classical codes.\n", "This is because the total number of stabilizer generators for the CSS code is the *sum* of the number of parity checks for the two classical linear codes, and each stabilizer generator cuts the dimension of the code space in half.\n", "For example, the $[7,4,3]$-Hamming code allows for the encoding of four classical bits, because we have just three parity check strings for this code, whereas the 7-qubit Steane code only encodes one qubit, because it has six stabilizer generators.\n", "\n", "## Code spaces of CSS codes\n", "\n", "The last thing we'll do in this discussion of CSS codes is to consider the *code spaces* of these codes.\n", "This will give us an opportunity to examine in greater detail the relationship that must hold between two classical linear codes in order for them to be compatible, in the sense that they can be combined together to form a CSS code.\n", "\n", "Consider any CSS code on $n$ qubits, and let $z_1, \\ldots, z_s \\in \\Sigma^n$ be the $n$-bit parity check strings that correspond to the $Z$ stabilizer generators of this code.\n", "This means that the classical linear code described by just the $Z$ stabilizer generators, which we'll name $\\mathcal{C}_Z,$ takes the following form.\n", "\n", "$$\n", "\\mathcal{C}_Z = \\bigl\\{ u \\in \\Sigma^n \\,:\\, u \\cdot z_1 = \\cdots = u \\cdot z_s = 0 \\bigr\\}\n", "$$\n", "\n", "In words, the classical linear code $\\mathcal{C}_Z$ contains every string whose binary dot product with every one of the parity check strings $z_1, \\ldots, z_s$ is zero.\n", "\n", "Along similar lines, let us take $x_1,\\ldots,x_t\\in\\Sigma^n$ to be the $n$-bit parity check strings corresponding to the $X$ stabilizer generators of our code.\n", "Thus, the classical linear code corresponding to the $X$ stabilizer generators takes this form.\n", "\n", "$$\n", "\\mathcal{C}_X = \\bigl\\{ u \\in \\Sigma^n \\,:\\, u \\cdot x_1 = \\cdots = u \\cdot x_t = 0 \\bigr\\}\n", "$$\n", "\n", "The $X$ stabilizer generators alone therefore describe a code that's similar to this code, but in the\n", "$\\{\\vert {+}\\rangle,\\vert {-}\\rangle\\}$ basis rather than the standard basis.\n", "\n", "Now we'll introduce two new classical linear codes that are derived from the same choices of strings, $z_1,\\ldots,z_s$ and $x_1,\\ldots,x_t,$ but where we take these strings as *generators* rather than parity check strings.\n", "In particular, we obtain these two codes.\n", "\n", "$$\n", "\\begin{aligned}\n", "\\mathcal{D}_Z & =\n", "\\bigl\\{ \\alpha_1 z_1 \\oplus \\cdots \\oplus\n", "\\alpha_s z_s \\,:\\, \\alpha_1,\\ldots,\\alpha_s \\in \\{0,1\\}\n", "\\bigr\\}\\\\[1mm]\n", "\\mathcal{D}_X & =\n", "\\bigl\\{ \\alpha_1 x_1 \\oplus \\cdots \\oplus\n", "\\alpha_t x_t \\,:\\, \\alpha_1,\\ldots,\\alpha_t \\in \\{0,1\\}\n", "\\bigr\\}\n", "\\end{aligned}\n", "$$\n", "\n", "These are known as the *dual codes* of the codes defined previously:\n", "$\\mathcal{D}_Z$ is the dual code of $\\mathcal{C}_Z$ and $\\mathcal{D}_X$ is the dual code of $\\mathcal{C}_X.$\n", "It may not be clear at this point why these dual codes are relevant, but they turn out to be quite relevant for multiple reasons, including the two reasons explained in the following paragraphs.\n", "\n", "First, the conditions that must hold for two classical linear codes $\\mathcal{C}_Z$ and $\\mathcal{C}_X$ to be compatible, in the sense that they can be paired together to form a CSS code, can be described in simple terms by referring to the dual codes.\n", "Specifically, it must be that $\\mathcal{D}_Z\\subseteq\\mathcal{C}_X,$ or equivalently, that $\\mathcal{D}_X\\subseteq\\mathcal{C}_Z.$\n", "In words, the dual code $\\mathcal{D}_Z$ includes the strings corresponding to $Z$ stabilizer generators, and their containment in $\\mathcal{C}_X$ is equivalent to the binary dot product of each of these strings with the ones corresponding to the $X$ stabilizer generators being zero.\n", "That, in turn, is equivalent to each $Z$ stabilizer generator commuting with each $X$ stabilizer generator.\n", "Alternatively, by reversing the roles of the $X$ and $Z$ stabilizer generators and starting from the containment $\\mathcal{D}_X\\subseteq\\mathcal{C}_Z,$ we can reach the same conclusion.\n", "\n", "Second, by referring to the dual codes, we can easily describe the code spaces of a given CSS code.\n", "In particular, the code space is spanned by vectors of the following form.\n", "\n", "$$\n", "\\vert u \\oplus \\mathcal{D}_X\\rangle\n", "= \\frac{1}{\\sqrt{2^t}} \\sum_{v\\in\\mathcal{D}_X} \\vert u \\oplus v\\rangle \\qquad \\text{(for all $u\\in\\mathcal{C}_Z$)}\n", "$$\n", "\n", "In words, these vectors are uniform superpositions over the strings in the dual code $\\mathcal{D}_X$ of the code corresponding to the $X$ stabilizer generators, shifted by (in other words, bitwise XORed with) strings in the code $\\mathcal{C}_Z$ corresponding to the $Z$ stabilizer generators.\n", "To be clear, different choices for the shift — represented by the string $u$ in this expression — can result in the same vector.\n", "So, these states aren't all distinct, but collectively they span the entire code space.\n", "\n", "Here's an intuitive explanation for why such vectors are both in the code space and span it.\n", "Consider the $n$-qubit standard basis state $\\vert u\\rangle,$ for some arbitrary $n$-bit string $u,$ and suppose that we *project* this state onto the code space.\n", "That is to say, letting $\\Pi$ denote the projection onto the code space of our CSS code, consider the vector $\\Pi\\vert u\\rangle.$\n", "There are two cases:\n", "\n", "* Case 1: $u\\in\\mathcal{C}_Z.$\n", " This implies that each $Z$ stabilizer generator of our CSS code acts trivially on $\\vert u\\rangle.$\n", " The $X$ stabilizer generators, on the other hand, each simply flip some of the bits of $\\vert u\\rangle.$\n", " In particular, for each generator $v$ of $\\mathcal{D}_X,$ the $X$ stabilizer generator corresponding to $v$ transforms $\\vert u\\rangle$ into $\\vert u\\oplus v\\rangle.$\n", " By characterizing the projection $\\Pi$ as the *average* over the elements of the stabilizer (as we saw in the previous lesson), we obtain this formula:\n", "\n", " $$\n", " \\Pi \\vert u \\rangle = \\frac{1}{2^t} \\sum_{v\\in\\mathcal{D}_{X}} \\vert u \\oplus v\\rangle = \\frac{1}{\\sqrt{2^t}} \\vert u \\oplus \\mathcal{D}_X\\rangle.\n", " $$\n", "\n", "* Case 2: $u\\notin\\mathcal{C}_Z.$ This implies that at least one of the parity checks corresponding to the $Z$ stabilizer generators fails, which is to say that $\\vert u\\rangle$ must be a $-1$ eigenvector of at least one of the $Z$ stabilizer generators. The code space of the CSS code is the intersection of the $+1$ eigenspaces of the stabilizer generators. So, as a $-1$ eigenvector of at least one of the $Z$ stabilizer generators, $\\vert u\\rangle$ is therefore orthogonal to the code space:\n", "\n", " $$\n", " \\Pi\\vert u\\rangle = 0.\n", " $$\n", "\n", "And now, as we range over all $n$-bit strings $u,$ discard the ones for which $\\Pi\\vert u\\rangle = 0,$ and normalize the remaining ones, we obtain the vectors described previously, which demonstrates that they span the code space.\n", "\n", "We can also use the symmetry between $X$ and $Z$ stabilizer generators to describe the code space in a similar but different way.\n", "In particular, it is the space spanned by vectors having the following form.\n", "\n", "$$\n", "H^{\\otimes n} \\vert u \\oplus \\mathcal{D}_Z\\rangle\n", "= \\frac{1}{\\sqrt{2^s}} \\sum_{v\\in\\mathcal{D}_Z}\n", "H^{\\otimes n}\\vert u \\oplus v\\rangle \\qquad \\text{(for $u\\in\\mathcal{C}_X$)}\n", "$$\n", "\n", "In essence, $X$ and $Z$ have been swapped in each instance in which they appear — but we must also swap the standard basis for the $\\{\\vert+\\rangle,\\vert-\\rangle\\}$ basis, which is why the Hadamard operations are included.\n", "\n", "As an example, let us consider the 7-qubit Steane code.\n", "The parity check strings for both the $X$ and $Z$ stabilizer generators are the same:\n", "$1111000,$ $1100110,$ and $1010101.$\n", "The codes $\\mathcal{C}_X$ and $\\mathcal{C}_Z$ are therefore the same; both are equal to the $[7,4,3]$-Hamming code.\n", "\n", "$$\n", "\\mathcal{C}_X = \\mathcal{C}_Z =\n", "\\{0000000, 0000111, 0011001, 0011110, 0101010, 0101101, 0110011, 0110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111\\}\n", "$$\n", "\n", "The dual codes $\\mathcal{D}_X$ and $\\mathcal{D}_Z$ are therefore also the same.\n", "We have three generators, so we obtain eight strings.\n", "\n", "$$\n", "\\mathcal{D}_X = \\mathcal{D}_Z =\n", "\\{0000000, 0011110, 0101101, 0110011, 1001011, 1010101, 1100110, 1111000\\}\n", "$$\n", "\n", "These strings are all contained in the $[7,4,3]$-Hamming code, and so the CSS condition is satisfied: $\\mathcal{D}_Z \\subseteq \\mathcal{C}_X,$ or equivalently, $\\mathcal{D}_X \\subseteq \\mathcal{C}_Z.$\n", "\n", "Given that $\\mathcal{D}_X$ contains half of all of the strings in $\\mathcal{C}_Z,$ there are only two different vectors $\\vert u\\oplus \\mathcal{D}_X\\rangle$ that can be obtained by choosing $u\\in\\mathcal{C}_Z.$\n", "This is expected, because the 7-qubit Steane code has a two-dimensional code space.\n", "We can use the two states we obtain in this way to encode the logical state $\\vert 0\\rangle$ and $\\vert 1\\rangle$ as follows.\n", "\n", "$$\n", "\\begin{aligned}\n", "\\vert 0\\rangle & \\mapsto\n", "\\frac{\n", " \\vert 0000000\\rangle + \\vert 0011110\\rangle + \\vert 0101101\\rangle + \\vert 0110011\\rangle + \\vert 1001011\\rangle + \\vert 1010101\\rangle + \\vert 1100110\\rangle + \\vert 1111000\\rangle\n", "}{\\sqrt{8}}\\\\[4mm]\n", "\\vert 1\\rangle & \\mapsto\n", "\\frac{\n", " \\vert 0000111\\rangle + \\vert 0011001\\rangle + \\vert 0101010\\rangle + \\vert 0110100\\rangle + \\vert 1001100\\rangle + \\vert 1010010\\rangle + \\vert 1100001\\rangle + \\vert 1111111\\rangle\n", "}{\\sqrt{8}}\n", "\\end{aligned}\n", "$$\n", "\n", "As usual, this choice isn't forced on us — we're free to use the code space to encode qubits however we choose.\n", "This encoding is, however, consistent with the example of an encoding circuit for the 7-qubit Steane code in the previous lesson.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }