1 Introduction↩︎

Motivated by the need to overcome the pervasive effects of noise in quantum systems, recent years have seen a rapid expansion in the study of quantum coding theory. The field has seen the development of many classes of quantum codes, some of which have natural classical analogues, and some of which are inherently quantum. Most notably on the former, in 2021, the existence of asymptotically good quantum LDPC codes was resolved in the affirmative by Panteleev and Kalachev [1], ending a 20-year search. This result mirrors the construction of the first explicit and asymptotically good classical LDPC codes—the expander codes of Sipser and Spielman [2]—and sparked a flurry of follow-up constructions [3]–[5].

Interestingly, a related work due to Spielman [6], which came out at approximately the same time, presented a breakthrough result using related techniques on a different class of classical codes. These were the first known asymptotically good codes to have linear-time encoding and decoding algorithms, where the time, also called the complexity, of an algorithm refers to the total number of gates used in the algorithm. Spielman also showed that these codes admit a parallel encoding algorithm of logarithmic depth and linear time, and a parallel decoding algorithm of logarithmic depth and \(\mathcal{O}(n\log n)\) time.

The results of Spielman’s paper apply in the code capacity setting. That is, a classical encoding algorithm, which runs without faults, takes in a bit string representing the message to be sent, and outputs the codeword corresponding to that message. That codeword is then passed through a noise channel, and at the other end, a faultless decoding algorithm attempts to recover the message. The relevance of this setting on the classical side is quite clear; indeed, classical processors can be assumed for many purposes to be essentially noiseless, whereas noise occurring during the transmission of a signal, or during long-term storage can be more severe. On the other hand, it is understandable on the face of it why this class of codes has not received attention yet quantumly. Indeed, quantum information is extremely susceptible to noise from environmental sources, and imperfections in the quantum devices themselves cause further problems. Accordingly, quantum information can never be stored, or computed “raw”, that is, not encoded in a code, and be assumed to remain accurate to any useful degree. As such, it is unsurprising that significant attention has been devoted to quantum codes and fault-tolerance schemes that assume imperfect operations, and do not allow important quantum information to be held unencoded [7]–[10]; one might call this the setting of quantum fault tolerance.

On the other hand, the code capacity setting has also been widely studied in quantum error correction, and more broadly in quantum information theory [11]–[24]. Here, the setting is the natural analogue of the classical code capacity setting. That is, a quantum message (for example, some number of qubits in a certain state) is encoded, via a faultless quantum operation, into a quantum codestate. This state is then sent through a noise channel. Then, a faultless quantum processor attempts to return the noisy codeword to the original message, usually assisted by a (faultless) classical algorithm. Of this latter process, the quantum part is called the unencoding operation, and the classical part is called the decoding operation. Many problems in this setting have been well-studied, especially on the capacities of various quantum channels, and conditions for the correctability of certain noise models.

The complexities of the operations essential to the channel capacity setting, the quantum encoding and unencoding, as well as the classical decoding, have not been studied. That is, quantum codes with low-depth or low-time encoders, unencoders and decoders, have not been discovered. However, we can consider a key reason why this is a worthwhile problem to study: quantum communication. Given two fault-tolerant quantum processors, there are numerous reasons that they may wish to send information between them. In such a case, it would be generically expected that the environment between the quantum computers is far noisier than the environment of the processors themselves, in which quantum information is already protected by some host error-correcting code. That is, using the fault-tolerant operations of the devices, information could be perfectly encoded and unencoded from an error-correcting code, which is then run at the logical level of the quantum computers’ host error-correcting code (stated another way, the two codes are concatenated). In such a case, having low-depth encoding, unencoding, and decoding operations is highly desirable to avoid a bottleneck in, for example, a distributed quantum computation or quantum information theoretic task that is being performed.

As well as the application in quantum communication, we believe studying the depth and complexity of the encoding, unencoding and decoding operations over quantum channels is an inherently interesting problem. Indeed, quantum error-correcting codes find utility across quantum information theory and quantum complexity theory, and understanding the complexity and depth of these operations is an important thing to understand.

Our main results follow. The depths and complexities of each algorithm are summarised in Table 1.

In the statements of Theorems 1 and 2, the phrase “asymptotically good” is a common term in coding theory which tells us that the code has a constant rate and constant relative distance. Having a constant rate means that the ratio between the number of the code’s logical qubits (the number of qubits in the message being communicated), and the number of the code’s physical qubits (the number of qubits that must be sent over the channel) is some constant (is bounded away from zero as the code’s number of physical qubits diverges). Similarly, having a constant relative distance means that any set of the physical qubits, whose size is some constant fraction of the total, may be arbitrarily damaged, and the original message may be recovered, and indeed in this case the message may be recovered using the described unencoders and decoders of low depth and total complexity.

1.1 Overview of the Methods↩︎

We now overview the methods we use to construct our quantum error-correcting codes. This is explained at a high level assuming knowledge of the essential elements of quantum error correction, but is made accessible to a broad theoretical computer science audience via the preliminary material in Section 3.

We start in Section 1.1.1 by explaining how these codes may themselves by constructed from certain concatenations of quantum error-reduction codes. Then, in Section 1.1.2, we explain how these quantum error-reduction codes may be constructed from a particular expanding graph that we term a “lossless \(Z\)-graph”. Finally, in Section 1.1.3, we describe how our lossless \(Z\)-graphs are constructed, both randomly and explicitly.

1.1.1 Quantum Error-Correcting Codes from Quantum Error-Reduction Codes↩︎

To overview our construction, we begin by describing the first construction of linear-time encodable and decodable classical error-correcting codes due to Spielman [6]. In this paper, we will find that certain elements of that construction quantise seamlessly, whereas others present much greater roadblocks in their quantisation.

Spielman constructs classical error-correcting codes with fast encoders and decoders by taking classical error-reduction codes with the same properties and concatenating them in a particular structure. An error-reduction code works as follows. We begin with the message, a sequence of logical bits \(x \in \mathbb{F}_2^n\) that we wish to communicate to a receiver. This will be encoded into the error-reduction code, and so we also start with \(m\) bits initialised in some fixed state such as \(0\). An encoding circuit is then run on the collective bits in order to produce the codestate corresponding to the message \(x\). Once we have the codestate corresponding to \(x\), the \(n\) bits that initially corresponded to the message are called message bits, whereas the \(m\) bits initialised before the encoding circuit in a fixed state are called check bits. In total, they form the codeword of length \(n+m\).

Typically, for an error-reduction code, we would think of this encoding circuit as taking place with extremely low complexity and depth; indeed, in [6], the error-reduction codes have constant-depth encoding circuits (of linear complexity). Of course, having a constant-depth encoding circuit means that the code must have a constant distance, and thus cannot be a good error-correcting code, but what can it do? Indeed, suppose that in the noise channel, \(v\) errors occur on the message bits, and \(t\) errors occur on the check bits, where \(v\) and \(t\) are some small constant fraction of the block length. The code is said to be an error-reduction code with error reduction \(\epsilon\) if it is possible (via some error-reduction algorithm) to recover the original message up to some residual error of size at most \(\epsilon \cdot t\). In some sense, therefore, the error-reduction code is still resilient to check bit errors even if it cannot correct them entirely. As well as the encoding algorithm having low depth and complexity, one should think of the error-reduction algorithm as also having low depth and complexity. The low depths and complexities of the encoding and error-reduction algorithms for the error-reduction codes will translate into low depths and complexities for the encoding and decoding algorithms of the error-correcting code, respectively.

Let us now describe the concatenation structure [6] that allows us to construct classical error-correcting codes from classical error-reduction codes. As always in this section, we omit details, and present the high-level idea. We construct a family of error-correcting codes \((\mathcal{Q}_k)_{k=0}^\infty\) inductively, where the base case \(\mathcal{Q}_0\) may simply be chosen to be a random code of constant size. Then, \(\mathcal{Q}_k\) is constructed from an error-reduction code \(\mathcal{R}\) and the error-correcting code \(\mathcal{Q}_{k-1}\), as follows.⁵ Describing the encoding circuit suffices to describe the code itself. The encoding is depicted in Figure 1.

1. The code \(\mathcal{Q}_k\) has a set of message bits \(M\) which we wish to encode. First, \(M\) is encoded into the code \(\mathcal{R}\) using a set of check bits \(A\).

2. The bits in \(A\) are encoded as message bits into the code \(\mathcal{Q}_{k-1}\) using another set of bits \(B\) as check bits.

3. The bits in \(A \cup B\) are encoded as message bits into the code \(\mathcal{R}\) using a final set of check bits \(C\).

First, we note that if \(\mathcal{R}\) has a very high rate (greater than \(1/2\)), then the family of codes \(\mathcal{Q}_k\) constructed in this way has a constant rate. Moreover, the length of the code family \(\mathcal{Q}_k\) grows exponentially with \(k\). In turn, this means that a number of layers of concatenation logarithmic in the block length is used to encode \(\mathcal{Q}_k\). This alone has consequences for the encoding circuit. Indeed, it is quite quick to show that if \(\mathcal{R}\) has a constant-depth encoding circuit with linear complexity, then \(\mathcal{Q}_k\) has a logarithmic-depth encoding circuit with linear complexity.

Next, let us describe the decoding of \(\mathcal{Q}_k\). There exist both sequential and parallel algorithms; here we describe only the sequential algorithm for brevity. First, assume that the noise channel has left errors on small constant fractions of the bits in \(M, A, B\) and \(C\). To decode the code, first, the error-reduction algorithm is run for the code \(\mathcal{R}\) on the bits \(A \cup B \cup C\). Doing so leaves us with bits \(M \cup A \cup B\), however, the number of errors in \(A \cup B\) has been reduced (relative to the initial number in \(C\)). Indeed, the idea is that the number of errors in \(A \cup B\) has been reduced to the extent that they are now fully correctable by the error-correcting code \(\mathcal{Q}_{k-1}\), using its own decoding algorithm. After using the decoding algorithm of \(\mathcal{Q}_{k-1}\), we are now left with the bits in \(M \cup A\) as a noisy codeword of the code \(\mathcal{R}\), however, the errors on \(A\) have been completely removed. Since this code \(\mathcal{R}\) has zero errors on its check bits (bits in \(A\)), we may thus recover the message \(M\) perfectly, by the definition of an error-reduction code. Here, one may show that the linear complexity of the error-reduction algorithm for \(\mathcal{R}\) translates to a linear complexity of decoding algorithm for \(\mathcal{Q}_k\). The parallel decoding algorithm follows via slightly different considerations, but, ultimately, a constant-depth and linear-complexity parallel error-reduction algorithm for \(\mathcal{R}\) translates into a logarithmic-depth decoding algorithm for \(\mathcal{Q}_k\) with complexity \(\mathcal{O}(n \log n)\).

Now that we have described Spielman’s procedure at a high level for constructing error-correcting codes from error-reduction codes, let us consider how these steps may be quantised. Indeed, we will go on to show that the high-level picture of constructing quantum error-correcting codes as concatenations of quantum error-reduction codes, using the same structure as that described above, passes smoothly to the quantum case. The majority of the difficulties are faced in the construction of the quantum error-reduction codes themselves, but we tackle these in later sections.

First, let us define quantum error-reduction codes; this is a new notion in the literature as far as we know. The quantum error-reduction codes, and the quantum error-correcting codes that we use them to construct, are all stabiliser codes, in particular CSS codes [25], [26]. CSS codes may be encoded by taking \(n\) qubits in a particular state that we wish to encode, as well as \(m\) qubits all in the state \(\ket{+}\), and \(m\) further qubits in the state \(\ket{0}\), and running a unitary encoding circuit on them. The \(n\) qubits are known as the “message qubits”, whereas the two groups of \(m\) qubits are known as the “\(X\)-check qubits” and “\(Z\)-check qubits”, respectively: collectively called “check qubits”. Note that the encoding circuit will simply be chosen to be a circuit of \(\mathop{\mathrm{\mathsf{CNOT}}}\) gates, and in this case, we end up with a CSS code with \(m\) checks of \(X\) type and \(m\) checks of \(Z\) type.

After encoding, we imagine that all \(n+2m\) qubits in the codeblock are sent through a noise channel, resulting in some small constant fraction of the message qubits and check qubits being afflicted by errors. Suppose that \(v\) message qubits are afflicted by errors, and \(t\) check qubits are afflicted by errors. At a high level, we call the code a quantum error-reduction code with error reduction \(\epsilon\), if there is some process that can return to us the \(m\) message qubits, afflicted by up to \(\epsilon\cdot t\) errors. A more formal statement may be found in Definition 1 based on the material in Section 4.1.

