2

Introduction

Is it possible that a decoder for a quantum code could return not only a most-likely correction, but also some quantification of the likelihood of a logical error having occurred? If so, it would be possible to post-select (reject) suspicious decoding instances, in exchange for a lower logical error rate on surviving shots. For the surface code [1], this is known to be readily possible by computing a complementary gap [2]–[5], a confidence measure comparing the log-likelihoods of the most-likely correction and a logically complementary one. High-rate quantum low-density parity check (LDPC) codes [6] can offer a greatly improved space overhead over the surface code, although one (of several) practical challenges for LDPC codes is that post-selection strategies based on complementary gaps do not directly apply to them. Despite this, recent works [7], [8] have initiated the development of such strategies.

In this work, we develop a new idea for post-selection applicable to high-rate quantum LDPC codes. At its core, this idea is a simple extension of the complementary gap strategy for surface codes to situations where many logical observables are present. We benchmark our post-selection strategy using the Relay-BP decoder [9] on bivariate bicycle (BB) codes, namely idling circuits for the \(72\)-qubit code and the \(144\)-qubit “gross” code [10], as well as logical operations for the latter constructed via LDPC code surgery in [11].

Problem Setup

In the surface code, the complementary gap for a given logical observable is the log-likelihood difference between the most-likely correction and the most-likely correction consistent with the complementary logical outcome for that observable. A small complementary gap indicates little difference in likelihoods between these two outcomes, implying a high probability of a logical error. It is computed as follows. Treating \(X\) and \(Z\) errors separately, one first performs a standard decode with a matching decoder to obtain the most-likely correction. Then, the decoding instance is re-run while being forced to produce a correction with the complementary logical outcome; for the \(X\) observable, for example, the sum of the two corrections is required to be a logical \(X\) operator. In the surface code, this modified decoding instance is still matchable and so may be efficiently solved. The log-likelihood difference between the two solutions gives the complementary gap.

The complementary gap technique does not extend immediately to general quantum LDPC codes for two important reasons. First, general quantum LDPC codes cannot be decoded by matching decoders. Second, circuits corresponding to high-rate quantum LDPC codes have many observables, rendering naïve comparative decoding of complementary logical classes infeasible. For example, a code with \(k\) logical qubits would have \(4^k\) distinct logical classes, even in an idling circuit. Even for relatively simple quantum LDPC codes such as the \(72\) and \(144\)-qubit BB codes, one has \(k = 12\), and so attempting to decode a most-likely correction in each logical class would be infeasible. In this work, we develop an efficient analogue that overcomes both obstacles, extending the complementary gap idea to general quantum LDPC codes with many logical observables.

Methods

We describe decoding problems using a parity-check matrix \(H \in \mathbb{F}_2^{M \times N}\), action matrix \(A \in \mathbb{F}_2^{K \times N}\), and prior probability vector \(p\in[0,1/2)^N\).² This represents a decoding problem with \(N\) possible errors, \(M\) detectors, and \(K\) logical observables.³ Given a decoding problem, a decoding instance is specified by an observed syndrome \(\sigma \in \mathbb{F}_2^M\) and an unobserved fault configuration \(f\in\mathbb{F}_2^N\) satisfying \(H\cdot f=\sigma\).

The decoder’s job is to find a correction \(e\) such that \(H\cdot e=\sigma\) with a successful decode characterised by \(A\cdot e=A\cdot f\), meaning the logical observables corrupted by faults \(f\) have been corrected by \(e\). A reasonable way to frequently decode successfully is to choose a correction that has a large likelihood \(\mathbb{P}[e]=\prod_{j=1}^N(1-p_j)^{1-e_j}p_j^{e_j}\) of having occurred given the syndrome. Decoders may attempt to do this heuristically [9], [14], [15] or exactly [13], [16].

