Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2004 | Published
Book Section - Chapter Open

The power of basis selection in fourier sampling: hidden subgroup problems in affine groups


Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a unknown subgroup H of a group G must be determined from a quantum state ψ over G that is uniformly supported on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling: the quantum Fourier transform of ψ is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation as well as its name) occurs. It has remained open whether the strong method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method.In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of the form ℤq × ℤp, where q | (p - 1) and q = p/polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the "forgetful" abelian method are insufficient for these groups so that, in fact, it appears that use of the corresponding nonabelian representation theory is crucial. We extend this to an informationtheoretic solution for the hidden subgroup problem over the groups ℤq × ℤp where q | (p - 1) and, in particular, the affine groups Ap. Finally, we prove a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

Additional Information

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. We are grateful to Wim van Dam, Frederic Magniez, Martin Rötteler, and Miklos Santha for helpful conversations, and to Sally Milius and Tracy Conrad for their support. Support for this work was provided by the California Institute of Technology's Institute for Quantum Information (IQI), the Mathematical Sciences Research Institute (MSRI), the Institute for Advanced Study (IAS), NSF grants ITR-0220070, ITR-0220264, CCR-0093065, EIA-0218443, QuBIC-0218563, the Charles Lee Powell Foundation, and the Bell Fund.

Attached Files

Published - p1113-moore.pdf


Files (273.6 kB)
Name Size Download all
273.6 kB Preview Download

Additional details

August 19, 2023
October 23, 2023