Solving Shift Problems and Hidden Coset Problem Using the Fourier Transform

2002/05/07 by Lawrence Ip, Ip, Lawrence · 2 citations
Computer Science · Engineering · Physics and Astronomy · #Coding theory and cryptography #Quantum Computing Algorithms and Architecture #graph theory and CDMA systems #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0205034

15 pages

arxiv created 2002/05/07 · arxiv updated 2009/12/01

Abstract

We give a quantum algorithm for solving a shifted multiplicative character problem over Z/nZ and finite fields. We show that the algorithm can be interpreted as a matrix factorization or as solving a deconvolution problem and give sufficient conditions for a shift problem to be solved efficiently by our algorithm. We also show that combining the shift problem with the hidden subgroup problem results in a hidden coset problem. This naturally captures the redundancy in the shift due to the periodic structure of multiplicative characters over Z/nZ.

Cited by

• Interconnection Networks for Scalable Quantum Computers
• Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation

Related

• Quantum Algorithms for some Hidden Shift Problems
• Hidden shift problem for complex functions
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• A new quantum algorithm for the hidden shift problem in ℤ2tn
• Efficient Quantum Algorithms for Shifted Quadratic Character Problems