FPGA-Accelerated Sub-Microsecond Union-Find Decoding for Real-Time Surface-Code Quantum Memory
Chloe Tully
Abstract
FPGA-Accelerated Sub-Microsecond Union-Find Decoding for Real-Time Surface-Code Quantum Memory Architecture manuscript. Latency, power, and resource figures are design estimates unless otherwise marked as measured. Related FPGA Union-Find implementations (Helios / Collision Clustering) are cited for comparison. Abstract Fault-tolerant quantum computation requires continuous decoding of stabilizer syndromes within cycle times that, for superconducting processors, are often 200 ns–1 μs. Host-processor decoders are subject to operating-system jitter, DMA overhead, and memory-hierarchy latency, which make deterministic sub-microsecond service difficult. This paper describes a fully pipelined FPGA architecture for a Union-Find decoder aimed at surface-code quantum memory. The pipeline integrates Aurora-based syndrome acquisition, streaming defect extraction, a path-halving Union-Find engine with hazard forwarding, localized peeling, and dual-port Pauli-frame updates. All latency-critical state is on-chip (BRAM, UltraRAM, distributed RAM). At a target clock of 400 MHz the design estimate for end-to-end latency is 170–390 ns below threshold, with a conservative worst-case bound near 500 ns—inside a 1 μs cycle. Memory for a decoding window scales as O(d³) with the space-time graph, not as O(d³) measurements per cycle. Power is estimated at 3–6 W per logical patch at the FPGA, which remains at room temperature. The contribution is a single deterministic pipeline that does not require a host CPU in the inner loop. It is an architecture and resource plan; it does not replace measured implementations such as Helios. Keywords: surface code; quantum error correction; Union-Find decoder; FPGA; real-time decoding; Pauli frame; clock gating. 1. Introduction Surface-code fault tolerance proceeds by repeated stabilizer measurement and classical decoding of the syndrome stream [1], [9], [10]. Superconducting cycle times commonly fall in T_cycle ~ 200 ns–1 μs [13]. Software decoders on CPUs or GPUs introduce scheduling jitter, DMA cost, cache misses, and synchronization [14]–[16]. Minimum-weight perfect matching (MWPM) is accurate but worst-case cubic in the number of defects and heavy for large distance [17], [18]. The Union-Find decoder of Delfosse and Nickerson is almost-linear and close to MWPM in accuracy, which makes it a natural hardware target [3]. FPGA and ASIC decoders have already shown that real-time surface-code decoding is possible. Das et al. gave a Union-Find micro-architecture; Liyanage et al. (Helios) implemented distributed Union-Find on a VCU129 up to d = 21 with mean times of order 10 ns per round under phenomenological noise, and a resource-optimized d = 51 point near 544 ns per round [14], [15]. Collision Clustering, another Union-Find variant, has been mapped to FPGA and ASIC with sub-microsecond times at large patch size [16]. The present manuscript specifies a single-tile, fully streaming pipeline—acquisition through Pauli frame—with explicit memory equations, banked Find ports, path-halving (not recursive compression), clock-enable power control, and a latency budget written against T_cycle = 1 μs. It is intended as a self-contained hardware architecture that can be implemented or compared against those measured designs. 2. System Architecture The decoder is a fixed-depth pipeline. Stages are registered and advance on the same clock. After fill, a new syndrome frame can be accepted every cycle from the control layer; variable work inside Union-Find is bounded by a worst-case iteration budget, not by a host thread. Stages: • Syndrome acquisition and deserialization (Aurora 64B/66B over GTY). • Defect extraction unit (DEU): frame-to-frame XOR and sparse packing. • Pipelined Union-Find engine: growth, union, path-halving find, boundary test. • Localized peeling of cluster spanning forests. • Dual-port Pauli-frame memory toward the quantum controller. No stage waits on a later stage. No latency-critical structure lives in DRAM or on a host. 3. Syndrome Acquisition and Deserialization Stabilizer outcomes arrive serialized on multi-gigabit links. The link layer is Aurora 64B/66B, a low-overhead framing protocol with about 3% encoding cost, AXI4-Stream user ports, and support for GTY/GTYP/GTM on UltraScale+ and Versal [7]. The physical layer uses GTY transceivers with channel bonding. The receiver aligns the 64B/66B stream, descrambles, strips idles and control words, and deserializes a parallel syndrome frame whose width matches the stabilizer schedule. Aurora framing markers hold alignment; a CRC flags link errors. An elastic FIFO absorbs residual clock-domain difference. The deserializer is intended to emit one frame per T_cycle without a deep buffer. 4. Streaming Defect Extraction Unit Decoding uses the syndrome change, not the raw bit [2], [11]: d_k(t) = s_k(t) XOR s_k(t−1). A one in d_k(t) is a space-time defect, an endpoint of an error chain in the decoding graph [11]. The DEU holds the previous frame in a register file, XORs all stabilizers in parallel, priority-encodes a sparse defect list, and pushes it to a FIFO. Below threshold the defect density is low and FIFO occupancy stays bounded [1], [11]. Boundary-adjacent stabilizers are tagged so cluster growth can terminate on the code boundary. 5. Pipelined Union-Find Engine 5.1 Cluster growth The scheduler follows Delfosse–Nickerson [3]. Each defect starts as its own cluster. Clusters grow by taking half-edges, then neighboring edges, in the parity-check (space-time) graph. Meeting clusters merge. Growth stops when every cluster is even or touches a boundary. Growth and merge requests are issued at a fixed issue rate into the disjoint-set pipeline. 5.2 Disjoint-set representation State is a parent array and a rank array. The primitives are Find(v) and Union(u, v). Weighted union keeps height logarithmic; path reduction keeps amortized cost nearly constant [4]. Together they underwrite the almost-linear sequential bound [3], [4]. 5.3 Path-halving find Recursive full compression has unbounded depth and is a poor FPGA citizen. The pipeline uses path halving: parent[v] ← parent[parent[v]]. This is a standard one-pass reduction with the same practical amortized cost [4]. Each iteration is a constant number of memory operations and maps to a fixed pipeline. Find ends when a root is reached or a bound on hops is hit (the bound is part of the worst-case latency contract). 5.4 Hazards and forwarding Overlapping Union and Find on the same node are read-after-write hazards [19]. A small hazard unit stalls a fixed number of cycles or forwards a newly written parent past BRAM read latency. The unit operates on a bounded register set and does not make latency data-dependent beyond that fixed stall. 5.5 Localized peeling After a cluster is valid, peeling walks its spanning forest and emits a correction chain that matches the defects in that cluster [3]. Peeling is local, so it can start on finished clusters while other clusters still grow. Edges from peeling become Pauli-frame writes. 6. Pauli Frame Management Corrections are not forced as extra quantum gates on the device. They accumulate in a classical Pauli frame [5], [6], [22]: P_frame ← P_frame XOR C_X. The frame sits in dual-port distributed RAM: the decoder writes the current frame while the controller reads the previous one. Reads and writes are registered. No extra architectural latency is added past peeling. 7. Memory Architecture Latency-critical state is on-chip: M_UF = M_parent + M_rank + M_parity + M_boundary + M_edge. With N vertices in the decoding graph: M_parent = N ceil(log2 N) bits; M_rank ≈ 4N bits; M_parity = N bits; M_boundary = N bits; M_edge = 2E bits. Structure Resource Parent table Dual-port BRAM, banked Rank table BRAM Edge state UltraRAM / BRAM Boundary flags LUTRAM Defect FIFO BRAM FIFO Pauli frame Distributed RAM Mapping follows the UltraScale+ / Versal memory hierarchy [20], [21]. UltraRAM is used for large edge tables (deterministic latency, high bits per column). Distributed RAM is used for the small, line-rate Pauli cache. Parent accesses are striped: Bank(v) = v mod B, so several Finds can issue together. Arbitration is a fixed-priority encoder on the bank index. Bank selection is combinational from the node id. 8. Scalability A distance-d surface-code cycle measures O(d²) stabilizers, not O(d³). The O(d³) figure belongs to the space-time decoding graph when the window depth w is taken of order d (w rounds × O(d²) checks). That is the N that enters M_UF. Per-cycle I/O remains O(d²). The earlier formula N_s = d²(d−1) as “measurements per cycle” is withdrawn; the table below is space-time volume for w = d, order-of-magnitude only. Distance d Order of space-time vertices (w = d) 5 ~10² 11 ~10³ 21 ~10⁴ 31 ~3×10⁴ 41 ~7×10⁴ Below threshold, active defects N_active ≪ N, so the FIFO and the scheduler visit neighborhoods, not the whole lattice [1], [11]. Multi-tile scaling replicates DEU, Union-Find, Pauli RAM, and a local FIFO per tile, with a light boundary mesh, consistent with modular decoder proposals [14]–[16]. 9. Throughput and Latency Budget Clock target: f_clk = 400 MHz, T_clk = 2.5 ns (4×10⁸ pipeline slots per second). Design estimate below threshold: 170 ns ≤ L_avg ≤ 390 ns. Worst case: L_max = L_fixed + N_c^max T_UF with L_fixed ≈ 45 ns for the front end, giving L_max ≈ 500 ns under a conservative cluster bound. That is less than T_cycle = 1 μs [13]. These numbers are budgets, not place-and-route measurements. Measured Union-Find FPGAs already report mean times from ~10 ns/round (Helios, small d, phenomenological) to hundreds of ns/round at large d [15], [16]; the present pipeline is specified to sit in that same real-time band. 10. Power and Thermal Placement P_total = P_static + P_logic + P_memory + P_