One interesting comment to make about the error-reduction process is that it is a hybrid classical-quantum process. Indeed, a quantum circuit unitarily unencodes the noisy codeword from the codespace (this is simply the inverse of the encoding circuit). If no errors occurred, this would just return the message qubits to the state sent as a message, all of the \(X\)-check qubits to \(\ket{+}\), and all of the \(Z\)-check qubits to \(\ket{0}\). However, in general, errors occur, leaving some \(X\)-check qubits in the state \(\ket{-}\), and some \(Z\)-check qubits in the state \(\ket{1}\), as well as some residual Pauli error on the message qubits. A quantum measurement of the \(X\)-check qubits in the \(X\) basis, as well as the \(Z\)-check qubits in the \(Z\) basis, reveals the syndrome, that is, the subset of the stabilisers that the noise has violated. It is then up to a classical error-reduction algorithm to decide on a Pauli correction for the message qubits upon input of this syndrome. This Pauli correction should reduce the size of the error on the message qubits to within the desired size, which is \(\epsilon\cdot t\).

We will go on to show in detail that this picture plays out well at a high level for quantum codes in Section 4. One complication that will arise will be in the handling of classical versus quantum information and algorithms. Indeed, we will have to be careful to interlace quantum unencoding operations, as well as classical error-reduction algorithms, in order to prevent a problem of error spreading (described in the next section). This issue is particularly noticeable when handling the parallel algorithms, for which we will need to continue with multiple rounds of error reduction even after the quantum information has been measured out and become classical. We defer the remaining details to Section 4.

1.1.2 Quantum Error-Reduction Codes from Lossless \(Z\)-Graphs↩︎

Whereas the translation from error-reduction codes to error-correcting codes quantises smoothly, up to being careful about details as mentioned, the construction of the quantum error-reduction codes themselves will present several challenges not present on the classical side, as we now describe.

One’s first attempt to create a quantum error-reduction code might be to define a quantum CSS code whose \(X\)-checks and \(Z\)-checks both correspond to classical error-reduction codes. That is, one might imagine a quantum CSS code with \(m\) \(X\)-check qubits, \(n\) message qubits, and \(m\) \(Z\)-check qubits, whose parity-check matrices take the form \[\begin{align} {4} H_X &= (I&&|A&&|0&&)\tag{1}\\ H_Z &= (0&&|B&&|I&&).\tag{2} \end{align}\] In this equation, the physical qubits of the code are separated into \(m\) \(X\)-check qubits, \(n\) message qubits, and \(m\) \(Z\)-check qubits, respectively. \(I\) denotes an \(m \times m\) identity matrix, and \(0\) denotes an \(m\times m\) zeros matrix. The matrices \(A,B \in \mathbb{F}_2^{m \times n}\) denote the support of the \(X\) checks and \(Z\) checks on the message qubits, respectively. One might hope that this forms a quantum error-reduction code if the matrices \((I|A)\) and \((I|B)\) are parity-check matrices for classical error-reduction codes on \(m\) check bits and \(n\) message bits. Of course, the immediate problem one faces is commutativity, that is, this choice of \(H_X\) and \(H_Z\) only form a valid CSS code if \(H_X\cdot H_Z^T = 0\), which is if and only if \(A\cdot B^T = 0\). On the face of it, this is problematic because we do not know constructions of classical error-reduction codes for which this is true.

The problem is, however, even worse than this, as follows. Suppose that one did have classical error-reduction codes for which this holds. One could try to implement this as shown in Figure 2. That is, the \(X\) checks are encoded via some \(\mathop{\mathrm{\mathsf{CNOT}}}\)s corresponding to the matrix \(A\), and the \(Z\) checks are encoded via some \(\mathop{\mathrm{\mathsf{CNOT}}}\)s corresponding to the matrix \(B^T\).⁶ Assuming \(AB^T = 0\), this would indeed encode the message qubits in the desired state \(\ket{\psi}\) into the quantum CSS code defined by the Equations 1 and 2 .

After the encoding, noise occurs on all the qubits. Then, the code is unencoded by inverting the encoding circuit,⁷ and finally the \(X\)-check qubits are measured out in the \(X\) basis, and the \(Z\)-check qubits are measured out in the \(Z\) basis, thus measuring the stabilisers of the code. One’s hope is that \(X\) errors on the message qubits are measured by the \(Z\) checks, and \(Z\) errors on the message qubits are measured by the \(X\) checks, and may be reduced.

At this point, however, we find the most drastic problem that one encounters when one tries to construct a quantum error-reduction code: the problem of error spreading. The problem is that \(X\) errors on the \(X\)-check qubits, and \(Z\) errors on the \(Z\)-check qubits can spread into the message qubits during the unencoding circuit, and are not detected or reduced by the code. In particular, note that \(X\) errors on the \(X\)-check qubits get transferred into the message qubits via the block “\(\mathop{\mathrm{\mathsf{CNOT}}}\)s \(A\)” in the unencoding, and \(Z\) errors on the \(Z\)-check qubits get transferred into the message qubits via the block “\(\mathop{\mathrm{\mathsf{CNOT}}}\)s \(B^T\)” in the unencoding. In some sense, we need a construction that treats all of the different types of errors on each type of qubit at the same time.

In this work, we find that these problems can all be handled simultaneously by a construction of quantum error-reduction codes that is based on a particular two-way expanding bipartite graph that we term a “lossless \(Z\)-graph”. The idea is as follows. First, we wish to add in some support of the \(X\) checks to the \(Z\)-check qubits, and \(Z\) checks to the \(X\)-check qubits, in order to attempt to catch \(Z\) errors happening on the \(Z\)-check qubits, and \(X\) errors happening on the \(X\)-check qubits, respectively. Indeed, we now let our parity-check matrices take the form \[\begin{align} {4} H_X &= (\,I&&|A&&|C&&)\\ H_Z &= (D&&|B&&|\,I&&), \end{align}\] where \(C, D \in \mathbb{F}_2^{m \times m}\). Considering the issue of commutativity, we have that this forms a valid quantum CSS code only if \(H_X \cdot H_Z^T = 0\), which is if and only if \[\label{eq:C95matrix} C = A\cdot B^T + D^T.\tag{3}\] Our strategy will be to specify the matrices \(A, B\) and \(D\), and then simply let \(C\) be chosen according to this equation.

First, we note that the code of this form may be simply operated in the code capacity setting as shown in Figure 3. This figure shows that the encoding and unencoding circuits have been augmented with new groups of \(\mathop{\mathrm{\mathsf{CNOT}}}\) gates from the \(X\)-check qubits to the \(Z\)-check qubits according to the matrix \(D^T\). Note that we have also given names to the \(X\) support and \(Z\) support of the noise occurring on each group of qubits. It may be initially surprising that the matrix \(C\) does not appear in this figure. However, we show in Section 5.1 that the (un)encoding circuit shown consisting of the three blocks of \(\mathop{\mathrm{\mathsf{CNOT}}}\)s suffices to (un)encode the quantum code, and this holds for any matrices \(A, B\) and \(D\). Importantly, if the matrices \(A, B\) and \(D\) are chosen to be sparse, then the encoding may be run in constant depth, and with a linear number of gates.

By considering only the matrices \(A, B\) and \(D\), and encoding circuits of the above form, and letting \(C\) be according to the form of Equation 3 , we have sidestepped the problem of ensuring commutativity, but retain the problem of error spreading, and the need to suppress errors that have spread to the message qubits. In order to make progress, we need to consider the exact syndromes that are measured, as well as the residual errors on the message qubits after error spreading in the unencoding circuit. Indeed, one can show that the syndromes measured from the \(Z\) checks and \(X\) checks are, respectively, \[\begin{align} \sigma_z &= D\cdot X_x + B \cdot X_q + X_z,\\ \sigma_x &= Z_x + A\cdot Z_q + C\cdot Z_z. \end{align}\] Moreover, we find that the residual errors on the message qubits, of \(X\) type and \(Z\) type are, respectively, \[\begin{align} X_{Res} &\coloneq A^T\cdot X_x + X_q,\\ Z_{Res} &\coloneq Z_q + B^T\cdot Z_z. \end{align}\] These are exactly the errors on the message qubits for which we want to develop approximations, in order to reduce their size.

Ultimately, we will have to take care of four problems: reducing residual errors of \(X\) and \(Z\) type, via both sequential and parallel algorithms, but let us start with the most simple case, which is the problem of reducing the \(X\) errors via a sequential algorithm (tackled in Section 5.2.1). The reason that the \(X\) errors are particularly simple to handle is that the syndrome and residual error of this problem are both entirely in terms of matrices over which we have direct control, that is, \(A\), \(B\) and \(D\). Examining the syndrome in this case, which is \(\sigma_z\), we note that it takes the form of a syndrome for a classical error reduction problem. In this analogy, \(X_x\) and \(X_q\) may be thought of as message bit errors, and \(X_z\) as check bit errors.