We motivate our post-selection strategy by considering what is possible if we had the ability to perform maximum-likelihood decoding (MLD), including the ability to calculate the likelihood of the most-likely logical error class. Though what we describe in this thought experiment is computationally infeasible in practice, it motivates our actual proposal which replaces certain steps with more practical computations approximating the MLD version.

As a quick review, MLD maximises the likelihood of a successful correction by returning a correction from the most-likely logical class \(\lambda^*=\mathrm{argmax}_{\lambda\in\mathbb{F}_2^K}\mathbb{P}_L[\lambda]\), where \(\mathbb{P}_L[\lambda]:=\sum_{e\in\mathbb{F}_2^N}\mathbb{P}[e]\mathbb{1}\left[H\cdot e=\sigma\right]\mathbb{1}\left[A\cdot e=\lambda\right]\) is the probability of logical class \(\lambda\) and syndrome \(\sigma\). We assume MLD returns \(\mathbb{P}_L[\lambda^*]\) as well as a correction.

To define a post-selection strategy, our goal is to calculate \[\mathrm{Exact\;Gap}:=\log\mathbb{P}_L[\lambda^*]-\log\mathbb{P}_L[\lambda^{**}],\] where \(\lambda^{**}\) is the second most-likely logical class. The Exact Gap is a natural generalisation of the complementary gap to many logical observables: rather than comparing the most-likely correction with a single logically complementary one, it compares the two most-likely logical classes overall. It is a reasonable measure of decoding confidence; if it is small, then the most-likely logical class and the second most-likely have similar likelihoods, and our confidence in a successful decode should be low. For instance, a post-selection threshold \(T\) can be imposed and decoding instances thrown out if their Exact Gap is below \(T\). To calculate the Exact Gap, we can use MLD directly to get the first term \(\log\mathbb{P}_L[\lambda^*]\) and, as we argue now, \(K\) instances of MLD on modified problems to get the second term \(\log\mathbb{P}_L[\lambda^{**}]\).

The second most-likely logical class \(\lambda^{**}\) must differ from the most-likely class \(\lambda^*\) in at least one of its \(K\) bits. If we write \(\lambda^{*i}\) to indicate the most-likely logical class of those classes differing from \(\lambda^*\) in the \(i\)’th bit, then \(\mathbb{P}_L[\lambda^{**}]=\max_{i=1,\dots,K}\mathbb{P}_L[\lambda^{*i}]\), reducing the calculation of \(\mathbb{P}_L[\lambda^{**}]\) to the calculation of each of \(\mathbb{P}_L[\lambda^{*i}]\).

To calculate \(\mathbb{P}_L[\lambda^{*i}]\), set up a modified decoding problem in which the \(i\)’th row of \(A\) is appended to the bottom of the parity-check matrix \(H\) to get a modified matrix \(H^{(i)}\). The syndrome is also modified by appending a bit \(1-\lambda^{*}_i\) to \(\sigma\) to get vector \(\sigma^{(i)}\). MLD finds a correction \(e^{(i)}\) with some logical class \(L^{(i)}=A\cdot e^{(i)}\) and consistent with the syndrome, \(H^{(i)}\cdot e^{(i)}=\sigma^{(i)}\). By construction of \(H^{(i)}\), this latter vector equality enforces exactly \(H\cdot e^{(i)}=\sigma\) and \(L^{(i)}_j=1-\lambda^{*}_i\) (from the last row of \(H^{(i)}\)). Thus, by running MLD on the modified decoding instance \((H^{(i)},A,p,\sigma^{(i)})\), we obtain a correction from \(L^{(i)}=\lambda^{*i}\) and also the according value of \(\mathbb{P}_L[\lambda^{*i}]\). Doing this for all \(i=1,\dots,K\), we complete the calculation of Exact Gap. Notably, this computation required much fewer than the naïve \(2^K\) decoding invocations: just 1 invocation on the baseline problem plus \(K\) invocations on modified problems.

