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 条
  • [31] Solving Random Subset Sum Problem by lp-norm SVP Oracle
    Hu, Gengran
    Pan, Yanbin
    Zhang, Feng
    PUBLIC-KEY CRYPTOGRAPHY - PKC 2014, 2014, 8383 : 399 - 410
  • [32] Tackling the Subset Sum Problem with Fixed Size using an Integer Representation Scheme
    Parque, Victor
    2021 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC 2021), 2021, : 1447 - 1453
  • [33] Spiking Neural P Systems with Structural Plasticity: Attacking the Subset Sum Problem
    Cabarle, Francis George C.
    Hernandez, Nestine Hope S.
    Angel Martinez-del-Amor, Miguel
    MEMBRANE COMPUTING (CMC 2015), 2015, 9504 : 106 - 116
  • [34] The k-subset sum problem over finite fields of characteristic 2
    Choe, Hyok
    Choe, Chunghyok
    FINITE FIELDS AND THEIR APPLICATIONS, 2019, 59 : 175 - 184
  • [35] Subset Sum in the Absence of Concentration
    Austrin, Per
    Kaski, Petteri
    Koivisto, Mikko
    Nederlof, Jesper
    32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015), 2015, 30 : 48 - 61
  • [36] Subset Sum and the Distribution of Information
    Van den Berg, Daan
    Adriaans, Pieter
    PROCEEDINGS OF THE 13TH INTERNATIONAL JOINT CONFERENCE ON COMPUTATIONAL INTELLIGENCE (IJCCI), 2021, : 134 - 140
  • [37] Subset sum problems with digraph constraints
    Gourves, Laurent
    Monnot, Jerome
    Tlilane, Lydia
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (03) : 937 - 964
  • [38] SOME REMARKS ON PROBLEMS OF SUBSET SUM
    Tang, Min
    Xu, Hongwei
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2022, 59 (06) : 1339 - 1348
  • [39] Dense Subset Sum May Be the Hardest
    Austrin, Per
    Kaski, Petteri
    Koivisto, Mikko
    Nederlof, Jesper
    33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
  • [40] Subset sum problems with digraph constraints
    Laurent Gourvès
    Jérôme Monnot
    Lydia Tlilane
    Journal of Combinatorial Optimization, 2018, 36 : 937 - 964
12345