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
- 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) - DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAO is the first decentralized, accelerated, asynchronous, primal, first-order algorithm to minimize a sum of $L$-smooth and $mu$-strongly convex functions distributed over a given network of size $n$.
We show that our algorithm requires $mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ local and only $mathcalO(nsqrtchisqrtfracLmulog(
arXiv Detail & Related papers (2022-07-26T08:47:54Z) - 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) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z) - 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.