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 条
  • [41] On the Variants of Subset Sum: Projected and Unbounded
    Dutta, Pranjal
    Rajasree, Mahesh Sreekumar
    [J]. 2023 25TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING, SYNASC 2023, 2023, : 86 - 93
  • [42] Optimal Merging in Quantum k-xor and k-sum Algorithms
    Naya-Plasencia, Maria
    Schrottenloher, Andre
    [J]. ADVANCES IN CRYPTOLOGY - EUROCRYPT 2020, PT II, 2020, 12106 : 311 - 340
  • [43] Scheduling lower bounds via AND subset sum
    Abboud, Amir
    Bringmann, Karl
    Hermelin, Danny
    Shabtay, Dvir
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2022, 127 : 29 - 40
  • [44] Subset sum "cubes" and the complexity of primality testing
    Woods, AR
    [J]. THEORETICAL COMPUTER SCIENCE, 2004, 322 (01) : 203 - 219
  • [45] A SUBSET SUM APPROACH TO COIL SELECTION FOR SLITTING
    Han, Yune T.
    Chang, Soo Y.
    [J]. INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING-THEORY APPLICATIONS AND PRACTICE, 2015, 22 (03): : 343 - 353
  • [46] Fixed points of the subset sum pseudorandom number generators
    Shparlinski, Igor E.
    [J]. DESIGNS CODES AND CRYPTOGRAPHY, 2023, 91 (07) : 2473 - 2479
  • [47] Multiple Subset Sum with Inclusive Assignment Set Restrictions
    Kellerer, Hans
    Leung, Joseph Y. -T.
    Li, Chung-Lun
    [J]. NAVAL RESEARCH LOGISTICS, 2011, 58 (06) : 546 - 563
  • [48] FPGA-Based Subset Sum Delay Lines
    Wang, Chung-Yun
    Chen, Yu-Yi
    Huang, Jiun-Lang
    Huang, Xuan-Lun
    [J]. 2014 IEEE 23RD ASIAN TEST SYMPOSIUM (ATS), 2014, : 287 - 291
  • [49] Fixed points of the subset sum pseudorandom number generators
    Igor E. Shparlinski
    [J]. Designs, Codes and Cryptography, 2023, 91 : 2473 - 2479
  • [50] A short note on Merlin-Arthur protocols for subset sum
    Nederlof, Jesper
    [J]. INFORMATION PROCESSING LETTERS, 2017, 118 : 15 - 16
12345