In practice, we do not have access to MLD or to the exact calculation of the logical class likelihoods \(\mathbb{P}_L[\lambda]\). Instead, for our post-selection strategy, we assume a decoder that operates on arbitrary \((H,A,p,\sigma)\) decoding instances but also allow the decoder to “give up" when it is unable to return any valid correction.⁴ Such”un-converged runs” are part of the nature of purely iterative decoders like BP or Relay-BP [9], and so we accommodate that potential behavior within our general post-selection framework. Our method for developing a post-selection strategy (illustrated in Fig. 1) is as follows. Given a decoding instance, we begin by running the chosen decoder as normal in what is called the baseline run. Provided the baseline run converged to some valid solution \(e^{(0)} \in \mathbb{F}_2^N\), its logical class is calculated as \(L^{(0)} \coloneq A\cdot e^{(0)}\). Then, \(K\) further runs of the decoder take place. These are called the \(K\) forced runs. In the \(i\)’th forced run, the decoder is forced to find a correction \(e^{(i)}\in \mathbb{F}_2^N\) where the \(i\)’th observable has the complementary logical outcome compared to \(L\), or, in other words, the \(i\)’th bit of \(L^{(i)} \coloneq A\cdot e^{(i)}\) differs from the \(i\)’th bit of \(L^{(0)}\). This is done by running the decoder on the modified decoding instance \((H^{(i)},A,p,\sigma^{(i)})\) defined previously.

Across the baseline and all forced runs that converged on some solution, every candidate correction has its logical class recorded, but only some of these are distinct. The set of distinct logical classes found is denoted by \[\Lambda = \{\lambda^{(0)}, \lambda^{(1)}, \ldots\}, \text{ where } \lambda^{(j)} \in \mathbb{F}_2^K,\] and each of these classes is associated with likelihoods \[\mathbb{P}\left[\lambda^{(j)}\right]:=\max_{i:\, L^{(i)} = \lambda^{(j)}}\left\{\,\mathbb{P}[e^{(i)}] \right\}\] (the likelihood of the most-likely correction found with that logical class). We order the set \(\Lambda\) by decreasing likelihood so that \(\mathbb{P}[\lambda^{(0)}]\ge\mathbb{P}[\lambda^{(1)}]\ge\dots\).

We then define the gap to be the difference in log-likelihoods of the two most-likely logical classes, that is, \[\text{Gap} \coloneq \log\;\mathbb{P}\left[\lambda^{(0)}\right] - \log\;\mathbb{P}\left[\lambda^{(1)}\right].\] The Gap is our practical analogue of the complementary gap: it approximates the Exact Gap by using the likelihoods of specific decoder-found corrections rather than exact logical-class probabilities. In the case that all forced runs were un-converged, so \(\Lambda\) is a set of size one and \(\lambda^{(1)}\) does not exist, we choose to set \(\text{Gap} = \infty\). If the baseline run was itself un-converged, \(\Lambda\) is empty and we choose to set \(\text{Gap}=0\). In this case, the decoding instance is termed an “erasure”.⁵

We create a family of post-selection strategies, named the forced gap strategies, by picking a threshold \(T \in \mathbb{R}_{\geq 0}\). Decoding instances are then rejected if the gap was found to be less than \(T\). Succinctly, \[\begin{gather} \text{Forced Gap }(T) = \left[\text{Reject if Gap}\; < \;T\right]. \end{gather}\] There is no post-selection when \(T=0\), and erasure events are considered logical errors. In contrast, erasures are always rejected when \(T\) is positive, since then \(\text{Gap} = 0\) by convention. Moreover, non-erasure instances where all forced runs were un-converged are always accepted, since then \(\text{Gap} = \infty\) by convention.

At first, running \(K\) forced runs might seem computationally daunting, although note that the forced runs may be run in parallel. Additionally, the total amount of computation scales linearly with \(K\), giving the same amount of computation if the same logical information were encoded in (multiple) low rate codes, like surface codes.

