CaltechAUTHORS
A Caltech Library Service

# The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts

Moore, Cristopher and Rockmore, Daniel and Russell, Alexander and Schulman, Leonard J. (2007) The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts. SIAM Journal on Computing, 37 (3). pp. 938-958. https://resolver.caltech.edu/CaltechAUTHORS:MOOsiamjc07

 Preview
PDF
See Usage Policy.

255kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:MOOsiamjc07

## Abstract

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup $H$ of a group $G$ must be determined from a quantum state $\psi$ 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 $\psi$ 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, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard 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 $H$ of the $q$-hedral groups, i.e., semidirect products ${\mathbb Z}_q \ltimes {\mathbb Z}_p$, where $q \mid (p-1)$, and in particular the affine groups $A_p$, can be information-theoretically reconstructed using the strong standard method. Moreover, if $|H| = p/ {\rm polylog}(p)$, these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/S0097539705447177DOIUNSPECIFIED
ORCID:
AuthorORCID
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:©2007 Society for Industrial and Applied Mathematics. Received by the editors March 9, 2005; accepted for publication (in revised form) December 20, 2006; published electronically August 24, 2007. 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, CCR-0049092, EIA-0218443, QuBIC-0218563, and CCF-0524613, the Charles Lee Powell Foundation, and the Bell Fund. We are grateful to Wim van Dam, Julia Kempe, Greg Kuperberg, Frederic Magniez, Martin Rötteler, and Miklos Santha for helpful conversations and to Sally Milius and Tracy Conrad for their support.
Subject Keywords:quantum computation; hidden subgroup problem; Fourier analysis; group representations
Issue or Number:3
Record Number:CaltechAUTHORS:MOOsiamjc07
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:MOOsiamjc07
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9092
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:26 Oct 2007
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page