From Subset-Sum to Decoding: Improved Classical and Quantum Algorithms via Ternary Representation Technique

The subset-sum problem, a foundational NP-hard problem in theoretical computer science, serves as a critical building block for cryptographic constructions. This work introduces novel classical and quantum heuristic algorithms for the random subset-sum problem at density d=1, where exactly one solution is expected. Classically, we propose the first algorithm based on a ternary tree representation structure, inspired by recent advances in lattice-based cryptanalysis. Through numerical optimization, our method achieves a time complexity of 𝒪˜20.2400n and space complexity of 𝒪˜20.2221n, improving upon the previous best classical heuristic result of 𝒪˜20.2830n. In the quantum setting, we develop a corresponding algorithm by integrating the classical ternary representation technique with a quantum walk search framework. The optimized quantum algorithm attains a time and space complexity of 𝒪˜20.1843n, surpassing the prior state-of-the-art quantum heuristic of 𝒪˜20.2182n. Furthermore, we apply our algorithms to information set decoding in code-based cryptography. For half-distance decoding, our classical algorithm improves the time complexity to 𝒪˜20.0453n, surpassing the previous best of 𝒪˜20.0465n. For full-distance decoding, we achieve a quantum complexity of 𝒪˜20.058326n, advancing beyond the prior best quantum result of 𝒪˜20.058696n. These findings demonstrate the broad applicability and efficiency of our ternary representation technique across both classical and quantum computational models.