To make this analogy more concrete, suppose we were to define a new matrix \(B' \coloneq (D|B)\), which has \(m\) rows and \(n'\) columns, where \(n' \coloneq m+n\). Then, we suppose \((B'|I)\) is a parity-check matrix for a classical error-reduction code. This means that, given a message bit error \(V \in \mathbb{F}_2^{n'}\) and a check bit error \(T \in \mathbb{F}_2^m\), where \(|V| = v\) and \(|T| = t\), we measure a syndrome \(B' \cdot V + T\). Since \((B'|I)\) is the parity-check matrix for a classical error-reduction code, there is then an algorithm allowing us to develop an approximation to \(V\), up to an error of size \(\leq \epsilon\cdot t\).

Returning to our problem of reducing the residual \(X\) error, what we aim to do, therefore, is let \(H_Z = (D|B|I)\) be a parity-check matrix for a classical error-reduction code (with \(n+m\) message bits and \(m\) check bits), at which point we will be able to develop approximations to \(X_x\) and \(X_q\), that are correct up to an error of size \(\leq \epsilon \cdot |X_z|\). Of course, the error that we are actually aiming to approximate is not \(X_x\) or \(X_q\), but \(X_{Res}\). We can use our approximations for \(X_x\) and \(X_q\) to calculate an approximation for \(X_{Res}\). One might be worried, however, that because \(X_x\) is multiplied by the matrix \(A^T\) in the expression for \(X_{Res}\), that having a good approximation for \(X_x\) and \(X_q\) may not result in a good approximation to \(X_{Res}\), that is, the error in our approximation to \(X_x\) could “blow up” so that the final approximation to \(X_{Res}\) in not a good one. In order to handle this, we will have to ensure that the amount of error reduction (called \(\epsilon\) above) achieved on the error \(X_x\) is small with respect to the maximum column weight of \(A^T\), thus ensuring that the final approximation to \(X_{Res}\) is still a good one.

At this point, we must explain how we can ensure that the factor of error reduction on \(X_x\) (the \(\epsilon\)) is sufficient, and in order to do this, we must explain the actual construction of the classical error-reduction code by which the matrix \((D|B|I)\) gets defined. Our inspiration comes from the randomised construction of classical error-reduction codes in Spielman [6]. There, a classical error-reduction code with parity-check matrix \((B'|I)\) gets defined by considering a one-sided lossless expander graph (which Spielman obtains randomly), with \(n'\) “left” vertices, corresponding to message bits, and \(m\) “right” vertices, corresponding to check bits. The matrix \(B'\) is defined as the adjacency matrix of the graph. Spielman showed that the lossless expansion may enable the error reduction, where the error reduction itself takes place via some simple small set flip algorithm.

We take a similar approach here, by letting \((D|B|I)\) be a parity-check matrix for a classical error-reduction code, which is achieved again via a lossless expander graph. Indeed, we consider a bipartite graph with two groups of “left” vertices, of sizes \(m\) and \(n\), and one group of “right” vertices, of size \(m\). This must expand in the sense that small sets of the \(m\) and \(n\) left-hand vertices must jointly have a large number of neighbours amongst the right-hand vertices. We show that a similar small-set flip algorithm, inputted with the syndrome \(\sigma_z = D\cdot X_x + B\cdot X_q + X_z\), may produce approximations to \(X_x\) and \(X_q\), such that the remaining error has size that is small in \(X_z\). In particular, supposing that in our bipartite graph, all the degrees of the left-hand set of \(m\) nodes are some constant \(\Delta_2 \in \mathbb{N}\), the remaining error on \(X_x\) will be shown to have size \(\lesssim \frac{|X_z|}{\Delta_2}\). We see that, by taking this degree \(\Delta_2\) to be some very large constant, a large amount of error reduction may be achieved. In particular, if we suppose the (column) sparsity of the matrix \(A^T\) is \(\sim \Delta_1\), then as long as \(\Delta_2 \gg \Delta_1\), our final calculated approximation to \(X_{Res}\) will still be a good one. It is interesting to comment at this point that, in our case, we have to be very careful about the amount of error reduction that we achieve, such as this factor \(\Delta_2\). In Spielman’s work, smaller factors, such as a simple error reduction by a factor of \(2\), turn out to be enough.

To summarise this part, the reduction of the \(X\) errors is made possible by taking the matrix \(H_Z = (D|B|I)\) to be the parity-check matrix for a classical error-reduction code, which we achieve by letting \((D|B)\) be the adjacency matrix for some bipartite graph with one-sided expansion. As long as the degree \(\Delta_2\) of the nodes corresponding to the columns of \(D\) is much larger than the (column) sparsity \(\sim \Delta_1\) of \(A^T\), then we will be able to achieve a reduction in the size of \(X_{Res}\).

Since we have already constrained the matrices \(A, B\) and \(D\) so much, it is not clear at this point how we will be able to handle the reduction of the \(Z\) errors, either with sequential or parallel algorithms. However, we may proceed as follows (see Section 5.2.2 for the sequential algorithm). We re-write the \(X\) syndrome via \[\begin{align} \sigma_x &= Z_x + A\cdot Z_q + C\cdot Z_z\\ &= Z_x + A \cdot Z_q + (A\cdot B^T+D^T)\cdot Z_z\\ &=Z_x + A\cdot (Z_q + B^T\cdot Z_z) + D^T\cdot Z_z\\ &= Z_x + A\cdot Z_{Res} + D^T\cdot Z_z. \end{align}\] We see now that the exact residual error of \(Z\) type we wish to reduce is sitting under the matrix \(A\). Moreover, the syndrome has again taken the form of that in a classical error reduction problem. By taking \((I|A|D^T)\) to be the parity-check matrix for a classical error-reduction code, we may aim to directly reduce the error \(Z_{Res}\), rather than developing approximations to two errors and calculating an approximation to the residual error, as we did for the \(X\) errors. In turn, we wish to now have \((A|D^T)\) be the adjacency matrix for a one-sided lossless expander.

In total, our requirements for the matrices \(A, B\) and \(D\) are as follows:

1. The matrix \((D|B)\) exhibits small-set expansion;

2. The matrix \((A|D^T)\) exhibits small-set expansion;

3. The (column) sparsity of the matrix \(D\) must be much greater than the (column) sparsity of the matrix \(A^T\).

Each of these requirements may be simultaneously satisfied by taking the three matrices \(A, B\) and \(D\) to be according to a two-way expanding structure, which we term a lossless \(Z\)-graph, described as follows, and depicted in Figure 4. The lossless \(Z\)-graph is a bipartite graph, with two sets of “left” vertices called \(L_1\) and \(L_2\), of sizes \(n\) and \(m\), respectively, and similarly two sets of “right” vertices called \(R_1\) and \(R_2\), of sizes \(n\) and \(m\), respectively. The graph obtained by restriction to the vertices \((L_1, R_2)\) is \((\Delta_1, \Delta_1')\)-biregular, where \(\Delta_1' = \frac{n}{m}\Delta_1\). Similarly, the graph obtained by restriction to \((R_1, L_2)\) is \((\Delta_1, \Delta_1')\)-biregular. Finally, the graph obtained by restriction to the vertices \((L_2, R_2)\) is \(\Delta_2\)-regular. There are no edges between the vertices \(L_1\) and \(R_1\), and so the graph appears in the form of the letter \(Z\), as shown. We let the matrix \(A\) be the adjacency matrix of the graph obtained by restriction to the vertices \((L_1, R_2)\), the matrix \(B\) be the adjacency matrix of the graph obtained by restriction to the vertices \((R_1, L_2)\), and finally the matrix \(D\) be the adjacency matrix of the graph obtained by restriction to the vertices \((R_2, L_2)\). Equivalently, the matrix \(D^T\) may be defined as the adjacency matrix of the graph obtained by restriction to the vertices \((L_2, R_2)\).

When we call the graph a lossless \(Z\)-graph, we mean that it has the following expansion properties. Suppose we take subsets \(S_1 \subseteq L_1\) and \(S_2 \subseteq L_2\) of some small constant-fractional size. Then, \(S_1\) and \(S_2\) must collectively have a large number of neighbours in \(R_2\). Let us denote the neighbours of \(S_1 \cup S_2\) in \(R_2\) as \(N_{R_2}(S_1 \cup L_2)\). Noting that \(|N_{R_2}(S_1 \cup S_2)| \leq \Delta_1|S_1| + \Delta_2|S_2|\), the graph is a lossless \(Z\)-graph only if \[\label{eq:rough95lossless95statement} |N_{R_2}(S_1 \cup S_2)| \geq (1-\epsilon_1)\Delta_1|S_1| + (1-\epsilon_2)\Delta_2|S_2|\tag{4}\] for some small \(\epsilon_1, \epsilon_2\). We also require that subsets \(S_1 \subseteq R_1\) and \(S_2 \subseteq R_2\) of some small constant-fractional size have a similarly large number of neighbours in \(L_2\). At a high level, the lossless \(Z\)-graph is a two-way lossless expander of mixed degree, but where the two-way expansion is only required to go “through” the edges connecting \(L_2\) and \(R_2\).

By taking \(\Delta_1, \Delta_2\) to be constants with \(\Delta_2 \gg \Delta_1\), we will have obtained all of the requirements described above, and constructed a quantum error-reduction code. To conclude this section, we finally remark that our parallel error-reduction algorithms for \(X\) errors and \(Z\) errors, described in Sections 5.3, come with some additional considerations, which we discussion in detail there. For now, we comment that the amount of error reduction required in our case is so great that our parallel error-reduction algorithms require especially strong lossless \(Z\)-graphs, which we can obtain randomly, but we are unable to obtain explicitly. Indeed, the parallel error-reduction algorithms will require lossless \(Z\)-graphs for which \(\epsilon_1 = \mathcal{O}(1/\Delta_1)\) and \(\epsilon_2 = \mathcal{O}(1/\Delta_2)\) (see Equation 4 ), which we are unable to obtain via the explicit construction. Moreover, our parallel error-reduction algorithms will require the quantity \(\frac{\Delta_1^2}{\Delta_2}\) to be small, which can be obtained randomly (since the random construction allows any two constant integers \(\Delta_1, \Delta_2\)), but the explicit construction only allows the quantity \(\frac{\Delta_1}{\Delta_2}\) to be made small. These two considerations explain why parallel error-reduction algorithms for the explicit quantum codes are not obtained in this work.

1.1.3 Constructions of Lossless \(Z\)-Graphs↩︎

We briefly remark on the construction of the lossless \(Z\)-graphs themselves, which is handled in Section 6.

First, for the random construction, we sample a graph from the natural ensemble, and show that it satisfies the expansion constraints with high probability. That is, we consider fixed sets of vertices \(L_1, L_2, R_1, R_2\) with the appropriate number of half-edges going towards the correct end-points, and join them to each other uniformly at random. Showing that the expansion properties hold uses mostly standard techniques, see for example [27]. One complication will be that showing the joint expansion of (for example) \(S_1 \subseteq L_1\) and \(S_2 \subseteq L_2\) is not possible directly when the sizes \(|S_1|\) and \(|S_2|\) are very imbalanced, that is, the quantity \(\frac{|S_1|}{|S_2|}\) is very large or very small. However, in such cases, we show that the joint expansion may be reduced to the usual lossless expansion. For example, when \(\frac{|S_1|}{|S_2|}\) is very large, the joint expansion may be demonstrated via the expansion of vertices \(L_2\) going into \(R_2\). Similarly, when \(\frac{|S_1|}{|S_2|}\) is very small, the joint expansion may be demonstrated via the expansion of vertices \(L_2\) going into \(R_2\). See Section 6.1 for details.

Our explicit construction proceeds via a white-box modification of the recent construction of two-sided lossless expanders by [28]. At first glance, it might seem that one could use their construction as a black box, by letting the graph between \((L_2, R_2)\) be a two-sided lossless expander, and taking \((L_1, R_2)\) and \((R_1, L_2)\) to both be one-sided lossless expanders. However, even if \(S_1 \subset L_1\) and \(S_2 \subset L_2\) are individually expanding, the lossless expansion guarantees do not prohibit their neighborhoods from matching exactly and canceling each other out. Thus, we need to open up their construction and modify the individual components.

At a high level, the two-sided expanders of [28] are constructed via a local-to-global framework. Specifically, they overlay a constant-sized “gadget” lossless expander many times according to some blueprint, and argue that the properties of the blueprint imply that the global graph will also experience lossless expansion. For our case, we will choose our constant-sized gadget graph to itself be a lossless Z-graph. Then, by overlaying it many times according to the blueprint in [28], we are able to argue that the global graph will be a lossless Z-graph as well. See Section 6.2 for details.

1.2 Future Directions↩︎

In this work, we have constructed the first quantum error-correcting codes with encoding, unencoding and decoding algorithms of low depth and complexity. In particular, we have presented asymptotically good codes with sequential encoding, unencoding, and decoding algorithms of linear complexity, as well as corresponding logarithmic-depth parallel algorithms, with complexities \(\mathcal{O}(n)\), \(\mathcal{O}(n)\), and \(\mathcal{O}(n \log n)\), respectively. For our explicit construction, the same is obtained, without the parallel classical decoding algorithm. The first natural direction for future work is therefore as follows.
Open Problem 1: Can we construct explicit and asymptotically good quantum error-correcting codes with low-depth parallel classical decoding algorithms?
As discussed above, our explicit lossless \(Z\)-graphs fail to meet the conditions required of our parallel classical decoding algorithm on two fronts, namely that we require very small \(\epsilon_1, \epsilon_2\), namely \(\mathcal{O}(1/\Delta_1)\), \(\mathcal{O}(1/\Delta_2)\), respectively, as well as the fact that we require \(\Delta_2\) to be quadratically larger than \(\Delta_1\), rather than simply a constant multiple larger. We note that the former of these seems to be a particular obstruction to the current approach, since the explicit two-sided lossless expander [28], are not yet known with \(\epsilon = \mathcal{O}(1/\Delta)\).
Open Problem 2: Can we understand the exact rate/distance tradeoff of explicit or randomised asymptotically good quantum codes with low-depth and low-complexity encoders and decoder?
In this work, we have only showed that our quantum codes are asymptotically good, and we also show that our construction can achieve rate close to \(1\). However, the exact rate/distance tradeoff is left to future work. Interestingly, on the classical side, following Spielman’s work, there has been a fruitful line of work studying the corresponding problem [29]–[33]. Notably, the recent work [33] constructs linear-time classical codes with parameters achieving the Gilbert-Varshamov bound, whose duals have the same properties. Given the importance of properties of the dual code when forming quantum CSS codes, it could be interesting to explore the connection of the codes in that work to quantum codes with fast encoders.
Open Problem 3: Can we construct (asymptotically good) quantum codes with low-depth and complexity fault-tolerant encoders?
As discussed, this paper considers only the code capacity setting which is relevant in communication problems and information theory. However, it is also interesting to ask whether codes with low-depth and complexity encoders exist in a fault-tolerant setting. Relatedly, it is not known whether there exist LDPC codes with low-depth or complexity encoders, even on the classical side. Must there be necessarily be a tradeoff between the parameters of a code, the depth or complexity or its encoder, and its maximum check weight?

2 Outline of the Paper↩︎

In Section 3, we describe the necessary preliminary material for this paper in order to make it accessible to a broad theoretical computer science audience; this may be skipped by those already familiar with the essentials of quantum error correction. In Section 4, we describe how quantum error-correcting codes may be constructed from quantum error-reduction codes. In Section 5, we describe how quantum error-reduction codes may be constructed from “lossless \(Z\)-graphs”. In Section 6, we describe the construction of lossless \(Z\)-graphs, both randomly and explicitly. Finally, in Section 7, we put all the ideas together to conclude the proofs of our main results, Theorems 1 and 2.

3 Preliminaries↩︎

In order to make the paper accessible to a general theoretical computer science audience, we present in this section the essential information on quantum error-correcting codes, in particular CSS codes. Those already familiar with CSS codes can safely skip this section.

The state of a single qubit is specified by a vector in \(\mathbb{C}^2\) of unit norm. The standard basis, also called the computational basis, is denoted by two vectors \(\ket{0}\) and \(\ket{1}\). Other important states are \(\ket{+} = (\ket{0}+\ket{1})/\sqrt{2}\) and \(\ket{-} = (\ket{0}-\ket{1})/\sqrt{2}\). The state of \(n\) qubits is specified by a vector in \((\mathbb{C}^2)^{\otimes n}\) of unit norm. Tensor product symbols are often dropped for readability, for example, a computational basis state on \(n\) qubits is commonly denoted \(\ket{x}\) for \(x \in \{0,1\}^n\).

Quantum stabiliser codes are by far the most commonly studied class of quantum codes, of which quantum CSS codes are a commonly-studied sub-class. To introduce quantum stabiliser codes, we begin with the single-qubit Pauli operators, \[I = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} X = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} Y = \begin{pmatrix} 0 & -i\\ i & 0 \end{pmatrix} Z = \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}.\] Up to an overall phase, the Pauli operators for \(n\) qubits are constructed by taking tensor products of the above operators. Given a set \(\mathcal{S}\) of \(n\)-qubit Pauli operators which commute, the stabiliser code corresponding to \(\mathcal{S}\) is the set of \(n\)-qubit states with eigenvalue \(+1\) under all operators in \(\mathcal{S}\) (the set of states stabilised by \(\mathcal{S})\), that is, \[\mathcal{Q} = \left\{\ket{\psi} \in (\mathbb{C}^2)^{\otimes n}: P\ket{\psi} = \ket{\psi} \text{ for all } P \in \mathcal{S}\right\}.\] Different \(\mathcal{S}\) may result in the same code \(\mathcal{Q}\). A quantum CSS code \(\mathcal{Q}\) is a stabiliser code which has an \(\mathcal{S}\) for which every Pauli in \(\mathcal{S}\) is either a tensor product of only \(I\) and \(X\) (an \(X\)-type stabiliser), or a tensor product of only \(I\) and \(Z\) (a \(Z\)-type stabiliser). Thus, a quantum CSS code may be specified by two binary matrices, \(H_X\) and \(H_Z\), each with \(n\) columns. \(H_X\) specifies a list of \(X\)-Pauli operators in the code’s stabiliser, known as the \(X\) stabilisers or \(X\) checks, and \(H_Z\) specifies a list of \(Z\)-Pauli operators in the code’s stabiliser, known as \(Z\) stabilisers or \(Z\) checks. Each row of \(H_X\) specifies an \(X\) check, where a \(0/1\) represents an \(I/X\) in the corresponding stabiliser, and similarly for \(H_Z\). In order to form a valid stabiliser code, all of the code’s stabilisers must commute. Trivially, all of the \(X\) checks commute amongst themselves, and all of the \(Z\) checks commute amongst themselves. To form a quantum CSS code from the matrices \(H_X\) and \(H_Z\), it is therefore necessary and sufficient that each \(X\) check commutes with each \(Z\) check. Since \(XZ = -ZX\), this is true if and only if every row of \(H_X\) has an even overlap with every row of \(H_Z\), which is to say that \(H_X\cdot H_Z^T = 0\), with arithmetic performed in binary.

Given a valid CSS code, the number of logical qubits that it encodes is \(n - \mathsf{rank} \;H_X - \mathsf{rank} \;H_Z\). While quantum errors are in principle continuous, the principle of error discretisation means that we need only consider a discrete set of errors. In particular, we may consider all errors to be Pauli operators. The distance of the code is the minimum number of qubits on which an error must occur in order that the error is undetectable and can change the logical state of the code. For a CSS code, there is a notion of \(X\)-distance and \(Z\)-distance, respectively: \[\begin{align} d_X &= \min\{|v|: v \in \ker H_X\setminus \mathop{\mathrm{im}}H_Z^T\}\\ d_Z &= \min\{|v|: v \in \ker H_Z\setminus \mathop{\mathrm{im}}H_X^T\}. \end{align}\] This is the minimum weight of an \(X\)-type Pauli and a \(Z\)-type Pauli, respectively, that can undetectably change the logical information. The distance of the code is then \[d = \min\{d_X, d_Z\}.\]

The remaining quantum operations that will be required for our exploration will be the \(\mathop{\mathrm{\mathsf{CNOT}}}\) gate, and the notion of single-qubit Pauli measurements. The \(\mathop{\mathrm{\mathsf{CNOT}}}\) gate is a two-qubit gate acting as follows, \[\mathop{\mathrm{\mathsf{CNOT}}}\ket{00} = \ket{00},\mathop{\mathrm{\mathsf{CNOT}}}\ket{01} = \ket{01},\mathop{\mathrm{\mathsf{CNOT}}}\ket{10} = \ket{11},\mathop{\mathrm{\mathsf{CNOT}}}\ket{11} = \ket{10},\] where the first qubit is referred to as the control, and the second as the target. If we wish to emphasise the control and target, then we may write \(\mathsf{CNOT}_{ab}\), where qubit \(a\) is the control and qubit \(b\) is the target.

For single-qubit Pauli measurements, the only necessary information for our exploration will be the fact that a measurement of a qubit in the \(X/Z\) basis returns the outcome \(y \in \{0,1\}\) with probability \(1\) if the qubit is an eigenstate of the \(X/Z\) operator with eigenvalue \((-1)^y\).

It will be useful for us to draw circuit diagrams, which depict quantum computations, and are read from left to right. Here, a single wire denotes a single qubit, whereas a slashed wire denotes multiple qubits (where the number may be labelled). Preparation of one or multiple qubits in a particular state may be indicated by writing that state before the wire. For example, the following diagrams depict, respectively, the preparation of a single qubit in the state \(\ket{0}\), the preparation of a single qubit in the state \(\ket{+}\), and the preparation of \(k\) qubits in the state \(\ket{\psi}\). \[\begin{quantikz} \lstick{\ket{0}} & \qw \end{quantikz} \qquad \begin{quantikz} \lstick{\ket{+}} & \qw \end{quantikz} \qquad \begin{quantikz} \lstick{\ket{\psi}} & \qw \qwbundle{k} \end{quantikz}\] The \(\mathop{\mathrm{\mathsf{CNOT}}}\) operation (controlled on the top wire and targeting the lower wire), and \(X/Z\) measurements are depicted as follows. \[\begin{quantikz} \qw & \ctrl{1} & \qw \\ \qw & \targ{} & \qw \end{quantikz} \qquad \begin{quantikz} \qw & \meter{X} \\ \end{quantikz} \qquad \begin{quantikz} \qw & \meter{Z} \\ \end{quantikz}\] The following commutation relations will be useful for us, and may be readily verified: \[\begin{align} {3}\label{eq:CNOT95commutation95rules} \mathsf{CNOT}_{12}X_1 &= X_1X_2\mathsf{CNOT}_{12}, &&\mathsf{CNOT}_{12}X_2&&=X_2\mathsf{CNOT}_{12}\\\mathsf{CNOT}_{12}Z_1 &= Z_1\mathsf{CNOT}_{12}, &&\mathsf{CNOT}_{12}Z_2 &&= Z_1Z_2\mathsf{CNOT}_{12}, \end{align}\tag{5}\] where, as always, tensor product symbols are dropped and subscripts are used to denote the qubit on which the given gate acts. Graphically, we have \[\begin{quantikz} \qw&\gate[wires=1]{X}&\ctrl{1} & \qw & \qw\\ \qw & \qw & \targ{} & \qw & \qw \end{quantikz} = \begin{quantikz} \qw&\qw&\ctrl{1} & \gate[wires=1]{X} & \qw\\ \qw &\qw & \targ{} & \gate[wires=1]{X} & \qw \end{quantikz},\begin{quantikz} \qw&\qw & \ctrl{1} & \qw & \qw\\ \qw & \gate[wires=1]{X} & \targ{} & \qw & \qw \end{quantikz} = \begin{quantikz} \qw&\qw&\ctrl{1} & \qw & \qw\\ \qw &\qw & \targ{} & \gate[wires=1]{X} & \qw \end{quantikz}\] and \[\begin{quantikz} \qw&\gate[wires=1]{Z}&\ctrl{1} & \qw & \qw\\ \qw & \qw & \targ{} & \qw & \qw \end{quantikz} = \begin{quantikz} \qw&\qw&\ctrl{1} & \gate[wires=1]{Z} & \qw\\ \qw &\qw & \targ{} & \qw & \qw \end{quantikz},\begin{quantikz} \qw&\qw & \ctrl{1} & \qw & \qw\\ \qw & \gate[wires=1]{Z} & \targ{} & \qw & \qw \end{quantikz} = \begin{quantikz} \qw&\qw&\ctrl{1} & \gate[wires=1]{Z} & \qw\\ \qw &\qw & \targ{} & \gate[wires=1]{Z} & \qw \end{quantikz}.\]

4 From Quantum Error Reduction to Quantum Error Correction↩︎

In this work, we will construct linear-time encodable and decodable quantum error-correcting codes, where we take inspiration from the original construction of linear-time encodable and decodable classical error-correcting codes due to Spielman [6]. It is interesting that certain elements of Spielman’s construction will prove very amenable to quantisation, whereas others will prove much more difficult.

At a high level, Spielman’s construction proceeds by concatenating a series of “classical error-reduction codes” in a particular structure, so that the whole thing forms an error-correcting code. The low complexity of encoding and decoding at each level of the concatenation translates to a low complexity encoding and decoding of the whole code. We will go on to find that the global picture, that of concatenating error-reduction codes to form error-correcting codes, translates mostly smoothly from the classical to the quantum case. There will be a minor alteration in the definition of error reduction. In particular, in the classical case, one talks about message and check bits, whereas in the quantum case, we will talk about message qubits, \(X\)-check qubits, and \(Z\)-check qubits, as we shortly introduce. Additionally, proving the translation from quantum error reduction for the parallel algorithms will require particular care, although proving the statement for the sequential algorithms will be a direct translation of the corresponding proof in Spielman [6]. The majority of the work will be in the actual construction of the quantum error-reduction codes, which is handled in Sections 5 and 6.

To prepare us for defining quantum error-reduction codes, we will now describe the encoding, unencoding and decoding of quantum CSS codes.

4.1 Encoding, Unencoding and Decoding of Quantum CSS Codes↩︎

We will now discuss the encoding, unencoding and decoding of quantum CSS codes in a way that is suitable for this context. As we work in the channel capacity/communication setting, the process of encoding quantum information, noise, and unencoding, using a general quantum CSS code, may be described as follows (see also Figure 5).

In words, we begin with \(N\) qubits, where \(N\) is the code’s block length. The first \(m_X = \mathsf{rank}\;H_X\) of these qubits each begin in the state \(\ket{+}\), and are called \(X\)-check qubits, and the last \(m_Z = \mathsf{rank}\;H_Z\) of the qubits each begin in the state \(\ket{0}\), and are called \(Z\)-check qubits. We refer to the \(X\)-check qubits and \(Z\)-check qubits collectively as check qubits. The remaining \(n\) qubits are referred to as the message qubits, and are initialised in whichever state we wish to encode and send through the noise channel; here we depict this state as some general \(n\)-qubit state \(\ket{\psi}\). The encoding operation is a quantum operation responsible for preparing the logical state \(\overline{\ket{\psi}}\). As we work in the channel capacity setting, this operation occurs without noise or faults. The important point is that, after the encoding operation, but before the noise occurs, the \(n\) qubits are in a quantum state that is a simultaneous \(+1\) eigenstate of all the code’s stabilisers. In particular, we may always take the encoding operation to consist entirely of \(\mathsf{CNOT}\) gates, and then \(m_X\) is the number of the code’s \(X\) checks, and \(m_Z\) is the number of the code’s \(Z\) checks. One notes that, before the encoding operation, the \(n\) qubits are in a \(+1\) eigenstate of every \(X\) operator acting on one of the first \(m_X\) qubits, and a \(+1\) eigenstate of every \(Z\) operator acting on one of the last \(m_Z\) qubits. After the encoding operation, the \(N\) qubits are in a \(+1\) eigenstate of each of these operations commuted through the encoding operation. Since we take the encoding operation to consist entirely of \(\mathop{\mathrm{\mathsf{CNOT}}}\) operations, the resulting stabilisers, both \(X\) checks and \(Z\) checks, may be calculated via Equation 5 . In summary, the encoding operation causes the \(X\) checks and \(Z\) checks to spread out across the \(N\) qubits.

The noise operation may then be taken to be some tensor product of Paulis. The Pauli error occurring on the \(X\)-check qubits may be written \(X_xZ_x\), where \(X_x\) and \(Z_x\) are respectively Paulis of pure \(X\) and \(Z\) type. Note that one may think of both of \(X_x\) and \(Z_x\) as bit strings of length \(N\) if desired, denoting the positions in which they are non-trivial. Similarly, we denote the Pauli errors occurring on the message qubits as \(X_qZ_q\) and \(X_zZ_z\), respectively. The situation appears as follows.

Again, since we work in the channel capacity setting, the unencoding operation is a quantum operation that is noiseless and without faults. It may be taken to be the inverse of the encoding operation. Because the \(\mathsf{CNOT}\) gate is self-inverse, it may just be taken to be the same sequence of \(\mathsf{CNOT}\)s as the encoding operation with the order reversed. In the last step, every \(X\)-check qubit is measured in the \(X\) basis, and every \(Z\)-check qubit is measured in the \(Z\) basis (note our slight abuse of notation in using single-qubit measurement symbols in Figure 6, where we are in fact denoting the measurement of \(m_X\) qubits, each in the \(X\) basis, and \(m_Z\) qubits, each in the \(Z\) basis).

At this point, at the end of the quantum operations, there is some Pauli error remaining on the message qubits that we wish to correct. Our attempt to correct this error is informed by our measurement outcomes; the measurement outcomes are turned into a candidate correction via a classical decoding algorithm.

When \(Z\) errors occur in the noise step, immediately after that step, they may cause the \(N\) qubits to no longer be in a \(+1\) eigenstate of certain \(X\) checks. In turn, this will cause certain \(X\) measurements at the end of the circuit to return the value \(1\) rather than \(0\). Likewise, when \(X\) errors occur in the noise step, immediately after that step, they may cause the \(N\) qubits to no longer be in a \(+1\) eigenstate of certain \(Z\) checks any longer, which will in turn cause some of the \(Z\) measurements at the end of the circuit to return the value \(1\) rather than \(0\) (which they would if there were no noise). To make this precise, we give more notation to our quantum code. That is, we write our \(X\)- and \(Z\)-check matrices as \[\begin{align} H_X &= \begin{pmatrix} H_{xx} & H_{xq} & H_{xz} \end{pmatrix} \in \mathbb{F}_2^{m_X \times n}\\ H_Z &= \begin{pmatrix} H_{zx} & H_{zq} & H_{zz} \end{pmatrix} \in \mathbb{F}_2^{m_Z \times n}. \end{align}\] Given \(a \in \{x,z\}\), \(H_{ax}\), \(H_{aq}\) and \(H_{az}\) denote the support of the \(a\)-type checks on the \(X\)-check qubits, message qubits and \(Z\)-check qubits, respectively. Then, one finds that the \(X\)-syndrome, that is, the collection of measurement outcomes of the \(X\)-basis measurements, written as a vector in \(\mathbb{F}_2^{m_X}\), is \[\sigma_x = H_{xx}Z_x + H_{xq}Z_q + H_{xz}Z_z,\] where arithmetic takes place in binary, and similarly the \(Z\)-syndrome is \[\sigma_z = H_{zx}X_x + H_{zq}X_q + H_{zz}X_z\] as a vector in \(\mathbb{F}_2^{m_Z}\). Notice that we are conflating the meaning of the symbols \(X_x, Z_x\), and so on, between Paulis, and binary vectors denoting their support.

Finally, the decoding process is a classical process that takes as input the syndromes \(\sigma_x\) and \(\sigma_z\) and attempts to compute the best correction to make to fix the residual Pauli error on the message qubits.

Before moving on, there are two remarks we wish to make. The first is that we are only interested in fixing the residual error on the message qubits. Typically in quantum error correction, the information remains permanently inside the error-correcting code, and measurements make use of ancillary qubits. In that setting, one wishes to correct all errors on all \(N\) qubits. Here, we are encoding into and unencoding out of the quantum code. \(X\)-check and \(Z\)-check qubits are measured and discarded, and we are only interested in correcting the residual error on the message qubits. Our second remark is to emphasise one interesting difference in this quantum setup with respect to the classical setup considered by Spielman [6]. In the classical setup, the unencoding and decoding operations, the operations that take your information out of the codespace, and attempt to find a correction, respectively, are rolled into one operation that is simply called “decoding”. In the quantum setting, it is interesting that these two operations must be separated, so that in particular the former is a quantum operation (a circuit of \(\mathsf{CNOT}\)s), whereas the latter is a classical algorithm.

4.2 Definition of Quantum Error-Reduction Codes↩︎

Following the corresponding classical definition of Spielman [6], our definition of quantum error-reduction codes is as follows.

4.3 Concatenation Structure↩︎

We now show how quantum error-reduction codes may be concatenated to form quantum error-correcting codes. As mentioned, a direct quantisation of Spielman’s structure [6] is sufficient. The analysis of the sequential algorithms also passes across nicely, although the analysis of the parallel algorithms is slightly more involved.

We define our family of quantum error-correcting codes \(\left(\mathcal{Q}_k\right)_{k=0}^\infty\) as follows. Let \(r^{(1)}\) and \(r^{(2)}\) be numbers in \((0,1)\) such that \[\label{eq:qerc95to95qecc95rate} R \coloneq 1+\frac{1}{r^{(2)}}-\frac{1}{r^{(1)}r^{(2)}} > 0.\tag{6}\] Let \(\mathcal{Q}_0\) be a quantum error-correcting code with \(n_0\) message qubits and rate \(R\), so that Pauli errors occurring on at most a \(\delta_0\) fraction of the qubits can be corrected. \(\mathcal{Q}_0\) is imagined to be some constant-sized code which may be constructed, for example, via a randomised procedure [25]. For \(k \geq 1\), let \(\mathcal{R}_k^{(1)}\) and \(\mathcal{R}_k^{(2)}\) be families of quantum error-reduction codes such that \(\mathcal{R}_k^{(j)}\) has rate \(r^{(j)}\), error reduction \(\epsilon^{(j)}\), and reducible distance \(\delta^{(j)}\) for \(j = 1,2\). In addition, let \(\mathcal{R}_k^{(1)}\) have \[n_k \coloneq n_0\left(\frac{r^{(1)}}{1-r^{(1)}}\right)^k\] message qubits, and let \(\mathcal{R}_k^{(2)}\) have \(n_k\left(\frac{1-r^{(1)}}{r^{(1)}}\right)\cdot\frac{1}{R} = \frac{n_{k-1}}{R}\) message qubits.⁸

For \(k \geq 1\), \(\mathcal{Q}_k\) will be a quantum error-correcting code with \(n_k\) message qubits. Describing its encoding circuit is enough to describe the code itself, which we do as follows. The \(n_k\) message qubits of \(\mathcal{Q}_k\) are collectively called \(M_k\), and are first encoded into the code \(\mathcal{R}_k^{(1)}\) to produce \(n_k\left(\frac{1-r^{(1)}}{r^{(1)}}\right) = n_{k-1}\) check qubits; we call this set of check qubits \(A_k\). Then, the qubits in \(A_k\) are encoded into the quantum error-correcting code \(\mathcal{Q}_{k-1}\), to produce a further set of check qubits called \(B_k\) of size \(n_{k-1}\left(\frac{1-R}{R}\right)\). Finally, the qubits in \(A_k \cup B_k\) are together encoded into the code \(\mathcal{R}_k^{(2)}\) to produce \(\frac{n_{k-1}}{R}\left(\frac{1-r^{(2)}}{r^{(2)}}\right)\) further check qubits: a set which we call \(C_k\).

The following may be readily verified from the construction.

4.3.1 Sequential Algorithms↩︎

Forming sequential error correction algorithms for \(\mathcal{Q}_k\) from the sequential error-reduction algorithms of \(\mathcal{R}_k^{(1)}\) and \(\mathcal{R}_k^{(2)}\) is a straightforward quantisation of the corresponding argument in Spielman [6], as long as one is careful about the ordering of classical and quantum operations, as we now show.

4.3.2 Parallel Algorithms↩︎

5 Quantum Error-Reduction Codes from Lossless Z-Graphs↩︎

In this section, we construct quantum error-reduction codes and their algorithms, reducing the problem to the construction of a certain structure that we call a lossless Z-graph. In turn, we construct lossless Z-graphs both randomly and explicitly in Section 6.

In Section 5.1, we present our construction of quantum error-reduction codes, and explain how to encode (and unencode) them with circuits of low depth and number of gates. In Section 5.2, we describe sequential error-reduction algorithms for our codes, proving their complexity and that they work. Finally, in Section 5.3, we do the same for our parallel error-reduction algorithms.

5.1 Construction of Quantum Error-Reduction Codes and their (Un)encoding↩︎

Our quantum error-reduction codes are quantum CSS codes with parity-check matrices of the form \[\begin{align} {4} H_X &= (\,I&&|A&&|C&&)\tag{9}\\ H_Z &= (D&&|B&&|\,I&&)\tag{10}. \end{align}\] As always, \(H_X\) and \(H_Z\) are binary matrices whose rows denote the support of \(X\) checks and \(Z\) checks, respectively, and whose columns correspond to the physical qubits of the code. We let \(H_X\) and \(H_Z\) both have \(m\) rows (so the number of \(X\) checks always equals the number of \(Z\) checks, \(m_X = m_Z = m\)). The physical qubits are grouped into \(m\) \(X\)-check qubits, \(n\) message qubits, and \(m\) \(Z\)-check qubits, respectively. \(I\) denotes the \(m \times m\) identity matrix. Matrices \(A\) and \(C\) correspond to the support of the \(X\) stabilisers on message qubits and \(Z\)-check qubits, respectively, whereas matrices \(D\) and \(B\) correspond to the support of \(Z\) stabilisers on the \(X\)-check qubits and message qubits, respectively.

As always, these parity-check matrices define a valid CSS code if and only if \(H_X\cdot H_Z^T = 0\), with arithmetic performed over \(\mathbb{F}_2\). One can check that this is the case if and only if \[C = AB^T+D^T.\] Our strategy in building quantum error-reduction codes will be to specify matrices \(A,B\) and \(D\), and then to simply let \(C\) be according to this equation.

5.1.1 Encoding Circuit↩︎

Let us consider the encoding of a quantum CSS code of this form. It turns out that any quantum code of this form can be encoded in constant depth and linear time if the matrices \(A, B\) and \(D\) are chosen to be sparse.

A circuit that encodes the code is described as follows.

1. Begin with \(m\) \(X\)-check qubits in the state \(\ket{+}\), \(m\) \(Z\)-check qubits in the state \(\ket{0}\), and \(n\) message qubits in the logical state that we wish to encode into the code;

2. For every \((i,j) \in [m] \times [n]\) such that \(A_{i,j} = 1\), perform a \(\mathop{\mathrm{\mathsf{CNOT}}}\) with the \(i\)’th \(X\)-check qubit as control and the \(j\)’th message qubit as target;

3. For every \((i,j) \in [m] \times [n]\) such that \(B_{i,j} = 1\), perform a \(\mathop{\mathrm{\mathsf{CNOT}}}\) with the \(j\)’th message qubit as control and the \(i\)’th \(Z\)-check qubit as target;

4. For every \((i,j) \in [m] \times [m]\,\,\,\) such that \(D_{i,j} = 1\), perform a \(\mathop{\mathrm{\mathsf{CNOT}}}\) with the \(j\)’th \(X\)-check qubit as control and the \(i\)’th \(Z\)-check qubit as target.

This encoding circuit is sketched in Figure 7. Let us show why it is an encoding circuit for the code. It is sufficient to show that, by the end of the circuit, the qubits are collectively in a \(+1\)-eigenstate of all (are stabilised by all) \(X\) checks and \(Z\) checks of the code, as specified by equations 9 and 10 . To do this, one notes that, after Step [step:encoding95init], the qubits are stabilised by every single-qubit \(X\)-operator acting on any \(X\)-check qubit, and any single-qubit \(Z\)-operator acting on any \(Z\)-check qubit. That is, after Step [step:encoding95init], the stabilisers of the code may be denoted \[\begin{align} {4} H_X &= (I&&|0&&|0&&)\\ H_Z &= (0&&|0&&|I&&). \end{align}\] It is sufficient to show that these stabilisers commute through the encoding circuit to the desired form of Equations 9 and 10 .

Step [step:encoding95A95matrix] causes \(X\) stabilisers to spread onto the message qubits. In particular, after Step [step:encoding95A95matrix], one can see using the commutation of \(X\) operators through \(\mathop{\mathrm{\mathsf{CNOT}}}\) gates (Equation 5 ) that the \(i\)-th \(X\) check has support on the message qubits corresponding to the \(i\)-th row of \(A\). That is, at this point, the qubits have stabilisers corresponding to \[\begin{align} {4} H_X &= (I&&|A&&|0&&)\\ H_Z &= (0&&|\,0&&|I&&). \end{align}\] Next, Step [step:encoding95B95matrix] causes \(X\) stabilisers to spread from the message qubits to the \(Z\)-check qubits, while simultaneously causing \(Z\) stabilisers to spread from the \(Z\)-check qubits onto the message qubits. In particular, the \(i\)’th \(Z\) stabiliser gains support on the message qubits corresponding to the \(i\)’th row of \(B\). Simultaneously, any single-qubit \(X\) operator on the message qubits in the support of an \(X\) stabiliser spreads to the \(Z\)-check qubits according to the columns of \(B\). Thus, after this step, the qubits are stabilised by operators described as \[\begin{align} {4} H_X &= (I&&|A&&|AB^T&&)\\ H_Z &= (0&&|B&&|\,\,\,\,I&&), \end{align}\] where arithmetic is performed in binary because \(X^2 = I\).

Finally, in Step [step:encoding95D95matrix], \(Z\) stabilisers are spread from the \(Z\)-check qubits to the \(X\)-check qubits, and \(X\) stabilisers are spread from the \(X\)-check qubits to the \(Z\)-check qubits according to the rows and columns of \(D\), respectively. Thus, at the end of the circuit, the qubits are stabilised by operators described as \[\begin{align} {4} H_X &= (\,I&&|A&&|AB^T + D^T&&)\\ H_Z &= (D&&|B&&|\,\,\,\,\,\,\,\,\,\,\,\,I&&), \end{align}\] as required, since \(C = AB^T+D^T\).

The complexity of the encoding circuit is exactly the number of \(1\)’s in the matrices \(A, B\) and \(D\), which is linear for sparse \(A, B\) and \(D\). Furthermore, for such matrices, the \(\mathop{\mathrm{\mathsf{CNOT}}}\)s can be organised into a constant number of layers, making the encoding circuit constant depth.

5.1.2 Unencoding, Stabiliser Measurement and Error Spreading↩︎

After the qubits of the code pass through the noise channel, they are unencoded and the stabilisers measured. This is performed by a circuit that inverts the encoding circuit, which may simply be achieved by running the \(\mathop{\mathrm{\mathsf{CNOT}}}\)s of the encoding circuit in the opposite order, before measuring each of the \(X\)-check qubits in the \(X\) basis, and each of the \(Z\)-check qubits in the \(Z\) basis. This is graphically depicted in Figure 8. As in Figure 6, we assign symbols to the Paulis occurring in the noise channel, so that the syndromes, i.e., the outcomes of the stabiliser measurements, are \[\begin{align} \sigma_x &= Z_x + A\cdot Z_q + C\cdot Z_z\\ \sigma_z &= D\cdot X_x + B \cdot X_q + X_z, \end{align}\] where it is understood that \(Z_x\) is both a pure-type \(Z\)-Pauli operator, and a bit string denoting the support of the Pauli operator.

At this point, we must address an issue that is a distinctly non-classical consideration: the issue of errors spreading during the unencoding circuit. This is an issue that results from the possibility of \(X\) errors occurring on the \(X\)-check qubits, and \(Z\) errors occurring on the \(Z\)-check qubits. The problem is that, after unencoding and stabiliser measurement, the errors remaining on the message qubits are not just the errors that occurred on them, \(X_qZ_q\), but errors that can spread to them in the unencoding circuit. In particular, one may check that the residual \(X\) error on the message qubits after this circuit is \[X_{Res} \coloneq A^T\cdot X_x + X_q,\] rather than simply \(X_q\), and the residual \(Z\) error on the message qubits after this circuit is \[Z_{Res} \coloneq Z_q + B^T\cdot Z_z.\] These are the errors that our error-reduction algorithms must ultimately find reduced versions of, in order to reduce the weight of the Pauli errors on the message qubits.

5.1.3 Constructing the Parity-Check Matrices from Lossless Z-Graphs↩︎

One of Spielman’s constructions of error-reduction codes [6] was based on lossless expanders (obtained via a random construction). Motivated by the need to construct quantum error-reduction codes which can reduce both \(X\)-type and \(Z\)-type errors, while handling the problem of error spreading, we make the following definition of a particular type of bipartite graph.

Given a lossless \(Z\)-graph \(G\), we construct the quantum error-reduction code corresponding to \(G\) as follows. The code has the usual parity-check matrices we take for a quantum error-reduction code, \[\begin{align} {4} H_X &= (\,I&&|A&&|C&&)\\ H_Z &= (D&&|B&&|\,I&&), \end{align}\] where \(C = AB^T+D^T\), and where

• \(A\) is a binary \(m \times n\) matrix, and is taken as the adjacency matrix of the subgraph of \(G\) obtained by restriction to \((L_1, R_2)\);

• \(B\) is a binary \(m \times n\) matrix, and is taken as the adjacency matrix of the subgraph of \(G\) obtained by restriction to \((R_1, L_2)\);

• \(D\) is a binary \(m \times m\) matrix, and is taken as the adjacency matrix of the subgraph of \(G\) obtained by restriction to \((R_2, L_2)\).

For the avoidance of doubt, the rows and columns of \(D\) correspond to the nodes in \(R_2\) and \(L_2\), respectively. A row in \(D\) corresponding to a node \(V \in R_2\) has support corresponding to the neighbours of \(V\) in \(L_2\). Notice that we could have equivalently defined \(D^T\) as the adjacency matrix of the subgraph of \(G\) obtained by restriction to \((L_2, R_2)\).

5.2 Sequential Error-Reduction Algorithms↩︎

Given a quantum error-reduction code constructed from a lossless Z-graph as above, we now describe how to perform error reduction on the \(X\) errors in Section 5.2.1, and then the \(Z\) errors in Section 5.2.2.

5.2.1 Reducing the X Errors↩︎

We now give some intuition before presenting the construction formally.

We begin by noting that the \(X\) errors are relatively easy to handle. Indeed, the input to the problem of reducing the \(X\) errors is the \(Z\)-check syndrome \[\sigma_z = D\cdot X_x + B\cdot X_q + X_z,\] and we aim to reduce the residual \(X\) error on the message qubits, \[X_{Res} \coloneq A^T\cdot X_x+X_q.\] In particular, we aim to flip bits in \(X_{Res}\) so that its Hamming weight \(|X_{Res}|\) becomes small as a function of \(X_z\).

At this point, we can notice that this just has the form of a classical error reduction problem. We have full control over our choices of \(D, B\) and \(A\), which are all the matrices appearing in the problem. The syndrome \(\sigma_z\) takes the form of a checked message bit error, \(D \cdot X_x + B \cdot X_q\) added to a check bit error \(X_z\). We can therefore get good approximations of the errors \(X_x\) and \(X_q\) (as a function of \(X_z\)) by simply taking \[H_Z = (D|B|I)\] to be the parity-check matrix for a classical error-reduction code. Indeed, when building our parity-check matrices for the quantum error-reduction code, we have taken the graph corresponding to \((D|B)\) to be a lossless expander, just with the added detail that nodes on one side of the graph can have two different degrees. It will be possible to perform error reduction of the \(X\) errors using this, in a similar manner to Spielman’s use of a (one-sided) lossless expander to construct a classical error-reduction code in [6].

It will be important, however, to take care of the issue that the degrees on one side of the graph are mixed. The reason for this will be as follows. Doing the initial error reduction will give us something like \(|X_x| \lesssim \frac{|X_z|}{\Delta_2}\) and \(|X_q| \lesssim \frac{|X_z|}{\Delta_1}\). Reducing \(X_x\) and \(X_z\) then allows us to reduce \(X_{Res}\), but the presence of \(A^T\) in the expression for \(X_{Res}\), which results from the spreading of quantum errors in the unencoding circuit, will then give us (something like) \(|X_{Res}| \lesssim \Delta_1'\frac{|X_z|}{\Delta_2} + \frac{|X_z|}{\Delta_1}\), where we recall that \(\Delta_1' = \frac{n}{m}\Delta_1\). This will be okay, as long as we eventually choose \(\Delta_2 \gg \Delta_1' \sim \Delta_1\). To be clear, both \(\Delta_1\) and \(\Delta_2\) are constants as the length of the code grows, but \(\Delta_2\) will be chosen to be a much larger constant than \(\Delta_1\).

We now describe the reduction of the \(X\) errors more formally. Our sequential error-reduction algorithm for \(X\) errors is given in Algorithm 9. In words, we imagine the errors \(X_x\), \(X_q\) and \(X_z\) as subsets of the vertices \(R_2, R_1\) and \(L_2\), respectively, connected by the graph \(G\). Because we are tackling what is fundamentally a classical error reduction problem, we refer to \(X_x\) and \(X_q\) as message bits and \(X_z\) as check bits for the purpose of discussing this algorithm.¹⁰ We also imagine the syndrome \(\sigma_z\) as a subset of the vertices \(L_2\), and refer to these as the syndrome bits. The algorithm then proceeds by flipping message bits (bits in \(X_x\) or \(X_q\)) sequentially, where at each time step we flip a bit if it is in contact with more violated syndrome bits than satisfied syndrome bits, so that the number of violated syndrome bits reduces at each time step. We continue until there are no violated syndrome bits. This allows us to construct approximations \(\tilde{X}_x\) and \(\tilde{X}_q\) to the bit strings \(X_x\) and \(X_q\). We then finish by computing the approximation \(\tilde{X}_{Res} = A^T\cdot \tilde{X}_x + \tilde{X}_q\) to \(X_{Res}\). We now analyse the runtime and performance of the algorithm.

5.2.2 Reducing the Z Errors↩︎

Initially, reducing the \(Z\) errors seems to be more problematic than reducing the \(X\) errors. The input to the \(Z\) error reduction is the \(X\) syndrome \[\sigma_x = Z_x + A\cdot Z_q + C\cdot Z_z,\] and we aim to reduce the residual \(Z\) error \[Z_{Res} = Z_q + B^T\cdot Z_z,\] where we have \[C = AB^T+D^T.\] We have direct control over the matrices \(A, B\) and \(D\), but are obliged to set \(C\) according to this equation. Thus, a direct reduction of the \(Z\) errors \(Z_q\) and \(Z_z\) (in order to calculate a reduction of \(Z_{Res}\)) using the matrices \(A\) and \(C\) (in analogy to what we do for the \(X\) errors) seems difficult. However, we are able to treat the \(Z\) errors in a fundamentally different way to the \(X\) errors. We re-write \[\begin{align} \sigma_x &= Z_x + A\cdot Z_q + (AB^T+D^T)\cdot Z_z\\ &= Z_x + A\cdot (Z_q + B^T\cdot Z_z) + D^T Z_z\\ &= Z_x + A\cdot Z_{Res} + D^T\cdot Z_z. \end{align}\] We find that the error that we ultimately want to reduce, \(Z_{Res}\), in this case sits directly under the matrix \(A\) in the syndrome \(\sigma_x\). This means that the reduction of the \(Z\) errors is also writeable in the form of a classical error reduction problem. The difference in this case is that we will directly reduce the errors \(Z_{Res}\) and \(Z_z\), instead of reducing \(Z_q\) and \(Z_z\) before calculating a reduced \(Z_{Res}\). Of course, this requires the matrices \(A\) and \(D^T\) to correspond to a classical error-reduction code, such as a lossless expander, but this is exactly what is given to us by the structure of the lossless \(Z\)-graph.

In Algorithm 10, we formally present the sequential error-reduction algorithm for the \(Z\) errors, although it is the same bit-flipping procedure as Algorithm 9, albeit applied to different vectors, and without the final calculation step. The proof of runtime and correctness of the algorithm are also essentially the same as for the \(X\) errors, and so we omit and abridge them as follows.

5.3 Parallel Error-Reduction Algorithms↩︎

We now turn to our parallel error-reduction algorithms for our quantum error-reduction codes constructed from lossless \(Z\)-graphs.

5.3.1 Parallel Reduction of X Errors↩︎

Just as with the quantum encoding circuits, the quantum unencoding circuits may be performed via a constant-depth quantum circuit with a linear number of quantum gates. Given \(X\) errors as before, the \(Z\)-check syndrome that is measured is \[\sigma_z = D\cdot X_x + B\cdot X_q + X_z,\] and the residual \(X\) error that we aim to reduce is \[X_{Res} = A^T\cdot X_x + X_q.\] Given that the graph corresponding to the matrix \((D|B)\) is a lossless expander, we may use a parallel small-set flip decoding algorithm, as Spielman does [6], but here to reduce the errors \(X_x\) and \(X_q\), before calculating a reduction of \(X_{Res}\). We will face the added complication that our lossless expander must be particularly strong in order to get a great enough reduction to overcome the problem of error spreading; in particular, we will require our lossless \(Z\)-graph to have \(\epsilon_i = \mathcal{O}(1/\Delta_i)\). This can be obtained in the randomised construction, although it is not known how to obtain explicit two-sided expanders with this property [28], and so we also do not obtain explicit lossless \(Z\)-graphs with this property. This is one key reason that our parallel algorithms are limited to the randomised construction.

Our parallel error-reduction algorithm for \(X\) errors is described formally in Algorithm 11.

5.3.2 Parallel Reduction of Z Errors↩︎

There is a further complication present for the parallel reduction of \(Z\) errors. As before, we have the measured \(X\)-syndrome \[\sigma_x = Z_x + A\cdot Z_q + C\cdot Z_z = Z_x + A\cdot Z_{Res} + D^T\cdot Z_z\] and we aim to reduce the residual \(Z\) error \[Z_{Res} = Z_q + B^T\cdot Z_z.\] Naively, we would attempt to perform the same parallel reduction to directly calculate an approximation to \(Z_{Res}\). The problem with this is that, if one does so, one ends up with (loosely speaking) \[|Z_{Res} + \tilde{Z}_{Res}| < \frac{32}{\Delta_1}\max\left(|Z_{Res}|, |Z_z| + |Z_x|\right).\] This is problematic because we can only estimate \(|Z_{Res}| \leq |Z_q| + \Delta_1\frac{n}{m}|Z_z|\), and in the worst case, our estimate would look something like \[|Z_{Res} + \tilde{Z}_{Res}| < 32\frac{n}{m}|Z_z|,\] which is not giving us error reduction at all.

To remedy this, we perform two rounds of the parallel error reduction. First, we attempt only to get an approximation to the error \(Z_z\), and in doing so we get a reduction of this error by a factor \(\sim \Delta_2\). We can use this to get an initial approximation to \(Z_{Res}\) via \(B^T\cdot Z_z\). Using this, we can then perform parallel error reduction on \(Z_{Res}\). Formally, the algorithm for reducing the \(Z\) errors in parallel is written in Algorithm 12.

We comment that, for the parallel reduction of \(Z\) errors, we require two properties of the lossless \(Z\)-graph that we may obtain from our randomised construction but not from our explicit construction. The first is the same as in the parallel reduction of \(X\) errors, that is, that the expansion of strong enough to achieve \(\epsilon_i = O(1/\Delta_i)\). The second is that, in the randomised construction, we may obtain the lossless \(Z\)-graphs for any pair of integers \(\Delta_1, \Delta_2\), which will allow us to fulfil the condition of Equation ?? . In our explicit construction of lossless \(Z\)-graphs, \(\Delta_1\) and \(\Delta_2\) are chosen to have some constant imbalance, and then taken to be large enough numbers, thus making this sort of condition hard to satisfy.

6 Lossless Z-Graphs↩︎

We now state our definition of lossless \(Z\)-graphs. In Section 6.1, we will prove their existence via a randomised procedure. In Section 6.2, we will construct them explicitly.

6.1 Random Construction↩︎

We now prove the existence of lossless \(Z\)-graphs via a simple randomised procedure.

6.2 Explicit Construction↩︎

We now prove the existence of explicit constructions of lossless \(Z\)-graphs with slightly weaker properties than the randomized construction of Theorem 3.

The remainder of this section will focus on proving 4.

6.2.1 Components↩︎

Our Z-graph will be constructed by combining a base graph and a constant size Z-gadget graph. The following was shown in [28].

The above lemma references notions of “small set neighbor expanders” and “small set skeleton expander.” We will not need to know what these mean, though the curious reader may refer to [28] for details.

Let \(\beta \in \bbN\) and let \(G = (V, M)\) be a bipartite graph. We will be concerned with properties of the \(\beta\)-duplication of \(G\), which is the graph on vertex sets \(V' = V_1 \cup \dots \cup V_\beta\) and \(M'\), where \(M' = M\), each \(V_i\) is a copy of \(V\), and each graph \(G'[V_i, M]\) is a copy of \(G\).

The proof of 6 is straightforward from the definitions.

6.2.1.1 The base graph.

We are now ready to define our base graph. For \(k\) a power of \(2\) and sufficiently large \(D' \in \bbN\), let \(G' = (V', M')\) be the structured \((k',D')\)-biregular bipartite graph guaranteed in 7. Our base graph \(G\) consists of five vertex sets, \(L_1, L_2, M, R_1, R_2\). The graphs \(G[L_1, M]\) and \(G[R_1, M]\) are \(\beta_1\)-duplications of \(G'\), and the graphs \(G[L_2, M]\) and \(G[R_2, M]\) are \(\beta_2\)-duplications of \(G'\). That is, \(L_1 = L_{1,1} \cup \dots \cup L_{1,\beta_1}\) and \(R_1 = R_{1,1} \cup \dots \cup R_{1,\beta_1}\) each consist of \(\beta_1\) copies of \(V'\), where each \(G[L_{1,i}, M]\) and \(G[R_{1,i}, M]\) is a copy of \(G'\), and \(L_2 = L_{2,1} \cup \dots \cup L_{2,\beta_2}\) and \(R_2 = R_{2,1} \cup \dots \cup R_{2,\beta_2}\) each consist of \(\beta_2\) copies of \(V'\), where each \(G[L_{2,i}, M]\) and \(G[R_{2,i}, M]\) is a copy of \(G'\).

The following is a corollary of 7, 6, and 7.

6.2.1.2 The Z-gadget graph.

To go with our base graph, we will want a gadget graph \(\calH\) on vertex sets \(Y_1 \cup Y_2 \cup Z_1 \cup Z_2\), where \(Y_1 = Z_1 = [D_1]\) and \(Y_2 = Z_2 = [D_2]\), that has edges between only parts \(Z_1\) and \(Y_2\), \(Y_2\) and \(Z_2\), and \(Z_2\) and \(Y_1\). We will also need \(\calH\) to respect the special sets of the base graph. The existence of such a gadget graph is given in the following lemma, proven in 6.2.4.

6.2.2 Our Expanding Z-Graph↩︎

For \(\eps \in (0, 1)\), integers \(\beta_1, \beta_2 \in \bbN\), and constant \(\alpha > 0\), let us pick \(k \ge 16/\eps^2\) to be a power of \(2\), and let us choose \(\delta \in (0, 1)\) and large enough \(d_1, d'_1, d_2, D_1, D_2 \in \bbN\) such that \(\beta_1 d_1 = \beta_2 d'_1\), \(d_2 \in (1 \pm 0.001) \alpha \cdot d_1\), \(D^{-1/16} \le \delta \le o_D(1) \cdot \frac{1}{k^2}\), and \(\frac{D^{1/4} \log^2 D}{\delta} \le d_1, d'_1, d_2 \le \frac{\delta D^{3/8}}{\log D}\), where \(D := D_1 + D_2\).

Let \(G\) be a base graph on vertex set \((L_1, L_2, M, R_1, R_2)\) as given in 8 such that \(G[L_1, M]\) and \(G[R_1, M]\) are \((k, D_1)\)-biregular structured bipartite graphs, and \(G[L_1, M]\) and \(G[R_2, M]\) are \((k, D_2)\)-biregular structured bipartite graphs. We have that \(G[L_1, M], G[L_2, M], G[R_1, M], G[R_2, M]\) are \(O(D^{5/8})\)-small-set \(2\sqrt{k}\)-neighbor expanders. Let \(\calH\) be a Z-gadget graph on vertex sets \((Y_1, Y_2, Z_1, Z_2)\) as given in [lem:Zgadget] such that \(Y_1 = Z_1 = [D_1]\), \(Y_2 = Z_2 = [D_2]\), and the subgraphs \(\calH[Y_1, Z_2]\) and \(\calH[Z_1, Y_2]\) are \((d_1, d'_1)\)-biregular graphs, and the subgraph \(\calH[Y_2, Z_2]\) is a \((d_2, d_2)\)-biregular graph. \(\calH\) also satisfies spread w.r.t. the special sets of \(G[R_2, M]\) and \(G[L_2, M]\).

We define our graph \(\calG\) as follows:

• \(\calG\) is on vertex sets \((L_1 \cup L_2, R_1, \cup R_2)\).

• For each \(u \in M\), we place a copy of \(\calH = (Y_1, Y_2, Z_1, Z_2; E_H)\) on the vertex sets \((N^G_{L_1}(u), N^G_{L_2}(u), N^G_{R_1}(u),\) \(N^G_{R_2}(u))\), where the bijection of the sets \(Y_i\) to \(N^G_{L_i}(u)\) and \(Z_i\) to \(N^G_{R_i}(u)\) are given by the orderings of the neighbors of \(u\) ([property:nbr]). We let this copy of \(\calH\) on the neighbors of \(u \in M\) be denoted \(\calH_u\). The edges of \(\calG\) are all the edges from the union of all the \(\calH_u\), \(u \in M\).

Note that each vertex in \(L_1 \cup L_2 \cup R_1 \cup R_2\) has exactly \(k\) neighbors in \(M\) in \(G\), so they each partake in exactly \(k\) different copies of \(H\). Thus \(\calG[Y_1, Z_2]\) and \(\calG[Z_1, Y_2]\) are \((\Delta_1, \Delta'_1)\)-biregular bipartite graphs, where \(\Delta_1 = k d_1\) and \(\Delta'_1 = k d'_1\), and \(\calG[Y_2, Z_2]\) is a \((\Delta_2, \Delta_2)\)-biregular bipartite graph, where \(\Delta_2 = k d_2\). We also let \(n = |L_1| = |R_1| = \beta_1 \cdot \frac{q(q^2-1)D'}{2}\) and \(m = |L_2| = |R_2| = \beta_2 \cdot \frac{q(q^2-1)D'}{2}\). Notice that \(\frac{n}{m} = \frac{\beta_1}{\beta_2}\).

6.2.3 Analysis↩︎

The proof that \(\calG\) satisfies the properties in 4 follows via a slight (and simple) modification of the proof of lossless expansion in [28]. In what follows, we give a proof sketch of 4, referring the reader to [28] for proofs of the claims.

Let us focus on showing expanion from subsets of \(L_1 \cup L_2\) to \(R_2\), as the \(R_1 \cup R_2 \rightarrow L_2\) case is identical. Fix \(S_1 \subseteq L_1\), \(S_2 \cup L_2\), so that \(|S_1|, |S_2| \le \eta D\). We will show that \(|N_{R_2}(S_1 \cup S_2)| \ge (1-\eps) (\Delta_1 |S_1| + \Delta_2 |S_2|)\).

Let \(U \subseteq M\) be the neighbors of \(S_1\) and \(S_2\) in the graph \(G\). We split \(U\) into its “high degree” part \(U_h := \{ u \in U : \deg_{G[S_1 \cup S_2, U]}(u) \ge \frac{\tau}{\delta} \}\) and its “low degree” part \(U_\ell := U \backslash U_h\). Here, \(\tau = \tau_1 + \tau_2\), where \(G[L_1, M]\) and \(G[L_2, M]\) are \(\tau_1\) and \(\tau_2\)-small-set \(2\sqrt{k}\)-neighbor expanders, respectively, and \(\tau_1, \tau_2 = O(D^{5/8})\). It happens that \(\frac{\tau_1}{\tau_2} = \frac{\beta_1}{\beta_2}\), so the precise setting of \(\tau\) is not important, only that it captures the asymptotic size of \(\tau_1, \tau_2\).

The first step is to show that most of the edges from \(S_1\) and \(S_2\) to \(U\) in fact point to \(U_\ell\).

The proof of this claim is identical to Claim 2.10 in [28] so we omit it. It relies only on the fact that \(G[L_i, M]\) is a \(\tau_i\)-small-set \(2\sqrt{k}\)-neighbor expander. Essentially, this claim says that most edges in \(G\) coming out of \(S_1\) and \(S_2\) point to low-degree middle vertices, whose gadgets experience good expansion into \(R_2\).

By the choice of the threshold, we have \(\frac{\tau}{\delta} \le o_D(1) \cdot \frac{D_2}{d_1 + d_2}\), and hence if we inspect the gadget \(\calH_u\) around \(u \in U_\ell\), letting \(S_1(u) := \Nbr^{G[L_1, M]}_u(N^G_{S_1}(u)) \subseteq Y_1\) and \(S_2(u) := \Nbr^{G[L_2, M]}_u (N^G_{S_2}(u)) \subseteq Y_2\), it holds that \(|N^{\calH_u}_{Z_2}(S_1(u) \cup S_2(u))| \ge (1 - o_D(1)) (d_1 |S_1(u)| + d_2 |S_2(u)|)\). In particular, this implies that \[\begin{align} e(\RED(S_1 \cup S_2)) &\ge \sum_{u \in U_\ell} (1 - o_D(1)) (d_1 |S_1(u)| + d_2 |S_2(u)|) \\ &= (1 - o_D(1)) \cdot \left( d_1 \cdot e_{G}(S_1, U_\ell) + d_2 \cdot e_G(S_2, U_\ell) \right) \\ &\ge (1 - o_D(1)) (1 - \sqrt{\delta} - 2k^{-1/2}) \cdot (d_1 \cdot e_G(S_1, U) + d_2 \cdot e_G(S_2, U)). \end{align}\]

The remainder of the argument is to show that there are very few collisions between the neighborhoods of different gadgets, so that most of the \(\RED\) edges are actually going to distinct elements of \(R_2\).

We construct the collision graph \(C\) — the multi-graph \(C\) on vertex set \(U \subseteq M\) by placing a copy of the edge \(\{u,v\}\) for each \(u \neq v \in U\), and \(r\in R_2\) such that \(\{u,r\}\) and \(\{v,r\}\) are red edges in \(\RED\). The number of neighbors of \(S_1 \cup S_2\) in \(R_2\) in the final product \(\calG\) is at least \[\begin{align} e(\RED) - e(C), \end{align}\] since a vertex \(v \in R_2\) with degree \(d_v\) in \(\RED\) contributes one neighbor, but it is counted \(d_v\) times in \(e(\RED)\) and \(\binom{d_v}{2}\) times in \(e(C)\), and \(d_v - \binom{d_v}{2} \leq 1\) for all \(d_v \in \bbN\).

The proof of this claim is analogous to the proof of Claim 2.13 in [28], so we omit it here. It relies on the graph \(G[R_2, M]\) being a \(O(D^{1/4})\)-small-set skeleton expander.

Now, to finish up the proof of 4, we have that for \(\delta \le o_D(1) \cdot \frac{1}{k^2}\) and \(k \ge 16/\eps^2\), \[\begin{align} e(\RED(S_1 \cup S_2) &\ge (1 - o_D(1)) (1 - \sqrt{\delta} - 2k^{-1/2}) \cdot (d_1 \cdot e_G(S_1, U) + d_2 \cdot e_G(S_2, U)) \\ &\ge (1-\eps/2) \cdot k(d_1 |S_1| + d_2|S_2|) \\ &= (1-\eps/2) \cdot (\Delta_1 |S_1| + \Delta_2 |S_2|). \end{align}\] The number of neighbors of \(S_1 \cup S_2\) in the final graph \(\calG\) is at least \(e(\RED(S_1 \cup S_2)) - e(C)\), and from 2 we have that \(e(C) \le o_D(1) \cdot (\Delta_1 |S_1| + \Delta_2 |S_2|)\). Thus, choosing \(D_1, D_2\) large enough, we have that \[|N_{R_2}(S_1 \cup S_2)| \ge (1 - \eps) \cdot (\Delta_1 |S_1| + \Delta_2 |S_2|).\] The proof for expansion from \(R_1 \cup R_2\) to \(L_2\) is identical.

6.2.4 The Existence of Good Z-Gadget Graphs↩︎

In this section, we prove [lem:Zgadget], restated below.

Define a distribution \(\calG_{D_1,D_2,d_1,d'_1,d_2}\) of random graphs as follows. We will show that a random graph sampled from \(\calG_{D_1,D_2,d_1,d'_1,d_2}\) will with high probability satisfy both expansion and spread as stated in [lem:Zgadget]. We start with spread.

6.2.4.1 Spread.

Showing that a random graph sampled from \(\calG_{D_1,D_2,d_1,d'_1,d_2}\) satisfies spread is a simple corollary of the following lemma from [37].

Let us apply 9 to the random graphs \((Y_1, Z_2)\) and \((Y_2, Z_2)\) sampled in \(\calG_{D_1,D_2,d_1,d'_1,d_2}\) and to the partitionings \((\calZ_i^{a,b})_{i \in [s(a,b)]}\). We obtain that with probability \(1 - \Theta(k^2/D)\), for all \(A_1 \subseteq Y_1\) and \(A_2 \subseteq Y_2\) and all \(W \subseteq [s]\) with \(|W| \ge \frac{s \log D}{\min \{ d_1, d_2 \}}\), \[\begin{align} \sum_{i \in W} |N_{Z_2}(A_1 \cup A_2) \cap \calZ_i^{a,b}| &\le \sum_{i \in W} |N_{Z_2}(A_1) \cap \calZ_i^{a,b}| + \sum_{i \in W} |N_{Z_2}(A_2) \cap \calZ_i^{a,b}|\\ &\le 32 |W| \cdot \max \left\{ \frac{d_1}{s} |A_1|, \log D \right\} + 32 |W| \cdot \max \left\{ \frac{d_2}{s} |A_2|, \log D \right\} \\ &\le 64 |W| \cdot \max \left\{ \frac{d_1 |A_1| + d_2 |A_2|}{s}, \log D \right\}, \end{align}\] as desired. The analogous statement for sets in \(Z_1 \cup Z_2\) expanding to \(Y_2\) follows via the exact same proof.

6.2.4.2 Expansion.

To show expansion, we will follow the outline given in [38]. We first show the desired statement for the appropriate mixture of Erdős-Renyi graphs, and then transfer the result to the mixed-regular random graphs that we are sampling from.

The Erdős-Renyi type distribution of graphs we consider is the following, denoted \(\calE_{D_1,D_2,p_1,p_2}\).

Now that we know that with high probability a random graph sampled from \(\calE_{D_1,D_2,p_1,p_2}\) satisfies the property of expansion, we’d like to say that the same thing holds for random graphs sampled from \(\calG_{D_1,D_2,d_1,d_1',d_2}\). To do this, we will use the following theorem stating that a random Erdős-Renyi graph is with high probability a subset of a slightly larger regular graph. The point is that this allows us to argue that the slightly larger regular graph inherits the properties of the Erdős-Renyi graph. For us, we will apply this theorem to the graphs on \((Y_1, Z_2)\), \((Z_1, Y_2)\), and \((Y_2,Z_2)\) to show that with high probability a random graph sampled from \(G_{D_1,D_2,d_1,d_1',d_2}\) contains a random graph sampled from \(\calE_{D_1,D_2,p_1,p_2}\).

Applying Theorem 5 to the graphs \((Y_1, Z_2)\), \((Z_1, Y_2)\), and \((Y_2, Z_2)\), we obtain the following corollary:

Now, let us finish off the proof of expansion for a random graph sampled from \(\calG_{D_1,D_2,d_1,d'_1,d_2}\). Let \(\gamma = o_D(1)\) satisfy the bounds in 1, and let \(p_1 = \frac{(1-\gamma)d_1}{D_2}\) and \(p_2 = \frac{(1-\gamma)d_2}{D_2}\). Sample \((E, G)\) from the joint distribution of \(\calE_{D_1,D_2,p_1,p_2}\) and \(\calG_{D_1,D_2,d_1,d'_1,d_2}\) as given by 1. With probability \(1-o(1)\), \(E \subset G\). Furthermore, by 10, with probability \(1-O(1/D)\), \(E\) satisfies the property that for all \(A_1 \subseteq Y_1, A_2 \subseteq Y_2\), \[\begin{align} |N_{Z_2}(A_1 \cup A_2)| &\ge (1 - \eps_{|A_1|,|A_2|}) \cdot (p_1|A_1| + p_2|A_2|) D_2 \\ &= (1 - \eps_{|A_1|,|A_2|})(1-\gamma) \cdot (d_1|A_1| + d_2|A_2|) \\ &\ge (1 - \gamma - \eps_{|A_1|,|A_2|}) \cdot (d_1|A_1| + d_2|A_2|) \\ &\ge \left( 1 - \gamma - \frac{d_1|A_1| + d_2|A_2|}{D_2} - \sqrt{\frac{4\log D}{(1-\gamma) \min \{ d_1, d_2 \}}} \right) \cdot (d_1|A_1| + d_2|A_2|) \\ &=: (1 - \eps) \cdot (d_1|A_1| + d_2|A_2), \end{align}\] thus because \(E \subset G\) the same bound holds for \(G\) as well. Further, with probability \(1 - O(1/D)\), the same bound holds for subsets of \(Z_1 \cup Z_2\) expanding to \(Y_2\). For \(d_1|A_1| + d_2|A_2| \le \mu |D_2|\) where \(\mu = o_D(1)\), and \(d_1,d_2 = \omega(\log D)\), \(\eps = o_D(1)\).

7 Putting it All Together↩︎

In this section, we briefly summarise how our results may be put together to prove our main results, Theorems 1 and 2. The main aim here is to confirm that the various parameters may be chosen of the correct size and in the correct order to ensure each required condition is satisfied.

Acknowledgements↩︎

AW acknowledges inspiring discussions with L. Golowich. AW acknowledges funding from NSF grant PHY-2325080. AW acknowledges funding from the MIT-IBM Watson AI Lab. AW acknowldges support from the MIT Department of Physics. This preprint is assigned number MIT-CTP/5994.

TCL is supported in part by funds provided by the U.S. Department of Energy (D.O.E.) under cooperative research agreement DE-SC0009919, and by the Simons Collaboration on Ultra-Quantum Matter, which is a grant from the Simons Foundation (652264, JM).

RYZ is supported by a Schwarzman College of Computing Future Research Fellowship with support from Google.

References↩︎

---

1. Center for Theoretical Physics — a Leinweber Institute, Massachusetts Institute of Technology, Cambridge, MA;
   Hon Hai (Foxconn) Research Institute, Taipei, Taiwan. Email: a_wills@mit.edu↩︎

2. Department of Physics, University of California at San Diego, La Jolla, CA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan. Email: til022@ucsd.edu↩︎

3. CSAIL, Massachusetts Institute of Technology, Cambridge, MA. Email: rachelyz@mit.edu↩︎

4. Hon Hai (Foxconn) Research Institute, Taipei, Taiwan. Email: min-hsiu.hsieh@foxconn.com↩︎

5. The error-reduction code \(\mathcal{R}\) will technically be some family of error-reduction codes, but we omit these details for this high-level description.↩︎

6. Formally, this would mean that we perform a \(\mathop{\mathrm{\mathsf{CNOT}}}\) gate from the \(i\)’th \(X\)-check qubit to the \(j\)’th message qubit for every \((i,j) \in [m]\times [n]\) for which \(A_{ij} = 1\), and similarly for \(B^T\).↩︎

7. Note that in Figure 2, the encoding circuit is inverted simply by running the \(\mathop{\mathrm{\mathsf{CNOT}}}\)s after the Pauli noise in the opposite order to the \(\mathop{\mathrm{\mathsf{CNOT}}}\)s before the Pauli noise.↩︎

8. Note that the condition \(R>0\) enforces that \(r^{(1)} > 1/2\), and thus that \(n_k \to \infty\) as \(k \to \infty\).↩︎

9. Note that this might seem strange, because the use of the error-reduction algorithms here is not proceeded by a quantum measurement, but is simply input some classical bit strings \(\sigma_{x,i}\) and \(\sigma_{z,i}\) of the form of Equation 7 and 8 . However, the error-reduction algorithm is exactly a classical algorithm taking input of this type and, given guarantees on the size of the bit strings \(Z_k, Z_{i-1}^{(x)}, Z_{i-1}^{(x)}, X_i, X_{i-1}^{(x)}\) and \(X_{i-1}^{(z)}\), outputs approximations to \(Z_i\) and \(X_i\) that are guaranteed to reduce their size.↩︎

10. This is not to be confused with the language used more broadly in the paper, where the qubits on which \(X_q\), \(X_x\) and \(X_z\) are supported are called, respectively, message qubits, \(X\)-check qubits, and \(Z\)-check qubits.↩︎