betaFeedback

WorksPhysics and Astronomy

Bounded decoding complexity in transversal circuits with magic state injection

Abstract

We characterize the complexity of space-time correlated decoding for fault-tolerant quantum computing architectures that implement Clifford gates transversally and realize non-Clifford gates via magic state injection. In this approach, decoding graphs for logical measurements are constructed by backpropagating measurement operators through the circuit, which causes them to grow with circuit volume. However, the decoding volume can be substantially reduced by decoding measurements sequentially, committing corrections, and excluding syndrome data that have already been processed for earlier measurements. For random circuits, we find that the resulting decoding volume associated with mid-circuit measurements approaches a stationary average that is determined by the density of magic state injections. Large decoding instances are exponentially suppressed. We further find that the decoding complexity is remarkably insensitive to different choices of measurement products to be decoded, and that the same qualitative behavior persists across different circuit connectivities and Clifford gate ensembles. These results suggest that scalable space-time correlated decoding of large-scale fault-tolerant quantum algorithms is achievable since the magic states that make transversal architectures universal also keep them decodable.

Introduction

Quantum computation is widely believed to offer asymptotic speedups over classical computation for certain problems, such as quantum simulation and integer factorization [1]. However, the noise in real devices poses a significant barrier to solving large-scale problems, and practical implementations will almost certainly require error correction [2, 3, 4, 5].

Over the past decade, there has been substantial progress in the experimental realization of quantum error correction across a variety of hardware platforms, including superconducting qubits [6, 7, 8, 9, 10, 11, 12, 13, 14, 15], trapped ions [16, 17, 18, 19], and neutral atom arrays [20, 21, 22, 23, 24, 25]. These experiments have demonstrated several important milestones in fault-tolerant quantum computation, including encoding of information in logical qubits, suppression of logical error rates with increasing code distance, as well as logical operations. In parallel, significant effort has been devoted to reducing the overhead associated with fault-tolerant architectures, both in terms of space (physical qubit count) as well as time (physical circuit depth). In particular, tailoring error correction schemes to the native connectivity and control capabilities of specific platforms has proven to be a powerful approach to minimizing overhead.

A key development in this context is the availability of reconfigurable, effectively nonlocal connectivity on certain platforms, particularly trapped-ion [26] and neutral-atom processors [20, 27]. This allows physical qubits that are distant in a static code layout to interact directly, enabling transversal gates between distant logical code blocks and transversal or fold-transversal gates within a block [28, 29, 30], and thereby circumventing the geometric constraints of strictly local two-dimensional architectures. For two-dimensional topological stabilizer codes with local checks, locality-preserving logical gates are restricted to the Clifford group [31], which is not sufficient for universal quantum computation [32]. Nevertheless, these capabilities have been leveraged for realizing low-overhead logical processing architectures based on transversal operations [33], as recently highlighted in several experimental demonstrations with neutral atom and ion platforms [18, 20, 21, 22, 27, 34, 35].

An important insight emerging from these architectures is that fault tolerance can be preserved with a minimal number of syndrome-extraction rounds between logical operations. In particular, it has been shown that a single syndrome-extraction round per transversal entangling gate, or even one round shared across several successive gates, can suffice to maintain fault tolerance under circuit-level noise models [33, 36, 37, 38, 39]. Such a low rate of syndrome extraction rounds contrasts with the conventional prescription of performing O(d)O(d) rounds to reliably distinguish data errors from measurement errors in a distance-dd code [40, 41]. The reduction in syndrome-extraction rate is enabled by space-time correlated decoding, in which syndrome information is not decoded independently between successive logical operations but instead processed jointly across multiple layers [20, 33, 36, 37, 38, 39, 42, 43, 44, 45, 46, 47].

In Clifford circuits, correlating syndrome information across circuit layers is possible because Clifford operations map Pauli operators to Pauli operators, so that the propagation of Pauli errors and stabilizers through the logical circuit can be efficiently tracked classically via the Gottesman–Knill theorem [48, 49]. Importantly, universal quantum computation can be achieved by supplementing Clifford operations with magic state injection [50]. The required forward operations are themselves Clifford, so that the non-Clifford resource is confined to the injected magic states and space-time correlated decoding can be extended to universal circuits.

By substantially reducing the number of syndrome extraction rounds, this paradigm of space-time correlated decoding directly lowers the time overhead associated with the implementation of error correction. At the same time, the size of the decoding graph and the complexity of the associated inference problem can grow substantially when adopting a correlated decoding strategy. This is because correlated decoding is done per logical measurement and errors that affect such a measurement can occur at any space-time point in the backpropagation of the measured operator [37, 39]. While efficient decoding strategies have been developed, such as minimum-weight perfect matching that exploits the specific structure of certain codes [40, 51], or heuristic algorithms such as belief propagation [52], decoding is generally considered a problem that scales badly with problem size [53, 54, 55]. It thus remains an open question whether correlated decoding could become a bottleneck in practical implementations of large-scale fault-tolerant computations.

Here, we address this question by analyzing the complexity of the decoding problem in a setting motivated by recent experimental and theoretical developments: random circuits that combine single- and two-qubit Clifford operations with magic state injection. A representative example, in which the two-qubit Clifford gates are arranged in a brickwork geometry, is illustrated in Figure 1. We investigate how the decoding complexity, as measured by the size of decoding graphs, scales with the number of computational qubits and with circuit depth. Our main finding is that the complexity remains bounded for a finite space-time density κ\kappa of injected magic.

Figure 1. Random-circuit model. (a) NN computational logical qubits, initialized in ∣0⟩L\lvert0\rangle_L or ∣+⟩L\lvert+\rangle_L, evolve under alternating Clifford and TT-gate layers and are finally measured in the XX or ZZ basis. The Clifford layers consist of random two-qubit gates in a one-dimensional brickwork geometry, while each TT gate is applied independently with probability κ\kappa. (b) TT gates are implemented by gate teleportation using a resource state ∣T⟩L\lvert T\rangle_L, a mid-circuit measurement, and a conditional SS gate. Grey boxes denote syndrome-extraction rounds.

The basic mechanism underlying our result is illustrated schematically in Figure 2. To decode a logical Pauli measurement, it is propagated backward through the preceding Clifford circuit to identify the space-time sensitivity region in which errors can affect the measurement outcome. When measurements are decoded sequentially, syndrome information that has already been processed for earlier measurements need not be revisited. Consequently, only the previously unprocessed part of the sensitivity region contributes to the next decoding problem. Magic state injection generates mid-circuit measurements throughout the computation, so that at a finite density κ\kappa of injected magic states, these previously processed regions continually restrict the amount of new syndrome information that must be considered. We find that the typical size of the resulting decoding graphs approaches a finite stationary value that is independent of both the number of computational qubits and the circuit depth, suggesting that scalable correlated decoding may be achievable in practice. Moreover, the amount of new information to be processed decreases with increasing κ\kappa, as anticipated by the comparison in Figure 2. Interestingly, there is substantial freedom in choosing specific products of logical measurements to decode. We find that the resulting decoding complexity is remarkably insensitive to this choice.

Figure 2. Origin of bounded decoding complexity. The grey shading marks the space-time sensitivity region of the logical Pauli measurement MiM_i associated with a magic state injection, obtained by propagating the measurement operator backward through the circuit. Red and blue lines indicate the X- and Z-Pauli content of the backpropagation, with faded lines corresponding to portions that have been already processed when decoding earlier measurements. Compared with (a) low magic state injection density, (b) a higher density κ\kappa leads to more frequent mid-circuit measurements and leaves less new syndrome information to be processed per measurement.

The paper is organized as follows. We begin in Sec. II with a review of space-time correlated decoding for fault-tolerant logical circuits composed of Clifford gates supplemented by magic states. A novel justification of the sampling strategy underlying correlated decoding is given in Appendix A. Section III is devoted to the decoding complexity in random circuits, with particular emphasis on the brickwork geometry shown in Figure 1. Additional numerical results for other circuit layouts are presented in Appendix B, and Appendix § 2.0.3 provides a detailed analysis of the scaling properties of the stationary decoding-volume distributions. Finally, in Sec. IV, we discuss the implications of our results for large-scale fault-tolerant quantum computation and outline directions for future research.

Space-time correlated decoding in transversal circuits

This section reviews the sampling and decoding strategy underlying space-time correlated decoding. Rather than decoding every logical measurement individually, the method introduced in Refs. [37, 39] identifies a set of reliable measurement products whose outcomes suffice to reconstruct the full distribution of logical measurement outcomes [56]. We explain first how these reliable products are constructed and then how they are decoded efficiently by exploiting the space-time structure of their backpropagation through the Clifford circuit. This is complemented by a novel rigorous justification of the sampling strategy underlying correlated decoding presented in Appendix Appendix A.

Constructing reliable measurement products

Consider a quantum computation implemented by an adaptive Clifford circuit acting on NN computational logical qubits and additional logical auxiliary qubits used for magic state injection, as illustrated in Figure 1. The computational qubits are initialized in +1+1 eigenstates of the logical XX or ZZ operators, denoted by ∣+⟩L\lvert+\rangle_L and ∣0⟩L\lvert0\rangle_L, respectively, while the auxiliary qubits are prepared in logical magic states, ∣T⟩L=T∣+⟩L\lvert T\rangle_L = T\lvert+\rangle_L.

The computation proceeds through a sequence of Clifford blocks UiU_i and single-qubit Pauli measurements MiM_i, where i∈{1,…,NM}i \in\{1,\ldots,N_M\}. We denote the corresponding measurement outcomes by mi=±1m_i = \pm1. Each Clifford block may depend on the outcomes of previous measurements. This occurs, in particular, in the feedforward required for magic state injection. In the circuit of Figure 1, the Clifford blocks UiU_i consist of two-qubit Clifford gates CC, CNOT gates, and conditional single-qubit SS gates.

The output of the computation is encoded in the joint probability distribution p(m)p(\mathbf{m}) of measurement outcomes m=(m1,…,mNM)\mathbf{m} = (m_1,\ldots,m_{N_M}). Space-time correlated decoding provides an efficient fault-tolerant method for reconstructing the distribution p(m)p(\mathbf{m}) by sampling realizations of an encoded circuit [33, 37, 39]. Here, we describe the sampling strategy underlying space-time correlated decoding. The decoding procedure itself is discussed in Sec. II B.

In principle, sampling from p(m)p(\mathbf{m}) could be done straightforwardly by executing the Clifford blocks UiU_i and measurements MiM_i sequentially, thereby directly obtaining the complete sequence of measurement outcomes, m=(m1,…,mNM)\mathbf{m} = (m_1,\ldots,m_{N_M}). However, determining them efficiently and fault-tolerantly in an encoded circuit is facilitated by adapting an alternative sampling strategy that focuses on measurements that are either reliable or can be combined with earlier measurements into reliable products; only these measurements have to be decoded. By contrast, unreliable measurements that cannot be combined to form reliable products need not be decoded, and their outcomes can be assigned uniformly at random. Therefore, for each measurement MiM_i, we distinguish between the assigned measurement outcome mim_i and the actual measurement outcome m~i\widetilde{m}_i. The alternative sampling strategy, motivated by the examples below and developed rigorously in Appendix Appendix A, reconstructs the distribution p(m)p(\mathbf{m}) by sampling assigned measurement outcomes.

We classify measurements as reliable or unreliable according to the stabilizers of the initial state. Each computational qubit j∈{1,…,N}j \in\{1,\ldots,N\} is associated with a logical Pauli stabilizer GjG_j, where Gj=XG_j = X for qubits initialized in ∣+⟩L\lvert+\rangle_L and Gj=ZG_j = Z for qubits initialized in ∣0⟩L\lvert0\rangle_L. A measurement MiM_i is called reliable if the backpropagated measurement operator at state initialization,

