Achieving arbitrarily high accuracy in quantum computation hinges on maintaining physical error rates below a constant threshold, a principle central to the viability of the technology. However, building fault-tolerant quantum computers introduces significant resource demands; the number of physical qubits needed scales with the square of the code distance ‘d’, while each round of operations grows linearly with ‘d’. Researchers are now proposing a new scheme for general quantum low-density parity-check (qLDPC) codes that lowers these demands, attaining a time overhead of O(da + o(1)) while maintaining constant qubit overhead. This method achieves a smaller time overhead than existing protocols for a broad range of codes, and for good qLDPC codes, further reduces the overhead to O(d1 + o(1)).
Quantum Error Correction & Fault-Tolerance Thresholds
The viability of scalable quantum computation rests on a delicate balance: maintaining accuracy despite inherent physical errors. According to the fault-tolerance theorem, when the physical error rate is below a constant threshold, arbitrarily high computational accuracy can be achieved by choosing a quantum error correction code with sufficiently large code distance d. However, implementing this error correction introduces resource overheads in terms of both qubit count and computational time. Each logical qubit, the fundamental unit of quantum information, demands multiple physical qubits for encoding and operation, and logical operations require multiple rounds of physical operations. Simultaneously, the time overhead scales as O(d), adding to the complexity. Recent advances focus on minimizing these costs; low-density parity-check (qLDPC) codes, like hypergraph product (HGP) codes, achieve a constant encoding rate.
Breakthroughs have even pushed code distance scaling from d = Θ(n1/2) to d = Θ(n) while preserving the constant encoding rate. Two primary strategies exist for operating on these qLDPC codes: concatenated codes with gate teleportation and code surgery, with the most efficient known method, gauging measurement combined with brute-force branching, achieving constant qubit overhead but a time overhead of O(d2 + o(1)). A new scheme aims to reduce this time overhead further, achieving a smaller time overhead for all constant-rate qLDPC codes whose relative distance exceeds that of HGP codes (i.e., a < 2). For good qLDPC codes, the time overhead is further reduced to O(d1 + o(1)).
The pursuit of practical quantum computers increasingly focuses on mitigating the inherent resource costs of maintaining quantum information, even as physical qubits improve. According to the fault-tolerance theorem, when the physical error rate is below a constant threshold, arbitrarily high computational accuracy can be achieved by choosing a quantum error correction code with sufficiently large code distance d. However, a refined variant of the CC + GT scheme can attain a lower time overhead of O(d1 + o(1)), though its applicability is restricted to (almost) good quantum locally testable codes (qLTCs). Researchers explain that “Our scheme integrates code surgery with gate teleportation by performing the parity-check measurements required in code surgery through gate teleportation,” detailing a new approach aiming for even greater efficiency.
Substantial effort has been devoted to reducing the resource overhead of fault-tolerant quantum computation. A major advance in this direction is the development of low-overhead quantum low-density parity-check (qLDPC) codes, such as hypergraph product (HGP) codes, which achieve a constant encoding rate. This property ensures that the logical qubit number k scales linearly with the physical qubit number n, meaning k = Θ ( n ). Recent breakthroughs have led to the discovery of good qLDPC codes, which further improve the code distance from d = Θ ( n 1 / 2 ) to d = Θ ( n ) while maintaining a constant encoding rate.
While the fault-tolerance theorem assures arbitrarily high accuracy is possible with sufficiently large code distances, the cost remains a significant hurdle. Researchers are actively refining techniques to reduce both qubit overhead, the number of physical qubits needed per logical qubit, and time overhead, the number of physical operations required for each logical operation. Two primary approaches dominate this field: concatenated codes combined with gate teleportation (CC+GT) and code surgery. This work details a new scheme that integrates code surgery with gate teleportation, performing parity-check measurements via teleportation. This achieves a smaller time overhead for all constant-rate qLDPC codes whose relative distance exceeds that of HGP codes (i.e., a < 2), and for good qLDPC codes, the time overhead is further reduced to O(d1 + o(1)).
While advancements in quantum low-density parity-check (qLDPC) codes promise more efficient encoding, achieving a logical qubit number that scales linearly with physical qubits, translating this potential into practical computation demands careful consideration of fault-tolerance protocols. When computation is performed using the surface code via lattice surgery, the qubit overhead scales as O(d2); however, a lower resource overhead is achieved than the Gauging Measurement combined with Brute-Force Branching (GM+BFB) protocol. Their primary difference lies in the time overhead. Researchers state, “Compared with GM + BFB, our method achieves a smaller time overhead for all constant-rate qLDPC codes whose relative distance exceeds that of HGP codes (i.e., a < 2),” highlighting a performance gain for certain code families. As general overhead-reduction techniques, PCS and LTSP not only improve the asymptotic scaling of FTQC but also offer practical means to lower overhead in near-term, finite-size implementations.
New Scheme for qLDPC Codes: Time & Qubit Overhead
A constant qubit overhead in fault-tolerant quantum computation is now within reach with a newly proposed scheme for quantum low-density parity-check (qLDPC) codes. A method integrating code surgery with gate teleportation offers a potential reduction in the time required for complex calculations. This advancement addresses a critical challenge: minimizing resource demands while maintaining accuracy in quantum systems. The approach centers on performing parity-check measurements, essential for code surgery, through gate teleportation, a technique that leverages pre-prepared quantum states to transfer information. To further optimize efficiency, two key techniques were introduced, parallelized code surgery (PCS) and locally testable state preparation (LTSP). PCS reduces qubit overhead to a constant by allowing multiple code blocks to share ancilla systems, while LTSP prepares resource states for gate teleportation with constant qubit and time overhead.
As general overhead-reduction techniques, PCS and LTSP not only improve the asymptotic scaling of FTQC but also offer practical means to lower overhead in near-term, finite-size implementations. For qLDPC codes with a constant encoding rate and code distance d = Ω (n1/a), the new scheme attains a time overhead of O(da + o(1)).
Current approaches to building fault-tolerant quantum computers grapple with significant resource demands. Existing methods, when computation is performed using the surface code via lattice surgery, see qubit overhead scale as O(d2), a considerable challenge. The time overhead, currently scaling as O(d), further complicates matters. A new scheme offers a potential path forward by integrating code surgery with gate teleportation. This approach performs parity-check measurements, essential for error correction, through gate teleportation itself. The resulting time overhead for qLDPC codes with a code distance d = Ω(n1/a) is O(da + o(1)), a reduction compared to existing methods like GM + BFB for all constant-rate qLDPC codes whose relative distance exceeds that of HGP codes (i.e., a < 2).
Researchers are refining techniques to lessen the substantial resource demands of fault-tolerant quantum computation, focusing on minimizing errors during the complex process of state preparation. While the fault-tolerance theorem assures arbitrarily high computational accuracy is possible with sufficiently large code distance d when the physical error rate is below a constant threshold, practical implementation necessitates reducing qubit and time overheads. A key innovation lies in the development of locally testable state preparation (LTSP), a technique designed to control measurement errors inherent in parity-check measurements.
PCS minimizes qubit overhead by enabling multiple code blocks to share a common ancilla system, while LTSP, utilizing classical locally testable codes, streamlines parity-check measurements. As general overhead-reduction techniques, PCS and LTSP not only improve the asymptotic scaling of FTQC but also offer practical means to lower overhead in near-term, finite-size implementations.
