Quantum algorithms for the subset-sum problem

DOI10.1007/978-3-642-38616-9_2MaRDI QIDQ4928586zbMATH OpenOpenAlexFDO

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

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

CVPdecodingquantum searchquantum walksradix treessubset sumSVP

Mathematics Subject Classification ID

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

Recommendations

• Improved classical and quantum algorithms for subset-sum
• The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
• Quantum algorithms for shifted subset problems
• scientific article; zbMATH DE number 5320343
• Improved low-density subset sum algorithms

Cited in

(31)

• Quantum algorithm design: techniques and applications
• Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
• Quantum key search for ternary LWE
• Optimal merging in quantum k-xor and k-sum algorithms
• Quantum algorithms for variants of average-case lattice problems via filtering
• Naor-Yung paradigm with shared randomness and applications
• Improved classical and quantum algorithms for subset-sum
• Naor-Yung Paradigm with Shared Randomness and Applications
• Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
• Exact Quantum Algorithms for the Leader Election Problem
• scientific article; zbMATH DE number 5320343 (Why is no real title available?)
• The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• Quantum Algorithms for Element Distinctness
• Subset Sum Quantumly in 1.17 n .
• 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
• Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
• Improved quantum algorithms for the k-XOR problem
• Integer syndrome decoding in the presence of noise
• Quantum data structure for range minimum query
• Quantum sieving for code-based cryptanalysis and its limitations for ISD
• Classical and quantum algorithms for variants of subset-sum via dynamic programming
• Quantum collision search for ternary LWE keys
• A unified framework of quantum walk search
• Quantum cryptography beyond quantum key distribution

This page was built for publication: Quantum algorithms for the subset-sum problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928586)