Abstract
The hidden subgroup problem (HSP) offers a unified framework to study problems of group-theoretical nature in quantum computing such as order finding and the discrete logarithm problem. While it is known that Fourier sampling provides an efficient solution in the abelian case, not much is known for general non-abelian groups. Recently, some authors raised the question as to whether post-processing the Fourier spectrum by measuring in a random orthonormal basis helps for solving the HSP. Several negative results on the shortcomings of this random strong method are known. In this paper however, we show that the random strong method can be quite powerful under certain conditions on the group G. We define a parameter r(G) and show that O((log |G| / r(G))2) iterations of the random strong method give enough classical information to solve the HSP. We illustrate the power of the random strong method via a concrete example of the HSP over finite Heisenberg groups. We show that r(G) = Ω(1) for these groups; hence the HSP can be solved using polynomially many random strong Fourier samplings followed by a possibly exponential classical post-processing without further queries. The quantum part of our algorithm consists of a polynomial computation followed by measuring in a random orthonormal basis. As an interesting by-product of our work, we get an algorithm for solving the state identification problem for a set of nearly orthogonal pure quantum states.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Spencer, J.: The probabilistic method. John Wiley and Sons, Chichester (2000)
Bacon, D., Childs, A., van Dam, W.: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. ArXiv preprint quant–ph/0504083 (2005)
Curtis, W.C., Reiner, I.: Representation Theory of Finite Groups and Algebras. Wiley and Sons, Chichester (1962)
Ettinger, M., Høyer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters 91(1), 43–48 (2004); See also ArXiv preprint quant–ph/0401083
Emerson, J.: Random quantum circuits and pseudo-random operators: theory and applications. ArXiv preprint quant–ph/0410087 (2004)
Emerson, J., Weinstein, Y., Saraceno, M., Lloyd, S., Cory, D.: Pseudo-Random unitary operators for quantum information processing. Science 302, 2098–2100 (2003)
Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and orbit coset in quantum computing. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 1–9 (2003)
Gavinsky, D.: Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups. Quantum Information and Computation 4(3), 229–235 (2004)
Grigni, M., Schulman, L., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Combinatorica, 137–154 (2004)
Hallgren, S., Russell, A., Ta-Shma, A.: The Hidden Subgroup Problem and Quantum Computation Using Group Representations. SIAM Journal on Computing 32(4), 916–934 (2003)
Ivanyos, G., Magniez, F., Santha, M.: Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. International Journal of Foundations of Computer Science, 723–740 (2003)
Ip, L.: Shor’s algorithm is optimal (2003) (unpublished manuscript)
Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ArXiv preprint quant–ph/0302112 (2003)
Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications, 2nd edn. Cambridge University Press, Cambridge (1994)
Matoušek, J.: Lectures on Discrete Geometry. In: Graduate Texts in Mathematics. Springer, Heidelberg (2002)
Moore, C., Russell, A.: For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets. ArXiv preprint quant–ph/0501177 (2005)
Moore, C., Rockmore, D., Russell, A., Schulman, L.: The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 1113–1122 (2004); ArXiv preprint quant–ph/0503095
Moore, C., Russell, A., Schulman, L.: The symmetric group defies strong Fourier sampling: Part I. ArXiv preprint quant–ph/0501056 (2005)
Serre, J.P.: Linear Representations of Finite Groups. Springer, Heidelberg (1977)
Wootters, W., Fields, B.: Optimal state-determination by mutually unbiased measurements. Ann. Physics 191(2), 363–381 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Radhakrishnan, J., Rötteler, M., Sen, P. (2005). On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds) Automata, Languages and Programming. ICALP 2005. Lecture Notes in Computer Science, vol 3580. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11523468_113
Download citation
DOI: https://doi.org/10.1007/11523468_113
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27580-0
Online ISBN: 978-3-540-31691-6
eBook Packages: Computer ScienceComputer Science (R0)