Compare Papers
Paper 1
Quantum fault tolerance with constant-space and logarithmic-time overheads
Quynh T. Nguyen, Christopher A. Pattison
- Year
- 2024
- Journal
- arXiv preprint
- DOI
- arXiv:2411.03632
- arXiv
- 2411.03632
In a model of fault-tolerant quantum computation with quick and noiseless polyloglog-time auxiliary classical computation, we construct a fault tolerance protocol with constant-space and $\widetilde{O}(\log N)$-time overhead, where $\widetilde{O}(\cdot)$ hides sub-polylog factors. Our construction utilizes constant-rate quantum locally testable codes (qLTC), new fault-tolerant gadgets on qLTCs and qLDPC codes, and a new analysis framework. In particular, 1) we develop a new simple and self-contained construction of magic state distillation for qubits using qudit quantum Reed-Solomon codes with $(\log \frac{1}{\varepsilon})^γ$ spacetime overhead, where $γ\rightarrow 0$. 2) We prove that the recent family of almost-good qLTCs of Dinur-Lin-Vidick admit parallel single-shot decoders against adversarial errors of weight scaling with the code distance. 3) We develop logical state preparation and logical gate procedures with $\widetilde{O}(1)$-spacetime overhead on qLTCs. 4) To combine these ingredients, we introduce a new framework of fault tolerance analysis called the weight enumerator formalism. The framework permits easy formal composition of fault-tolerant gadgets, so we expect it to be of independent interest. Our work gives the lowest spacetime overhead to date, which, for the first time, matches that of classical fault tolerance up to sub-polylog factors. We conjecture this is optimal up to sub-polylog factors.
Open paperPaper 2
Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound
Soham Ghosh, Evagoras Stylianou, Holger Boche
- Year
- 2024
- Journal
- arXiv preprint
- DOI
- arXiv:2410.04130
- arXiv
- 2410.04130
We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ \frac{k}{n} = \frac{1}{3} $. For higher rates, our EAQECC also meets the Singleton bound, although with increased entanglement requirements. Additionally, we demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs. The complexity of our encoding protocol for $k$-qudits with $q$ levels is $\mathcal{O}(k \log_{\frac{q}{q-1}}(k))$, excluding the complexity of encoding and decoding the classical MDS code. While this complexity remains linear in $k$ for systems of reasonable size, it increases significantly for larger-levelled systems, highlighting the need for further research into complexity reduction.
Open paper