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