Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder

• URL: http://arxiv.org/abs/2503.13601v2
• Date: Wed, 26 Mar 2025 16:07:10 GMT
• Title: Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
• Authors: Yugo Takada, Hayata Yamasaki,
• Abstract summary: We develop a protocol that achieves doubly polylog time overhead while maintaining the conventional polylog space overhead.<n>Our protocol integrates this decoder with a topological-code protocol that incorporates single-shot decoding for efficient extraction.<n>Results suggest the feasibility of surpassing the conventional polylog-time-overhead barrier, opening a new frontier in low-overhead FTQC.
• Score: 1.6114012813668932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reducing space and time overheads of fault-tolerant quantum computation (FTQC) has been receiving increasing attention as it is crucial for the development of quantum computers and also plays a fundamental role in understanding the feasibility and limitations of realizing quantum advantages. Shorter time overheads are particularly essential for demonstrating quantum computational speedups without compromising runtime advantages. However, surpassing the conventional polylogarithmic (polylog) scaling of time overheads has remained a significant challenge, since it requires addressing all potential bottlenecks, including the nonzero runtime of classical computation for decoding in practical implementations. In this work, we construct a protocol that achieves FTQC with doubly polylog time overhead while maintaining the conventional polylog space overhead. The key to our approach is the development of a highly parallelizable minimum-weight perfect matching (MWPM) decoder, which achieves a polylog parallel runtime in terms of the code size while providing theoretical guarantees on threshold existence and overhead bounds. Our protocol integrates this decoder with a topological-code protocol that incorporates single-shot decoding for efficient syndrome extraction; furthermore, we concatenate this with the concatenated Steane codes to guarantee the existence of the threshold while avoiding a backlog problem, enabling us to achieve doubly polylog time overheads even when accounting for the decoder's runtime. These results suggest the feasibility of surpassing the conventional polylog-time-overhead barrier, opening a new frontier in low-overhead FTQC.

Related papers

• Polylog-time- and constant-space-overhead fault-tolerant quantum computation with quantum low-density parity-check codes [2.048226951354646]
  A major challenge in fault-tolerant quantum computation is to reduce both space overhead and time overhead.<n>We show that a protocol using non-vanishing-rate quantum low-density parity-check codes achieves constant space overhead and polylogarithmic time overhead.
  arXiv  Detail & Related papers  (2024-11-06T06:06:36Z)
• Demonstrating real-time and low-latency quantum error correction with superconducting qubits [52.08698178354922]
  We demonstrate low-latency feedback with a scalable FPGA decoder integrated into a superconducting quantum processor. We observe logical error suppression as the number of decoding rounds is increased. The decoder throughput and latency developed in this work, combined with continued device improvements, unlock the next generation of experiments.
  arXiv  Detail & Related papers  (2024-10-07T17:07:18Z)
• Fast and Parallelizable Logical Computation with Homological Product Codes [3.4338109681532027]
  High-rate quantum low-density-parity-check (qLDPC) codes promise a route to reduce qubit numbers, but performing computation while maintaining low space cost has required serialization of operations and extra time costs. We design fast and parallelizable logical gates for qLDPC codes, demonstrating their utility for key algorithmic subroutines such as the quantum adder.
  arXiv  Detail & Related papers  (2024-07-26T03:49:59Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• Robust sparse IQP sampling in constant depth [3.670008893193884]
  NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation. We propose a scheme to achieve a provable superpolynomial quantum advantage that is robust to noise with minimal error correction requirements.
  arXiv  Detail & Related papers  (2023-07-20T09:41:08Z)
• Single-shot decoding of good quantum LDPC codes [38.12919328528587]
  We prove that quantum Tanner codes facilitate single-shot quantum error correction (QEC) of adversarial noise. We show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round.
  arXiv  Detail & Related papers  (2023-06-21T18:00:01Z)
• Modular decoding: parallelizable real-time decoding for quantum computers [55.41644538483948]
  Real-time quantum computation will require decoding algorithms capable of extracting logical outcomes from a stream of data generated by noisy quantum hardware. We propose modular decoding, an approach capable of addressing this challenge with minimal additional communication and without sacrificing decoding accuracy. We introduce the edge-vertex decomposition, a concrete instance of modular decoding for lattice-surgery style fault-tolerant blocks.
  arXiv  Detail & Related papers  (2023-03-08T19:26:10Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation [2.3020018305241337]
  Protocols for fault-tolerant quantum computation demand excessive space overheads.<n>We introduce an alternative approach to constant-space-overhead fault-tolerant quantum computing.<n>Our protocol is fault tolerant even if a decoder has a non-constant runtime.
  arXiv  Detail & Related papers  (2022-07-18T18:00:00Z)
• On Quantum-Assisted LDPC Decoding Augmented with Classical Post-Processing [1.0498337709016812]
  This paper looks into the Quadratic Unconstrained Binary Optimization (QUBO) and utilized D-Wave 2000Q Quantum Annealer to solve it. We evaluated and compared this implementation against the decoding performance obtained using Simulated Annealing (SA) and belief propagation (BP) decoding with classical computers.
  arXiv  Detail & Related papers  (2022-04-21T08:01:39Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.