Source-linked AI summary
Extractors: QLDPC Architectures for Efficient Pauli-Based Computation
Zhiyang He, Alexander Cowtan, Dominic J. Williamson, Theodore J. Yoder
TL;DR
QLDPC memories face a longstanding challenge in performing fault-tolerant logical computation. The paper introduces extractor systems and fixed-connectivity architectures that support fault-tolerant Pauli measurements and universal circuits using high-fidelity |T⟩ states.
Problem
Performing fault-tolerant logical computation on QLDPC memory remains a longstanding challenge in theory and practice.
Method
The paper augments QLDPC memories with extractor systems to form EAC blocks, then connects blocks with bridges for fixed-connectivity computation through logical Pauli measurements.
Results
Any logical Pauli operator can be measured fault-tolerantly in one logical cycle involving O(d) physical syndrome measurement cycles, and multi-block products can be measured with fault distance d.
Takeaways & Limitations
With a user-defined source of high-fidelity |T⟩ states, the architecture supports universal quantum circuits via parallel logical measurements while compiling away single-block Clifford gates.
Takeaways & Limitations
The execution-depth and resource bounds are loose, omit optimized choices of compilation and factories, and more accurate algorithm-specific estimates are left to future work.
Abstract
from arXiv · showhide
In pursuit of large-scale fault-tolerant quantum computation, quantum low-density parity-check (LDPC) codes have been established as promising candidates for low-overhead memory when compared to conventional approaches based on surface codes. Performing fault-tolerant logical computation on QLDPC memory, however, has been a long standing challenge in theory and in practice. In this work, we propose a new primitive, which we call an $\textit{extractor system}$, that can augment any QLDPC memory into a computational block well-suited for Pauli-based computation. In particular, any logical Pauli operator supported on the memory can be fault-tolerantly measured in one logical cycle, consisting of $O(d)$ physical syndrome measurement cycles, without rearranging qubit connectivity. We further propose a fixed-connectivity, LDPC architecture built by connecting many extractor-augmented computational (EAC) blocks with bridge systems. When combined with any user-defined source of high fidelity $|T\rangle$ states, our architecture can implement universal quantum circuits via parallel logical measurements, such that all single-block Clifford gates are compiled away. The size of an extractor on an $n$ qubit code is $\tilde{O}(n)$, where the precise overhead has immense room for practical optimizations.
1 Main Results
The paper introduces extractor systems that turn arbitrary QLDPC memories into fixed-connectivity computational blocks supporting fault-tolerant logical Pauli measurements. Bridges and adapters connect these blocks into a customizable architecture for parallel Pauli-based universal computation.
- Extractor architecture: An extractor augments any [[n, k, d]] QLDPC memory into an EAC block that measures any supported logical Pauli in one logical cycle of O(d) syndrome cycles.The extractor uses code switching between the memory and a measurement code, while retaining fixed, constant-degree connectivity.
- Extractor architecture: The extractor has a theoretical size bound of O(n(log n)^3) physical qubits, while the paper notes substantial room for practical optimization.
- Multi-block architecture: Bridge and adapter systems connect EAC blocks into larger extractors, allowing logical Pauli measurements across multiple blocks and accommodating different underlying QLDPC codes.For two blocks, the connecting ancilla system uses d qubits and d − 1 checks.
- Universal computation: EAC blocks fit Pauli-based computation because arbitrary Clifford-plus-T circuits reduce to Pauli measurements and |T⟩ magic-state preparation.The architecture therefore supports universal computation when supplied with high-fidelity magic states.
- Compilation: The architecture allocates one ancilla logical qubit per EAC block, leaving K = B(k − 1) logical workspace qubits across B blocks.
- Compilation: The compilation procedure moves T rotations and cross-block Clifford operations forward, absorbs in-block Cliffords into final measurements, and executes the remaining Pauli rotations on EAC blocks.Measurements on disjoint blocks can be parallelized, and execution depth depends on reduced circuit depth and magic-state supply.
2 Discussions and Open Questions
The proposed architecture is presented as flexible and broadly applicable, but its practical performance remains dependent on optimized extractors, architectural choices, compilation, decoding, and resource estimates. The paper identifies several concrete directions for closing these gaps.
- Discussion: The architecture is designed to execute universal circuits with user-defined magic-state sources, while compiling away all in-block Clifford gates.
- Open questions: Detailed resource estimates for specific algorithms remain an open priority because they require jointly optimizing the circuit, code, extractors, block map, factories, and compilation.
- Extractor optimization: Extractor constructions are given in Õ(n) qubits for arbitrary codes, but code-specific designs could substantially reduce space, connectivity, and time overheads.Partial extractors may further reduce overhead for codes with constant-depth logical Clifford gates.
- Compilation and time overhead: Compilation and scheduling currently provide loose upper bounds, and the analysis assumes every cross-block CNOT is supported by a bridge-connected pair of EAC blocks.
- Measurement throughput: An EAC block currently measures one logical Pauli per logical cycle, motivating future work on simultaneous measurements of commuting Paulis.
- Fault-tolerance: Logical-cycle cost is taken as O(d) syndrome cycles, although single-shot QLDPC decoding could reduce this to O(1) for suitable code families.
- Relation to prior work: The architecture is a theoretical model with broad generality, whereas the concurrently developed bicycle architecture emphasizes practical blueprinting and extensive optimization.
3 QLDPC Surgery with Auxiliary Graphs
QLDPC surgery uses auxiliary measurement graphs to convert logical Pauli operators into products of stabilizers, enabling fault-tolerant logical measurements while preserving the remaining logical space. The toolkit builds LDPC-compatible graphs with controlled congestion, expansion, and fault distance, but remains primarily a theoretical blueprint with loose bounds.
- Motivation: Arbitrary logical Pauli measurements support selective logical readout, ancilla initialization, and universal Pauli-based computation with suitable magic states.Pauli-based computation uses measurements and reusable ancilla space to avoid collapsing computational qubits.
- Logical measurements: Measurement hypergraphs assign code-support qubits to ports and add vertex and cycle checks so the target operator becomes a stabilizer product.The construction uses a port function from the operator support to graph vertices, with qubits on hyperedges.
- Logical measurements: Connected measurement graphs preserve the k − 1 logical qubits that commute with the measured operator.Each commuting logical operator retains an independent equivalence class in the modified code.
- Fault tolerance: d syndrome-measurement rounds before and after surgery, plus d rounds during merging, give the fault-tolerant protocol space-time fault distance d.The protocol includes initialization, merge, correction, decoding, and correction stages.
- Graph construction: The constructed graph has maximum degree at most 2(∆ + δ + 1), at most O(|L|(log |L|)^3) edges, congestion 2, and cycle length at most 4.Expansion is maintained through thickening and cellulation, and bridges preserve relative expansion for combined graphs.
- Graph construction: O(|L|(log |L|)^3) ancilla qubits suffice for ancillary graph surgery with an LDPC guarantee in the worst case.Thickening and decongestion reduce congestion while preserving the required graph properties.
- Practical considerations: The toolkit is a theoretical blueprint because nearly all stated conditions and proofs are loose upper bounds requiring practical reassessment.Decoder performance beyond distance guarantees remains an open practical consideration.
4 Extractor Systems
Extractor systems augment QLDPC memories with a single ancilla system that supports logical Pauli measurements while preserving LDPC structure. EAC blocks can be bridged into modular, fixed-connectivity architectures, though partial-extractor bridges have a stated limitation.
- A single extractor ancilla system enables measurement of any logical Pauli operator supported on the QLDPC memory.
- Single-block extractor: Extractor desiderata depend on the base code Q rather than on a specific logical operator, enabling one graph to support all logical measurements.
- Single-block extractor: O(n(log n)^3) total data and check qubits preserve LDPC structure while supporting measurement codes for every logical Pauli operator.
- Single-block extractor: O(d) syndrome measurement cycles and fault distance d characterize one logical measurement without SWAP gates or connectivity rearrangement.
- Architectural variants: Uniform architectures propagate local optimizations globally, while partial extractors provide intermediate designs but may have limited measurement capability.
- Multi-block architecture: Bridge systems connect EAC blocks modularly, enabling multi-block Pauli measurements and compatibility with different QLDPC code families.
- Architectural variants: Bridging partial extractors is not guaranteed to produce a larger partial extractor satisfying all desiderata, limiting the supported logical-operator set in the worst case.
5 QLDPC Architecture for Pauli-Based Computation
The architecture combines EAC blocks, bridges, and magic-state sources to support parallel Pauli-based computation with fixed, constant-degree connectivity. Its performance depends on block organization, scheduling, magic-state supply, and the physical cost of logical cycles.
- Universal computation: High-quality magic states combined with EAC blocks enable universal quantum computation through parallel logical measurements.The architecture supports Pauli-based computation while compiling away in-block Clifford gates.
- Architecture parameters: O(1) maximum qubit connectivity supports the fixed, constant-degree architecture.The architecture uses bounded-degree interactions across data and check qubits.
- Architecture parameters: B(λn + α(2d −1)) qubits are required when each EAC block uses λn physical qubits.The λBn term comes from EAC blocks, while αB(2d −1) comes from bridges.
- Architecture parameters: B(k −1) logical qubits form the active workspace when one logical ancilla is reserved per EAC block.The full architecture contains Bk logical qubits, including the allocated ancillas.
- Resource scaling: λ + O(1) is the scaling for asymptotically good codes with d, k = Θ(n).The construction gives λ ≤O((log n)3), while practical optimization may make λ a small constant.
- Parallel computation: A connected block map can implement arbitrary Pauli-based computation, and operators on connected block partitions can be measured in parallel in one logical cycle.The block-map choice affects compilation, while Proposition 45 establishes parallel measurement capacity.
- Time overhead: O(kΛ) bounds the worst-case depth of the serialized circuit, while executing all measurements can require 4k · Λ + k logical cycles.The final k term accounts for final Pauli measurements, and magic-state supply must be included for specific architectures.
- Practical considerations: Magic-state overhead depends on factory throughput, batch size, and cache size, while equation (14) is a loose upper bound that omits choices of C and Π.Increasing k can reduce factory throughput requirements but may increase serialization depth.
A Omitted Proofs
The omitted proofs establish cycle-basis, partition, and bridging properties used to construct bounded-degree extractor architectures. They show that bridges preserve the relevant graph and extractor desiderata while maintaining controlled congestion and path structure.
- Cycle partitioning: The greedy partition outputs groups of non-overlapping cycles with t ≤log2(|V |) · ρ + 1.The ordering bounds how many later cycles each cycle can overlap, enabling the stated partition depth.
- Cycle-basis construction: A cycle basis of the thickened graph combines length-4 inter-level cycles with one lifted representative of each base-graph cycle.Every base cycle can be represented on any level, and the combined set has the full cycle-space rank.
- Thickening lemma: The thickening argument lower-bounds boundary size using the relative Cheeger constant and layerwise port imbalance.The proof compares inter-level and within-level contributions to the boundary.
- Graph bridging: A bridge of d edges connects two graph systems while preserving the graph desiderata for the product operator.The construction first establishes connected helper graphs on the relevant ports, then applies the bridging lemma.
- Graph bridging: Bridging preserves constant degree, sparse path matchings, and constant congestion for the combined graph.The combined path matchings follow from the disjoint supports of the two operators, while congestion remains O(1).
- Extractor bridging: Two extractor systems can be joined by a d-edge bridge while preserving the extractor desiderata for the union code.The result supports recursively connecting extractor systems associated with disjoint code blocks.