Quantum Algorithms for the Subset-Sum Problem

DOI10.1007/978-3-642-38616-9_2zbMath1295.68127OpenAlexW2131684748MaRDI QIDQ4928586

Alexander Meurer, Tanja Lange, Stacey Jeffery, Daniel J. Bernstein

Publication date: 14 June 2013

Published in: Post-Quantum Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38616-9_2

zbMATH Keywords

decodingquantum walkssubset sumquantum searchCVPSVPradix trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (18)

The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound ⋮ Naor-Yung paradigm with shared randomness and applications ⋮ Lattice Sieving via Quantum Random Walks ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ Algebraic algorithms for variants of subset sum ⋮ Efficient reductions and algorithms for subset product ⋮ Quantum time/memory/data tradeoff attacks ⋮ Quantum complexity for vector domination problem ⋮ Near-optimal quantum algorithms for string problems ⋮ Improved classical and quantum algorithms for subset-sum ⋮ Quantum cryptography beyond quantum key distribution ⋮ Quantum algorithm design: techniques and applications ⋮ Subset Sum Quantumly in 1.17 n . ⋮ Unnamed Item ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ Naor-Yung Paradigm with Shared Randomness and Applications ⋮ Quantum key search for ternary LWE ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms

This page was built for publication: Quantum Algorithms for the Subset-Sum Problem