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

Lecture notes in computer science

Memory-Efficient Quantum Information Set Decoding Algorithm

Naoto Kimura, Atsushi Takayasu, Tsuyoshi Takagi

Published Jan 1, 2023• 9 citations
Publisher
DOI
10.1007/978-3-031-35486-1_20

Related papers

Improved Quantum Information Set Decoding Algorithm with Low Memory

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

IEICE Technical Report; IEICE Tech. Rep.•May 13, 2020•0 citations

Quantum Information Set Decoding Algorithms

Ghazal Kachigar, Jean–Pierre Tillich

Lecture notes in computer science•Jan 1, 2017•76 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

Improved Quantum Information Set Decoding

Elena Kirshanova

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

Box and match soft decision decoding of linear block codes with iterative information set reduction

M.P.C. Fossorier, A. Valembois

The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.

IEEE Information Theory Workshop (ITW)•Aug 27, 2003•6 citations

Convolutional Polar Codes on Channels with Memory using Tensor Networks

Benjamin Bourassa, Tremblay, Maxime, David Poulin

Arikan's recursive code construction is designed to polarize a collection of memoryless channels into a set of good and a set of bad channels, and it can be efficiently decoded using successive cancellation. It was recently shown that the same construction also polarizes channels with memory, and a generalization of successive cancellation decoder was proposed with a complexity that scales like the third power of the channel's memory size. In another line of work, the polar code construction was extended by replacing the block polarization kernel by a convoluted kernel. Here, we present an efficient decoding algorithm for finite-state memory channels that can be applied to polar codes and convolutional polar codes. This generalization is most effectively described using the tensor network formalism, and the manuscript presents a self-contained description of the required basic concepts. We use numerical simulations to study the performance of these algorithms for practically relevant code sizes and find that the convolutional structure outperforms the standard polar codes on a variety of channels with memory.

arXiv:1805.09378•May 23, 2018•3 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.
The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.
Arikan's recursive code construction is designed to polarize a collection of memoryless channels into a set of good and a set of bad channels, and it can be efficiently decoded using successive cancellation. It was recently shown that the same construction also polarizes channels with memory, and a generalization of successive cancellation decoder was proposed with a complexity that scales like the third power of the channel's memory size. In another line of work, the polar code construction was extended by replacing the block polarization kernel by a convoluted kernel. Here, we present an efficient decoding algorithm for finite-state memory channels that can be applied to polar codes and convolutional polar codes. This generalization is most effectively described using the tensor network formalism, and the manuscript presents a self-contained description of the required basic concepts. We use numerical simulations to study the performance of these algorithms for practically relevant code sizes and find that the convolutional structure outperforms the standard polar codes on a variety of channels with memory.