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

Please wait, while we are loading the content...

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

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Moore, Cristopher Rockmore, Daniel Schulman, Leonard J. Russell, Alexander
Copyright Year	2007
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 literaturethe forgetful abelian method, and measurement in a random basisand 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.
Starting Page	938
Ending Page	958
Page Count	21
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539705447177
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	37
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2007-08-24
Access Restriction	Subscribed
Subject Keyword	Quantum computation hidden subgroup problem Applications of group representations to physics group representations Fourier analysis quantum computation
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in