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

26 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
Country/TerritoryFrance
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