Actis: A Strictly Local Union-Find Decoder

• URL: http://arxiv.org/abs/2305.18534v4
• Date: Wed, 8 Nov 2023 18:08:15 GMT
• Title: Actis: A Strictly Local Union-Find Decoder
• Authors: Tim Chan, Simon C. Benjamin
• Abstract summary: The Union-Find decoder is one of the best candidates for fault-tolerant quantum computing. We show for the first time that this strict (rather than partial) locality is practical. A novel parity-calculation scheme is employed which can simplify previously proposed architectures.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fault-tolerant quantum computing requires classical hardware to perform the decoding necessary for error correction. The Union-Find decoder is one of the best candidates for this. It has remarkably organic characteristics, involving the growth and merger of data structures through nearest-neighbour steps; this naturally suggests the possibility of its realisation using a lattice of simple processors with nearest-neighbour links. In this way the computational load can be distributed with near-ideal parallelism. Here we show for the first time that this strict (rather than partial) locality is practical, with a worst-case runtime $\mathcal O(d^3)$ and mean runtime subquadratic in the surface code distance $d$. A novel parity-calculation scheme is employed which can simplify previously proposed architectures, and our approach is optimised for circuit-level noise. We compare our local realisation with one augmented by long-range links; while the latter is of course faster, we note that local asynchronous logic could negate the difference.

Related papers

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• 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)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  In practical distributed systems, workers typically not homogeneous, and can have highly varying processing times. We introduce a new parallel method Freya to handle arbitrarily slow computations. We show that Freya offers significantly improved complexity guarantees compared to all previous methods.
  arXiv  Detail & Related papers  (2024-05-24T13:33:30Z)
• Fault-tolerant quantum computing with the parity code and noise-biased qubits [0.0]
  We present a fault-tolerant universal quantum computing architecture based on a code concatenation of noise-biased qubits and the parity architecture. The parity architecture can be understood as a LDPC code tailored specifically to obtain any desired logical connectivity from nearest neighbor physical interactions.
  arXiv  Detail & Related papers  (2024-04-17T12:49:31Z)
• The closed-branch decoder for quantum LDPC codes [0.0]
  Real-time decoding is a necessity for implementing arbitrary quantum computations on the logical level. We present a new decoder for Quantum Low Density Parity Check (QLDPC) codes, named the closed-branch decoder.
  arXiv  Detail & Related papers  (2024-02-02T16:22:32Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  Communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. We propose Common Om REOm, which can be used to compress information transmitted between machines.
  arXiv  Detail & Related papers  (2023-09-23T08:45:27Z)
• Scalable Quantum Error Correction for Surface Codes using FPGA [67.74017895815125]
  A fault-tolerant quantum computer must decode and correct errors faster than they appear. We report a distributed version of the Union-Find decoder that exploits parallel computing resources for further speedup. The implementation employs a scalable architecture called Helios that organizes parallel computing resources into a hybrid tree-grid structure.
  arXiv  Detail & Related papers  (2023-01-20T04:23:00Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
  Exact algorithms for computing Optimal Transport can be slow. We introduce a new and very simple approach to find an $varepsilon$approximation of the OT distance. Our algorithm achieves a near-optimal execution time of $O(n2/varepsilon2)$ for computing OT distance.
  arXiv  Detail & Related papers  (2022-03-07T21:40:14Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)
• Optimal local unitary encoding circuits for the surface code [0.2770822269241973]
  The surface code is a leading candidate quantum error correcting code, owing to its high threshold. We present an optimal local unitary encoding circuit for the planar surface code. We also show how our encoding circuit for the planar code can be used to prepare fermionic states in the compact mapping.
  arXiv  Detail & Related papers  (2020-02-02T11:09:46Z)

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.