Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Technical Report; IEICE Tech. Rep.

Improved Quantum Information Set Decoding Algorithm with Low Memory

直人 木村, 敦 高安, 剛 高木

Published May 13, 2020• 0 citations
OpenAlex

Related papers

Memory-Efficient Quantum Information Set Decoding Algorithm

Naoto Kimura, Atsushi Takayasu, Tsuyoshi Takagi

Lecture notes in computer science•Jan 1, 2023•9 citations

An Improved Quantum Both-May ISD Algorithm

Yu Li, Yue Cao, Sen Hou +1 more

Syndrome decoding (SD) is recognized as an NP-hard problem, and its best solver is known as the information set decoding (ISD) algorithm. Recently, Kimura et al. proposed a partially quantized version of the classical Both-May ISD algorithm, and stated that the best quantum time complexity is derived as O(20.059809n) when the memory complexity is constrained to O(20.0014901n), where n is a given positive integer parameter. In this paper, we quantize the depth-2 Both-May algorithm using a quantum nearest neighbor (NN) algorithm, and derive its asymptotic time complexity as O(20.05679n) with memory O(20.033011n), which is lower than the result obtained by Kimura et al., and also lower than O(20.058660n), the time complexity of the state-of-the-art quantum BJMM algorithm under unbounded memory.

International Conference on Electronic Engineering and Informatics (EEI)•Jun 1, 2026•0 citations

Advantage of Quantum Neural Networks as Quantum Information Decoders

Weishun Zhong, Oles Shtanko, Ramis Movassagh

A promising strategy to protect quantum information from noise-induced errors is to encode it into the low-energy states of a topological quantum memory device. However, readout errors from such memory under realistic settings is less understood. We study the problem of decoding quantum information encoded in the groundspaces of topological stabilizer Hamiltonians in the presence of generic perturbations, such as quenched disorder. We first prove that the standard stabilizer-based error correction and decoding schemes work adequately well in such perturbed quantum codes by showing that the decoding error diminishes exponentially in the distance of the underlying unperturbed code. We then prove that Quantum Neural Network (QNN) decoders provide an almost quadratic improvement on the readout error. Thus, we demonstrate provable advantage of using QNNs for decoding realistic quantum error-correcting codes, and our result enables the exploration of a wider range of non-stabilizer codes in the near-term laboratory settings.

arXiv:2401.06300•Jan 11, 2024•3 citations

Quantum Information Set Decoding Algorithms

Ghazal Kachigar, Jean–Pierre Tillich

Lecture notes in computer science•Jan 1, 2017•76 citations

Improved Quantum Information Set Decoding

Elena Kirshanova

arXiv:1808.00714•Lecture notes in computer science•Jan 1, 2018•33 citations

Syndrome-Generalized Belief Propagation Decoding for Quantum Memories

Nithin Raveendran, Mohsen Bahrami, Bane V. Vasic

Quantum low-density parity check (QLDPC) codes are promising in realization of scalable, fault tolerant quantum memory for computation. Many of the QLDPC codes constructions suffer from unavoidable short cycles in their Tanner graph which degrade the decoding performance of the belief propagation (BP) algorithm. In this paper, we propose a syndrome based generalized belief propagation (GBP) algorithm for decoding of quantum LDPC codes and analyze how the proposed algorithm escapes from short cycle trapping sets effectively compared to the BP algorithm. Simulation results show improved decoding performance of the GBP algorithm over BP for the dual containing Calderbank, Shor and Steane (CSS) codes when cycles of length 4 are considered in the region based approach.

International Conference on Communications•May 1, 2019•10 citations
Syndrome decoding (SD) is recognized as an NP-hard problem, and its best solver is known as the information set decoding (ISD) algorithm. Recently, Kimura et al. proposed a partially quantized version of the classical Both-May ISD algorithm, and stated that the best quantum time complexity is derived as O(20.059809n) when the memory complexity is constrained to O(20.0014901n), where n is a given positive integer parameter. In this paper, we quantize the depth-2 Both-May algorithm using a quantum nearest neighbor (NN) algorithm, and derive its asymptotic time complexity as O(20.05679n) with memory O(20.033011n), which is lower than the result obtained by Kimura et al., and also lower than O(20.058660n), the time complexity of the state-of-the-art quantum BJMM algorithm under unbounded memory.
A promising strategy to protect quantum information from noise-induced errors is to encode it into the low-energy states of a topological quantum memory device. However, readout errors from such memory under realistic settings is less understood. We study the problem of decoding quantum information encoded in the groundspaces of topological stabilizer Hamiltonians in the presence of generic perturbations, such as quenched disorder. We first prove that the standard stabilizer-based error correction and decoding schemes work adequately well in such perturbed quantum codes by showing that the decoding error diminishes exponentially in the distance of the underlying unperturbed code. We then prove that Quantum Neural Network (QNN) decoders provide an almost quadratic improvement on the readout error. Thus, we demonstrate provable advantage of using QNNs for decoding realistic quantum error-correcting codes, and our result enables the exploration of a wider range of non-stabilizer codes in the near-term laboratory settings.
Quantum low-density parity check (QLDPC) codes are promising in realization of scalable, fault tolerant quantum memory for computation. Many of the QLDPC codes constructions suffer from unavoidable short cycles in their Tanner graph which degrade the decoding performance of the belief propagation (BP) algorithm. In this paper, we propose a syndrome based generalized belief propagation (GBP) algorithm for decoding of quantum LDPC codes and analyze how the proposed algorithm escapes from short cycle trapping sets effectively compared to the BP algorithm. Simulation results show improved decoding performance of the GBP algorithm over BP for the dual containing Calderbank, Shor and Steane (CSS) codes when cycles of length 4 are considered in the region based approach.