Quantum algorithms for the subset-sum problem

D.J. Bernstein, S. Jeffery, T. Lange, A. Meurer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Citations (Scopus)
1 Downloads (Pure)

Abstract

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 streamlined data structure for quantum walks on Johnson graphs. Keywords: subset sum; quantum search; quantum walks; radix trees; decoding; SVP; CVP
Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)
EditorsPh. Gaborit
Place of PublicationBerlin
PublisherSpringer
Pages16-33
ISBN (Print)978-3-642-38615-2
DOIs
Publication statusPublished - 2013
Event5th International Conference on Post-Quantum Cryptography (PQCrypto 2013) - Limoges, France
Duration: 4 Jun 20137 Jun 2013
Conference number: 5
http://pqcrypto2013.xlim.fr/

Publication series

NameLecture Notes in Computer Science
Volume7932
ISSN (Print)0302-9743

Conference

Conference5th International Conference on Post-Quantum Cryptography (PQCrypto 2013)
Abbreviated titlePQCrypto 2013
CountryFrance
CityLimoges
Period4/06/137/06/13
Internet address

Fingerprint Dive into the research topics of 'Quantum algorithms for the subset-sum problem'. Together they form a unique fingerprint.

  • Cite this

    Bernstein, D. J., Jeffery, S., Lange, T., & Meurer, A. (2013). Quantum algorithms for the subset-sum problem. In P. Gaborit (Ed.), Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings) (pp. 16-33). (Lecture Notes in Computer Science; Vol. 7932). Springer. https://doi.org/10.1007/978-3-642-38616-9_2