Quantum algorithm for a generalized hidden shift problem
- Creators
- Childs, Andrew M.
- van Dam, Wim
Abstract
Consider the following generalized hidden shift problem: given a function f on {0,...,M − 1} × ZN promised to be injective for fixed b and satisfying f(b, x) = f(b + 1, x + s) for b = 0, 1,...,M − 2, find the unknown shift s ∈ ZN. For M = N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M = 2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive �, we give an efficient (i.e., poly(logN)) quantum algorithm for this problem provided M ≥ N^∈. The algorithm is based on the "pretty good measurement" and uses H. Lenstra's (classical) algorithm for integer programming as a subroutine.
Additional Information
© 2007 Society for Industrial and Applied Mathematics. AMC was supported in part by the National Science Foundation under Grant No. PHY-456720, and by the Army Research Office under Grant No. W911NF-05-1-0294. WvD was supported in part by the Disruptive Technology Office (DTO) under Army Research Office (ARO) contract number W911NF-04-R-0009. We thank Oded Regev for discussions about the relationship between lattice problems and the generalized hidden shift problem, and for pointing out that one can classically find the period of a noisy, periodic probability distribution using Lenstra's algorithm.Attached Files
Published - Childs2007p11687Proceedings_Of_The_Eighteenth_Annual_Acm-Siam_Symposium_On_Discrete_Algorithms.pdf
Files
Name | Size | Download all |
---|---|---|
md5:7e6c02c86f4d40e174257715e20e7c80
|
308.6 kB | Preview Download |
Additional details
- Eprint ID
- 20588
- Resolver ID
- CaltechAUTHORS:20101028-154950504
- PHY-456720
- NSF
- W911NF-05-1-0294
- Army Research Office
- W911NF-04-R-0009
- Disruptive Technology Office (DTO)
- Created
-
2010-11-19Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field