Polylog-time- and constant-space-overhead fault-tolerant quantum computation with quantum low-density parity-check codes

Abstract

A major challenge in fault-tolerant quantum computation (FTQC) is to reduce both space overhead -- the large number of physical qubits per logical qubit -- and time overhead -- the long physical gate sequences per logical gate. We prove that a protocol using non-vanishing-rate quantum low-density parity-check (LDPC) codes, combined with concatenated Steane codes, achieves constant space overhead and polylogarithmic time overhead, even when accounting for non-zero classical computation time. This protocol offers an improvement over existing constant-space-overhead protocols, which have polynomial time overhead using quantum LDPC codes and quasi-polylogarithmic time overhead using concatenated quantum Hamming codes. To ensure the completeness of this proof, we develop a technique called partial circuit reduction, which enables error analysis for the entire fault-tolerant circuit by examining smaller parts composed of a few gadgets. With this technique, we resolve a previously unaddressed logical gap in the existing arguments and complete the proof of the threshold theorem for the constant-space-overhead protocol with quantum LDPC codes. Our work highlights that the quantum-LDPC-code approach can realize FTQC with a negligibly small slowdown and a bounded overhead of physical qubits, similar to the code-concatenation approach, underscoring the importance of a comprehensive comparison of the future realizability of these two approaches.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.