Before moving on, we note that if a single run of the decoder finds multiple valid corrections per decoding instance, possibly logically distinct from one another, these can all be used to create the set of logical classes \(\Lambda\), improving the forced gap strategy. Relay-BP, for example, explicitly has a parameter denoting the number of solutions it should find before terminating a single decoding instance (see Appendix 1 for brief review of Relay-BP), and we indeed use all solutions in our simulations.

Results

As mentioned, we instantiate our “forced gap” post-selection strategy with the Relay-BP decoder [9], primarily because it provides strong performance, while being fast and suitable for FPGA implementation [17], [18]. While convergence is not guaranteed, we find in testing that Relay-BP converges often enough on the forced runs to make forced gap post-selection work well.

We test forced gap post-selection on the \(72\) and \(144\)-qubit BB code memories [10], and on surgery constructions for the latter from [11], all under the the circuit depolarizing noise model common to both those prior works. It is known that a careful choice of memory parameters for the Relay-BP decoder can dramatically improve its error correction performance [9], and so for each circuit tested we optimise those parameters over an initial sweep for logical error rate (with no post-selection) before testing forced gap post-selection with those values. The choices of memory parameters, and other parameter choices for Relay-BP, are included in Appendix 1. Otherwise, our testing uses the implementation of Relay-BP as in [19].

The performance of forced gap post-selection on idling circuits is shown in Figure 2. In both cases, very few erasure shots were found, but for the \(72\)-qubit code, a noticeable number of non-erasure shots were found with exactly \(\mathrm{Gap} = 0\), which we always post-select for \(T>0\). This explains the space between the (black) “no post-selection” line, and the left-hand end of the (blue) post-selection curve there. In both cases, once all shots with finite gap are post-selected, the curve remains flat thereafter; what remains at this point are shots with \(\mathrm{Gap} = \infty\) in which the baseline run found a solution but all forced runs did not converge. We see that Forced Gap performs well at reducing logical error rate with a minimal amount of post-selection, but does not continue to get better performance at post-selection rates much above \(1\%\) for these idling circuits. With that said, for many post-selection use cases, like resource generation protocols, a post-selection rate of greater than \(1\%\) may not be of interest.

Next, we present results for LDPC surgery circuits on the \(144\)-qubit BB code. Here, the circuits we tested are constructed using the methodology of [11], with one exception. As explained in that paper, the surgery circuits proceed via an initialisation and merging of the ancilla system with the code, a certain number of rounds of syndrome extraction in the merged system, and finally a splitting of the ancilla system with the code. In principle, the optimal number of rounds of syndrome extraction in the merged system should be \(d_{\text{Circ}}\), the circuit distance, to balance the effects of errors in spacetime (\(d_{\text{Circ}} = 10\) for all circuits considered here). On the other hand, it is possible that a number of rounds of syndrome extraction slightly above, or slightly below \(d_{\text{Circ}}\), could lead to an improved logical error rate [20]. After optimising the memory parameters for a given surgery operation, we then attempt to optimise the number of rounds of syndrome extraction to improve the logical error rate without post-selection. We find, however, that a number of rounds of syndrome extraction equal to the circuit distance is essentially optimal in all cases, with only very slight differences. We list the number of rounds of syndrome extraction used for each gadget with the corresponding figure.

In Figure 3, we present the results for the forced gap strategy on the in-module \(X_1\), in-module \(Y_1\), and inter-module \(X_1X_1\) surgery instructions on the gross code [11], all at physical noise \(p = 2.5\times 10^{-3}\). We see that the strategy continues to offer good performance on these logical instructions, with the post-selection curve flattening out around \(1\%\) once again. For the in-module \(X_1\) and inter-module \(X_1X_1\) instructions, there is noticeable space between the left edges of the (blue) post-selection curve, and the (black) line showing the error rate with no post-selection. Interestingly, the reason for this space is different to the reason on the \(72\)-qubit code at idling (see Figure 2). On the \(72\)-qubit code, there were very few erasure shots, but a larger number of non-erasure shots with exactly \(\mathrm{Gap} = 0\). Here, there are a larger number of erasure shots, and very few non-erasure shots with exactly \(\mathrm{Gap} = 0\).