Mi,0=U1†⋯Ui†MiUi⋯U1,(1)M_{i,0} = U_1^\dagger\cdots U_i^\dagger M_i U_i \cdots U_1, \tag*{(1)}

commutes with every stabilizer of the initial state, and unreliable otherwise [37, 39]. Logical auxiliary qubits prepared in magic states ∣T⟩L\lvert T\rangle_L do not possess Pauli stabilizers and therefore do not affect this classification.

In an adaptive circuit, the Clifford operations appearing in the backpropagation may depend on the outcomes of earlier measurements Mi′M_{i'} with i′<ii' < i. Consequently, whether a given measurement is reliable may itself depend on the measurement branch. Nevertheless, the backpropagated operator can always be computed efficiently on a classical computer, since Clifford conjugation maps Pauli operators to Pauli operators.

To understand why we can randomly assign the outcomes of unreliable measurements that are not part of a reliable product, consider an unreliable measurement MiM_i whose backpropagated Mi,0M_{i,0} anticommutes with a stabilizer GjG_j. Since GjG_j stabilizes the initial state, applying it leaves the state unchanged. Propagating the stabilizer through the circuit, however, flips the sign of the measurement operator, Mi↦−MiM_i \mapsto-M_i. Equivalently, the measurement statistics are identical whether one measures MiM_i or −Mi-M_i, implying that the measurement outcomes m~i=±1\widetilde{m}_i = \pm1 occur with equal probability. A simple example is the circuit

∣+⟩L→M=Z(2)\left|+\right\rangle_L \quad\xrightarrow{\quad M=Z\quad} \tag*{(2)}

where the stabilizer G=XG=X flips the measurement operator M=ZM=Z. This can be seen graphically as the backpropagation of the ZZ measurement (blue) terminates on an XX eigenstate (red). Instead of decoding the actual outcome m~i\widetilde{m}_i, we may thus simply assign a measurement outcome mi=±1m_i=\pm1 uniformly at random.

Reliable measurements, in contrast, cannot be treated in this way. For example, replacing the ZZ measurement in Eq. (2) by an XX measurement yields the deterministic outcome +1+1. The same is true whenever an unreliable measurement can be combined with earlier measurements to form a reliable product, indicating that correlations exist between their outcomes. Such correlations arise when a stabilizer anticommutes not only with MiM_i but also with previous measurements. As an example, consider the circuit shown in Figure 3(a) which prepares a Bell state between logical qubits j=1j=1 and 22 and measures both qubits in the ZZ basis. The joint distribution of measurement outcomes is p(m~)=12δm~1,m~2p(\widetilde{\boldsymbol{m}})=\frac{1}{2}\delta_{\widetilde{m}_1,\widetilde{m}_2}. Both measurements being individually unreliable is reflected in the marginal distributions, p(m~1)=p(m~2)=1/2p(\widetilde{m}_1)=p(\widetilde{m}_2)=1/2, meaning that the outcomes m~i=±1\widetilde{m}_i=\pm1 occur with equal probability. However, both measurements are flipped by the same stabilizer G1=X1G_1=X_1 of the first logical qubit. In the figure, this can be seen from the backpropagations of both measurements terminating as Z1Z_1 (blue) on the initial XX eigenstate of the first qubit. Consequently, when the measurements are performed sequentially, only the first measurement has equiprobable outcomes; owing to the Bell-state correlations, the outcome of the second measurement is deterministically equal to that of the first. That is, although the second measurement is unreliable by itself, its product with the first measurement is reliable. Graphically, the backpropagation of the product has support only on the second qubit, and its Pauli type ZZ matches the initialization (both blue). When sampling assigned outcomes mim_i instead of actual outcomes m~i\widetilde{m}_i, this means that only m1=±1m_1=\pm1 can be assigned uniformly at random, whereas the second measurement outcome has to be assigned such that also the assigned values obey Bell-state correlations. Put differently, the reliable product has to be the same when expressed in terms of assigned or actual outcomes, m1m2=m~1m~2m_1m_2=\widetilde{m}_1\widetilde{m}_2. This ensures that m\boldsymbol{m} and m~\widetilde{\boldsymbol{m}} follow the same distribution.

Figure 3. Example of the construction of the decoding graph for Bell-state preparation. (a) At the logical level, the backpropagation of each individual measurement anticommutes with the initialization stabilizer G1=X1G_1 = X_1 of the first qubit and is therefore unreliable. The backpropagation of their product, by contrast, commutes with all initialization stabilizers, so that the product is reliable. (b) Construction of the corresponding decoding graph for two [37,1,7][37,1,7] color-code logical qubits. Stabilizer measurements are related across circuit layers by the same Clifford-conjugation rules as logical Pauli operators (highlighted lines; only representative examples are shown). The construction of the checks is described in the main text and in Eq. (5). At the final time slice, products of the physical ZZ-basis measurement outcomes determine ZZ-type stabilizer outcomes, which form checks with the corresponding preceding stabilizer measurement (top) or with preceding stabilizer measurements on both logical qubits (bottom). The first measurements of XX-type (ZZ-type) stabilizers form stand-alone checks for qubits initialized in ∣+⟩L\lvert+ \rangle_L (∣0⟩L\lvert0 \rangle_L), as illustrated at the top (bottom).

While in this example the outcome for the reliable product was deterministic, this does not have to be the case. In particular, the outcomes of reliable measurements and reliable products are probabilistic whenever their back-propagated operators have support on logical auxiliary qubits prepared in magic states ∣T⟩L\lvert T\rangle_L.

In practice, reliable products are constructed sequentially as measurements are encountered during circuit execution. To determine whether a reliable product containing a given measurement MiM_i exists, we define the commutation matrix Ci,j∈F2C_{i,j}\in\mathbb{F}_2 to equal 11 whenever the backpropagation (1) of MiM_i anticommutes with GjG_j, and 00 otherwise. When the measurement MiM_i is performed, the corresponding row of the commutation matrix, bi=(Ci,j)j=1N\boldsymbol{b}_i=(C_{i,j})_{j=1}^{N}, is computed by backpropagating MiM_i through the preceding Clifford circuit and checking its commutation with each initial stabilizer. To construct a reliable product containing MiM_i, we write Ri=∏i′=1NMMi′vi′,iR_i=\prod_{i'=1}^{N_M}M_{i'}^{v_{i',i}} with vi′,i∈F2v_{i',i}\in\mathbb{F}_2. Since the product must include MiM_i, but may involve only preceding measurements, its indicator vector takes the form vi=(vi′,i)i′=1NM=(xi,1,0,…,0)\boldsymbol{v}_i=(v_{i',i})_{i'=1}^{N_M}=(x_i,1,0,\ldots,0), where xix_i has i−1i-1 components. The condition for RiR_i to be reliable is

viC=0⟺xiBi=bi(mod2),(3)\boldsymbol{v}_i C=0 \quad\Longleftrightarrow\quad\boldsymbol{x}_i B_i=\boldsymbol{b}_i \pmod2, \tag*{(3)}

where BiB_i denotes the submatrix of CC consisting of its first i−1i-1 rows. The measurement MiM_i is therefore reliable precisely when bi=0\boldsymbol{b}_i=0 and Eq. (3) is solved by xi=0\boldsymbol{x}_i=0. Otherwise, it can be incorporated into a reliable product if and only if Eq. (3) admits a nontrivial solution. In deep circuits with i≫Ni\gg N, this solution is typically not unique. We discuss different choices of reliable products below.

Maintaining a row-echelon form of CC throughout the circuit allows Eq. (3) to be solved in O(N2)O(N^2) operations per measurement, where NN is the number of computational qubits and hence the number of initial stabilizers. The total computational cost therefore scales as O(NMN2)O(N_MN^2), which is polynomial in the circuit size.

Having established how measurements are classified as reliable or unreliable, and how reliable products are constructed when they exist, we can now describe the sampling procedure used to reconstruct the joint distribution of measurement outcomes p(m)p(\boldsymbol{m}).

When MiM_i is encountered during circuit execution, we first determine whether it is reliable or, if it is unreliable, whether it can be combined with previous measurements into a reliable product. The latter is possible only when Eq. (3) admits a solution. In that case, we write the corresponding reliable product as Ri=∏i′=1iMi′vi′,iR_i=\prod_{i'=1}^{i}M_{i'}^{v_{i',i}}, with vi=1v_i=1, and decode its outcome rir_i. Since all preceding measurements contained in RiR_i have already been assigned outcomes, we assign an outcome mim_i such that ri=∏i′=1imi′vi′,i=∏i′=1im~i′vi′,ir_i=\prod_{i'=1}^{i}m_{i'}^{v_{i',i}}=\prod_{i'=1}^{i}\widetilde{m}_{i'}^{v_{i',i}}. The equality between the products of assigned and actual outcomes is discussed above for the example of Bell-state correlations and shown in full generality in Appendix A. The special case in which MiM_i is reliable by itself corresponds to vi′=0v_{i'}=0 for all i′≠ii'\ne i, so that the assigned outcome equals the actual one, ri=mi=m~ir_i=m_i=\widetilde{m}_i. If no reliable product containing MiM_i exists, we do not decode MiM_i and instead assign the outcome mi=±1m_i=\pm1 uniformly at random.

During circuit execution, Clifford operations are conditioned on the assigned rather than the actual measurement outcomes. As explained in Appendix A, even if there is a mismatch between these values, sampling assigned outcomes correctly reproduces the distribution p(m)p(\boldsymbol{m}).

This sampling procedure forms the basis of space-time correlated decoding. It therefore remains to specify how the outcomes of reliable products are decoded.

Decoding reliable measurement products

We assume the computational and auxiliary qubits to be encoded in blocks of an [n,k,d][n,k,d] Calderbank–Shor–Steane (CSS) code that admits a transversal or fold-transversal implementation of a generating set of the Clifford group, such as {H,S,CX}\{H, S, CX\}, where HH and SS denote the Hadamard and phase gates, respectively. Examples include the two-dimensional color code, for which these Clifford generators can be realized transversally [28], and the surface code [57, 58], where they can be realized fold-transversally [29]. Under such (fold-)transversal Clifford operations, code stabilizers are mapped to code stabilizers, with their Pauli content transforming according to the same Clifford conjugation rules as logical Pauli operators. This property underlies the construction of the decoding graph described below.

Once a reliable product RiR_i is identified, the decoder must determine its value from noisy physical syndrome data. The corresponding decoding problem is obtained

by backpropagating RiR_i layer by layer through the circuit. Its backpropagation to a layer i′<ii' < i is defined as

Ri,i′=Ui′+1†⋯Ui†RiUi⋯Ui′+1.(4)R_{i,i'} = U_{i'+1}^{\dagger} \cdots U_i^{\dagger} R_i U_i \cdots U_{i'+1}. \tag*{(4)}

At each layer i′i', the support of Ri,i′R_{i,i'} identifies the logical qubits on which an error can influence the value of RiR_i. Taken over all layers i′∈{0,…,i}i' \in\{0,\ldots,i\}, these supports define a space-time sensitivity region for the measurement product. A physical error within this region affects the value of RiR_i precisely when it anticommutes with the corresponding backpropagated operator Ri,i′R_{i,i'}. The Pauli type of Ri,i′R_{i,i'} on each logical qubit therefore determines which code stabilizers are sensitive to the relevant errors, and hence which syndrome measurements must be included in the decoding problem.

The decoding graph for RiR_i is constructed directly from this space-time sensitivity region. At each layer, one includes the stabilizer measurements of the Pauli type selected by the backpropagated operator Ri,i′R_{i,i'}. For notational simplicity, the backpropagation layers in Eq. (4) are defined by the blocks UiU_i between successive logical measurements. In practice, however, a block UiU_i may have to be decomposed into individual transversal gate layers, with a single round of syndrome extraction inserted between them [33, 36, 37, 39]. Each check is obtained by comparing a stabilizer measurement with the stabilizer, or product of stabilizers, to which it backpropagates through the preceding logical gate. Consequently, a check may involve more than two stabilizer-measurement outcomes. This occurs, for example, when a ZZ stabilizer spreads onto another logical qubit under a transversal CNOT gate, or when an XX stabilizer is mapped to a product of XX- and ZZ-type stabilizers by an SS gate.

We have so far described checks in the space-time bulk of the circuit. Let us now turn to the temporal boundaries associated with logical-state preparation and measurement. Computational qubits are initialized transversally in ∣+⟩⊗n\lvert+\rangle^{\otimes n} or ∣0⟩⊗n\lvert0\rangle^{\otimes n}, corresponding to the logical states ∣+⟩L\lvert+\rangle_L and ∣0⟩L\lvert0\rangle_L, respectively. The first measurements of the corresponding XX- or ZZ-type stabilizers therefore have deterministic outcomes and form stand-alone checks. By contrast, the complementary stabilizers are initially undetermined: their first measurement outcomes are random and, in the presence of measurement errors, would require O(d)O(d) rounds of syndrome extraction to determine reliably.

Auxiliary qubits prepared in logical magic states ∣T⟩L\lvert T\rangle_L are treated differently. We assume these states to be prepared fault-tolerantly with well-defined eigenvalues of all code stabilizers.

Crucially, the backpropagation of a reliable product cannot terminate on an undetermined initial stabilizer. If it did, then on at least one corresponding input qubit the backpropagated operator would contain the Pauli operator conjugate to the known initialization stabilizer. It would therefore anticommute with that stabilizer, in contradiction with the reliability condition (3). Hence, the decoding graph of a reliable product terminates only on stabilizers whose initial values are known [37, 39].

The final temporal boundary is set by logical measurement. Logical measurements are performed transversally. The code stabilizers of the same Pauli type as the logical measurement can therefore be inferred from products of the individual data-qubit measurement outcomes. These are precisely the stabilizers sensitive to errors that can affect the logical measurement and are incorporated into the decoding problem together with the preceding syndrome measurements.

In Figure 3(b), we illustrate the construction of the decoding graph for Bell-state preparation, using the two-dimensional [37,1,7]\left\lbrack37,1,7\right\rbrack color code. The two logical qubits, j=1,2j=1,2, are initialized in ∣+⟩L\lvert+\rangle_L and ∣0⟩L\lvert0\rangle_L with a single round of syndrome extraction. Syndrome information is obtained at two time slices, i=1,2i=1,2, immediately after initialization and from the final transversal measurements. We denote the outcome associated with stabilizer ll of Pauli type μ∈{X,Z}\mu\in\{X,Z\} on logical qubit jj at time slice ii by Sj,l,iμS^{\mu}_{j,l,i}, with l∈{1,…,18}l\in\{1,\ldots,18\}. As discussed in Sec. II A, both measurements M1=Z1M_1=Z_1 and M2=Z2M_2=Z_2 are individually unreliable, but the product R2=Z1Z2R_2=Z_1Z_2 is reliable. Its backpropagation is illustrated on the logical level in Figure 3(a). Checks are constructed by backpropagation of stabilizers as illustrated in Figure 3(b), which gives

C1,l,2Z=S1,2ZS1,1Z,C2,l,2Z=S2,l,2ZS1,l,1ZS2,l,1Z,C^{Z}_{1,l,2}=S^{Z}_{1,2}S^{Z}_{1,1},\qquad C^{Z}_{2,l,2}=S^{Z}_{2,l,2}S^{Z}_{1,l,1}S^{Z}_{2,l,1},
C2,l,1Z=S2,l,1Z.(5)C^{Z}_{2,l,1}=S^{Z}_{2,l,1}. \tag*{(5)}

where the latter is a stand-alone check associated with the known initial stabilizer value.

Constructing checks by backpropagating stabilizers ensures that the syndromes of single data and measurement errors remain localized in space-time. Consequently, data and measurement errors correspond to space-like and time-like hyperedges in the decoding graph, respectively. Space-like hyperedges connect check nodes within the same time slice, whereas time-like hyperedges connect check nodes in successive time slices.

The weight of space-like hyperedges depends on the underlying code. For the surface code, they have weight at most two, whereas for the color code they can have weight three. By contrast, measurement errors give rise to time-like hyperedges that, in principle, connect up to three checks across a transversal logical gate. However, irrespective of the chosen reliable product, only two of these checks appear in its decoding graph [37, 39]. Consequently, every time-like hyperedge reduces to an ordinary edge. In the example shown in Figure 3, a measurement error in S2,l,1ZS^{Z}_{2,l,1} gives rise to a weight-two time-like edge connecting checks C2,l,2ZC^{Z}_{2,l,2} and C2,l,1ZC^{Z}_{2,l,1} in Eq. (5). If, in addition, the space-like hyperedges have weight at most two, as in the surface code, the resulting space-time decoding graph can be decoded efficiently using minimum-weight perfect matching.

Once the errors have been identified by the decoder, the corrected value of the reliable product is obtained by determining whether the decoded error anticommutes with the backpropagated measurement operator.

The computational cost of decoding a reliable product is determined by the number of checks in its decoding graph, which is set by the space-time extent of its backpropagation. Decoding each reliable product independently would therefore repeatedly process the same regions of the circuit. Moreover, because backpropagations typically extend all the way to the initialization of the logical qubits, the decoding graphs grow with circuit depth.

To avoid this overhead, reliable products are decoded in temporal order, committing the corresponding corrections after each decoding step [37]. Once a check has been decoded and its correction committed, it is never revisited when decoding subsequent products. Consequently, each reliable product is decoded only within the previously unexplored portion of its backpropagation region, substantially reducing the effective decoding volume.

A subtle issue arises from weight-three time-like hyperedges associated with measurement errors. As discussed above, for any choice of reliable product, only two of the three checks incident on such a hyperedge are included in the corresponding decoding graph. Erroneously committing this hyperedge can therefore flip the third check, creating a virtual defect in a subsequent decoding graph.

This becomes problematic if an odd number of such defects occurs within a connected space-time region, since at least one must then be matched to a spatial or temporal boundary and can thereby induce a logical error. Such situations can arise in circuits containing time-like loops [37, 39]. Suitable circuit identities can sometimes be used to eliminate these loops. When this is not possible, the problem can instead be resolved by introducing virtual edges, corresponding to closed space-time loops within already decoded regions, which allow virtual defects in disconnected regions of subsequent decoding graphs to be matched consistently [37].

Complexity in random circuits

Having introduced space-time correlated decoding, we now analyze its computational complexity in a generic setting. Previous work presented full-scale numerical simulations of the execution and decoding of transversal Clifford circuits encoded in the surface code [37, 39]. Circuit execution can be simulated efficiently with stim [59], while minimum-weight perfect matching decoding is performed using pymatching [51]. Extending such full-scale simulations to circuits with magic state injection, however, is substantially more challenging, particularly when the circuits are deep and act on many computational qubits. Consequently, the computational complexity of space-time correlated decoding for such circuits remains largely unexplored.

In particular, we seek to understand how the decoding complexity scales with the number of computational qubits and the circuit depth. If the decoding cost were to grow with either, classical processing could become a bottleneck for real-time circuit execution. One approach to controlling this growth is windowed decoding, which explicitly restricts decoding to finite space-time regions [39, 44, 45]. Transversal operations, however, correlate syndrome information across logical qubits, making it challenging to define a decoding problem that preserves fault tolerance. Here, we investigate a complementary mechanism in which finite decoding regions arise dynamically from the sequential decoding of reliable measurement products and the commitment of previous corrections. For a broad class of circuits, the resulting decoding complexity can be characterized without simulating the full encoded dynamics. As a proxy for the cost of decoding a reliable product, we use the size of its decoding graph, measured by the number of checks it contains, and exclude checks that have already been processed when decoding earlier reliable products. As we show below, the resulting circuit-dependent decoding volume remains bounded: it grows neither with the number of computational qubits nor with the circuit depth.

Circuit layout and complexity measure

As a representative example, we consider the circuit layout shown in Figure 1. The circuit comprises random two-qubit Clifford blocks arranged in a brickwork geometry and interspersed with TT-gate injections occurring independently with probability κ\kappa. Such Clifford blocks can be implemented transversally with the two-dimensional color code [28]. The qualitative conclusions of our analysis, however, are independent of the particular circuit layout. In Appendix B, we present additional results for circuits with all-to-all connectivity and Clifford gates drawn from the set {H,S,CX}\{H, S, CX\}, which admit fold-transversal implementations with surface-code logical qubits [29, 30].

In general, circuits containing multiple layers of two-qubit gates give rise to time-like loops, which can lead to virtual defects [37, 39]. As discussed at the end of Sec. II B, loops whose structure is known in advance can sometimes be simplified or eliminated using suitable circuit identities, with the corresponding preprocessing performed offline. In adaptive circuits, however, the loop structure may depend on whether conditional gates are executed, so that the appropriate simplifications may have to be determined for the realized measurement branch during circuit execution. Any loops that remain require the corresponding virtual edges and their weights to be constructed online, introducing additional classical overhead. Since the size of the decoding graph remains bounded, however, we expect this overhead to remain bounded as well.

Although magic state injection introduces adaptive gates, it is nevertheless unnecessary to simulate the quantum state in order to characterize the decoding complexity. Instead, it suffices to sample the sequence of logical gates appearing in the circuit. To see this, recall that each TT gate is implemented by injecting a logical magic state ∣T⟩L=T∣+⟩L|T\rangle_L = T|+\rangle_L. The injection circuit, which is shown in Figure 1, consists of a CNOT gate from the computational qubit to the auxiliary magic state qubit, followed by a logical ZZ measurement of the auxiliary qubit and a logical SS gate conditioned on the measurement outcome. Depending on the circuit, the conditioning measurement may itself be unreliable or belong to a reliable product. In either case, however, the backpropagated measurement operator terminates as ZZ on the auxiliary ∣T⟩L|T\rangle_L state, implying that the two measurement outcomes occur with equal probability. Consequently, the conditional SS gate is applied with probability 1/21/2. The sequence of logical gates can therefore be generated simply by sampling each conditional SS gate independently with probability 1/21/2, without simulating the underlying quantum state.

As a proxy for the complexity of decoding a reliable product RiR_i, we use the normalized check count NCN_C of its decoding graph after excluding checks that have already been processed. More precisely, suppose that, upon backpropagating RiR_i to an earlier circuit step i′<ii' < i, its restriction to logical qubit jj is XjX_j or ZjZ_j. The corresponding set of XX- or ZZ-type checks is then included in the decoding graph of RiR_i, contributing 1 to NCN_C. If the restriction tion is YjY_j, both sets of checks are included, contributing 2. Checks that have already appeared in previously decoded graphs are excluded.

Strictly speaking, NCN_C is not the literal number of stabilizer checks in the decoding graph. Rather, the actual number depends on the code used to encode each logical qubit. For codes with equal numbers of XX- and ZZ-type stabilizers, including the unrotated surface code and self-dual codes such as the color code, the actual number of checks is obtained by multiplying NCN_C by the number of stabilizers of either type. For a distance-dd unrotated surface code and color code, this factor is d(d−1)d(d-1) and 3(d2−1)/83(d^2-1)/8, respectively. Thus, while the normalized check count NCN_C captures the dependence of the decoding problem on the logical circuit, its absolute size retains the dependence on the underlying code through the number of stabilizer checks per logical block. In particular, this number grows with the code distance dd, even though NCN_C remains bounded with increasing circuit width and depth.

Decoding complexity

Figure 4(a) shows the normalized check count NCN_C as a function of the circuit layer index tt for N=16N=16 and 128 computational logical qubits and four values of the magic state injection probability κ\kappa. Each circuit layer consists of a Clifford layer followed by a TT-gate layer, as shown in Figure 1. The data are averaged over Nreal=104N_{\mathrm{real}}=10^4 and 10310^3 circuit realizations for N=16N=16 and 128, respectively. Since each circuit layer contains, on average, κN\kappa N magic state injections, each data point is obtained from approximately κNNreal\kappa N N_{\mathrm{real}} decoding instances. The shaded regions indicate the spread of the data and are defined by upper and lower standard deviations, computed separately from samples above and below the mean and normalized such that they reduce to the conventional standard deviation for a symmetric distribution.

We first consider the transient behavior at early circuit times. During the initial stages of circuit execution, only a small number of previous measurements are available to form reliable products. Consequently, the first O(N)O(N) measurements are typically unreliable and are not decoded immediately. Their associated checks therefore accumulate until they are eventually incorporated into the decoding graphs of subsequent reliable products, causing the average normalized check count NCN_C to increase. This growth continues until approximately NN unreliable measurements have accumulated, corresponding to a transient regime of duration t∼κ−1t\sim\kappa^{-1}. As reliable products subsequently become available, the accumulated backlog of checks is gradually depleted, producing the overshoot visible in Figure 4(a). The check count then relaxes towards a stationary regime in which its average becomes independent of circuit depth. Increasing κ\kappa shortens the transient and reduces the height of the overshoot because reliable products are generated more rapidly.

Figure 4. Decoding complexity in random circuits for different numbers of computational logical qubits NN and magic state injection probabilities κ\kappa. Colors indicate κ\kappa, while marker shapes distinguish N=16N=16 and 128. (a) Average normalized check count NCN_C for mid-circuit measurements performed at circuit layer tt. Black dashed lines indicate fits to the stationary regime. Inset: Stationary values NC,∞N_{C,\infty} extracted from these fits (markers), together with the analytical prediction in Eq. (6) (dashed line). (b) Probability distribution p(NC)p(N_C) in the stationary regime. The dashed lines indicate exponential fits to the large-NCN_C tails. Inset: Fitted decay rate bb versus κ\kappa.

To understand the stationary regime analytically, note

first that the number of unreliable measurements that cannot be combined with previous measurements is bounded by the number of computational qubits NN. This follows because one can choose a basis of stabilizers of the initial state such that every such measurement is flipped by exactly one basis element, and the number of basis stabilizers equals the number of computational qubits [37]. Once this bound is reached, every subsequent measurement can be incorporated into a reliable product. A stationary regime is then established in which checks are generated and decoded at equal average rates. Inspection of Figure 1 shows that each circuit layer contributes 2N2N checks from the Clifford gates and another 4N4N checks from the TT-gate layer, corresponding to one XX and one ZZ check per computational qubit. In addition, each magic state injection contributes three checks: one obtained by backpropagating the logical ZZ measurement of the auxiliary qubit and two stand-alone checks associated with the logical ∣T⟩L\lvert T\rangle_L state, as discussed in Sec. II B. Since the mean number of magic state injections per layer is κN\kappa N, the average number of newly generated checks per layer is 3(2+κ)N3(2+\kappa)N. Although a given check may be contained in the decoding graphs of many subsequent reliable products, it is counted only the first time it appears. Consequently, in the stationary regime, the average number of newly counted checks per layer equals the average number of newly generated checks. Dividing by the mean number of reliable products created per layer, κN\kappa N, yields the stationary value

NC,∞=3(2+κ)κ.(6)N_{C,\infty}=\frac{3(2+\kappa)}{\kappa}. \tag*{(6)}

More generally, for all circuit architectures that reach such a stationary regime, this counting argument shows that the stationary normalized check count is given by the ratio of the average number of newly generated checks per circuit layer to the average number of reliable products created per layer.

The numerical data shown in Figure 4(a) are in excellent agreement with this prediction. In particular, the stationary value is independent of the number of computational qubits, as demonstrated by the collapse of the data for N=16N=16 and 128128. This follows because both the number of generated checks and the number of reliable products per layer are proportional to NN. The dependence of NC,∞N_{C,\infty} on κ\kappa is shown in the inset of Figure 4(a), where Eq. (6) is found to accurately describe the numerical results. Notably, the decoding complexity per reliable product decreases with increasing magic state injection probability.

Having established that the average normalized check count remains bounded with both the number of computational qubits and the circuit depth, we next consider fluctuations around the stationary value. The stationary distribution p(NC)p(N_C) is shown in Figure 4(b). As for the mean, the results for N=16N=16 and 128128 collapse, indicating that the full stationary distribution is likewise insensitive to the number of computational qubits. At large NCN_C, the distribution exhibits an exponential tail, p(NC)∼e−bNCp(N_C)\sim e^{-bN_C}. The decay rate bb increases with the magic state injection density approximately as ∼κα\sim\kappa^\alpha where α=0.98\alpha=0.98; this behavior is shown in the inset of Figure 4(b). Thus, increasing κ\kappa suppresses not only the average decoding complexity but also the probability of large decoding instances.

The fitted exponent α=0.98\alpha=0.98 suggests an almost linear dependence b∼καb\sim\kappa^\alpha. However, the detailed analysis of the stationary distribution presented in Appendix § 2.0.3 favors scaling behavior with a nontrivial exponent α<1\alpha<1. In particular, we find that for circuits composed of random two-qubit Clifford gates, the distribution obeys the one-parameter scaling form

p(NC)=καF ⁣[κα(NC−NC,∞)].(7)p(N_C)=\kappa^\alpha F\!\left[\kappa^\alpha\left(N_C-N_{C,\infty}\right)\right]. \tag*{(7)}

While the data hints that α\alpha and FF are independent of the circuit connectivity, we cannot determine conclusively if this is a universal behavior across random one-dimensional brickwork and all-to-all circuits. By contrast, restricting the gate ensemble to a subset of the Clifford group leads to deviations from this scaling form. Understanding the origin of this scaling behavior and the conditions under which it emerges remains an interesting direction for future research.

Choice of reliable measurement products

As discussed in Sec. II A, the choice of a reliable product containing a given measurement MiM_i is generally not unique. We now investigate how this freedom in choosing RiR_i affects the decoding complexity.

We first quantify how many different reliable products can be associated with a given measurement MiM_i. Each such product corresponds to a different solution xi\mathbf{x}_i of Eq. (3). Given a particular solution, the entire solution space is obtained by adding vectors in the left nullspace of BiB_i. The dimension of the solution space is therefore i−1−rank⁡(Bi)i-1-\operatorname{rank}(B_i). Hence, determining the number of possible reliable products reduces to determining the rank of BiB_i. For a deep circuit with i≫Ni\gg N, BiB_i is a tall matrix: it has only NN columns, but each column contains i−1i-1 entries. We now argue that these columns are linearly independent with high probability, meaning that rank⁡(Bi)=N\operatorname{rank}(B_i)=N.

To see this, recall the definition of BiB_i. Its row indexed by i′<ii'<i describes the commutation of the backpropagated measurement Mi′M_i' with the NN Pauli stabilizers GjG_j of the initial computational state: the matrix element (Bi)i′,j(B_i)_{i',j} equals 11 if the backpropagation of Mi′M_i' anticommutes with GjG_j, and 00 otherwise. In a sufficiently deep random circuit, the restriction of a backpropagated measurement to a given computational qubit is approximately uniformly distributed over {I,X,Y,Z}\{I,X,Y,Z\}. Since GjG_j is either XjX_j or ZjZ_j, half of these Pauli operators commute with GjG_j and half anticommute. The entries of BiB_i can therefore be regarded, to a good approximation, as unbiased binary variables. Accordingly, its NN columns behave approximately as long random binary strings. For i−1≫Ni-1\gg N, such strings are overwhelmingly likely to be linearly independent over F2\mathbb{F}_2, so that rank⁡(Bi)=N\operatorname{rank}(B_i)=N with high probability. The solution space then has dimension i−1−Ni-1-N and contains 2i−1−N2^{i-1-N} solutions. Thus, the number of possible reliable products grows exponentially with circuit depth.

To determine whether this freedom affects the decoding complexity, we compare four different prescriptions for selecting a solution of Eq. (3). These prescriptions produce solutions with different Hamming weights and hence reliable products containing different numbers of measurements. As a simple baseline, which we label Free, we solve the transposed system (3) by Gaussian elimination and set all free variables to zero. This is the prescription used for the results presented in the previous subsection and in Figure 4. Since BiTB_i^{\mathsf{T}} has at most NN pivot columns, at most NN components of xi\mathbf{x}_i can be nonzero. Including the current measurement MiM_i, the Hamming weight hih_i of the full indicator vector vi=(xi,1,0,…,0)\mathbf{v}_i=(x_{i,1},0,\ldots,0), and hence the number of measurements contained in RiR_i, therefore satisfies hi≤N+1h_i \le N + 1. We further consider a solution labeled Random, obtained by adding a uniformly sampled vector from the homogeneous solution space to the Free solution. For i≫Ni \gg N, such a random solution is approximately an unbiased binary vector of length i−1i - 1, subject only to NN linear constraints. Approximately half of its components are therefore nonzero, giving hi∼(i+1)/2h_i \sim(i + 1)/2 and thus a Hamming weight that grows linearly with ii. Finally, we consider a low-Hamming-weight solution obtained using belief propagation with ordered-statistics decoding (BP+OSD), as implemented in the Python package ldpc [60, 61], and an exact minimum-Hamming-weight solution obtained using a MaxSAT solver from pysat [62]. The Hamming weights obtained with these four prescriptions are compared in Figure 5(a) for the same random-circuit ensemble considered above, with N=16N = 16. For the Random choice, hih_i quickly leaves the range of the plot due to its approximately linear growth with the measurement index ii. By contrast, the other three prescriptions produce much smaller reliable products. For Free, the boundedness follows directly from the analytical bound hi≤N+1h_i \le N + 1 derived above. BP+OSD typically yields lower Hamming weights than Free, while MaxSAT gives the exact minimum-Hamming-weight solution. The four methods therefore generate reliable products whose numbers of constituent measurements differ substantially.

Figure 5. Dependence of the decoding complexity on the choice of reliable measurement product for N=16N = 16. Colors indicate the magic state injection probability κ\kappa, while marker shapes distinguish the four methods used to select a solution of Eq. (3). (a) Hamming weight hih_i of the reliable product RiR_i as a function of the measurement index ii. Random denotes a random solution; Free the Gaussian-elimination solution with all free variables set to zero; BP+OSD a low-Hamming-weight solution; and MaxSAT the exact minimum-Hamming-weight solution. (b) Stationary distribution p(NC)p(N_C) of the normalized check count. Inset: Average NCN_C versus circuit layer tt. Despite the pronounced differences in hih_i, the decoding-complexity statistics are indistinguishable within numerical resolution.

Despite these pronounced differences in the sizes of the reliable products, their decoding complexities are essentially indistinguishable. Figure 5(b) shows the stationary distribution of the normalized check count NCN_C, while the inset shows its average as a function of circuit layer tt. No discernible dependence on the prescription used to select the reliable product is observed. Thus, minimizing the number of measurements contained in RiR_i does not translate into a reduction of the effective decoding volume. For the random circuits considered here, computationally expensive optimization procedures such as MaxSAT are therefore unnecessary: the Free solution obtained efficiently by Gaussian elimination is sufficient.

Conclusions and outlook

Magic state injection is usually regarded as the most resource-demanding step in fault-tolerant quantum computation. Yet, for space-time correlated decoding, our results reveal a counterbalancing effect: magic state injections introduce mid-circuit measurements that enable certain corrections to be committed, thereby reducing the complexity of decoding. In random circuits composed of transversal or fold-transversal Clifford gates and magic state injections, these measurements continually break the decoding problem into pieces of finite size, provided the magic state density κ\kappa remains finite. The decoding volume associated with each reliable measurement product approaches a stationary average distribution that is independent of both the number of computational qubits and the circuit depth. Its mean is determined by a simple balance between the rates at which checks are generated and consumed, as expressed by Eq. (6), while large decoding instances are exponentially suppressed.

These findings have direct implications for the classical cost associated with correlated decoding. For κ=0.5\kappa= 0.5, for instance, the average decoding problem is comparable in size to a memory experiment for a single logical qubit over about fifteen syndrome-extraction rounds, independent of the width or depth of the computation. As in the memory experiment, the absolute decoding cost retains a dependence on the underlying quantum code: it is obtained by multiplying the decoding volume by the number of relevant stabilizers per code block, which grows with the code distance. While a memory experiment is restricted to a single logical qubit, bounded decoding regions thus emerge dynamically in our approach, even for computations involving arbitrarily many logical qubits. This provides an attractive alternative to windowed decoding, which likewise aims to bound the real-time decoding problem in large-scale fault-tolerant computations. Windowed decoding confines the decoding problem to a finite moving region of space-time [39, 44, 45]; for circuits with transversal operations, however, determining boundaries at which corrections can be safely committed while preserving fault tolerance is nontrivial. By contrast, the approach considered here sequentially decodes reliable measurement products and commits the corresponding corrections, thereby removing syndrome information that has already been processed and dynamically determining the boundaries of the decoding regions. Crucially, these commitments preserve fault tolerance by construction, without requiring additional prescriptions [45].

Additionally, sequential decoding of reliable measurement products does introduce additional complexity into classical real-time control. In particular, preparing each decoding problem requires identifying a reliable measurement product and constructing the corresponding decoding graph. Interestingly, however, the freedom in choosing reliable measurement products does not appear to require optimization. Although the number of reliable products available for a given measurement grows exponentially with circuit depth, the space-time volume to decode is effectively localized around the latest measurement, and the choice of the reliable product does not matter. The prescriptions considered here yield indistinguishable statistics within our numerical resolution; for the random circuits studied here, the simple Gaussian-elimination solution is therefore sufficient.

Our results open several promising directions for future research. Because the decoding volume is controlled by the local density of magic rather than by circuit size, it becomes a quantity that can be optimized at compile time: distributing magic state injections as uniformly as possible in space and time, within the constraints of a given algorithm, directly limits the decoding load. Extending our analysis from random circuits to deep, structured circuits representative of concrete algorithms is therefore a natural next step toward a joint optimization of compilation and decoding. The stationary distribution of decoding volumes, in turn, provides a basis for determining the computational resources required for real-time decoding, including the capacity to handle rare, unusually large decoding instances. Finally, for matchable codes, it would be desirable to develop a systematic procedure for ensuring matchability of space-time decoding in circuits containing time-like loops. As discussed in Sec. II B, measurement errors in such circuits can generate virtual defects whose decoding requires the introduction of virtual edges. While virtual edges arising from certain elementary gate sequences preserve matchability of the underlying code, this is generally no longer the case for longer and more complex circuits [37]. Whether and how such circuits can be transformed to restore matchability remains

an open question. Resolving this issue would unlock the use of fast matching decoders for real-time processing of the bounded decoding volumes identified here.

Taken together, our results indicate that the classical processing for transversal fault-tolerant architectures can scale alongside the quantum hardware, and that the magic states that make these architectures universal also help keep them decodable.

Acknowledgments

We used OpenAI ChatGPT (GPT-5.6 Pro) and Anthropic Claude (Fable 5.1) to assist with refining and checking selected technical arguments, writing and debugging code used in our numerical analysis, identifying relevant literature, and editing the manuscript. We critically reviewed and revised all generated outputs and take full responsibility for the scientific content and conclusions. G.G. acknowledges support from the German Federal Ministry of Education and Research (BMBF) through the funded project ALMANAQ-C, grant number 13N17236 within the research program “Quantum Systems.”

Data availability

The data that support the findings of this article are publicly available [63].

Sampling assigned measurement outcomes

In Sec. II A, we argued that sampling assigned measurement outcomes is equivalent to sampling the actual measurement outcomes. Here, we establish this result. Since the argument is independent of the particular decoding method, we formulate the discussion at the logical level and, for simplicity, do not distinguish explicitly between logical and physical qubits.

Recall that, in the computational model considered here, a quantum computation is implemented by an adaptive Clifford circuit. Formally, such a circuit consists of a sequence of unitary Clifford blocks UiU_i and single-qubit Pauli XX and ZZ measurements MiM_i with outcomes mi=±1m_i = \pm1, where i∈{1,…,NM}i \in\{1,\ldots,N_M\} labels gates and measurements in temporal order. The adaptivity of the circuit implies that the gates may depend on previous measurement outcomes, i.e., Ui=Ui(m1,…,mi−1)U_i = U_i(m_1,\ldots,m_{i-1}). We further assume that gates that have been measured do not participate in the subsequent unitary evolution, so that [Mi,Ui]=0[M_i,U_i]=0 for all i<i′i < i'. This assumption is satisfied, in particular, for auxiliary qubits used in magic state injection.

The outcome of the computation is encoded in the joint probability distribution of the NMN_M measurement outcomes, denoted by p(m)p(\mathbf{m}), where m=(m1,…,mNM)\mathbf{m} = (m_1,\ldots,m_{N_M}). This distribution can be obtained by sampling realizations of the circuit. In each experimental run, the gate operations Ui=Ui(m1,…,mi−1)U_i = U_i(m_1,\ldots,m_{i-1}) and measurements MiM_i are performed sequentially, with each gate UiU_i conditioned on the actual outcomes m~i′\tilde{m}_{i'} of preceding measurements.

The initial state ∣ψ0⟩\lvert\psi_0\rangle is a product state of logical computational qubits prepared in ∣+⟩\lvert+\rangle or ∣0⟩\lvert0\rangle states and auxiliary qubits prepared in magic ∣T⟩\lvert T\rangle states where, as noted above, we omit the subscript L indicating that these are logical states. After NMN_M Clifford blocks UiU_i and measurements, MiM_i, the unnormalized state reads

∣ψ(m)⟩=PNMUNM⋯P1U1∣ψ0⟩(8)\lvert\psi(\mathbf{m})\rangle= P_{N_M}U_{N_M}\cdots P_1U_1\lvert\psi_0\rangle \tag*{(8)}

where the projection operators are given by

Pi=12(1+miMi).(9)P_i = \frac{1}{2}(1+m_iM_i). \tag*{(9)}

The probability of obtaining the sequence of measurement outcomes m\mathbf{m} when sampling the circuit is given by the norm of the state:

p(m)=∥∣ψ(m)⟩∥2.(10)p(\mathbf{m}) = \left\|\lvert\psi(\mathbf{m})\rangle\right\|^2. \tag*{(10)}

This representation of the probability distribution forms the starting point for establishing the equivalence between sampling actual and assigned measurement outcomes.

We thus distinguish for each measurement MiM_i between the assigned outcome mim_i and the actual outcome m~i\tilde{m}_i. The procedure for sampling assigned measurement outcomes is as follows. In step ii of the circuit execution, we first apply the gates Ui=Ui(m1,…,mi−1)U_i = U_i(m_1,\ldots,m_{i-1}), conditioned on the assigned values of the previous measurements. To determine the assigned value mim_i, we check whether MiM_i is reliable or, if MiM_i is unreliable, whether it is possible to form a reliable product containing MiM_i and previous measurements. As discussed in Sec. II A, this can be done by solving a linear system over F2\mathbb{F}_2. We denote the set of such measurements by R⊆{1,…,NM}\mathbf{R}\subseteq\{1,\ldots,N_M\}. For i∈Ri\in\mathbf{R}, we write the reliable Pauli product as Ri=∏i′=1iMi′Vi′,iR_i=\prod_{i'=1}^{i}M_{i'}^{V_{i',i}}, where Vi′,i∈F2V_{i',i}\in\mathbb{F}_2 with Vi,i=1V_{i,i}=1 determines whether Mi′M_{i'} is part of the reliable product. As noted above, the case in which MiM_i is reliable by itself is included as the special instance where Vi′,i=0V_{i',i}=0 for i′≠ii'\ne i.

We then measure the reliable product. At this point, all previous measurements Mi′M_{i'} with i′∈{1,…,i−1}i'\in\{1,\ldots,i-1\} have already been performed. Therefore, measuring RiR_i reduces to measuring MiM_i with actual outcome m~i\tilde{m}_i, corresponding to the outcome ri=∏i′=1im~i′Vi′,ir_i=\prod_{i'=1}^{i}\tilde{m}_{i'}^{V_{i',i}} for the measurement of RiR_i. The assigned value mim_i is then chosen such that the value of the reliable product is the same when expressed in terms of assigned values,

ri=∏i′=1imi′Vi′,i=∏i′=1im~i′Vi′,i,(11)r_i=\prod_{i'=1}^{i}m_{i'}^{V_{i',i}}=\prod_{i'=1}^{i}\tilde{m}_{i'}^{V_{i',i}}, \tag*{(11)}

which implies

mi=ri∏i′=1i−1mi′Vi′,i=m~i∏i′=1i−1(mi′m~i′)Vi′,i.(12)m_i=r_i\prod_{i'=1}^{i-1}m_{i'}^{V_{i',i}}=\tilde{m}_i\prod_{i'=1}^{i-1}(m_{i'}\tilde{m}_{i'})^{V_{i',i}}. \tag*{(12)}

If, instead, MiM_i is unreliable and is not part of any reliable product, we assign an outcome mi=±1m_i=\pm1 uniformly at random. We denote the set of these measurements by U={1,…,NM}∖R\mathbf{U}=\{1,\ldots,N_M\}\setminus\mathbf{R}.

The resulting unnormalized state is

∣ψ~(m,m~)⟩=P~NMUNM⋯P~1U1∣ψ0⟩.(13)\lvert\tilde{\psi}(\mathbf{m},\tilde{\mathbf{m}})\rangle=\tilde{P}_{N_M}U_{N_M}\cdots\tilde{P}_1U_1\lvert\psi_0\rangle. \tag*{(13)}

This should be compared with Eq. (8). There, both the gates UiU_i and the projectors PiP_i, which describe the collapse of the state induced by the measurement MiM_i, are determined by the same outcomes mim_i. In Eq. (13), by contrast, the assigned values mim_i determine only the gates UiU_i, while the collapse of the state is governed by the actual measurement outcomes m~i\tilde{m}_i,

P~i=12(1+m~iMi).(14)\tilde{P}_i=\frac{1}{2}(1+\tilde{m}_iM_i). \tag*{(14)}

Writing the state in this form already implicitly uses the fact that, for i∈Ri\in\mathbf{R}, measuring RiR_i with outcome rir_i is equivalent to measuring MiM_i with outcome m~i\tilde{m}_i, since all previous measurements appearing in the product have already been performed. The two outcomes are related by Eq. (11). To make this equation explicit, note that Eq. (11) can be rewritten as

m~i=ri∏i′=1i−1m~i′Vi′,i.(15)\tilde{m}_i=r_i\prod_{i'=1}^{i-1}\tilde{m}_{i'}^{V_{i',i}}. \tag*{(15)}

The projector (A7) can therefore be expressed as

P~i=12[1+ri(∏i′=1i−1m~i′Vi′,i)Mi].(16)\tilde{P}_i=\frac{1}{2}\left[1+r_i\left(\prod_{i'=1}^{i-1}\tilde{m}_{i'}^{V_{i',i}}\right)M_i\right]. \tag*{(16)}

In Eq. (13), the projectors corresponding to i∈Ri\in\mathbf{R} are multiplied from the right by projectors P~i′\tilde{P}_{i'} associated with earlier measurements, i′∈{1,…,i−1}i'\in\{1,\ldots,i-1\}. Since measured qubits do not participate in the subsequent evolution, the projectors P~i′\tilde{P}_{i'} commute with all unitary gate operators to their left. Using the identity m~i′P~i′=Mi′P~i′\tilde{m}_{i'}\tilde{P}_{i'}=M_{i'}\tilde{P}_{i'} together with Vi,i=1V_{i,i}=1, we may therefore rewrite P~i\tilde{P}_i as

P~i=12(1+riRi)=Pi.(17)\tilde{P}_i=\frac{1}{2}(1+r_iR_i)=P_i. \tag*{(17)}

In this form, it becomes clear that the projectors P~i\tilde{P}_i with i∈Ri\in\mathbf{R} enforce agreement between the actual and assigned outcomes of the reliable Pauli products RiR_i. Consequently, the state (A6), with the projectors written in this form, describes the logical state encountered in correlated decoding, where the products RiR_i are obtained through transversal measurements of all logical qubits contained in the product. The assigned outcomes are then completely determined by the randomly assigned values mim_i for measurements i∈Ui\in\mathbf{U} and the values of the reliable products rir_i for i∈Ri\in\mathbf{R}, which can be decoded efficiently.

As in Eq. (10), the probability of observing a sequence of assigned and actual measurement outcomes, m\mathbf{m} and m~\widetilde{\mathbf{m}}, respectively, is given by the norm of the state,

p~(m,m~)=12∣U∣∥∣ψ~(m,m~)⟩∥2.(18)\widetilde{p}(\mathbf{m},\widetilde{\mathbf{m}})=\frac{1}{2^{|U|}}\left\lVert\lvert\widetilde{\psi}(\mathbf{m},\widetilde{\mathbf{m}})\rangle\right\rVert^2. \tag*{(18)}

The prefactor accounts for the probability of selecting a particular sequence of randomly assigned outcomes for measurements i∈Ui \in U that are unreliable and cannot be combined with previous measurements to form a reliable product. We denote the number of such measurements by ∣U∣|U|. As we now show, the distribution of assigned measurement outcomes coincides with the distribution of actual measurement outcomes given in Eq. (10),

p(m)=2∣U∣p~(m,m~).(19)p(\mathbf{m})=2^{|U|}\widetilde{p}(\mathbf{m},\widetilde{\mathbf{m}}). \tag*{(19)}

On the right-hand side, m\mathbf{m} and m~\widetilde{\mathbf{m}} are not completely independent. For i∈Ri \in R, the assigned outcome mim_i is determined by the actual outcome m~i\widetilde{m}_i together with the previous assigned and actual outcomes through Eq. (12). By contrast, for i∈Ui \in U, the assigned outcome mim_i is chosen independently and uniformly at random, irrespective of the actual outcome m~i\widetilde{m}_i. We therefore need to show that the two probability distributions remain identical even when assigned and actual outcomes differ for an arbitrary subset M⊆UM \subseteq U of unreliable measurements.

We first establish Eq. (19) for the case in which all randomly assigned outcomes mim_i with i∈Ui \in U coincide with the corresponding actual outcomes m~i\widetilde{m}_i, that is, when M=∅M=\varnothing. In this situation, the assigned and actual outcomes also agree for all i∈Ri \in R. This can be shown inductively. Consider the smallest i∈Ri \in R. In Eq. (12), the product on the right-hand side involves only indices i′∈Ui' \in U, for which the assigned and actual outcomes coincide by assumption. It follows immediately that mi=m~im_i=\widetilde{m}_i. The same argument can then be applied successively to all remaining i∈Ri \in R in increasing order.

Since m=m~\mathbf{m}=\widetilde{\mathbf{m}}, the projectors (A2) and (A7) are identical, and Eq. (13) reduces to Eq. (8). Consequently, the probabilities defined in Eqs. (10) and (18) coincide up to the prefactor. This establishes Eq. (19) for the case in which mi=m~im_i=\widetilde{m}_i for all i∈Ui \in U.

To establish Eq. (19) in full generality, we now consider the case in which mi=−m~im_i=-\widetilde{m}_i for a subset of unreliable measurements i∈M⊆Ui \in M \subseteq U, while mi=m~im_i=\widetilde{m}_i for all i∈U∖Mi \in U\setminus M. We show that the set of measurements for which assigned and actual outcomes differ can be reduced iteratively until M=∅M=\varnothing. Specifically, for i∈Mi \in M, the projectors (A2) and (A7) project onto orthogonal subspaces,

P~i=12(1−miMi)=1−Pi.(20)\widetilde{P}_i=\frac{1}{2}(1-m_iM_i)=1-P_i. \tag*{(20)}

As we now demonstrate, the projectors P~i\widetilde{P}_i appearing in Eq. (13) can be replaced by PiP_i without affecting the distribution of assigned measurement outcomes. This is accomplished by iteratively “flipping” the measurements Mi→−MiM_i \rightarrow-M_i for each i∈Mi \in M.

Flipping measurements is accomplished by exploiting stabilizers of the initial state ∣ψ0⟩\lvert\psi_0\rangle. Recall that each logical computational qubit is initially prepared in either the ∣+⟩\lvert+\rangle or ∣0⟩\lvert0\rangle state. Consequently, the stabilizers of the initial state are products of Pauli XX and ZZ operators. As shown in [37], it is possible to choose a basis of stabilizers such that, for every unreliable measurement MiM_i with i∈Ui \in U, there exists a unique stabilizer Gi,i′G_{i,i'} whose forward propagation through the adaptive circuit to layer i′i',

Gi,i′=Ui′⋯U1GiU1†⋯Ui′†,(21)G_{i,i'}=U_{i'}\cdots U_1G_iU_1^\dagger\cdots U_{i'}^\dagger, \tag*{(21)}

anticommutes with MiM_i while commuting with all other unreliable measurements Mi′M_{i'} with i′∈U∖{i}i' \in U\setminus\{i\},

{Gi,i′,Mi}=[Gi,i′,Mi′]=0.(22)\{G_{i,i'},M_i\}=[G_{i,i'},M_{i'}]=0. \tag*{(22)}

In terms of projection operators, these relations can be rewritten as

(1−Pi)Gi,i′=Gi,i′Pi,PiGi,i′=Gi,i′Pi′.(23)\begin{aligned} (1-P_i)G_{i,i'}&=G_{i,i'}P_i,\\ P_iG_{i,i'}&=G_{i,i'}P_i'. \tag*{(23)} \end{aligned}

These commutation relations show that the stabilizer GiG_i can be used to flip the measurement MiM_i appearing in the projector P~i\widetilde{P}_i, while leaving all other projectors P~i′\widetilde{P}_{i'} with i′∈M∖{i}i'\in M\setminus\{i\} unchanged. To see that the projectors P~i′\widetilde{P}_{i'} with i′∈Ri'\in R are likewise unaffected by commutation with Gi,i′G_{i,i'}, note first that Gi,i′G_{i,i'} commutes with all reliable measurement products by construction. That is, for every i′∈Ri'\in R,

[Gi,i′,Ri′]=0.(24)[G_{i,i'},R_{i'}]=0. \tag*{(24)}

Using Eq. (17), this relation can be cast into the same form as the second line of Eq. (23).

Now consider i∈Mi\in M and use Gi∣ψ0⟩=∣ψ0⟩G_i\lvert\psi_0\rangle=\lvert\psi_0\rangle in Eq. (13). We commute GiG_i to the left using Ui′Gi′,i−1=Gi,i′Ui′U_{i'}G_{i',i-1}=G_{i,i'}U_{i'}. To commute Gi,i′G_{i,i'} through the projection operators, we use the relations in Eq. (23). In this way, P~i=1−Pi\widetilde{P}_i=1-P_i is transformed into PiP_i, while all other projectors with i′≠ii'\ne i remain unchanged. We then commute the stabilizer all the way to the left. Since the stabilizer is unitary, this does not affect the probability distribution (A11). Thus, MM is effectively replaced by M∖{i}M\setminus\{i\}. Repeating this procedure for all remaining elements of M∖{i}M\setminus\{i\} eventually yields M=∅M=\varnothing.

Finally, we iteratively use mi′Pi′=MiPi′m_i'P_i'=M_iP_i' to bring the projectors (A10) with i∈Ri\in R into the standard form of Eq. (9). This establishes Eq. (19). Hence, the outcomes of unreliable measurements can be assigned uniformly at random, provided that the assigned values of reliable products are chosen to coincide with their actual values.

Example: Bell state

We illustrate the equivalence of sampling assigned and actual measurement outcomes with two concrete examples. The first one is the preparation of a Bell state and subsequent measurement of correlations in the ZZ basis as shown in Figure 3(a). In the notation used above, the initial state is ∣ψ0⟩=∣+⟩∣0⟩|\psi_0\rangle= |+\rangle|0\rangle. The circuit has NM=2N_M = 2 layers with unitary gates and measurements given by

U1=CX1,2,M1=Z1,U2=1,M2=Z2.(25)U_1 = CX_{1,2},\quad M_1 = Z_1,\quad U_2 = 1,\quad M_2 = Z_2. \tag*{(25)}

Applying the CNOT gate to the initial state yields the Bell state ∣Φ⟩=U1∣ψ0⟩|\Phi\rangle= U_1|\psi_0\rangle.

The backpropagations of M1M_1 and M2M_2 terminate as Z1Z_1 on ∣+⟩|+\rangle and are thus unreliable. However, R2=M1M2R_2 = M_1M_2 is a reliable measurement product. The stabilizer that flips M1=Z1M_1 = Z_1 is given by G1=X1G_1 = X_1, with forward propagation G1,1=U1G1U1†=X1X2G_{1,1} = U_1G_1U_1^\dagger= X_1X_2 and G1,2=G1,1G_{1,2} = G_{1,1}. The forward propagation commutes with the reliable measurement product, [G1,2,R2]=0[G_{1,2}, R_2] = 0.

Let us first consider sampling the outcomes of M1M_1 and M2M_2 directly. The joint distribution of measurement outcomes reads

p(m)=∥P2P1∣Φ⟩∥2=12δm1,m2.(26)p(\mathbf{m}) = \lVert P_2P_1|\Phi\rangle\rVert^2 = \frac{1}{2}\delta_{m_1,m_2}. \tag*{(26)}

Instead, distinguishing between assigned and actual measurement outcomes, the joint distribution takes the form

p~(m,m~)=12∥P~2P~1∣Φ⟩∥2=14δm~1,m~2,(27)\widetilde{p}(\mathbf{m},\widetilde{\mathbf{m}}) = \frac{1}{2}\left\lVert\widetilde{P}_2\widetilde{P}_1|\Phi\rangle\right\rVert^2 = \frac{1}{4}\delta_{\widetilde{m}_1,\widetilde{m}_2}, \tag*{(27)}

where the assigned outcome of the second measurement is m2=m1m~1m~2m_2 = m_1\widetilde{m}_1\widetilde{m}_2 as follows from the condition that the reliable product R2=M1M2R_2 = M_1M_2 should take the same value when expressed in terms of assigned or actual measurement outcomes.

To check that the distributions for the two strategies agree, we first consider the case m1=m~1m_1 = \widetilde{m}_1. Then also m2=m~2m_2 = \widetilde{m}_2, and we directly obtain p(m)=2p~(m,m)p(\mathbf{m}) = 2\widetilde{p}(\mathbf{m},\mathbf{m}).

Let us now consider a mismatch between the assigned and actual outcomes of the first measurement, m1=−m~1m_1 = -\widetilde{m}_1. Expressing the projector P~2\widetilde{P}_2 in terms of the reliable product R2R_2 as in Eq. (17), we write the probability distribution as

p~(m,m~)=132∥(1+m1m2R2)(1−m1M1)∣Φ⟩∥2.(28)\widetilde{p}(\mathbf{m},\widetilde{\mathbf{m}}) = \frac{1}{32}\left\lVert(1+m_1m_2R_2)(1-m_1M_1)|\Phi\rangle\right\rVert^2. \tag*{(28)}

The minus sign in the projector containing M1M_1 can be flipped by inserting the stabilizer of the Bell state, ∣Φ⟩=G1,1∣Φ⟩|\Phi\rangle= G_{1,1}|\Phi\rangle, and using that M1G1,1=−G1,1M1M_1G_{1,1} = -G_{1,1}M_1 and M2G1,2=G1,2M2M_2G_{1,2} = G_{1,2}M_2. Finally, in the product with the projector P1=12(1+m1M1)P_1 = \frac{1}{2}(1+m_1M_1), the reliable product can be rewritten as R2P1=m1M2P1R_2P_1 = m_1M_2P_1, which again establishes the equality between the two sampling strategies.

In this example, the first measurement is unreliable with equiprobable outcomes. Accordingly, we can assign an outcome independently from the actual outcome. Also the second measurement is unreliable with equiprobable outcomes according to the marginal distribution p(m2)=∑m1=±1p(m1,m2)=1/2p(m_2) = \sum_{m_1=\pm1}p(m_1,m_2) = 1/2. However, during execution of the circuit, the outcome of the second measurement is conditioned on the outcome of the first measurement. Bell-state correlations result in the second measurement being deterministic: p(m2∣m1)=p(m1,m2)/p(m1)=δm1,m2p(m_2|m_1) = p(m_1,m_2)/p(m_1) = \delta_{m_1,m_2}. When sampling assigned measurement outcomes, these correlations are accounted for by requiring the assigned and actual values of the reliable product R2R_2 to agree, m1m2=m~1m~2m_1m_2 = \widetilde{m}_1\widetilde{m}_2.

Example: magic state injection

Our second example is the application of a TT gate on a qubit in the state ∣+⟩|+\rangle through magic state injection,

Circuit for magic state injection

Figure A22.

Here, the initial state is ∣ψ0⟩=∣+⟩∣T⟩|\psi_0\rangle= |+\rangle|T\rangle. The first layer of the circuit consists of a CNOT gate and a measurement of the auxiliary qubit in the ZZ basis,

U1=CX1,2,M1=Z2.(29)U_1 = CX_{1,2},\qquad M_1 = Z_2. \tag*{(29)}

The measurement M1M_1 is unreliable. In the second layer of the circuit, feedforward is applied based on the assigned outcome m1m_1, and the computational qubit is measured in the XX basis,

U2(m1)={1m1=+1,S1m1=−1,M2=X1.(30)U_2(m_1) = \begin{cases} 1 & m_1 = +1,\\ S_1 & m_1 = -1, \end{cases} \qquad M_2 = X_1. \tag*{(30)}

The second measurement is reliable for m1=+1m_1 = +1 and unreliable for m1=−1m_1 = -1. In the latter case, however, the product R2=M1M2=X1Z2R_2 = M_1M_2 = X_1Z_2 is reliable. The stabilizer that flips M1=Z2M_1 = Z_2 is G1=X1G_1 = X_1 with forward propagation G1,1=U1G1U1†=X1X2G_{1,1} = U_1G_1U_1^\dagger= X_1X_2 and

G1,2={X1X2m1=+1,−Y1X2m1=−1.(31)G_{1,2} = \begin{cases} X_1X_2 & m_1 = +1,\\ -Y_1X_2 & m_1 = -1. \end{cases} \tag*{(31)}

For m1=+1m_1 = +1, G1,2G_{1,2} commutes with the reliable measurement M2=X1M_2 = X_1; for m1=−1m_1 = -1, G1,2G_{1,2} commutes with the reliable measurement product R2=X1Z2R_2 = X_1Z_2. As in the previous example, inserting the stabilizer G1G_1 of the initial state allows us to correct a potential mismatch between the assigned and actual outcomes of the first, unreliable measurement, and thus establish the equivalence between the different sampling strategies.

Finally, it is instructive to consider the case of a computational qubit in the state ∣0⟩|0\rangle, so that the first measurement M1=Z2M_1 = Z_2 is reliable. Since the backpropagation of M1M_1 terminates as Z2Z_2 on the auxiliary qubit in the state ∣T⟩|T\rangle, both outcomes of the reliable measurement M1M_1 are equiprobable. However, we are not allowed to randomly assign the outcome of M1M_1. The reason for this is that while ∣T⟩\lvert T\rangle states are +1+1 eigenstates of TXT†=(X+Y)/2TXT^\dagger= (X+Y)/\sqrt{2}, this operator is not contained in the Pauli group. Hence it cannot be used to correct a mismatch between assigned and actual outcomes of the auxiliary qubit measurement.

Additional circuit layouts and gate ensembles

In our analysis of the decoding complexity in § 2, we focused primarily on the random brickwork circuits shown in Figure 1, in which two-qubit Clifford gates act on neighboring computational qubits in a one-dimensional geometry. Here, we show that the qualitative conclusions of this analysis are robust to changes in both the connectivity and the Clifford gate ensemble.

We compare three circuit ensembles in Figure 6. The brickwork-circuit results shown in Figure 4 are reproduced in Figure 6(a) for reference. In Figure 6(b), we retain the same random two-qubit Clifford gates but replace the one-dimensional nearest-neighbor connectivity by all-to-all connectivity: in each Clifford layer, the computational qubits are randomly paired and a random two-qubit Clifford gate is applied to each pair. Figure 6(c) considers an all-to-all circuit constructed directly from Clifford generators. Each Clifford layer consists of a single-qubit sublayer, in which one of {I,H,S}\{I,H,S\} is applied independently to every computational qubit with equal probability, and a two-qubit sublayer, consisting of CNOT gates on a random pairing of the computational qubits. The nontrivial Clifford gates are therefore drawn from the generating set {H,S,CX}\{H,S,CX\}, which admits fold-transversal implementations with surface-code logical qubits [29, 30].

Figure 6. Decoding complexity for different circuit architectures. Main panels show the stationary distribution p(NC)p(N_C) of the normalized check count, while the insets show the average NCN_C as a function of circuit layer tt. Colors indicate the magic state injection probability κ\kappa, while marker shapes distinguish N=16N=16 and 128128. (a) Random two-qubit Clifford gates in a one-dimensional nearest-neighbor brickwork geometry; the data are the same as in Figure 4 and are reproduced here for comparison. (b) The same random two-qubit Clifford gates applied to random pairings of qubits with all-to-all connectivity. (c) All-to-all circuit constructed from the generating set {H,S,CX}\{H,S,CX\} of the Clifford group.

For all three ensembles, we consider N=16N=16 and 128128 computational logical qubits and four values of the magic state injection probability κ\kappa. The data are averaged over Nreal=104N_{\mathrm{real}}=10^4 and 10310^3 circuit realizations for N=16N=16 and 128128, respectively, using the same procedure as in § 2 B. Reliable measurement products are selected using the Free prescription introduced in § 2 C.

Across all three circuit ensembles, we observe the same qualitative behavior found for the brickwork circuits in § 2 B. After an initial transient and overshoot, the average normalized check count approaches a stationary value NC,∞N_{C,\infty}. At fixed κ\kappa, this stationary value becomes independent of the number of computational qubits NN, although its value depends on the circuit ensemble through the number of checks per circuit layer as discussed below. Likewise, the stationary distributions shown in the main panels of Figure 6 are insensitive to NN and exhibit approximately exponential suppression at large NCN_C, with increasingly steep tails for increasing κ\kappa.

The stationary values NC,∞N_{C,\infty} can be understood using the same counting argument as in § 2 B. For the brickwork and all-to-all circuits in Figure 6(a) and Figure 6(b), the gate structure and syndrome-extraction schedule are identical and the circuits differ only in their connectivity. The counting argument therefore applies unchanged, yielding the stationary value in Eq. (6).

For the Clifford-generator circuit in Figure 6(c), the Clifford part of each circuit layer instead contains separate single- and two-qubit sublayers, contributing 2N2N checks each. Following the same counting argument as in § 2 B, the stationary value is therefore modified to

NC,∞=8+3κκ,(32)N_{\mathrm{C},\infty} = \frac{8+3\kappa}{\kappa}, \tag*{(32)}

which accounts for the larger stationary check counts observed in Figure 6(c).

For the all-to-all circuits in Figure 6(b) and Figure 6(c), a weak dependence on NN remains visible during the transient overshoot at the smallest injection probability, κ=0.2\kappa= 0.2. Instead, for larger κ\kappa, the results for N=16N = 16 and 128128 agree closely throughout the evolution. Therefore, we expect also the residual transient dependence at κ=0.2\kappa= 0.2 to disappear with increasing NN.

In summary, these results support the conclusion that the bounded decoding complexity found in § 2 B is not specific to the one-dimensional brickwork geometry or to the particular Clifford gate ensemble used there.

Scaling form of the stationary distribution

The one-parameter scaling form (7) implies that the decay rate bb of the exponential tail and the standard deviation σ\sigma of the stationary distribution scale as b∼καb \sim\kappa^\alpha and σ∼κ−α\sigma\sim\kappa^{-\alpha}, respectively. Here, we test these predictions for the circuit ensembles introduced in Appendix B and examine the resulting collapse of the full distributions.

Figure 7(a) shows that the tail decay rates exhibit approximate power-law behavior for both brickwork and all-to-all circuits, which are composed of random two-qubit Clifford gates and differ only in their connectivity.

The fitted exponents are α=0.98\alpha= 0.98 and α=0.92\alpha= 0.92, respectively. By contrast, no comparable power-law dependence is observed for Clifford-generator circuits.

Extracting the decay rate requires fitting the sparsely sampled large-NCN_{\mathrm{C}} tails, making the results sensitive to statistical noise. We therefore also consider the standard deviation σ\sigma, which provides a more robust measure of the width of the distribution. As shown in Figure 7(b), we find approximate power-law behavior σ∼κ−α\sigma\sim\kappa^{-\alpha} for brickwork and all-to-all circuits, with exponents α=0.91\alpha= 0.91 and α=0.94\alpha= 0.94, respectively. Taken together, the fitted exponents favor a nontrivial value α<1\alpha< 1, with estimates in the range 0.9≲α≲10.9 \lesssim\alpha\lesssim1. Their spread is too large to resolve a possible dependence on circuit connectivity or to conclusively exclude α=1\alpha= 1.

Figure 7. Scaling analysis of the stationary check-count distributions in Figure 6. (a) Decay rate bb of the exponential tail as a function of κ\kappa. Power-law fits b∼καb \sim\kappa^\alpha yield α=0.98\alpha= 0.98 for brickwork circuits and α=0.92\alpha= 0.92 for all-to-all circuits. (b) Standard deviation σ\sigma of the stationary distributions. Fits to σ∼κ−α\sigma\sim\kappa^{-\alpha} yield α=0.91\alpha= 0.91 and α=0.94\alpha= 0.94 for brickwork and all-to-all circuits, respectively. Neither observable exhibits a comparable power-law dependence for Clifford-generator circuits. (c) Collapse of the stationary distributions for brickwork and all-to-all circuits according to Eq. (7), using the exponents obtained from the fits to σ∼κ−α\sigma\sim\kappa^{-\alpha} in (b). Insets show the distributions before rescaling.

Finally, using the exponents obtained from the standard deviations, we rescale the stationary distributions according to Eq. (7). As shown in Figure 7(c), the data collapse well for both brickwork and all-to-all circuits over a broad range of the scaling variable. The remaining deviations are concentrated at small values of the scaling variable, where details of the microscopic circuit structure may become important.

References

References

  1. [1]M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, England, 2002).
  2. [2]B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).
  3. [3]E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017).DOI
  4. [4]D. Gottesman, Opportunities and Challenges in Fault-Tolerant Quantum Computation, arXiv:2210.15844 [quant-ph] (2022).
  5. [5]J. Eisert and J. Preskill, Mind the gaps: The fraught road to quantum advantage, arXiv:2510.19928 [quant-ph] (2025).arxiv.org/abs/2510.19928
  6. [6]S. Krinner et al., Realizing repeated quantum error correction in a distance-three surface code, Nature 605, 669 (2022).
  7. [7]J. F. Marques, B. M. Varbanov, M. S. Moreira, H. Ali, N. Muthusubramanian, C. Zachariadis, F. Battistel, M. Beekman, N. Haider, W. Vlothuizen, A. Bruno, B. M. Terhal, and L. DiCarlo, Logical-qubit operations in an error-detecting surface code, Nat. Phys. 18, 80 (2022).
  8. [8]V. V. Sivak, A. Eickbusch, B. Royer, S. Singh, I. Tsiout­sios, S. Gan­jam, A. Miano, B. L. Brock, A. Z. Ding, L. Frunzio, S. M. Girvin, R. J. Schoelkopf, and M. H. Devoret, Real-time quantum error correction beyond break-even, Nature 616, 50 (2023).DOI
  9. [9]Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit, Nature 614, 676 (2023).
  10. [10]N. Sundaresan, T. J. Yoder, Y. Kim, M. Li, E. H. Chen, G. Harper, T. Thorbeck, A. W. Cross, A. D. Córcoles, and M. Takita, Demonstrating multi-round subsystem quantum error correction using matching and maximum likelihood decoders, Nat. Commun. 14, 2852 (2023).
  11. [11]R. S. Gupta, N. Sundaresan, T. Alexander, C. J. Wood, S. T. Merkel, M. B. Healy, M. Hillenbrand, T. Jochym-O’Connor, J. R. Wootton, T. J. Yoder, A. W. Cross, M. Takita, and B. J. Brown, Encoding a magic state with beyond break-even fidelity, Nature 625, 259 (2024).
  12. [12]H. Putterman et al., Hardware-efficient quantum error correction via concatenated bosonic qubits, Nature 638, 927 (2025).
  13. [13]Google Quantum AI and Collaborators, Quantum error correction below the surface code threshold, Nature 638, 920 (2025).
  14. [14]W. Lin et al., Surface code logical operations on a superconducting quantum processor, arXiv:2607.01473 [quant-ph] (2026).
  15. [15]Y. Wang et al., A superconducting surface-code processor with lattice-surgery logical operations, arXiv:2606.06598 [quant-ph] (2026).
  16. [16]L. Egan, D. M. Debroy, C. Noel, A. Risinger, D. Zhu, D. Biswas, M. Newman, M. Li, K. R. Brown, M. Cetina, and C. Monroe, Fault-tolerant control of an error-corrected qubit, Nature 598, 281 (2021).
  17. [17]C. Ryan-Anderson et al., Realization of Real-Time Fault-Tolerant Quantum Error Correction, Phys. Rev. X 11, 041058 (2021).
  18. [18]L. Postler, S. Heußen, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, P. Schindler, M. Müller, and T. Monz, Demonstration of fault-tolerant universal quantum gate operations, Nature 605, 675 (2022).
  19. [19]A. Steiner, T. Andrzejewski, P. Rembold, H. P. Nautrup, C. D. Marciniak, R. Freund, I. Pogorelov, T. Monz, P. Schindler, M. Meyer, and N. Friis, Genuine Multipartite Entanglement between Logical Qubits via Cross-Code Lattice Surgery, arXiv:2607.04227 [quant-ph] (2026).
  20. [20]D. Bluvstein et al., Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024).
  21. [21]D. Bluvstein et al., A fault-tolerant neutral-atom architecture for universal quantum computation, Nature 649, 39 (2026).DOI
  22. [22]B. W. Reichardt et al., Fault-tolerant quantum computation with a neutral atom processor, arXiv:2411.11822 [quant-ph] (2025).
  23. [23]P. Sales Rodriguez et al., Experimental demonstration of logical magic state distillation, Nature 645, 620 (2025).
  24. [24]W. C. Chung et al., Fault-tolerant operation and materials science with neutral atom logical qubits, npj Quantum Inf. 11, 193 (2025).
  25. [25]A. Computing and Collaborators, Quantum error correction with the toric code, arXiv:2606.04079 [quant-ph] (2026).
  26. [26]A. Ransford et al., A 98-qubit trapped-ion quantum computer with all-to-all connectivity, Nature 655, 81 (2026).arxiv.org/abs/2511.05465
  27. [27]S. J. Evered, M. Xu, S. H. Li, A. A. Geim, J. P. B. Ataides, M. Kalinowski, D. Bluvstein, N. Maskara, C. Kokail, M. Greiner, V. Vuletić, and M. D. Lukin, High-fidelity entangling gates and nonlocal circuits with neutral atoms, arXiv:2604.25987 [quant-ph] (2026).
  28. [28]H. Bombin and M. A. Martin-Delgado, Topological Quantum Distillation, Phys. Rev. Lett. 97, 180501 (2006).DOI
  29. [29]J. E. Moussa, Transversal Clifford gates on folded surface codes, Phys. Rev. A 94, 042316 (2016).
  30. [30]N. P. Breuckmann and S. Burton, Fold-Transversal Clifford Gates for Quantum Codes, Quantum 8, 1372 (2024).
  31. [31]S. Bravyi and R. König, Classification of Topologically Protected Gates for Local Stabilizer Codes, Phys. Rev. Lett. 110, 170503 (2013).
  32. [32]B. Eastin and E. Knill, Restrictions on Transversal Encoded Quantum Gate Sets, Phys. Rev. Lett. 102, 110502 (2009).
  33. [33]H. Zhou, C. Zhao, M. Cain, D. Bluvstein, N. Maskara, C. Duckering, H.-Y. Hu, S.-T. Wang, A. Kubica, and M. D. Lukin, Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation, Nature 646, 303 (2025).
  34. [34]C. Ryan-Anderson et al., High-fidelity teleportation of a logical qubit using transversal gates and lattice surgery, Science 385, 1327 (2024).
  35. [35]S. Dasu et al., Computing with many encoded logical qubits beyond break-even, arXiv:2602.22211 [quant-ph] (2026).
  36. [36]M. Cain, C. Zhao, H. Zhou, N. Meister, J. P. B. Ataides, A. Jaffe, D. Bluvstein, and M. D. Lukin, Correlated Decoding of Logical Algorithms with Transversal Gates, Phys. Rev. Lett. 133, 240602 (2024).arxiv.org/abs/2505.13587
  37. [37]M. Cain, D. Bluvstein, C. Zhao, S. Gu, N. Maskara, M. Kalinowski, A. A. Geim, A. Kubica, M. D. Lukin, and H. Zhou, Fast correlated decoding of transversal logical algorithms, arXiv:2505.13587 [quant-ph] (2025).arxiv.org/abs/2505.13587
  38. [38]K. H. Wan, M. Webber, A. G. Fowler, and W. K. Hensinger, An iterative transversal CN0T decoder, arXiv:2407.20976 [quant-ph] (2025).
  39. [39]M. Serra-Peralta, M. H. Shaw, and B. M. Terhal, Decoding across Transversal Clifford Gates in the Surface Code, PRX Quantum 7, 010335 (2026).
  40. [40]E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, J. Math. Phys. 43, 4452 (2002).DOI
  41. [41]D. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14, 123011 (2012).DOI
  42. [42]K. Sahay, Y. Lin, S. Huang, K. R. Brown, and S. Puri, Error Correction of Transversal Cnot Gates for Scalable Surface-Code Computation, PRX Quantum 6, 020326 (2025).DOI
  43. [43]Y. Zhou, C. Wan, Y. Xu, J. P. Zhou, K. Q. Weinberger, and E.-A. Kim, Learning to decode logical circuits, Nat. Comput. Sci. 5, 1158 (2025).arxiv.org/abs/2504.16999
  44. [44]J. Zhang, Z.-Y. Chen, J.-N. Li, T.-H. Wei, H.-Y. Liu, X.-N. Zhuang, Q.-S. Li, Y.-C. Wu, and G.-P. Guo, Scalable Constant-Time Logical Gates for Large-Scale Quantum Computation Using Window-Based Correlated Decoding, arXiv:2410.16963 [quant-ph] (2025).arxiv.org/abs/2410.16963
  45. [45]M. L. Turner, E. T. Campbell, O. Crawford, N. I. Gillespie, and J. Camps, Scalable Decoding Protocols for Fast Transversal Logic in the Surface Code, PRX Quantum 7, 010320 (2026).arxiv.org/abs/2505.23567
  46. [46]J. P. Bonilla Ataides, A. Gu, S. F. Yelin, and M. D. Lukin, Neural Decoders for Universal Quantum Algorithms, PRX Intelligence 1, 013008 (2026).DOI
  47. [47]M. Webber, S. Sadana, M. A. Lane, L. J. Robson, and A. O’Rourke, High-Accuracy Propagation-Assisted Local Decoding for Fast Transversal Clifford Circuits, arXiv:2610.26784 [quant-ph] (2026).arxiv.org/abs/2610.26784
  48. [48]D. Gottesman, The Heisenberg Representation of Quantum Computers, arXiv:quant-ph/9807006 (1998).arxiv.org/abs/quant-ph/9807006
  49. [49]S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004).DOI
  50. [50]S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas, Phys. Rev. A 71, 022316 (2005).DOI
  51. [51]O. Higgott and C. Gidney, Sparse Blossom: Correcting a million errors per core second with minimum-weight matching, Quantum 9, 1600 (2025).DOI
  52. [52]D. Poulin and Y. Chung, On the iterative decoding of sparse quantum codes, Quantum Info. Comput. 8, 987 (2008).arxiv.org/abs/0801.1241
  53. [53]M.-H. Hsieh and F. Le Gall, NP-hardness of decoding quantum error-correction codes, Phys. Rev. A 83, 052331 (2011).DOI
  54. [54]K.-Y. Kuo and C.-C. Lu, On the hardness of decoding quantum stabilizer codes under the depolarizing channel, in 2012 International Symposium on Information Theory and Its Applications (2012) pp. 208–211.
  55. [55]P. Iyer and D. Poulin, Hardness of Decoding Quantum Stabilizer Codes, IEEE Trans. Inform. Theory 61, 5209 (2015).
  56. [56]Throughout, we use the terms reliable and unreliable for measurements and measurement products, following Ref. [37]; unreliable measurements are equivalent to the fragile measurements of Ref. [39].
  57. [57]A.Yu. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2 (2003).DOI
  58. [58]A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012).DOI
  59. [59]C. Gidney, Stim: A fast stabilizer circuit simulator, Quantum 5, 497 (2021).DOI
  60. [60]J. Roffe, LDPC: Python tools for low density parity check codes (2022).
  61. [61]J. Roffe, D. R. White, S. Burton, and E. Campbell, Decoding across the quantum low-density parity-check code landscape, Phys. Rev. Research 2, 043423 (2020).DOI
  62. [62]A. Ignatiev, A. Morgado, and J. Marques-Silva, PySAT: A Python Toolkit for Prototyping with SAT Oracles, in Theory and Applications of Satisfiability Testing – SAT 2018, Vol. 10929, edited by O. Beyersdorff and C. M. Wintersteiger (Springer International Publishing, Cham, 2018) pp. 428–437.DOI
  63. [63]L. M. Sieberer and G. Giudice, Data for “Bounded decoding complexity in transversal circuits with magic-state injection”, Zenodo (2026), https://doi.org/10.5281/zenodo.23371719.

Paper details

vlnc:W_ybfzrbsb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

OpenAI ChatGPT (GPT-5.6 Pro), Claude Fable 5.1 (bare)

View statement
Looking for related papers…
Contents