STOC Conference 2025 Conference Paper
Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads
- Quynh T. Nguyen
- Christopher A. Pattison
Author name cluster
Christopher A. Pattison
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2STOC Conference 2023 Conference Paper
An Efficient Decoder for a Linear Distance Quantum LDPC Code
- Shouzhen Gu
- Christopher A. Pattison
- Eugene Tang
Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.