ABSTRACT Title of Dissertation: PRACTICAL APPLICATIONS FOR PARTIAL QUANTUM ERROR CORRECTION Noah Berthusen Doctor of Philosophy, 2025 Dissertation Directed by: Professor Daniel Gottesman Department of Computer Science Quantum computers have the theoretical potential to solve problems intractable for classi- cal computers. However, realizing this potential requires dealing with the noise inherent in near and far-term devices. One way of doing this is to redundantly encode the quantum information in a quantum error-correcting code and manipulate the encoded states to do computation. Protecting quantum information in this way incurs additional space overhead in the form of extra qubits; this is problematic since qubits are a scarce resource, especially for near-term quantum computers. Reducing these overheads could significantly accelerate the arrival of large-scale, fault-tolerant quantum computation. In this thesis, we address this topic of research and present techniques which aim to prac- tically reduce the space and time overheads of implementing quantum error correction. The overarching motivation for the works presented in this thesis is the belief that it is advantageous, perhaps even essential, to measure every stabilizer generator when performing quantum error cor- rection. To address this claim, we introduce partial quantum error correction, which we broadly define to be using incomplete syndrome information from the code or neglecting to correct errors on some part of the system. We show that it is not necessary to measure every stabilizer genera- tor in order to obtain a threshold, and we will describe several situations where we obtain better logical performance and/or reduced overheads by not doing so. In particular, we present an error correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We show through numerical simulations that high-rate quantum error correcting codes implemented with this protocol achieve logical error rates comparable to the surface code while using fewer physical qubits. We then introduce adaptive syndrome extraction as a scheme to improve code performance and reduce the quantum error correction cycle time by measuring only the stabilizer generators that are likely to provide useful syndrome information. We describe and numerically evaluate a concrete example of the scheme instantiated using a concatenated code and a syndrome extraction cycle that uses quantum error detection to modify the syndrome extraction circuits in real time. PRACTICAL APPLICATIONS FOR PARTIAL QUANTUM ERROR CORRECTION by Noah Berthusen Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2025 Advisory Committee: Professor Daniel Gottesman, Chair/Advisor Professor Michael J. Gullans, Co-chair Professor Andrew M. Childs Professor Runzhou Tao Professor Saikat Guha, Dean’s Representative © Copyright by Noah Berthusen 2025 Acknowledgments Firstly, I would like to thank my advisor Daniel Gottesman for guidance and support throughout my PhD. Coming to the University of Maryland, I had no prior experience with quan- tum error correction, and Daniel is one of the best resources to learn from. While Daniel’s work is often more theoretical, I am grateful that he supported me in specializing in a more numerical, experimental QEC focus. I wouldn’t have started in quantum computing were it not for Peter Orth. I am grateful he asked me if I wanted to learn quantum computing just as he was beginning as well. Had he not, I’d most likely be doing something less exciting and much less fulfilling. The following years and resulting research were invaluable to building my base as a researcher, and they were likely one of the main reasons why I got into a PhD program in the first place—and was successful during my time at UMD. I am also grateful to many other professors and students from QuICS who I have had the privilege of working with. Michael Gullans has been great (un)official co-advisor and was a driving factor in getting the work of Chapter 4 started. Alexey Gorshkov was also a big help in producing Chapter 4, and his enthusiasm for the work was always appreciated. I’d also like to thank the QEC team at Quantinuum for having me as an intern during the summers. They, too, gave me great freedom in terms of research direction, and I learned a lot during my time there. Additionally, discussions with Ciarán Ryan-Anderson and Natalie Brown helped bring about the idea on which Chapter 5 is based. ii I am grateful to my friends who made my time in Maryland and DC excellent. In particular, I would like to thank Yuelin Liu, Shramay Palta, and Ethan Hickman for being great housemates and filling my first year with good food. I am grateful to Matt Chan, Jon Nelson, and Joel Ra- jakumar for being good friends practically from the very first research day. R.I.P. Town Hall. The Los Alamos Quantum Computing summer school also brought me new friends including George Umbrarescu and Shi Jie Samuel Tan, the latter of whom was a very good research influence dur- ing the final years of my program. I’d like to extend a thanks to my old friends, Simon, Claire, Heidi, Bryce, and Austin for being great climbing partners and making my summers in Colorado great. Additionally, I’d like Dakota, Drew, Izaak, and Grant for making my time back in Iowa enjoyable and being great long-time friends. Finally, I am grateful for my family for their love and support. Over the past three years I’ve probably spent more time with my cat Olive than just about anyone else, and given the number of times she has walked across my keyboard during the writing of this thesis and my other papers, she ought to be included as a coauthor. To my parents and grandparents, I am thankful for all the encouragement I have received throughout my life and for instilling in me the work ethic to accomplish this. I would especially like to thank my wonderful fiancé, Kelsey Riemenschneider, for moving across the country for me and supporting me during these exciting four years. iii Table of Contents Acknowledgements ii Table of Contents iv List of Tables vi List of Figures vii Chapter 1: Introduction 1 1.1 Relation to previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Partial error correction . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Floquet codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Single-shot QEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.4 Approximate quantum error correction . . . . . . . . . . . . . . . . . . . 6 1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Chapter 2: Preliminary material 9 2.1 Classical error correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Quantum information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Error models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Quantum error correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 Hypergraph product codes . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Bivariate bicycle codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.3 Iceberg codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.4 Concatenated codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.5 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Chapter 3: Masking and partial syndrome measurement 41 3.1 The stacked model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2 Syndrome masking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.1 Masking and the stacked model . . . . . . . . . . . . . . . . . . . . . . 49 3.3 Analytic results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Numerical simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4.1 2D hyperbolic surface codes . . . . . . . . . . . . . . . . . . . . . . . . 60 3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Chapter 4: 2D local implementations of nonlocal codes 66 iv 4.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 Teleportation routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3 Implementing the stacked model . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.4 Routing bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.4.1 Greedy routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.5 Bilayer architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.5.1 Syndrome extraction circuits . . . . . . . . . . . . . . . . . . . . . . . . 83 4.6 Numerical simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Chapter 5: Adaptive syndrome extraction 100 5.1 Adaptive syndrome extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.2 Canonical logical basis for hypergraph product codes . . . . . . . . . . . . . . . 107 5.2.1 Assignment of [[4,2,2]] logical qubits . . . . . . . . . . . . . . . . . . . 108 5.3 Logical Computation for [[4,2,2]]-concatenated hypergraph product codes . . . . 109 5.4 Numerical simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.4.1 [[4,2,2]]-concatenated decoding . . . . . . . . . . . . . . . . . . . . . . 112 5.4.2 Memory experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.5.1 2D-local implementations of nonlocal codes . . . . . . . . . . . . . . . . 127 5.5.2 Modular QPU architectures . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Chapter 6: Conclusion 133 Appendix A: Decoding algorithms 136 A.1 Small-set flip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 A.2 Belief propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 A.3 Ordered statistic decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Appendix B: Logical computation for [[4,2,2]]-concatenated hypergraph product codes 143 B.1 Logical operators for the [[4,2,2]] code . . . . . . . . . . . . . . . . . . . . . . . 143 B.2 Clifford Logical Operators for [[4,2,2]]-concatenated HGP codes . . . . . . . . . 146 B.3 Universal Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Bibliography 171 v List of Tables 2.1 Stabilizer generators for the [[5, 1, 3]] five-qubit code. . . . . . . . . . . . . . . . 15 2.2 Stabilizer generators and logical operators for a [[8, 2, 2]] code obtained from the concatenation of the [[4, 2, 2]] code with itself according to Procedure 1. . . . . . 34 3.1 Extracted values of Λ for different masking percentages and schedules. . . . . . . 60 4.1 Examples of BB qLDPC codes found through a computer search and their result- ing parameters and properties. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.2 Code parameters, total number of qubits used, and logical memory performance for BB and surface codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.3 Code parameters, total number of qubits used, and logical memory performance for BB and surface codes with no idle error. . . . . . . . . . . . . . . . . . . . . 95 5.1 Average check weight, w, and average number of generators each qubit partici- pates in, q, for several HGP and concatenated-HGP codes. . . . . . . . . . . . . 124 B.1 SWAP-transversal logical Clifford gates of the [[4, 2, 2]] code. . . . . . . . . . . . 144 B.2 Logical Clifford gates of the [[4, 2, 2]] code via embedded code technique. . . . . 144 vi List of Figures 2.1 Tanner graph for the [7, 4, 3] Hamming code. . . . . . . . . . . . . . . . . . . . . 10 2.2 Example errors and syndromes for the Hamming code. . . . . . . . . . . . . . . 11 2.3 Circuits for measuring the eigenvalues of an X- and Z-type generator. . . . . . . 17 2.4 Tanner graph for the Steane code. . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Tanner graph of a hypergraph product code. . . . . . . . . . . . . . . . . . . . . 22 2.6 A commutative diagram representing the double complex that arises from the tensor product of two 2-term chain complexes. . . . . . . . . . . . . . . . . . . . 25 2.7 Canonical logical basis for HGP codes. . . . . . . . . . . . . . . . . . . . . . . . 28 2.8 Parity check matrix for a hypergraph product code. . . . . . . . . . . . . . . . . 29 2.9 Parity check matrix for a hypergraph product code with additional columns to account for syndrome noise. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.10 Detectors for a portion of the bit-flip repetition code. . . . . . . . . . . . . . . . 39 3.1 Illustration of stacked model layer interaction radius and frequency. . . . . . . . 44 3.2 Overview of the stacked model. . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3 Logical memory performance for quantum expander codes across several mask- ing percentages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Distance versus logical error rate per round across several masking percentages. . 59 3.5 Logical memory performance for the 2D hyperbolic surface code. . . . . . . . . 61 4.1 Overview of gate teleportation, the bilayer architecture, and BB code embeddings. 72 4.2 Depth from greedy routing versus the theoretical optimal routing depth. . . . . . 78 4.3 Long- and short-range generators of a single type for a BB code. . . . . . . . . . 81 4.4 Example five-step schedule to route and purify the Bell pairs needed to measure the short-range, Z-type generators of a BB code. . . . . . . . . . . . . . . . . . . 84 4.5 Implementing multiple long-range Bell pair purifications in parallel. . . . . . . . 84 4.6 Entanglement purification simulation results. . . . . . . . . . . . . . . . . . . . . 87 4.7 Qubit usage versus logical performance. . . . . . . . . . . . . . . . . . . . . . . 90 4.8 Logical memory performance of BB codes on the proposed bilayer architecture. . 92 4.9 Potential circuit depth savings versus unmasking frequency. . . . . . . . . . . . . 94 4.10 Logical memory performance of BB codes on the proposed bilayer architecture with no idling errors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.1 A QED+QEC concatenated code. . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.2 Stabilizer structure of Iceberg-concatenated HGP codes. . . . . . . . . . . . . . . 104 5.3 Assignment of physical HGP qubits to logical Iceberg qubits. . . . . . . . . . . . 108 5.4 Circuit to measure an X-type concatenated HGP generator. . . . . . . . . . . . . 115 vii 5.5 Logical memory performance for non-concatenated and adaptive, concatenated quantum expander codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.6 Existence of single-shot QEC for non-concatenated and adaptive, concatenated quantum expander codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.7 Threshold for non-concatenated and adaptive, concatenated quantum expander codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.8 Logical memory performance of non-concatenated and adaptive, concatenated La-cross codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.9 Logical error rate per round as a function of the blocklength for concatenated codes and the adaptive scheme, non-concatenated codes, and surface codes. . . . 125 5.10 Layout of the data and check qubits of a La-cross code. . . . . . . . . . . . . . . 129 A.1 Example of the search process SSF uses when searching for a correction. . . . . . 138 B.1 Circuit for preparing the |0+⟩ state. . . . . . . . . . . . . . . . . . . . . . . . . . 145 B.2 Circuit for a logical-physical CNOT gate. . . . . . . . . . . . . . . . . . . . . . 158 B.3 Logical quantum circuit for performing logical CNOT gate between intra-block logical qubits, |ψ⟩ , |ϕ⟩. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 B.4 Fault-tolerant circuit for implementing S1 = S1S3CZ1,3 on the [[4, 2, 2]] code. . 165 B.5 Logical quantum circuit for teleporting the logical S gate to the logical qubits that do not lie on the principal diagonal. . . . . . . . . . . . . . . . . . . . . . . . . . 166 viii Chapter 1: Introduction Quantum computers have the theoretical potential to solve problems intractable for classi- cal computers. Notably, the simulation of quantum many-body systems, as originally proposed by Feynman [1], and integer factorization [2] are believed to provide superpolynomial speed-ups over classical computing. Applying these and other methods could yield advances in material science, drug discovery, optimization, machine learning, cryptography, and more. However, the current generation of quantum computers are are small, with around ∼ 102 − 103 qubits, and noisy, with error rates around 0.1% per operation [3–6]. At these scales, we are unable to ex- ecute the most promising applications of quantum computing, which may require closer to 106 qubits [7] and circuits with millions or billions of operations. In this noisy intermediate-scale quantum (NISQ) era [8], as it has been called, efforts have been instead focused on finding use for quantum computers through variational algorithms [9] and simulations of small physical sys- tems [10, 11]. However, there have not been definitive demonstrations of quantum advantage save for contrived mathematical problems [12, 13] Coherence times and error rates have significantly improved over the last decade; however, improvements in the hardware are unlikely to provide the error rates required to run quantum algorithms with deep circuits and large gate-counts. To achieve these long circuits and low error rates, it is likely that quantum error correction [14] (QEC) will be required. At a high level, QEC 1 allow us to redundantly encode quantum information in a subspace of the full 2n-dimensional Hilbert space and occasionally check to see if errors have caused the information to leave this logical subspace. By performing operations on the degrees of freedom of this highly entangled system, we can achieve universal quantum computation on a noisy quantum computer [15, 16]. The threshold theorem [17–19] guarantees that such a procedure can work for arbitrarily long quantum computations as long as the noise rate of the system is below some threshold. Encoding quantum information in this way incurs additional space overhead: namely, quan- tum error correcting codes (QECCs) encode k logical qubits into n physical qubits, where n > k. To minimize the total number of qubits required, we would like that the number of logical qubits scales like the number of physical qubits, k = O(n), or the rate k/n is constant as n → ∞. Previously, this was not possible without sacrificing the error correction capabilities of the code, its distance d. However, recent good quantum low-density parity-check (qLDPC) code construc- tions were found which have parameters scaling like k = d = O(n) [20–23]. In addition to the qubits required to simply construct the code, ancilla qubits are needed to make the logical quantum computation fault tolerant. Although polylogarithmic overhead is needed in the gen- eral case, it was later shown that the use of these asymptotically good LDPC codes could reduce the required space overhead a constant [24]. Furthermore, there is a time overhead associated with performing encoded quantum computation, with the quantum error correction itself taking significant time, in addition to performing the logical gates on the QECC. Minimizing the time overhead, too, has been focus of recent research [25–28]. Practically, many of these threshold and code construction works have somewhat optimistic constraints on the capabilities of the quantum computer; reality is much more restrictive. There are a number of potential candidates for large-scale quantum computers, including 2 superconducting transmon qubits [29], ion-traps [30–32], neutral-atoms [33], photonics [34], bosonic qubits [35, 36], and semiconductor spin qubits [37], among others, each with their own strengths and weaknesses. As such, for each architecture there are certain QECCs that are well- suited and others that are inefficient or even incompatible. Notable examples include the surface code [38, 39], which is ideal for the nearest neighbor connectivity of superconducting qubits, or GKP codes [40], which require the infinite-dimensional Hilbert space of bosonic qubits. On many of these platforms, there have been various experimental realizations of logical quantum memory and logical computation [41–46], including some that exhibit below threshold performance [47– 52]. These demonstrations are necessary and encouraging steps towards large-scale FT quantum computing, but we are still most likely several years, or even several decades, away. Further research focused on reducing the required overheads could significantly accelerate this timeline. In this thesis, we address this topic of research and present techniques which aim to prac- tically reduce the space and time overheads of implementing quantum error correction. The overarching motivation for the works presented in this thesis is the belief that it is advantageous, perhaps even essential, to measure every stabilizer generator when performing quantum error cor- rection. To address this claim, we introduce partial quantum error correction, which we broadly define to be using incomplete syndrome information from the code or neglecting to correct errors on some part of the system. We will show that is not necessary to measure every stabilizer gener- ator in order to obtain a threshold, and we will describe several situations where we obtain better logical performance and/or reduced overheads by not doing so. 3 1.1 Relation to previous work We briefly discuss the relation to techniques which are either named similarly or share a similar implementation to partial quantum error correction as described in this thesis. Note that there are many recent works that aim to reduce the time and space overheads in quantum error correction. Indeed, this is essentially the underlying motivation behind much of all current quantum error correction research. 1.1.1 Partial error correction Partial (quantum) error correction has been coined before. In particular, Refs. [53, 54] introduced a framework that employs error-corrected “clean” qubits in conjunction with non- error-corrected “dirty” qubits, motivated by the qubit limitations imposed by near-term quantum computers. During quantum computation, clean logical qubits are interacted with dirty qubits in an attempt to increase the computational space of the (small) QECC. They present evidence to suggest that this model offers some benefits over fully noisy circuits. The difference compared to our version of partial quantum error correction is we assume quantum computation is conducted solely on the clean logical qubits. In other words, all physical qubits used for computation (that is, apart from those used to measure, as flags, perform routing, etc.) are part of some error correcting code. It is just that by occasionally neglecting to measure some generators, some qubits become temporarily dirty. However, the scheduling of the generator measurements ensure that no error is ignored for too long, and that all qubits are eventually cleaned of any residual errors. This is in contrast to the partial error correction of Refs. [53, 54], in which the dirty qubits are never cleaned despite the fact that they are used for computation. 4 1.1.2 Floquet codes Floquet codes [55] and dynamical codes [56, 57], as their names suggest, are QECCs gen- erated from a sequence of low-weight measurement operators. For both Floquet codes and partial quantum error correction, the measurement schedule may repeat over some number of rounds, but we do not require the round-to-round measurements to be identical. Indeed, this is precisely what enables Floquet codes to function as a quantum memory. The main difference between the two methods is the location of logical information: for Floquet codes, the logical qubits arise as a consequence of the particular sequence of measure- ments; whereas for partial quantum error correction, we focus on stabilizer codes with a static logical subspace. Note that in syndrome extraction rounds where a submaximal set of stabilizer generators is measured, the physical qubits are stabilized by fewer generators, and as such are technically in a different code than they were originally encoded. This new code will likely have a smaller distance, see Section 3.3, and seeing as it has fewer generators, it encodes more log- ical qubits. However, these additional logical qubits are not used, and the encoded information remains in the original logical subspace. 1.1.3 Single-shot QEC Slightly less related is the concept of single-shot QEC. Usually, to be fault-tolerant to both qubit and syndrome errors, the stabilizer generators have to measured O(d) times, and the entire syndrome history must be used in decoding [58]. For quantum error correcting codes with the single-shot [59, 60] property a single round of syndrome extraction suffices. In this way, single- shot codes inherently tolerate syndrome errors. Nonetheless, the syndrome measurements are 5 required to at least be attempted, especially for codes where the single-shot property is facilitated by soundness [60]. Codes that are single-shot can immediately be applied in a partial quantum error correction scheme in which stabilizer measurements are skipped, with some performance guarantees, see Section 3.3. 1.1.4 Approximate quantum error correction Similar sounding, but not very related is the concept of approximate quantum error correc- tion [61]. For approximate error correcting codes, we are not required to return exactly to the computational subspace after correction, but instead we are allowed to return to a state that is ϵ-close to a codeword. In this thesis, partial quantum error correction is still exact in the sense that whenever we do corrections, we want them to return us to the codespace. 1.2 Outline This dissertation is structured as follows: Chapter 2 presents the necessary background material needed for the following chapters. In particular, we provide introductions to classical and quantum error correction including the codes and decoders used in this work. In Chapter 3, we introduce partial syndrome measurement and masking as a general tech- nique for quantum error correction. We then motivate an application of partial syndrome mea- surement inspired by the so-called stacked model, in which generators acting on spatially distant qubits are measured less frequently than those which do not. Through analytical and numerical means, we investigate the performance of a simplified version of this scheme where the measured 6 generators are randomly selected. This chapter is based on the following publication: • Noah Berthusen and Daniel Gottesman. Partial syndrome measurement for hypergraph product codes. Quantum, 8:1345, May 2024. In Chapter 4, we study the stacked model application of Chapter 3 in a more realistic set- ting; namely, we present a full error correction protocol that is built on a bilayer architecture and uses bivariate bicycle codes. In doing so, we discuss code embeddings, a parallel syndrome mea- surement scheme using fast routing with local operations and classical communication (LOCC), and entanglement purification. This chapter is based on the following publication: • Noah Berthusen, Dhruv Devulapalli, Eddie Schoute, Andrew M. Childs, Michael J. Gul- lans, Alexey V. Gorshkov, and Daniel Gottesman. Toward a 2D local implementation of quantum LDPC codes. PRX Quantum 6:010306, Jan 2025. In Chapter 5, we present another application of partial quantum error correction in the form of adaptive syndrome extraction. We show that for certain codes, namely a concatenated code consisting of a error detecting code and a high-rate low-density parity-check code, syndrome ex- traction could be optimized by utilizing the correlations in the syndromes between concatenation layers. Using this idea, we present a framework that can ‘short-circuit’ syndrome extraction and skip measuring generators that are unlikely to be useful for decoding. Specifically, we look at [[4, 2, 2]]-concatenated hypergraph product codes and investigate the potential benefits of using these codes and the adaptive syndrome extraction in quantum memory and logical computation. This chapter is based on the following preprint: • Noah Berthusen, Shi Jie Samuel Tan, Eric Huang, and Daniel Gottesman. Adaptive Syn- drome Extraction. arXiv preprint arXiv:2502.14835, Feb 2025. 7 http://dx.doi.org/10.22331/q-2024-05-14-1345 https://doi.org/10.1103/PRXQuantum.6.010306 https://doi.org/10.48550/arXiv.2502.14835 Finally, we conclude in Chapter 6 with a discussion and present some potential future applications of partial quantum error correction. Other work completed during the completion of this degree but not reported in this disser- tation include: • Noah Berthusen, Michael J. Gullans, Yifan Hong, Maryam Mudassar, and Shi Jie Samuel Tan. Automorphism gadgets in homological product codes. To appear, 2025. • Noah Berthusen, Joan Dreiling, Cameron Foltz, John P. Gaebler, Thomas M. Gatter- man, Dan Gresh, Nathan Hewitt, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, and David Hayes. Experiments with the four-dimensional surface code on a quantum charge-coupled device quantum computer. Phys. Rev. A, 110:062413, Dec 2024. • Noah Berthusen, Faisal Alam, and Yu Zhang. Multi-reference Quantum Davidson Algo- rithm for Quantum Dynamics. arXiv preprint arXiv:2406.08675, Jun 2024. 8 https://link.aps.org/doi/10.1103/PhysRevA.110.062413 https://doi.org/10.48550/arXiv.2406.08675 Chapter 2: Preliminary material In this chapter we present an introduction to the material that will be used throughout the thesis. In particular, we provide introductions to classical and quantum error correction, including the codes, error models, and general decodering scenarios used in this work. 2.1 Classical error correction An [n, k, d] binary linear code C encodes k classical bits in a k-dimensional subspace of the n bit, n-dimensional space, Fn 2 . Codewords are the binary vectors v ∈ Fn 2 that satisfy the equation H · v = 0, where H is a binary matrix of size m × n called the parity check matrix (pcm) and arithmetic is done over F2. The number of logical bits k can be computed from H like k = n− rk(H), where rk(H) denotes the rank of H . As an example, the matrix shown below in Eq. (2.1) is the pcm for the [7, 4, 3] Hamming code. H =  1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1  (2.1) The distance d of a binary linear code is the minimum weight of a non-zero codeword. The weight, or Hamming weight, of a vector v ∈ Fn 2 is simply the number of ones in v and is denoted 9 Figure 2.1: Tanner graph for the [7, 4, 3] Hamming code. by |v|. An [n, k, d] error correcting code is able to correct all errors of weight up to ⌊(d− 1)/2⌋, and it is able to detect all errors of weight up to d − 1. Note that there may be higher weight errors that are detectable and correctable, but it is not guaranteed in general. The parity check matrix can be represented as a bipartite graph G = (V ⊔ C,E) called a Tanner graph. For a [n, k, d] binary linear code, there are two sets of nodes in the graph: the bit nodes V , with |V | = n, and the check nodes C, with |C| = m. A bit node v ∈ V and a check node c ∈ C are connected by an edge if v is involved in the check c. In other words, the ith bit is connected to the jth check if Hj,i = 1. In this sense, the Tanner graph can be considered the graph whose biadjacency matrix is H . Fig. 2.1 shows the Tanner graph for the [7, 4, 3] Hamming code. From a Tanner graph G of some binary linear code C, we can obtain the transpose code CT by swapping the bit and check nodes of G. That is, the Tanner graph remains the same, but the bit nodes are now considered check nodes and the check nodes are now considered bit nodes. Equivalently, the pcm of CT is HT . The resulting code has parameters [m, kT , dT ]. Note that if H is full rank then CT consists of only the zero codeword, and so kT = 0 and dT = ∞. To determine whether a received message w experienced an error during transmission we compute its syndrome, σ(w) = H ·w. Since all codewords of v ∈ C are elements of the kernel of H , a non-zero outcome for σ(w) indicates that an error has occurred. Fig. 2.2 shows two example errors on the [7, 4, 3] Hamming code and the corresponding syndromes: the error depicted in 10 Figure 2.2: Example errors and syndromes for the [7, 4, 3] Hamming code. In panel (b), a weight- three error causes a zero syndrome, indicating that the distance of the code is at most three. panel (a) has a non-zero syndrome, and since |w| ≤ ⌊(d − 1)/2⌋ = 1 we are able to uniquely identify the error. In panel (b), a weight-three error causes an all-zero syndrome, indicating that the distance of the code is at most three. For this specific code, there is no lower-weight error that causes an all-zero syndrome, and so the distance is three. Determining the smallest satisfying error, or equivalently the closest codeword to the received vector, is difficult in general [62]. This process, called decoding, is instead usually done using heuristic algorithms called decoders. We further discuss the decoding problem in Section 2.3.5. Once the decoder outputs a correction, it can be applied to the received message to (hopefully) obtain the originally sent message. A classical code is considered a low-density parity-check (LDPC) code [63] if the weights of the rows and columns of its parity check matrix are bounded by a constant. We say that a code is (∆V ,∆C)-LDPC if the weight of every column and row of H is bounded by ∆V ,∆C ∈ O(1), respectively. We can equivalently say that the Tanner graph has bit node degree bounded by ∆V and check node degree bounded by ∆C . Due to the sparsity of their Tanner graphs, LDPC codes are amenable to efficient decoding by message-passing algorithms like belief propagation [64], allowing them to approach the Shannon limit [65]. Their performance and simplicity have caused them to find widespread use in communications including Wi-Fi, Ethernet, 5G, and more. 11 2.2 Quantum information The fundamental unit of classical computation is the bit, which can be in the 0 and 1 states. The fundamental unit of computation of quantum computation, the qubit, can also be in discrete states called basis states: |0⟩ = 1 0  |1⟩ = 0 1  . (2.2) However, the qubit can also be in a superposition of |0⟩ and |1⟩, |ψ⟩ = α |0⟩+ β |1⟩ = α 1 0 + β 0 1  = α β  , (2.3) where α, β ∈ C, and we have the condition |α|2 + |β|2 = 1. From this it can be seen that a single qubit is just a normalized vector in C2. Similarly, a system of n qubits can be represented as a statevector |ψ⟩ ∈ (C2)⊗n = C2n which we call a pure state. Alternatively, we can represent the qubit state with its density matrix ρ = |ψ⟩ ⟨ψ|. The density matrix representation allows us to also consider mixed states, which are a statistical mixture of pure states, ρ = ∑ i pi |ψi⟩ ⟨ψi| , (2.4) where {pi} is a valid probability distribution. Just as classical computation can be expressed using logic gates such as OR and NOT, quantum computation is accomplished by applying unitary operator U , i.e. operators satisfying UU † = U †U = I , where I is the identity matrix. When a unitary gate U is applied to an initial 12 state |ψ⟩, we obtain a transformed state |ϕ⟩ = U |ψ⟩, which can simply be obtained by matrix multiplication. We can also express this transformation on the density matrix, σ = |ϕ⟩ ⟨ϕ| = U |ψ⟩ ⟨ψ|U † = UρU †. (2.5) Of course, computing the action on a n qubit system will, in general, require keeping track of the statevector |ψ⟩ ∈ C2n and performing matrix multiplication with an operator U ∈ C2n×2n . For even a modest number of qubits this method is classically intractable, hence the potential for quantum advantage. One important set of unitary operators are the Pauli operators: X = 0 1 1 0  Y = 0 −i i 0  Z = 1 0 0 −1  (2.6) which when tensored over n qubits and phases are included form the Pauli group: Pn = {I,X, Y, Z}⊗n × {±1,±i}. (2.7) In quantum error correction, it often suffices to only consider errors coming from the Pauli group. This simplification is valid due to a discretization of errors [66] that occurs during quantum measurements. Indeed, arbitrary-angle rotation errors get converted into Pauli errors which can then be corrected with appropriate application of Pauli corrections. 13 2.2.1 Error models During a quantum computation, the system of qubits is interacting with the external envi- ronment and may experience unintended noise and decoherence. The most general way to model noise is with a completely positive trace preserving (CPTP) map. We can represent a CPTP map with a set of Kraus operators E(ρ) = ∑ i EiρE † i , (2.8) where ∑ iEiE † i = I . Perhaps the simplest noise models are the bit- and phase-flip (dephasing) channels: Bp(ρ) = (1− p)ρ+ pXρX† Pp(ρ) = (1− p)ρ+ pZρZ† (2.9) Additional error models include amplitude damping, qubit loss, or the depolarizing channel, which is shown below: Dp(ρ) = (1− p)ρ+ p 3 XρX† + p 3 Y ρY † + p 3 ZρZ†. (2.10) Throughout this thesis, when we say an error has occurred the qubits, we mean that one of these CPTP maps (mainly the bit-flip and depolarizing channels) has been applied to the system. 2.3 Quantum error correction An [[n, k, d]] quantum error correcting code (QECC) Q encodes k logical qubits into a 2k- dimensional subspace of the n qubit, 2n-dimensional Hilbert space, (C2)⊗n = C2n . A commonly used class of QECCs are stabilizer codes [67, 68]. A stabilizer code is defined by its stabilizer S, 14 X Z Z X I I X Z Z X X I X Z Z Z X I X Z Table 2.1: Stabilizer generators for the [[5, 1, 3]] five-qubit code. consisting of elements of the Pauli group Eq. (2.7) whose action is the identity on the codewords |ψ⟩ of Q, e.g., Q = {S |ψ⟩ = |ψ⟩ ,∀S ∈ S}. (2.11) In other words, the quantum codewords |Ψ⟩ ∈ Q form the joint +1-eigenspace for the elements of S. To have a codespace at all, we require that −I /∈ S and that S forms an abelian subgroup of Pn. S is generated by m independent stabilizer generators S = ⟨S1, ..., Sm⟩, and the corresponding stabilizer code encodes n−m = k logical qubits. As an example, consider the [[5, 1, 3]] five-qubit code [69, 70], the smallest stabilizer code that is able to correct an arbitrary single-qubit error. Its four independent stabilizers generators are shown in Table 2.1; as such, it encodes 5− 4 = 1 logical qubit. Denote by N(S) the normalizer of S, the set of Pauli operators that commute with everything in the stabilizer, N(S) = {N ∈ Pn | [N,M ] = 0 ∀M ∈ S}. The distance d of Q is then defined to be the minimum weight of an operator in N(S) \ S . For the five-qubit code, it can be easily checked that the Pauli operator P = X1Z3X5 commutes with all of the stabilizer generators. It is also straightforward to verify that P cannot be written as a product of the stabilizer generators, and so P ∈ N(S) \ S. Hence the distance of the code is at most |P | = 3; in this case, the distance is exactly three. In order to do computation on the encoded qubits, we identify the logical Pauli group N(S)/S, which is isomorphic to the Pauli group on k qubits, Pk. For any stabilizer code, we can find a basis of logical operators X1, Z1, ..., Xk, Zk which generate the Pauli group on the k logical qubits. 15 To determine whether the encoded quantum information has left the logical subspace, the eigenvalues of the stabilizer generators are measured. There are several ways to do this. The circuits depicted in Fig. 2.3 provide one of the most straightforward approaches, which we use throughout the thesis. Eq. (2.11) states that in the absence of errors, all generators will have a +1 eigenvalue; whereas a −1 eigenvalue indicates that an error has caused the encoded information to leave the codespace. Note that obtaining all +1 measurement results does not guarantee an error-free codespace: if E ∈ N(S) \ S, then by definition E commutes with everything in S, yet is an unintended error. These logical errors are especially detrimental since they cause logical actions on one or more of the logical qubits. Let E ∈ Pn be some Pauli error on the n qubits. Since Paulis either commute or anticommute, there are only two options for each of the stabilizer generators of S. If [E, Si] = 0, then SiE |ψ⟩ = ESiE |ψ⟩ = E |ψ⟩ , (2.12) i.e. E |ψ⟩ is a +1-eigenstate of Si. Hence, performing the circuit in Fig. 2.3 would yield a measurement result of 0. The other scenario is if {E, Si} = 0; in this case SiE |ψ⟩ = −ESi |ψ⟩ = −E |ψ⟩ , (2.13) and so E |ψ⟩ is −1-eigenstate of Si. Measuring the corresponding eigenvalue using the circuit in Fig. 2.3 would yield a result of 1. These measurement results constitute a classical syndrome σ(E) ∈ Fm 2 , which is then used as input to a decoding algorithm that outputs a correction, see Section 2.3.5. We note that the syndrome labels the 2m cosets of Pn/N(S). 16 Figure 2.3: Circuits for measuring the eigenvalue of an X-type generator (red) and a Z-type generator (blue). The Z-type measurement presented here is a variation from the standard circuit which uses CZ gates. The binary symplectic representation of a Pauli P ∈ Pn/{±1,±i} = P̂n is a bitstring consisting of two n-bit binary vectors, (x|z) ∈ F2n 2 . The ith component of x is 0 if P acts on qubit i with I or Z and 1 if P acts on qubit i with X or Y . Similarly, the ith component of z is 0 if P acts on qubit i with I or X and 1 if P acts on qubit i with Z or Y . In other words, P̂n ∼= F2n 2 . This transformation allows us to use techniques from classical coding theory on QECCs. In particular, we can represent the stabilizer generators as a m× 2n binary parity check matrix, H . For example, the binary symplectic representation of the stabilizer generators of the five-qubit code, Table 2.1, is then: H =  1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1  (2.14) The symplectic product on two Pauli strings in the symplectic form is defined as (x1|z1) ⊙ (x2|z2) = x1 · z2 + x2 · z1, where multiplication and addition are performed over F2. There is a natural equivalence between the symplectic product and the commutativity of Pauli opera- 17 tors: let P1 = (x1|z1) and P2 = (x2|z2), then [P1, P2] = 0 ⇐⇒ P1 ⊙ P2 = 0. (2.15) And similarly when [P1, P2] = 1. It can be easily verified that the generators of the five-qubit code commute by applying the symplectic product. CSS codes [71, 72] are a subclass of stabilizer codes where the stabilizer generators consist entirely of tensor products of X and I or Z and I . As such, these codes have a parity check matrix with the following symplectic representation: H =  HX 0 0 HZ  . (2.16) Here HX and HZ are mX × n and mZ × n binary matrices, respectively, that satisfy HZ ·HT X = HX · HT Z = 0. Note that it is not necessary for mX = mZ : an example in which mX ̸= mZ is the 3D surface code [73]. CSS codes encode k = n− rk(HX)− rk(HZ) logical qubits. With the pcm in this form, it can be seen that error correction with CSS codes can be broken down into correcting X- and Z- type errors separately, with HX detecting and correcting Z-type errors, and HZ detecting and correcting X-type errors. Hence we obtain separate syndromes when decoding an error E = (x|z), σ(E) = (σZ(x), σX(z)) = (HZ · x,HX · z). (2.17) Decoding CSS codes is greatly simplified compared to general stabilizer codes, since σZ(x) and σX(z) can be treated as the syndromes for classical codes with pcms HZ , HX , respectively. As such, we can apply efficient classical decoders—with some modifications, see Section 2.3.5. We 18 Figure 2.4: Tanner graph for the Steane code. exclusively focus on CSS codes throughout this thesis. We can also represent a CSS code with a Tanner graph. For a [[n, k, d]] CSS code, Q, there are now three sets of nodes in its Tanner graph GQ = (VQ ⊔ CX ⊔ CZ , E): the qubit nodes VQ, with |VQ| = n, the X-type check nodes CX , with |CX | = mX , and the Z-type check nodes CZ , with |CZ | = mZ . Edges are connected between VQ and CX according to HX , and edges are connected between VQ and CZ according to HZ . In other words, the symplectic representation of the pcm of Q is the biadjacency matrix of GQ. As an example, consider the [[7, 1, 3]] Steane code [74], a CSS code which is obtained by setting bothHX andHZ to be the pcm for the [7, 4, 3] Hamming code, Eq. (2.1). Fig. 2.4 shows the Tanner graph for the Steane code. Alternatively, we can represent a quantum code Q using its connectivity graph G ′ Q = (VQ, E). Here each vertex corresponds to a qubit in Q, and two vertices are connected if the two qubits are in the support of the same stabilizer generator. Quantum codes can also be (quantum) LDPC. Specifically, an [[n, k, d]] stabilizer code is (∆V ,∆C)−qLDPC if, for some constants ∆V and ∆C , each qubit is involved in at most ∆V stabilizer generators and each generator measures at most ∆C qubits. We can equivalently say that in the Tanner graph, each qubit node v ∈ V has degree bounded by ∆V and each check node 19 c ∈ CX ⊔ CZ has degree bounded by ∆C . For stabilizer codes, the qLDPC property is important because it means that the syndrome extraction circuits shown in Fig. 2.3 can be done in con- stant time. This ensures that errors cannot build up overwhelmingly during syndrome extraction which, in part, allows qLDPC codes to achieve fault-tolerant quantum computation with constant overhead [24]. Recent years have seen enormous research efforts focused on constructing qLDPC codes with better performance and better parameters [75]. 2.3.1 Hypergraph product codes Hypergraph product (HGP) codes [76] are are CSS-type codes constructed by taking the graph product of two classical linear binary codes C1, C2. Equivalently, they can be considered the homological product [77], or the tensor product, of the chain complex and cochain com- plex corresponding to the two classical codes. Let C1 be a binary linear code with parameters [n1, k1, d1], a pcm H1, and a Tanner graph G1. Let CT 1 be the transposed code of C1 with param- eters [m1, k T 1 , d T 1 ], pcm HT 1 , and Tanner graph GT 1 . Similarly define C2 and CT 2 , with parameters [n2, k2, d2], [m2, k T 2 , d T 2 ], pcms H2, H T 2 , and Tanner graphs G2,GT 2 , respectively. The HGP code obtained by using seed codes C1, C2, HGP (H1, H2), has the following pcms: HZ = ( In1 ⊗H2, H T 1 ⊗ Im2 ) HX = ( H1 ⊗ In2 , Im1 ⊗HT 2 ) , (2.18) and parameters [[n1n2 +m1m2, k1k2 + kT1 k T 2 ,min(d1, d2, d T 1 , d T 2 )]]. (2.19) 20 When H1 and H2 are full-rank, then kT1 = kT2 = 0 and dT1 = dT2 = ∞, and so the parameters of the resulting HGP code, HGP (H1, H2), reduce to [[n1n2 +m1m2, k1k2,min(d1, d2)]]. (2.20) Furthermore, when C := C1 = C2 is a binary linear code with parameters [n, k, d] and a full-rank parity check matrix H , the parameters of the resulting HGP code, HGP (H,H), further reduce to [[n2 +m2, k2, d]]. A HGP code which is formed from two copies of a single classical code H is called a square HGP code. In this thesis, we exclusively investigate square HGP codes where H is full-rank. Note that if the input classical code is (∆V ,∆C)−LDPC with ∆V ≤ ∆C , then the resulting quantum code is (2∆C ,∆V +∆C)−qLDPC. One notable instance of the hypergraph product is the surface code [38, 39] and toric code [18], which is formed from the product of two [n, 1, n] repetition codes. The two dif- ferent constructions are obtained depending on whether the pcm for the repetition code is full rank (yielding the surface code) or not (yielding the toric code). Another notable family of HGP codes are those formed from classical expander codes [78], whose parameters scale like [n,O(n), O(n)]. The resulting quantum codes are deemed quantum expander codes [79] and have parameters scaling like [[n,O(n), O( √ n)]]. Additionally, they are equipped with a linear time decoder [79], single-shot decoding [80], and single-shot state preparation [81]. These codes are the focus of Chapter 3 and Chapter 5. We first give the graphical interpretation of the hypergraph product. Again consider the HGP code Q obtained by using seed codes C1, C2. The Tanner graph GQ of the HGP code is then obtained by performing the graph product of G1 and G2. Intuitively, this means that when the 21 Figure 2.5: Tanner graph of a [[58, 16, 3]] hypergraph product code constructed from two copies of the [7, 4, 3] Hamming code. A Z-type generator (blue) and an X-type generator (red) are highlighted. qubits and checks are laid out as shown in Fig. 2.4, each row is a copy of the nodes and edges from G1, and each column is a copy of the nodes and edges from G2. More formally, let V1, V2 be the bit nodes, and let C1, C2 be the check nodes for G1,G2, respectively. Then the qubits and checks of Q are assigned as follows: the qubits V := V1 × V2 ⊔ C1 × C2, the X-type checks CX := V1 × C2, and the Z-type checks CZ := C1 × V2. This graphical interpretation provides a convenient representation for the stabilizer generators and logical operators, see Section 2.3.1.1. An alternative interpretation to the graphical hypergraph product can be obtained through the homological product [77]. We first give a brief review of chain complexes and F2 homology. 22 A chain complex is a collection of vector spaces over F2 together with linear maps ∂i, ∂n ∂n−1 ∂2 ∂1 C = Cn Cn−1 ... C1 C0, (2.21) where ∂i+1∂i = 0. We refer to elements of Ci as i-chains, elements of Zi(C) = ker ∂i as i-cycles, and elements of Bi(C) = im ∂i+1 as i-boundaries. The i-th homology is then defined as the vector space of i-cycles modulo i-boundaries, Hi(C) = Zi(C)/Bi(C). (2.22) Similarly, we also define elements of Zi(C) = ker ∂Ti+1 as i-cocycles, elements of Bi(C) = im ∂Ti as i-coboundaries, and the i-th cohomology, H i(C) = Zi(C)/Bi(C). An [n, k, d] classical error correcting code can be considered a 2-term chain complex, ∂1 C = C1 C0 , where its boundary map ∂1 = H is a linear map from Fn 2 to the vector space of syndromes, Fm 2 . A CSS code can similarly be represented as a 3-term chain complex, ∂2 ∂1 C = C2 C1 C0, (2.23) where ∂2 = HT Z and ∂1 = HX . The condition that ∂i+1∂i = 0 translates to the requirement that the X and Z checks must commute, e.g. HT ZHX = 0, and so Eq. (2.23) defines a valid CSS code. Given an arbitrary length chain complex, one may define a CSS code by only considering two consecutive boundary operators. When identifying qubits with elements of Ci, the resulting code parameters are n = dimCi, k = dimHi(C) = dimH i(C), and d is the minimum Hamming weight of a non-trivial element in Hi(C) or H i(C). 23 Quantum error correcting codes, i.e. 3-term chain complexes, can be obtained by taking the homological [77], or hypergraph [76] product of two chain complexes. The difference between the two products is subtle and concerns the use of a transpose Tanner graph, D in Eq. (2.28). The construction described here corresponds to the hypergraph product. The first step of the product is to take the double complex of two chain complexes, C ⊠ D, which is equipped with vertical boundary maps ∂vi = ∂Ci ⊗ IDi and horizontal boundary maps ∂hi = ICi ⊗ ∂Di . Here we use the notation ∂Ai to denote the ith boundary operator of the chain complex A. See Fig. 2.6 for an example of a double complex arising from the tensor product of two 2-term chain complexes. From a double complex, we associate the total complex by performing the direct sum over vector spaces and boundary maps of like dimension Tot(C ⊠D)i = ⊕ i=j+k Cj ⊗Dk = Ei (2.24) ∂Ei = ⊕ i=j+k ∂vj ⊕ ∂hk . (2.25) The resulting chain complex, deemed the tensor product of C and D, C ⊗ D, can be used to construct a CSS code by choosing some consecutive three-term sequence. The parameters of the resulting code can be explicitly calculated or the Künneth formula can be applied, Hi(C ⊗D) ∼= ⊕ i=j+k Hj(C)⊗Hk(D). (2.26) While the distance of a code is in general difficult to calculate, it was shown in Ref. [82] that the distances of a tensor product of an arbitrary-length chain complex with a 2-term chain complex 24 In1 ⊗HT 2 H1 ⊗ Im2 H1 ⊗ In2 Im1 ⊗HT 2 C1 ⊗D1 C1 ⊗D0 C0 ⊗D1 C0 ⊗D0 Figure 2.6: A commutative diagram representing the double complex that arises from the tensor product of two 2-term chain complexes. can be calculated exactly, di(C ⊗D) = min ( di(C)d0(D), di−1(C)d1(D) ) . (2.27) Now, we present an explicit construction of a hypergraph product code using the homolog- ical product. We define the following two 2-term chain complexes C,D, representing the two classical codes C = [n1, k1, d1],D = [n2, k2, d2], respectively, which are the basis for the product construction, H1 C = C1 C0 HT 2 D = D1 D0. (2.28) Note that we are using HT 2 as the boundary map for D, so D is really the cochain complex of D. To obtain the hypergraph product of C and D, we take the tensor product of C and D, yielding the double complex shown in Fig. 2.6. Performing a direct sum over vector spaces of equal dimension according to Eq. (2.24) results in the tensor product complex ∂2 ∂1 C1 ⊗D1 C0 ⊗D1 ⊕ C1 ⊗D0 C0 ⊗D0 (2.29) 25 where ∂2 = In1 ⊗HT 2 H1 ⊗ Im2  (2.30) ∂1 = ( H1 ⊗ In2 , Im1 ⊗HT 2 ) . (2.31) It can be easily verified that ∂1∂2 = 0, and so Eq. (2.29) is a valid chain complex. Let us relabel the vector spaces and boundary maps in Eq. (2.29) to ∂E 2 ∂E 1 E = E2 E1 E0. For each vector space Ei, we calculate the dimension dimEi. dimE2 = dim(Fn1 2 ⊗ Fm2 2 ) = n1m2 (2.32) dimE1 = dim(Fm1 2 ⊗ Fm2 2 ) (2.33) + dim(Fn1 2 ⊗ Fn2 2 ) = n1n2 +m1m2 dimE0 = dim(Fm1 2 ⊗ Fn2 2 ) = m1n2 (2.34) To consider E a CSS code, we identify the n1n2 + m1m2 physical qubits with 1-chains. Parity check matrices are then assigned to the boundary operators ∂E2 = HT Z and ∂E1 = HX , matching the pcms defined in Eq. (2.18). We can determine the number of logical qubits by calculating the dimension of the first homology group, dimH1(E) with the Künneth formula, Eq. (2.26). Here, H1(C) ∼= Zk1 , and H0(C) ∼= ZkT1 . Similarly, H1(D) ∼= ZkT2 and H0(D) ∼= Zk2 . 26 Plugging into Eq. (2.26) as expected yields, dimH1(E) = dimH1(C ⊗D) (2.35) = dim ( H1(C)⊗H0(D)⊕H0(C)⊗H1(D) ) = k1k2 + kT1 k T 2 . We can use Eq. (2.27) to calculate the distances of the resulting chain complex. The dis- tance d0 of the homology group H0(C) is d0 = 1, unless ∂1 has full column-rank in which case d0 = ∞. For i > 0, we say di = ∞ if Hi(C) is trivial. Otherwise, di is the minimum weight of a non-zero vector x ∈ ker ∂i, i.e., the distance of binary linear code defined by ∂i. Hence we obtain, d1(E) = min ( d1(C) d0(D), d0(C) d1(D) ) (2.36) = min ( d1 · 1, 1 · dT2 ) (2.37) Technically, this is only dZ , and d = min(dZ , dX). dX can be obtained by also taking the minimum Hamming weight of non-zero elements in the cohomology classes,H i(C) and applying Eq. (2.36). With this, we obtain the same distance as noted in Eq. (2.19). 2.3.1.1 Canonical logical basis The physical qubits of HGP(H,H) can be arranged into two square grids of size n × n and m×m, see Fig. 2.4 and Fig. 2.7. In this representation, the stabilizer generators and logical operators have a convenient geometric structure. For each physical qubit in the code, we assign a triplet (i, j, L) or (k, ℓ, R) where 1 ≤ i, j ≤ n and 1,≤ k, ℓ ≤ m. Here, i (k) denotes the 27 Figure 2.7: Partitioning the qubits of a [[52, 4, 4]] HGP code formed from two copies of a [6, 2, 4] classical code. (a) Z-type generator SZ(1, 3) (blue) andX-type generator SX(4, 4) (red) obtained by taking rows and columns of the (transpose) parity check matrix of the classical code. (b) Canonical logical operators Z2 and X2. The qubit highlighted both blue and red is the pivot qubit for that logical pair. (c) Diagonal qubits (black) and twin qubits (yellow). row coordinate, j (ℓ) denotes the column coordinate, and L (R) specifies whether the qubit is in the left n × n sector or the right m ×m sector. We denote the physical qubits on the principal diagonal of each sector, i.e. (r, r, •), as diagonal qubits. Additionally, for an (r, c, •) qubit, we identify the (c, r, •) qubit as its mirror qubit, with the two together considered twin qubits, see Fig. 2.7(c). With this layout of the physical qubits, the stabilizer generators of the code have the prop- erty that their support is contained in a single row of one sector and a single column of the other. Specifically, X-type stabilizers have support on the kth row of the R sector and the jth column of the L sector. As such, each can be labeled by SX(k, j). Similarly, a Z-type generator labeled by SZ(i, ℓ) has support on the ith row of the L sector and the ℓth column of the R sector. The stabilizer generators as expressed in this representation can by constructed by indexing specific rows and columns of the underlying classical parity check matrix H [83], see Fig. 2.7(a), or by reshaping the HGP pcms shown in Eq. (2.18). Given the HX and HZ matrices, the X-type stabi- lizer generators expressed in the representation defined above can be obtained by taking the first n2 columns ofHX and reshaping them into a n×n×M matrix, whereM is the number ofX-type 28 Figure 2.8: (a) The X-type parity check matrix for a [[20, 4, 2]] hypergraph product code. (b) Considering the first row of the pcm, we take the first n2 = 16 columns and reshape them into a 4 × 4 matrix. We similarly take the remaining m2 = 4 columns and reshape them into a 2 × 2 matrix. The two matrices together constitue the first stabilizer generator in canonical form. generators. Also take the remaining m2 = (n−k)2 columns and reshape them into a m×m×M matrix. In this representation, the full ith stabilizer is then given by ((•, •, i), (•, •, i)). The Z- type generators can be obtained by instead using HZ . An example of this reshaping in shown in Fig. 2.8, where we consider HX from a [[20, 4, 2]] hypergraph product code where the underlying classical pcm comes from F2×4 2 . To obtain the stabilizer generators in canonical form, we take the first n2 = 16 qubits and reshape them into a 4×4 matrix, and similarly for the remaining m2 = 4 qubits. The two matrices together constitute the first stabilizer generator in canonical form. In this layout, we can also obtain a canonical basis for hypergraph product code logical operators [84]. For these codes, a canonical basis is defined to be a set of logical operators such that they have support contained in a single row or column of a single sector. Additionally, X i and Zi share support on exactly one qubit, whereas X i and Zj for i ̸= j do not share any support. The physical qubit on which X i and Zi overlap is deemed the pivot qubit for that logical qubit. Similarly to the physical qubits, the logical qubits are either diagonal logical qubits or part of a 29 twin logical qubit pair depending on the location of its pivot qubit. We refer to Ref. [84] where they provide a method for constructing a canonical basis for square hypergraph product codes. 2.3.2 Bivariate bicycle codes In Chapter 4, we investigate bivariate bicycle qLDPC codes [85], which come from the wider family of generalized bicycle codes [86]. Let Iℓ be the ℓ × ℓ identity matrix and let Sℓ be the ℓ× ℓ cyclic permutation matrix, which is obtained by shifting the columns of Iℓ one position to the right. Also let x = Sℓ ⊗ Im and y = Iℓ ⊗ Sm (2.38) for integers ℓ,m. We then define two matrices A = A1 + A2 + A3 and B = B1 +B2 +B3 (2.39) where Ai, Bi are powers of x or y. Here we perform all arithmetic over Z2. Using A and B, we can construct the CSS-type BB code BB(A,B) with X- and Z-parity checks that, respectively, take the form HX = [A|B] and HZ = [BT |AT ]. (2.40) To define a valid stabilizer code, we require that all X-type checks commute with all Z-type checks, which translates to the condition HX · HT Z = AB + BA = 0. Since [x, y] = 0, this condition is satisfied. As with other stabilizer codes, k = n− rk(HX)− rk(HZ), and the distance is the minimum weight logical operator. 30 2.3.3 Iceberg codes Iceberg codes [67, 72, 87], also known as quantum parity codes, are a family of CSS codes with parameters [[n, n− 2, 2]]. The two weight-n stabilizer generators, SZ = ⊗ i∈[n] Zi and SX = ⊗ i∈[n] Xi, (2.41) allow the code to detect a single bit-flip and phase-flip error. Technically, any error of odd parity is detectable, but the code is unable to differentiate between the error weights. Its n− 2 weight-2 logical operators can be defined as X i = X1Xi+1 and Zi = Zi+1Zn, (2.42) and it is easily verified that the commutation relations between logical operators are satisfied. The logical all-zero state |00...0⟩ for an Iceberg code is simply the n-qubit Greenberg-Horne-Zeilinger (GHZ) state: |00...0⟩ = |00...0⟩+ |11...1⟩√ 2 , (2.43) and so to initialize the codespace we only need to prepare this state. Ref. [88] presents explicit circuits on how to do this fault-tolerantly. The same reference also explains how to do logical computation with these codes. In Appendix B.1 we present a set of logical operators that generate the Clifford group on both logical qubits. 31 2.3.4 Concatenated codes Quantum code concatenation [67] is a procedure that takes two stabilizer codes and pro- duces a larger stabilizer code. In a concatenated code, the physical qubits are first encoded in some [[n1, k1, d1]] stabilizer code encoding k1 logical qubits. These k1 logical qubits then serve as the physical qubits for an [[n2, k2, d2]] stabilizer code. This process can be repeated arbitrarily many times, with each encoding step generally increasing the error correction properties of the code. One concatenation scheme is shown below. Note that the scheme requires k1 | n2. Procedure 1. (Concatenation of quantum codes, see e.g., Section 3.5 of Ref. [67]). Consider stabilizer codes Q1 and Q2 with parameters [[n1, k1, d1]], [[n2, k2, d2]] and stabilizers S1, S2, respectively. Then a concatenated code Q with parameters [[n1n2/k1, k2, d ≥ d1d2/k1]] can be constructed as follows: Divide the n2 qubits into n2/k1 blocks of k1 qubits, B(b), b ∈ {1, ..., n2/k1}. Each block of k1 qubits is then encoded into n1 qubits using Q1. 1. For each generator M ∈ S1 include in S the Pauli Mi acting on the ith block of n1 qubits tensored with the identity on all other blocks. 2. Also include in S every generator M ∈ S2, where each single-qubit Pauli Pi is replaced with the corresponding logical Pauli operator according to the mapping of B(b). As an example, let us concatenate the [[4, 2, 2]] Iceberg code with itself according to Pro- cedure 1. The resulting code will have parameters [[8, 2, d ≥ 2]]. The generators and logical operators for the [[4, 2, 2]] code are shown below: 32 SX = X1X2X3X4 SZ = Z1Z2Z3Z4 (2.44) X1 = X1X2 Z1 = Z2Z4 (2.45) X2 = X1X3 Z2 = Z3Z4 (2.46) Intuitively, we are constructing a [[4, 2, 2]] code where the physical qubits are each a logical qubit encoded in another [[4, 2, 2]] code. Thus we need two code blocks to give us the required number of logical qubits. For simplicity let us denote the logical qubits of the first code block as logical qubits 1, 2, and the logical qubits of the second code block as logical qubits 3, 4. Additionally, we let logical qubits with odd indices to correspond to the specific logical represen- tation shown in Eq. (2.45), while logical qubits with even indices correspond to Eq. (2.46). This assignment can be arbitrary, but certain assignments may provide increased distance and error correcting performance, see Section 5.2.1. Following step 1 of Procedure 1, we add the stabilizer generators for these two code blocks to the stabilizer of the concatenated code. Following step 2, we must then replace the [[4, 2, 2]] stabilizers of Eq. (2.44) with the corresponding logical op- erators according to this assignment. Thus, for example, we substitute X1 with X1 on the first block: X1X2 and we substitute X4 with X2 on the second block: X4X7. SX = X1X2X3X4 hence becomes X2X3X5X6. We do the same mapping with the two sets of logical operators, Eq. (2.45), (2.46) to obtain logical operators for the two logical qubits of the resulting concate- nated code. We see that the commutation relations between X i and Zi are satisfied, so this set of logical operators forms a valid logical basis. There is an alternative concatenation procedure: Procedure 2. Concatenation of quantum codes. Consider stabilizer codes Q1 and Q2 with pa- 33 X X X X I I I I Z Z Z Z I I I I I I I I X X X X I I I I Z Z Z Z I X X I I X X I I Z Z I I Z Z I X1 I X X I I I I I Z1 I Z I Z I Z I Z X2 X X I I X X I I Z2 I I I I I Z Z I Table 2.2: Stabilizer generators and logical operators for a [[8, 2, 2]] code obtained from the concatenation of the [[4, 2, 2]] code with itself according to Procedure 1. rameters [[n1, k1, d1]], [[n2, k2, d2]] and stabilizers S1, S2, respectively. Then a concatenated code Q with parameters [[n1n2, k1k2, d ≥ d1d2]] can be constructed as follows: Divide the n1n2 qubits into n2 blocks of n1 qubits, B(b), b ∈ {1, ..., n2/k1}. Each block of n1 qubits is then encoded into k1 logical qubits using Q1. 1. For each generator M ∈ S1 include in S the Pauli Mi acting on the ith block of n1 qubits tensored with the identity on all other blocks. 2. Using the ith logical qubit from each block B(b) include in S every generator M ∈ S2, where each single-qubit Pauli Pi is replaced with the corresponding logical Pauli operator. 3. Repeat the previous step k1 times, for each logical qubit in B(b). In Chapter 5 we use Procedure 1 to construct a concatenated code; however, we could just as easily used Procedure 2, and it may be interesting to consider reproducing Chapter 5 with this second concatenation procedure. 34 2.3.5 Decoding As alluded to in the previous sections, decoding is process of determining an correction based on the observed syndrome. The syndrome, which is obtained using syndrome extraction circuits like those in Fig. 2.3, is given to an algorithm called a decoder that outputs a likely correction. Consider an error E and correction E ′ with E,E ′ ∈ Pn. It might seem like a sufficient condition for decoding success, i.e. returning the quantum state to the codespace, is that σ(E ⊕ E ′) = 0; however, this is not enough to guarantee success. It may be the case that E ⊕ E ′ ∈ N(S) \ S, in which case the overall effect of the error and the correction is a logical error—yet σ(E ⊕ E ′) = 0. So we instead consider the logicals matrix consisting of the logical representatives, X1, Z1, ..., Xk, Zk, of the code. When expressed in the binary symplectic representation, the logical matrix for CSS codes has a similar structure to its parity check matrix, Eq. 2.16 L =  LX 0 0 LZ  (2.47) Decoding is then considered a success if L · E = L · E ′, otherwise we say that a logical error has occurred. We now briefly describe common noise models for simulating the logical memory performance of a QECC and the corresponding decoding techniques. 2.3.5.1 Code capacity The simplest noise model is when only the data qubits experience noise, often at the be- ginning of an error correction cycle. For example, they may all experience depolarizing noise, Eq. (2.10), with probability p. Or we may consider CSS codes for simplicity, and consider bit-flip 35 noise and phase-flip noise, Eq. (2.9), separately. Unless there is an asymmetry between the X- and Z-type generators for a CSS code, it often suffices to investigate the performance of only one type. Hence it is often customary to consider, for example, only X-type errors and the Z- type syndrome, treating the problem like decoding a classical code. Although belief propagation performs remarkably well for classical LDPC codes, decoding CSS codes in this way yields sub- optimal performance [89–91], due to short cycles in the Tanner graph and error degeneracy. To address the failures of belief propagation, post-processing methods have been introduced [92– 94]. Additionally, entirely new decoders tailored to specific quantum codes have been devel- oped [23, 79, 83, 95, 96] (among many others), in some instances providing better performance than general-use decoders like belief propagation. 2.3.5.2 Phenomenological noise A slightly more realistic noise model is one in which the syndromes themselves can be noisy, namely the phenomenological noise model. When performing syndrome extraction circuits like Fig. 2.3 on noisy quantum computers, there is the possibility of errors propagating to the ancilla qubit or the measurement of the ancilla qubit failing. In general, this results in bit-flip errors being applied to the syndrome with probability psynd. As the syndrome is the main input to the decoder, incorrect syndromes can cause significant increases in the logical error rate. We say main input, as there is also the option of providing soft information to the decoder, usually in the form of error probabilities on each qubit. It has been shown that providing this extra information can improve decoding performance [97–99]. The typical method for dealing with syndrome noise is to repeat the stabilizer measurements Θ(d) times and then decode over the 36 Figure 2.9: The X-type parity check matrix for a [[20, 4, 2]] hypergraph product code with addi- tional columns to account for syndrome noise. entire syndrome history [58]. It was shown in Ref. [59] that for certain single-shot QECCs, only a single round of noisy stabilizer measurements is necessary to display increased error suppression with larger block- lengths. There are two sufficient conditions to be single-shot: some codes, namely those con- structed from 5-term chain complexes such as the 4D surface code [58] and higher-dimensional hypergraph product codes [82, 100], have redundancies in their stabilizer generators that allow them to correct for syndrome errors before decoding according to Section 2.3.5.1. Codes with this property are said to be single-shot by soundness [60]. Other codes are single-shot by confine- ment [101], which very roughly states that the residual qubit and syndrome error remain bounded after decoding. To decode these codes, we follow Ref. [94] to modify the Tanner graph and parity check matrices of the CSS code: for each check node, we add a single bit node which represents the possibility of a syndrome error. Fig. 2.9 displays the pcm for a [[20, 4, 2]] hypergraph product code (shown unaltered in Fig. 2.8) after including columns for potential syndrome errors. This augmented pcm can then be used in a decoding algorithm as described above. Note that when applying the correction to the system, these syndrome errors are ignored. 37 2.3.5.3 Circuit-level noise In reality, errors may occur at any operation in the syndrome extraction circuit, including qubit initialization, single- and two-qubit gates, measurements, and idle locations. To model this, we instead consider the standard circuit-based depolarizing noise model [102], where for each operation in the circuit, an error is introduced with some probability p. For example, an error arising from a CNOT gate is the gate followed by one of the possible 15 non-identity two-qubit Pauli products on the control and target qubits. Although it is possible to decode circuit-level noise using the same method as for phenomological noise [103], it has been shown to be advantageous to instead use a space-time circuit-level decoder [104, 105]. The goal now is to guess the error at specific locations in the syndrome extraction circuit. Again, decoding is considered a success if the guessed errors have the same effect on the logical observables as the actual error. The input to the space-time decoder is not the syndrome of the error, but rather the parities of the syndrome measurements between error correction rounds. In the absence of errors, the syndrome between rounds should be constant, i.e. have parity of zero. A parity of one indicates that an error occurred at some point in the previous error correction round. Following the notation of Stim [106, 107], we define the ith detector at time t to be the parity of the syndrome of the current and previous rounds D(t) i = σ (t) i ⊕ σ (t−1) i , where σ(t) i is the ith bit of the syndrome at time t. We make one change to allow for the possibility of partial quantum error correction, where we have the choice of neglecting to measure certain generators for some number of rounds, tm. As such, detectors for these generators must compare the parities of the corresponding syndromes tm rounds apart, D(t) i = σ (t) i ⊕ σ (t−tm) i . Each detector allows us to determine whether errors have 38 Figure 2.10: (a) Detectors for a portion of the bit-flip repetition code. The highlighted regions represent the detecting region [107] of a detector, the set of errors that would cause the detector to be triggered. The corresponding detectors are then the parities of the measurements in that region. Since syndrome j was masked for a round, the detector now represents the parities of the measurements in the region that spans three rounds. (b) The bipartite space-time decoding graph of the circuit. The check nodes of this graph are the detectors, and the bit nodes are possible errors during the execution of the circuit. A detector and error are connected by an edge if the error causes the detector to be activated. Errors on the boundary of two detecting regions cause both detectors to trigger. occurred in a specific detecting region [107] of the circuit. Figure 2.10(a) shows a simple exam- ple of a classical repetition code circuit with its associated detectors and highlighted detecting regions. To correct for errors in the circuit-level model, we relate the detectors with errors in the circuit by constructing a bipartite graph. Let the detectors over T rounds be the check nodes, and let every possible single- and two-qubit error over the circuit make up the bit nodes. A detector and error are connected by an edge if the error causes the detector to activate. As a practical note, many errors have the same action on the detectors and logical observables, so they 39 can be consolidated into a single node. Since each error in this set has the same action on the final logical observables, one can choose an arbitrary representative when checking for decoding success. Similarly, some errors will have no effect on the detectors or logical observables, and as such are not included as a node in the bipartite graph. This bipartite graph can be considered the Tanner graph of a classical code and can be decoded by any appropriate decoder to deduce the errors that have occurred. Figure 2.10(b) shows the bipartite decoding graph corresponding to the circuit of panel (a). The classes of equivalent errors from each detecting region constitute the bit nodes of the graph and are connected by edges to the appropriate detectors. For a more detailed discussion of the circuit-level noise decoding process, see Ref. [85]. 40 Chapter 3: Masking and partial syndrome measurement In this chapter, we introduce the notion of using a submaximal set of stabilizer generators to do quantum error correction, which we call partial syndrome measurement, and we formal- ize it with masking and (un)masking schedules. This procedure forms the basis for the other instantiations of partial error correction described in the following chapters. Applying this new technique, we motivate a new practical protocol for implementing nonlocal qLDPC codes on quantum hardware restricted to 2D local gates. We first begin by introducing the concept driving the motivation for this and the next chap- ter: locality. Let G be the Tanner graph or connectivity graph of a quantum code, and consider assigning the vertices of the graph to the points in a D-dimensional grid. Such an assignment is called an embedding: Definition 3. (Graph embeddings) For a graph G = (V,E), a map ηθ : V → ZD is called an embedding. An embedding ηθ is a θ-embedding if for all distinct vertices u, v ∈ V , |ηθ(u)− ηθ(v)| ≥ θ. (3.1) When θ = O(1), the corresponding code is said to be local in D dimensions, or DD local. Equivalently, a code is considered local in ZD if, when embedded in a lattice with side length 41 O( D √ n)D, its generators act on qubits within a ball of constant radius. It was shown that there is an intimate relationship between locality and the parameters of a quantum code. In particular, Refs. [108, 109] showed the distance d for a local code in Z2 is bounded above by O( √ n), and the number of logical qubits k obeys the relation kd2 = O(n). In D dimensions, these so-called Bravyi-Poulin-Terhal (BPT) bounds are generalized like d = O(n1−1/D) and kd2/(D−1) = O(n). Several quantum computing modalities are based on two-dimensional architectures with fixed qubit layouts, including superconducting qubits [110], quantum dots [111], and nitrogen- vacancy (NV) center qubits [112]. On these devices, two-qubit entangling gates are only natively available between qubits that are neighboring. We say natively because longer range entangling gates can be compiled into the available gateset; however, this incurs additional overhead that often makes these compiled gates noisier than the native two-qubit gates, see Chapter 4. As such, on these devices it is significantly easier to implement QECCs that are 2D local. Recently, a popular choice for code family with this property has been the surface code and its variations [38, 39]. While it has local, weight-four generators and a favorable Θ( √ n) distance scaling, the surface code has a rate, k/n, which tends to zero as n approaches infinity. These parameters saturate the BPT, and so they are the best we can hope to achieve for a 2D local code. To surpass the BPT bounds, additional nonlocality is required; that is, we need θ = Ω(1) in Definition 3. Precisely how much locality is required was first studied in Refs. [113, 114] and later refined in Ref. [115]. The latter work proved the following, optimal, statement about 2D embeddings of stabilizer codes: Theorem 4 ([115], Theorem 1.2). There exist absolute constants c0, c1 > 0 such that the follow- ing holds. Any 2D-embedding of a [[n, k, d]] stabilizer code with kd2 ≥ c1 · n must have at least 42 c0 ·max(k, d) interactions of length at least c0 ·max ( d√ n , ( kd2 n )1/4). That is to say that exceeding the BPT bound is costly in terms of the amount of nonlocality that arises from any D-dimensional embedding. One such family that provides improved parameters is hypergraph product (HGP) codes [76], specifically quantum expander codes [79]. This con- struction has the same Θ( √ n) distance scaling, but now with a constant rate, k = Θ(n); the trade-off, however, is that the stabilizer generators of HPG codes are very nonlocal, requiring Ω(n) interactions of length Ω(n1/4). This nonlocality poses problems for 2D local implementa- tion of qLDPC codes, such as HGP codes, that surpass the BPT bound. Indeed, several recent works have provided evidence against the possibility of doing error correction on architectures restricted to 2D local gates. Delfosse et al. [103] investigated the problem of performing syndrome extraction circuits of HGP codes using 2D local gates and clas- sical communication and presented numerical simulations suggesting that the resulting overhead was prohibitive. Baspin et al. [116] provide further evidence against 2D local implementations of qLDPC codes by deriving bounds on the amount of overhead needed to perform error correction at a given logical error rate. They show that the restriction to 2D local gates incurs polyno- mial overhead. However, they also note that their definition of error rate is very restrictive and that computations not satisfying this definition might not obey the overhead bound. It therefore remains possible that we could obtain more favorable performance by using alternative error correction schemes, such as partial syndrome extraction and the stacked model, which we now introduce. 43 Figure 3.1: Illustration of stacked model layer interaction radius and frequency. Blue circles represent the support coverage of the stabilizer generators. For codes in the stacked model, the lower layers contain many small generators. The code will also have larger generators; however, as interaction radius increases, the frequency decreases. 3.1 The stacked model As a concrete example of partial syndrome measurement, we show through analytic and numerical evidence that repeated quantum error correction with quantum expander codes still provides a threshold even when a constant fraction of generators are not measured. This re- sult suggests that it may be possible to build a fault-tolerant quantum computer with nonlocal qLDPC codes on architectures restricted to 2D local gates with a procedure based on the stacked model [113]. After embedding a QECC in a grid of size O( √ n)×O( √ n), the stabilizer genera- tors are partitioned into a stack of layers based on the radius of the ball containing the qubits they act on. The bottom layer of the stack contains local generators, and as we move up the stack, the interaction radius increases while the number of generators of that size decreases. Note that the layers in the stack do not correspond to physical layers on hardware. Instead, they are a concep- tual tool for partitioning the generators into sets based on their geometric size. Fig. 3.1 illustrates this: for codes in the stacked model, the relative frequency of the stabilizer generators is related to their interaction radius. Ideally, we can use codes which when embedded into Z2 have the 44 property that the number of generators decreases exponentially with increasing radius. That is, a (large) constant fraction of the generators act on qubits within a support of constant radius. The reason for wanting this is that when restricted to 2D local gates, the set of nonlocal generators takes much longer to route and measure than the local generators, see Chapter 4. The key insight is that measuring the nonlocal generators less frequently than the local ones could significantly shorten the syndrome extraction time, at the cost of potentially reduced error correction capabil- ities. It was shown in Ref. [113] that any code constrained to the above model has a distance that is bounded by Õ(n2/3) and obeys the relation k3d4 = Õ(n5). Here, Õ(·) is a variant of big O no- tation that ignores log factors, e.g. f(n) ∈ Õ(h(n)) is equivalent to ∃k : f(n) ∈ O(h(n) logk n). Quantum expander codes codes satisfy this trade-off. However, since the publication of the paper this chapter was based on [117], another work [115] refined the bounds of Ref. [113] yielding a tighter distance bound d ≤ O(n2/3) and improved rate-distance trade-offs: kd4 ≤ O(n3), k3d4 ≤ O(n3). Quantum expander codes (k = Θ(n), d = Θ(n1/2)) no longer satisfy these bounds, and as such cannot be implemented in the stacked model. This was somewhat expected by us, given as expander graphs are no- toriously hard to embed into any finite dimension [118]. Indeed, we made some effort to find specific embeddings into Z2 that yielded good generator size distributions; however, the resulting distributions instead often favored mid-sized generators. While this rules out quantum expander codes, it still remains the case that codes such as 2D hyperbolic codes [119], 4D hyperbolic codes [120, 121], or fiber bundle codes [122] may be implemented in the stacked model. Al- ternatively, there might be enough practical benefit to use codes that have the same asymptotic parameter scaling as the surface code (k = Θ(1), d = Θ( √ n)), but encode more qubits at small blocklengths, such as semi-topological codes [92], long-range-enhanced surface codes [123], or 45 (a) F re qu en cy (b) (c) EC EC EC Time Figure 3.2: Overview of the stacked model. (a) After embedding a quantum code into Z2, each stabilizer generator has a parameter γ that denotes the radius of the ball containing the qubits in its support. (b) Two possible distributions of γ over the set of generators. The most advantageous distributions for this scheme are those where the relative frequency decays exponentially with increasing γ (red curve). (c) An example schedule for the generator measurements. The syn- drome extraction circuits for the smaller generators are able to be prepared quickly, and so their syndromes are available during every round of error correction (red dashed lines). The larger generators require more time to build their syndrome extraction circuits, so this is done over a period of time that may stretch over several error correction rounds. More practically, priority is given to the smaller generators, and after completing them, the larger generators are worked on using any remaining time before an error correction round. La-cross codes [124]. Measurement of the generators at the bottom of the stack takes constant time, since they are local. As such, these generators can be considered ‘easy’ in some sense, and their syndrome information can be assumed to be available during every round of error correction. As we move up the stack, the interaction radius increases. The important distinction to make is that while the generators on higher layers are nonlocal, we are still measuring them with only 2D local gates, and so extracting these syndromes takes longer than for local generators. To mitigate the extra noise arising from additional idling and the compiled long-range gates, these nonlocal generators are measured less frequently than those lower in the stack, and hence their syndrome is not always available. This scheme is depicted in Fig. 3.2. Doing this, as we will briefly argue, has the potential of reducing the overhead of performing syndrome extraction, given that the intermediate rounds of error correction are actually correcting errors. 46 We can roughly approximate the amount of work required to perform syndrome measure- ment using 2D local gates by estimating the number of SWAP gates in the extraction circuits. For a generator with interaction radius γ, the total number of SWAP gates needed to perform the syndrome measurement is proportional to γ. As a concrete example, consider a qLDPC code on n = 100, 000 qubits which when embedded into Z2 results in a generator distribution where the number of generators decays exponentially with increasing γ. Drawing O(n) generators from this distribution and summing the radii of the smallest 90% is ∼ 3% of the total sum across all generators. Thus, we can estimate that the syndrome of these smallest 90% of generators can be obtained using only ∼ 3% of the SWAP gates required to perform all of the syndrome mea- surements. Obtaining the remaining 10% of the syndromes requires the majority of the work, but these circuits are built up over time (see Fig. 3.2(c)), allowing for a significant portion of the full error correction capabilities to be available during each error correction round. Alternatively, the syndrome measurement circuits of the large generators can just be performed less frequently, which is the method we use in Chapter 4. Although the resulting logical error rates will be strictly larger than when using a full syndrome, the reductions in overhead may outweigh the increases in the logical error rate. The remainder of the chapter is structured as follows. Section 3.2 introduces the idea of masking and contextualizes it with respect to the stacked model. In Section 3.3, we apply previ- ous results about quantum expander codes to provide some analytical bounds on using masking during multi-round error correction. Section 3.4 provides empirical evidence to suggest that the analytical thresholds are better in practice. We conclude in Section 3.5 with a discussion of the remaining problems for an physical implementation of the stacked model. 47 3.2 Syndrome masking The notion of masking was originally introduced as a way of describing fault-tolerant pro- tocols for space-time codes [125]. We use the same idea here, although in a different context. An element of the stabilizer is considered masked if we cannot measure its eigenvalue during an error correction round. We follow the definition from [125] and define two subgroups of the stabilizer, U and T , where U ⊆ T ⊆ S. The always unmasked subgroup, U , are the stabilizers whose eigenvalues can be measured in a constant number of rounds, whereas the temporarily unmasked subgroup, T , are the stabilizers whose eigenvalues can be measured in a number of rounds that can scale with the size of the code, n. In general, it could be the case that T ⊊ S where the set S \T contains stabilizers that cannot be measured on any time scale. In this chapter, we consider the case U ⊂ T = S. The subgroups form valid stabilizer codes, and as such can be described by their parameters. Defining k for these codes has no real meaning since logical information is not being stored in the subspace; however, we can define the corresponding distances, where dU = min |N(U) \ S| dT = min |N(T ) \ S|. (3.2) In other words, dU (dT ) is the weight of the smallest Pauli operator outside of the full group that has zero syndrome when measuring only the stabilizer generators of U (T ). We call dU and dT masked distances, whereas d is the unmasked distance. Note that dU ≤ dT ≤ d. Since not every generator is measured, the resulting syndrome may have less information about the error than would otherwise be available if the full set of stabilizer generators were measured. For any number of masked generators, there is a set of invisible errors that have zero 48 syndrome on the generators of U (or T ) while having a non-zero syndrome in S. In particular, the new normalizer N(U) contains N(S) as well as all cosets of Pn/N(S) labeled with undetectable error syndromes. Furthermore, errors that were previously correctable may no longer be uniquely identifiable with the syndrome of U or T . Note that errors with a zero syndrome for U do not immediately cause logical errors, unlike errors with a zero syndrome for all of S. If an error has a non-zero syndrome for T , it will eventually be detected, once the generators of T \ U are unmasked. The risk is that such errors will accumulate over time and become logical errors before they can be corrected. 3.2.1 Masking and the stacked model Identifying which layers of the stack are available during an error correction round cor- responds to specifying the temporarily unmasked subgroup, Tt, at each time step in the circuit, t = 1, ..., τ . The always unmasked subgroup, U ⊂ Tt, is static over the execution of the circuit and so can be specified at the beginning. This set contains all local generators, as their eigenval- ues can be measured in constant time and so are assumed to always be available. Tt will contain U as well as any additional layers that have completed syndrome extraction between time t − 1 and t. Since, in general, we want to measure all generators throughout the course of the circuit,⋃ t Tt = S; however, it may not be the case that any one time step has all generators available. An equivalent interpretation is to specify S \ Tt, the set of generators whose eigenvalues are not available during time step t. For the remainder of the chapter, we consider ‘applying’ a mask D to be specifying this set, S \ Tt. 49 Algorithm 1 A simplified fault-tolerance scheme for t = 1, ..., τ do Generate an error Ft with probability pphys and apply Ft to the current error: E ′ t := Ft ⊕ Et−1 Generate a syndrome error Dt with probability psynd Decode on the input (Et, Dt) and correct using the decoded error Êt: Et := E ′ t ⊕ Êt end for Generate an error Ft with probability pphys and apply to the current error: Eτ := Fτ ⊕ Eτ−1 Decode on the input (ET ,∅) 3.3 Analytic results In this section, we consider previous results on quantum expander codes in the context of masking in a multi-round error correction procedure. To decode we use the small-set flip (SSF) decoder [79], a detailed description of which is given in Appendix A.1. A quantum circuit is considered fault-tolerant if it prevents errors from propagating through- out the circuit; in this way, it keeps the size of the residual error manageable for the QECC. To convert a circuit into a fault-tolerant version, the qubits are first encoded in some QECC, and then each operation in the original circuit is replaced with a fault-tolerant logical gadget that acts on the logical qubits of the QECC. We need gadgets to initialize qubits, perform measurements, im- plement logical operations from N(S)/S, and do error correction. In general, errors may occur in any of the gadgets, so after each gadget in the circuit a round of fault-tolerant error correction is performed. To investigate how an error propagates throughout a fault-tolerant circuit more easily, we often abstract the above model and instead work with the procedure described in Al- 50 gorithm 1. For the purposes of analysis and simulation, we condense all gadgets, except error correction, into a single event where every qubit has a bit/phase flip error applied with probability pphys. Additionally, error correction is noisy in the sense that each syndrome bit is flipped with probability psynd. We later discuss how to make this scheme more realistic, but for the purposes of determining the effects of performing error correction with partial syndromes this simplified model is sufficient. In this model we consider qubit errors, E, and syndrome errors/masks, D, that follow a local stochastic noise model: Definition 5. (Local stochastic error model). We say that an error (E,D) is local stochastic if there are error parameters (pphys, psynd) such that for any F and L, Pr[F ⊆ E,L ⊆ D] ≤ p |F | physp |L| synd. Much work has been put into the investigation of quantum expander codes and the SSF decoder in this model [80, 126, 127]. Most relevant to us is the fact that they can tolerate random qubit errors and syndrome errors of linear size, as stated in the following theorem. Theorem 6. (modified from Fawzi, Grospellier, Leverrier [80]). There exists a non-zero con- stant p0 > 0 such that the following holds. Suppose that the error (E,D) each satisfy a local stochastic noise model with parameters pphys and psynd where pphys < p0 and psynd < p0. If we run Algorithm 4 on the input (E,D) then there exists a random variable Els ⊆ V with a local stochastic distribution with parameter pls := p Ω(1) synd such that: Pr [ Els and E ⊕ Ê are not equivalent ] ≤ e−Θ( √ n) (3.3) In the analysis for the above theorem, Fawzi et al. consider an error D in the syndrome 51 Algorithm 2 Multi-round decoding with a fixed (random) mask Apply a mask D with probability pmask for t = 1, ..., τ do Generate an error Ft with probability pphys and apply Ft to the current error: E ′ t := Ft ⊕ Et−1 Decode on the input (Et, D) and correct using the decoded error Êt: Et := E ′ t ⊕ Êt end for Generate an error Ft with probability pphys and apply to the current error: Eτ := Fτ ⊕ Eτ−1 Decode on the input (ET ,∅) to be a subset of the stabilizer generators whose measurement results have been flipped. Very briefly, the argument requires that the syndrome error does not form clusters on the syndrome adjacency graph [24] for it to be tolerable. As such, p0 must be below the percolation threshold of the syndrome adjacency graph of Q. This value is a constant that depends only on ∆V and ∆C of the code. We can turn the result of a masked measurement into the above form by randomly assigning measurement outcomes to the generators included in the mask. Thus, in this context, we can say that Theorem 6 holds when a mask—turned syndrome error—D satisfies a local stochastic noise model with parameter pmask < p0. The above analysis is sufficient in the case when we do a single round of masked error correction where the mask is treated like a random syndrome error. However, we will not be using random masks when implementing the stacked model in reality; instead, for a code and an embedding, we will have fixed masks corresponding to different layers. These masks are then applied on error correction rounds when the corresponding syndromes are not available, potentially several in a row. When we use the same mask over consecutive rounds, we have to be 52 more careful about accounting for the correlations between the syndrome errors, new qubit errors, and residual qubit errors. Accurately characterizing these correlations is likely difficult. As a first step toward this reality, we will only consider a random mask that is fixed at the beginning of the computation, see Algorithm 2. Following the notation of Algorithm 2, in each round t we have the syndrome error from the mask D, any error that was not fully corrected in the previous round Et−1, and a new error Ft. When considered individually, all three error sources are local stochastic described by parameters pmask, pres, and pphys, respectively. When looked at together, the new error and the syndrome error are bounded by Pr[F ⊆ E and L ⊆ D] ≤ p |F | physp |L| mask (3.4) and similarly for the residual error and the new error, as per the definition of a locally stochastic error. However, we would expect to see correlations arise between the residual error and the syndrome error over the rounds, and so together they no longer obey a local stochastic noise model. Instead, they are bounded by: Pr[F ⊆ E and L ⊆ D] ≤ min{p|F | res , p |L| mask}. (3.5) When max{pres, pmask} < p0, the threshold fro