arXiv:2609.26973
Near-optimal high-rate surgery from linear PCPPs
Alexander Cowtan, Benjamin Ide
Abstract
A central problem for surgery with quantum Low-Density Parity Check (LDPC) codes is the design of auxiliary systems which measure large sets of logical operators in parallel, while preserving sparsity and fault distance. We introduce a very general method for designing surgery gadgets which are 'high rate', meaning that the number of operators measured in parallel is large in comparison to the size of the auxiliary system. Given an arbitrary initial $[[ n, k, d ]]$ quantum LDPC Calderbank-Shor-Steane (CSS) code, and an arbitrary subcode of size $μ\leq n$ that contains $t \leq k$ logical qubits, the method produces a sparse high-rate surgery gadget with size $μ(\logμ)^{O(\log\log μ)}=μ^{1+o(1)}$ which measures all $t$ logicals in the subcode. The space overhead is asymptotically optimal up to subpolynomial factors, as the lower bound is $Ω(μ)$. This gadget is produced in time polynomial in $μ$. When logical measurement is performed using these surgery gadgets, the phenomenological fault distance is at least $d$ when performed for $d$ rounds. Our main result comes from relating surgery gadgets with relative cosystolic expansion to linear Probabilistically Checkable Proofs of Proximity (PCPPs), which allow a randomised verifier to probabilistically verify the input to a linear circuit, using only oracle access to the input and a claimed proof.
AI Summary
The paper asks how much ancillary space is needed to measure many logical operators simultaneously in a quantum LDPC CSS code while retaining sparse checks and fault distance. It considers measuring all logicals supported in a prescribed subcode, rather than arbitrary independently specified Pauli products. For any $[[n,k,d]]$ LDPC CSS code and subcode on $\mu\leq n$ qubits containing $t\leq k$ logical qubits, it constructs a surgery gadget of size $\mu(\log\mu)^{O(\log\log\mu)}=\mu^{1+o(1)}$ in polynomial time. Measurements over $d$ syndrome rounds have phenomenological fault distance at least $d$. The space bound approaches the stated $\Omega(\mu)$ lower bound for sparsely attaching to the prescribed subcode. For good codes with $t=\Omega(k)$, ancillary space decreases from the cited quadratic bounds to $n^{1+o(1)}$, and spacetime volume to $n^{2+o(1)}$. The construction turns linear probabilistically checkable proofs of proximity into auxiliary complexes with relative cosystolic expansion. It translates subcode checks into circuits over an extension field, converts PCPP tests into binary constraints, and reduces degrees using expander graphs. Mapping-cone surgery and a spacetime-detector argument establish the measurement and fault-distance guarantees. An appendix sketches a refinement giving $\mu(\log\mu)^{O(1)}$ space. Constants and practical blocklength performance are undetermined. Detectors can be dense and span all $d$ rounds, complicating real-time decoding; no efficient decoding guarantee is supplied. The intermediate deformed code need not retain distance $d$. Fully addressable Pauli-product measurements and constant-round surgery are not established.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 30 pages, comments welcome