Date of Award

Fall 1-1-2025

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Zhong, Lin

Abstract

Quantum error correction (QEC) is essential for fault-tolerant quantum computing, but its practical deployment is limited by the complexity of decoding. Most-Likely-Error (MLE) decoding offers near-optimal accuracy but is computationally challenging, especially for general quantum Low-Density Parity-Check (qLDPC) codes. This dissertation develops a family of Minimum-Weight Parity Factor (MWPF) decoders that accelerate MLE decoding by exploiting the locality and parallelism inherent in the decoding problem. We first improve locality by designing decoders that operate on the sparse decoding hypergraph rather than the dense syndrome graph. This leads to an almost-linear average runtime and enables a generalization to hypergraphs with certifying proximity bounds, unifying existing decoders such as Union-Find, Minimum-Weight Perfect Matching, and Hypergraph Union-Find. To improve speed and scalability, we introduce both coarse-grained and fine-grained parallelism. A coarse-grained divide-and-fuse strategy enables parallel decoding with global optimality, while a hardware-accelerated fine-grained vertex-level parallelization reduces the latency to sub-microsecond. Together, these contributions bring MLE decoding closer to meeting the demands of practical, large-scale, fault-tolerant quantum computing.

Download

Share

COinS