Quantum Algorithms for Some Hidden Shift Problems
Authors:
- Wim van DamWDWim van Dam
- Sean HallgrenSHSean Hallgren
- Lawrence IpLILawrence Ip
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (3) , 763-778
Abstract
Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of “unknown shift” problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- The query complexity of order-findingInformation and Computation, 2004
- Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup ProblemCombinatorica, 2004
- Sharp Quantum versus Classical Query Complexity SeparationsAlgorithmica, 2002
- Quantum Algorithms for Weighing Matrices and Quadratic ResiduesAlgorithmica, 2002
- On Quantum Algorithms for Noncommutative Hidden SubgroupsAdvances in Applied Mathematics, 2000
- Quantum algorithms revisitedProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- Secure circuit evaluationJournal of Cryptology, 1990
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984