Quantum Algorithms for Some Hidden Shift Problems

DOI10.1137/S009753970343141XzbMath1126.81019OpenAlexW2017112356MaRDI QIDQ3446818

Wim van Dam, Sean Hallgren, Lawrence Ip

Publication date: 26 June 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753970343141x

zbMATH Keywords

quantum computingefficient algorithmsLegendre symbol

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Quantum computation (81P68) Number-theoretic algorithms; complexity (11Y16)

Related Items (18)

Quantum machine learning: a classical perspective ⋮ Post-quantum security of the Even-Mansour cipher ⋮ Quantum Fourier transform in computational basis ⋮ Quantum algorithms for typical hard problems: a perspective of cryptanalysis ⋮ Homomorphic encryption: a mathematical survey ⋮ Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem ⋮ Quantum linear key-recovery attacks using the QFT ⋮ The quantum query complexity of learning multilinear polynomials ⋮ Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields ⋮ Polynomial interpolation and identity testing from high powers over finite fields ⋮ Quantum algorithm design: techniques and applications ⋮ Quantum pattern matching fast on average ⋮ Identity testing and interpolation from high powers of polynomials of large degree over finite fields ⋮ Quantum algorithms for algebraic problems ⋮ Identifying Generalized Reed-Muller Codewords by Quantum Queries ⋮ Quantum computing: survey and analysis ⋮ A novel fault-tolerant quantum divider and its simulation ⋮ A fusion algorithm for solving the hidden shift problem in finite abelian groups

This page was built for publication: Quantum Algorithms for Some Hidden Shift Problems