SOME: Symmetric One-Hot Matching Elector -- A Lightweight Microsecond Decoder for Quantum Error Correction

• URL: http://arxiv.org/abs/2507.23618v1
• Date: Thu, 31 Jul 2025 14:57:39 GMT
• Title: SOME: Symmetric One-Hot Matching Elector -- A Lightweight Microsecond Decoder for Quantum Error Correction
• Authors: Xinyi Guo, Geguang Miao, Shinichi Nishizawa, Hiromitsu Awano, Shinji Kimura, Takashi Sato,
• Abstract summary: We propose a novel decoder that reformulates the QEC decoding task as a Quadratic Unconstrained Binary Optimization problem.<n>It achieves up to a 99.9x reduction in variable count and reduces decoding times from milliseconds to microseconds on a single-threaded commodity CPU.<n>It also maintains performance up to a 10.5% physical error rate, surpassing the highest known threshold of MWPM@.
• Score: 3.6525689137085178
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conventional quantum error correction (QEC) decoders such as Minimum-Weight Perfect Matching (MWPM) and Union-Find (UF) offer high thresholds and fast decoding, respectively, but both suffer from high topological complexity. In contrast, Ising model-based decoders reduce topological complexity but demand considerable decoding time. We propose the Symmetric One-Hot Matching Elector (SOME), a novel decoder that reformulates the QEC decoding task as a Quadratic Unconstrained Binary Optimization (QUBO) problem -- termed the One-Hot QUBO (OHQ). Each variable in the QUBO represents whether a given pair of flipped syndromes is matched, while the error probabilities between the pair are encoded as interaction coefficients (weight). Constraints ensure that each flipped syndrome is matched exactly once. Valid solutions of OHQ correspond to self-inverse permutation matrices, characterized by symmetric one-hot encoding. To solve the OHQ efficiently, SOME reformulates the decoding task as the construction of permutation matrices that minimize the total weight. It initializes each candidate matrix from one of the minimum-weight syndrome pairs, then iteratively appends additional pairs in ascending order of weight, and finally selects the permutation matrix with the lowest total energy. SOME achieves up to a 99.9x reduction in variable count and reduces decoding times from milliseconds to microseconds on a single-threaded commodity CPU. OHQ also maintains performance up to a 10.5% physical error rate, surpassing the highest known threshold of MWPM@.

Related papers

• Minimum-Weight Parity Factor Decoder for Quantum Error Correction [3.523914647883289]
  HyperBlossom is a unified framework that formulates MLE decoding as a Minimum-Weight Parity Factor problem.<n>HyperBlossom unifies all the existing graph-based decoders like (Hypergraph) Union-Find decoders and Minimum-Weight Perfect Matching (MWPM) decoders.<n>HyperBlossom achieves a 4.8x lower logical error rate compared to the MWPM decoder on the distance-11 surface code.
  arXiv  Detail & Related papers  (2025-08-07T01:44:34Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
  We show a more qubit-efficient circuit construction for optimization problems by the example of the Travelingperson Sales Problem (TSP)<n>Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding.<n>Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical iterations increases only slightly.
  arXiv  Detail & Related papers  (2024-12-10T12:12:34Z)
• Reweighted Solutions for Weighted Low Rank Approximation [47.790126028106734]
  Weighted low rank approximation (WLRA) is an important yet challenging primitive with applications ranging from statistical analysis to signal processing. In this work, we introduce a new relaxed solution to WLRA which outputs a matrix that is not necessarily low rank, but can be stored using very few parameters. Our central idea is to use the weight matrix itself to reweight a low rank solution, which gives an extremely simple algorithm with remarkable empirical performance.
  arXiv  Detail & Related papers  (2024-06-04T15:50:35Z)
• The END: An Equivariant Neural Decoder for Quantum Error Correction [73.4384623973809]
  We introduce a data efficient neural decoder that exploits the symmetries of the problem. We propose a novel equivariant architecture that achieves state of the art accuracy compared to previous neural decoders.
  arXiv  Detail & Related papers  (2023-04-14T19:46:39Z)
• Sparse Blossom: correcting a million errors per core second with minimum-weight matching [0.03320194947871346]
  We introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder.<n>Our algorithm, which we call sparse blossom, is a variant of the blossom algorithm which directly solves the decoding problem relevant to quantum error correction.
  arXiv  Detail & Related papers  (2023-03-28T12:42:54Z)
• Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems [9.516147599772243]
  SSQA is designed based on computing and quantum Monte Carlo. It can handle a 100-times larger problem size compared to QA and atimes larger problem size compared to a traditional SA method.
  arXiv  Detail & Related papers  (2023-02-24T05:08:09Z)
• 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)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
  arXiv  Detail & Related papers  (2022-10-23T00:32:04Z)
• Syndrome decoding by quantum approximate optimization [5.625796693054094]
  We use the quantum approximate optimization algorithm (QAOA) to address the syndrome decoding problem. We evaluate the level-4 check-based QAOA decoding of the [7,4,3] Hamming code. We study QAOA decoding of degenerate quantum codes.
  arXiv  Detail & Related papers  (2022-07-13T03:40:25Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)

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.