Relation to Prior Works

The last few months have seen a notable amount of work done on post-selection strategies for quantum LDPC codes. First was [7], based on clustering decoders, which inspired us to pursue this work. While preparing this work, [8] appeared, and very recently also [21]. [8] offers a similar level of generality to ours, and is philosophically quite similar, where instead of “forced runs” (in which a logically distinct solution is forced of the decoder), the decoder is re-run with the physical likelihood of the initial correction suppressed. The primary focus of [21] is not to develop post-selection strategies, although it is shown that accurate and well-calibrated post-selection is possible using their neural decoder (see Figure 5 therein).

Both [7] and [8] also test their strategies within the sliding-window framework, which is an important component of ultimately obtaining real-time and scalable decoding. One case not considered by the three works mentioned is testing the strategies on the logical instructions of high-rate codes, which is an important step towards their applicability to offline state preparation tasks like magic state distillation.

As for the performance of the various schemes, the only common point of comparison is the \(72\)-qubit code at physical noise \(p = 1\times 10^{-3}\) (we test other circuits at higher physical noise). At the highest level of post-selection that it gets to, \(1\%\), the forced gap strategy achieves a logical error rate per round of around \(3.5 \times 10^{-8}\). By comparison, [7] achieves around \(10^{-5}\), and [8] around \(1.5\times10^{-7}\).⁶⁷ We see that forced gap post-selection can offer significant improvements. With this said, both of those other strategies can continue to offer improvements at higher rates of post-selection than \(1\%\). In particular, whereas our strategy does not improve above its \(1\%\) post-selection rate value of \(3.5\times 10^{-8}\), [7] surpasses it at a post-selection rate of about \(30\%\), and [8] improves on it at a post-selection rate of about \(5\%\), although note that the latter uses repeated runs of a heavy-duty BP-OSD decoder [22]. One might draw the conclusion that forced gap post-selection is preferred in the regime of low post-selection rates (less than \(1\%\)), but other schemes are preferable in the higher post-selection rate regime.

A direct comparison to the performance of the post-selection strategies in [21] (see Figure 5b therein) is hard, both because they consider higher physical error rates than \(p = 10^{-3}\), and also because there they consider the (post-selected) logical error rate of one particular logical qubit, not the whole block.⁸

A further work [23] also performed post-selection via comparative decoding, although this was across exponentially many decoding instances (rather than linearly many) using a maximum-likelihood decoder. This was feasible given the focus on a small, non-LDPC code for magic state distillation.

Outlook

In this work, we proposed a decoder-agnostic post-selection strategy for quantum LDPC codes with many logical observables. We instantiated and tested it with the Relay-BP decoder on bivariate bicycle codes and their instructions. In regimes of interest, our results show improved logical error rates relative to prior techniques, despite the relatively light-weight computation required. We believe these concepts are likely to provide utility for many situations where post-selection is available for quantum LDPC codes, especially offline resource state generation. One immediate application could be to the results of [24], where magic states are distilled in BB codes, since it is shown that operational noise (i.e. logical measurements instructions) dominate for several key protocols, including the \(15\)-to-\(1\) protocol [25] on the gross code.

Future work could attempt to break the error floor that results from the forced runs failing to converge by introducing other decoding strategies for those runs specifically, such as following Relay-BP with ordered statistics decoding (OSD) [22] or by using decimation [26] to break up the high-weight row of the \(H^{(i)}\) matrices that may be impeding convergence.

Another direction is to combine post-selection strategies like forced gap with rare-events analysis for fault-tolerant quantum systems [27]–[29] with the goal of accurately determining how post-selection scales to larger code distances and lower physical error rates without having to perform direct Monte Carlo simulation.