Keywords and Synonyms
Generalization of Abelian stabilizer problem; Generalization of Simon's problem
Problem Definition
The Abelian hidden subgroup problem is the problem of finding generators for a subgroup K of an Abelian group G, where this subgroup is defined implicitly by a function \( { f \colon G \rightarrow X } \), for some finite set X. In particular, f has the property that \( { f(v) = f(w) } \) if and only if the cosetsFootnote 1 \( { v + K } \) and \( { w + K } \) are equal. In other words, f is constant on the cosets of the subgroup K, and distinct on each coset.
It is assumed that the group G is finitely generated and that the elements of G and X have unique binary encodings (the binary assumption is not so important, but it is important to have unique encodings.) When using variables g and h (possibly with subscripts) multiplicative notation is used for the group operations. Variables x and y(possibly with subscripts) will denote integers with addition. The boldface...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Assuming additive notation for the group operation here.
Recommended Reading
Boneh, D., Lipton, R.: Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract) In: Proceedings of 15th Annual International Cryptology Conference (CRYPTO'95), pp. 424–437, Santa Barbara, 27–31 August 1995
Brassard, G., Høyer, P.: An exact quantum polynomial-time algorithm for Simon's problem. In: Proc. of Fifth Israeli Symposium on Theory of Computing ans Systems (ISTCS'97), pp. 12–23 (1997) and in: Proceedings IEEE Computer Society, Ramat-Gan, 17–19 June 1997
Cheung, K., Mosca, M.: Decomposing Finite Abelian Groups. Quantum Inf. Comp. 1(2), 26–32 (2001)
Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum Algorithms Revisited. Proc. Royal Soc. London A 454, 339–354 (1998)
Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Royal Soc. London A 400, 97–117 (1985)
Deutsch, D., Jozsa, R.: Rapid solutions of problems by quantum computation. Proc. Royal Soc. London A 439, 553–558 (1992)
Ettinger, M., Høyer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Inf. Process. Lett. 91, 43–48 (2004)
Grigoriev, D.: Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. Theor. Comput. Sci. 180, 217–228 (1997)
Høyer, P.: Conjugated operators in quantum algorithms. Phys. Rev. A 59(5), 3280–3289 (1999)
Kaye, P., Laflamme, R., Mosca, M.: An Introduction to Quantum Computation. Oxford University Press, Oxford (2007)
Kitaev, A.: Quantum measurements and the Abelian Stabilizer Problem. quant-ph/9511026, http://arxiv.org/abs/quant-ph/9511026 (1995) and in: Electronic Colloquium on Computational Complexity (ECCC) 3, Report TR96-003,http://eccc.hpi-web.de/eccc-reports/1995/TR96-003/ (1996)
Kitaev, A.Y.: Quantum computations: algorithms and error correction. Russ. Math. Surv. 52(6), 1191–1249 (1997)
Mosca, M., Ekert, A.: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In: Proceedings 1st NASA International Conference on Quantum Computing & Quantum Communications. Lecture Notes in Computer Science, vol. 1509, pp. 174–188. Springer, London (1998)
Shor, P.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134, Santa Fe, 20–22 November 1994
Shor, P.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comp. 26, 1484–1509 (1997)
Simon, D.: On the power of quantum computation. In: Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 116–123, Santa Fe, 20–22 November 1994
Simon, D.: On the Power of Quantum Computation. SIAM J. Comp. 26, 1474–1483 (1997)
Vazirani, U.: Berkeley Lecture Notes. Fall 1997. Lecture 8. http://www.cs.berkeley.edu/~vazirani/qc.html (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag
About this entry
Cite this entry
Mosca, M. (2008). Abelian Hidden Subgroup Problem. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30162-4_1
Download citation
DOI: https://doi.org/10.1007/978-0-387-30162-4_1
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30770-1
Online ISBN: 978-0-387-30162-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering