Improved quantum algorithm for the random subset sum problem

2019/12/18 by Yang Li, Li, Yang, Hongbo Li +1
Computer Science · #Quantum Computing Algorithms and Architecture #Cryptography and Data Security #Quantum Information and Cryptography

paper · pdf · doi:10.48550/arxiv.1912.09264

Abstract

Solving random subset sum instances plays an important role in constructing cryptographic systems. For the random subset sum problem, in 2013 Bernstein et al. proposed a quantum algorithm with heuristic time complexity \widetildeO(2^0.241n), where the "\widetildeO" symbol is used to omit poly(log n) factors. In 2018, Helm and May proposed another quantum algorithm that reduces the heuristic time and memory complexity to \widetildeO(2^0.226n). In this paper, a new quantum algorithm is proposed, with heuristic time and memory complexity \widetildeO(2^0.209n).

Related

• Improved Classical and Quantum Algorithms for Subset-Sum
• Towards An Implementation of the Subset-sum Problem on the IBM Quantum Experience
• A Quantum Approach to Subset-Sum and Similar Problems
• Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis
• Quantum Information Set Decoding Algorithms