Quantum algorithm for a generalized hidden shift problem

ABSTRACT

Consider the following generalized hidden shift problem: given a function f on {0,..., M - 1} x 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(log N)) 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.

REFERENCES

• 1: N. Alon and J. H. Spencer, The Probabilistic Method, 2nd ed., Wiley Interscience, New York, 2000.
• 2: D. Bacon, A. M. Childs, and W. van Dam, Optimal measurements for the dihedral hidden subgroup problem, to appear in Chicago Journal of Theoretical Computer Science. arXiv:quant-ph/0501044.
• 3: Dave Bacon , Andrew M. Childs , Wim van Dam, From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.469-478, October 23-25, 2005 [doi>10.1109/SFCS.2005.38]
• 4: Dan Boneh , Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.424-437, August 27-31, 1995
• 5: I. Borosh and L. B. Treybig, Bounds on positive integral solutions of linear diophantine equations, Proceedings of the American Mathematical Society 55 (1976), 299--304.
• 6: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 7: Wim van Dam , Sean Hallgren , Lawrence Ip, Quantum algorithms for some hidden shift problems, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: M. Ettinger and P. Høyer, A quantum observable for the graph isomorphism problem. arXiv:quant-ph/9901029.
• 9: Mark Ettinger , Peter Høyer, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics, v.25 n.3, p.239-251, Oct. 2000 [doi>10.1006/aama.2000.0699]
• 10: Katalin Friedl , Gábor Ivanyos , Frédéric Magniez , Miklos Santha , Pranab Sen, Hidden translation and orbit coset in quantum computing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780544]
• 11: D. Gavinsky, Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups, Quantum Information and Computation 4 (2004), no. 3, 229--235.
• 12: Michelangelo Grigni , J. Schulman , Monica Vazirani , Umesh Vazirani, Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem, Combinatorica, v.24 n.1, p.137-154, January 2004 [doi>10.1007/s00493-004-0009-8]
• 13: Sean Hallgren , Cristopher Moore , Martin Rötteler , Alexander Russell , Pranab Sen, Limitations of quantum coset states for graph isomorphism, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132603]
• 14: P. Hausladen and W. K. Wootters, A 'pretty good' measurement for distinguishing quantum states, Journal of Modern Optics 41 (1994), no. 12, 2385--2390.
• 15: C. W. Helstrom, Quantum Detection and Estimation Theory, Academic Press, New York, 1976.
• 16: A. S. Holevo (Kholevo), On asymptotically optimal hypothesis testing in quantum statistics, Theory of Probability and its Applications 23 (1979), no. 2, 411--415. English translation of Teoriya Veroyatnosteǐ i ee Primeneniya 23 (1978), no. 2, 429--432.
• 17: Y. Inui and F. Le Gall, An efficient algorithm for the hidden subgroup problem over a class of semi-direct product groups. arXiv:quant-ph/0412033.
• 18: G. Ivanyos, F. Magniez, and M. Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, International Journal of Foundations of Computer Science 14 (2003), no. 5, 723--739. arXiv:quant-ph/0102014.
• 19: Ravi Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operations Research, v.12 n.3, p.415-440, August 1, 1987 [doi>10.1287/moor.12.3.415]
• 20: R. M. Karp, Reducibility among computational problems, Complexity of Computer Computations, 1972, pp. 85--103.
• 21: Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, SIAM Journal on Computing, v.35 n.1, p.170-188, 2005 [doi>10.1137/S0097539703436345]
• 22: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen 261 (1982), no. 4, 515--534.
• 23: H. W. Lenstra, Jr., Integer programming with a fixed number of variables, Mathematics of Operations Research 8 (1983), no. 4, 538--548.
• 24: Cristopher Moore , Daniel Rockmore , Alexander Russell , Leonard J. Schulman, The power of basis selection in fourier sampling: hidden subgroup problems in affine groups, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 25: Cristopher Moore , Alexander Russell , Leonard J. Schulman, The Symmetric Group Defies Strong Fourier Sampling, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.479-490, October 23-25, 2005 [doi>10.1109/SFCS.2005.73]
• 26: M. A. Neumark, On a representation of additive operator set functions, Comptes Rendus de l'Académie des Sciences de l'URSS (Doklady Akademii Nauk SSSR) 41 (1943), 359--361.
• 27: Oded Regev, Quantum Computation and Lattice Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.520-529, November 16-19, 2002
• 28: O. Regev, A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv:quant-ph/0406151.
• 29: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]