Quantum Algorithms for the Subset-Sum Problem

被引：0
作者：
Bernstein, Daniel J. [1 ,2 ]
Jeffery, Stacey [3 ]
Lange, Tanja [2 ]
Meurer, Alexander [4 ]
机构：
[1] Univ Illinois, Dept Comp Sci, Chicago, IL 60607 USA
[2] Tech Univ Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
[3] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada
[4] Ruhr Univ Bochum, Horst Gortz Inst IT Secur, Bochum, Germany
来源：
POST-QUANTUM CRYPTOGRAPHY, PQCRYPTO 2013 | 2013年 / 7932卷
关键词：
subset sum; quantum search; quantum walks; radix trees; decoding; SVP; CVP; DISCRETE LOGARITHMS;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25. The new algorithm combines the 2010 Howgrave-Graham-Joux subset-sum algorithm with a new stream-lined data structure for quantum walks on Johnson graphs.
引用
收藏
页码：16 / 33
页数：18
相关论文
共 50 条
  • [21] Learning-augmented algorithms for online subset sum
    Chenyang Xu
    Guochuan Zhang
    Journal of Global Optimization, 2023, 87 : 989 - 1008
  • [22] Faster algorithms for k-subset sum and variations
    Antonopoulos, Antonis
    Pagourtzis, Aris
    Petsalakis, Stavros
    Vasilakis, Manolis
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2023, 45 (01)
  • [23] QUANTUM ALGORITHMS FOR SHIFTED SUBSET PROBLEMS
    Montanro, Ashley
    QUANTUM INFORMATION & COMPUTATION, 2009, 9 (5-6) : 500 - 512
  • [24] Effectiveness of penalty function in solving the subset sum problem
    Wang, H
    Ma, ZQ
    Nakayama, K
    1996 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '96), PROCEEDINGS OF, 1996, : 422 - 425
  • [25] A POLYNOMIAL-APPROXIMATION SCHEME FOR THE SUBSET SUM PROBLEM
    SOMA, NY
    ZINOBER, ASI
    YANASSE, HH
    HARLEY, PJ
    DISCRETE APPLIED MATHEMATICS, 1995, 57 (2-3) : 243 - 253
  • [26] A competitive local search heuristic for the subset sum problem
    Ghosh, D
    Chakravarti, N
    COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (03) : 271 - 279
  • [27] Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis
    Biesner, David
    Gerlach, Thore
    Sifa, Rafet
    Bauckhage, Christian
    Kliem, Bernd
    2022 21ST IEEE INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND APPLICATIONS, ICMLA, 2022, : 903 - 908
  • [28] FASTER SPACE-EFFICIENT ALGORITHMS FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS
    Bansal, Nikhil
    Garg, Shashwat
    Nederlof, Jesper
    Vyas, Nikhil
    SIAM JOURNAL ON COMPUTING, 2018, 47 (05) : 1755 - 1777
  • [29] The k-subset sum problem over finite fields
    Wang, Weiqiong
    Nguyen, Jennifer
    FINITE FIELDS AND THEIR APPLICATIONS, 2018, 51 : 204 - 217
  • [30] Approximating Subset Sum Ratio via Subset Sum Computations
    Alonistiotis, Giannis
    Antonopoulos, Antonis
    Melissinos, Nikolaos
    Pagourtzis, Aris
    Petsalakis, Stavros
    Vasilakis, Manolis
    COMBINATORIAL ALGORITHMS (IWOCA 2022), 2022, 13270 : 73 - 85
12345