This dissertation concerns the Hidden Subgroup Problem (HSP) in quantum computation. We explore certain facets of the problem which, we expect, will lead towards a general framework for understanding such problems. We first present an implementation of an optimal measurement, the Pretty Good Measurement (PGM), for the problem of the hidden subgroup problem over the dihedral group. This is a problem for which no efficient algorithm is known. This problem is relevant to the shortest vector in a lattice problem (SVP) in cryptography. We give a representation theoretic implementation of the PGM, achievable with only abelian transforms. The subset sum problem, an NP-complete problem, is needed in identification of certain subspaces. There are some novel ideas and techniques used in the implementation that make it realizable. This brings into focus how a measurement specified through a POVM (positive operator valued measure) is achievable through a basis change in a particular representation. This has connections to the HSP for other groups. We also study the question of optimal query selection to maximize the probability of subgroup identification. This part of the research complements a well-researched topic of finding optimal measurements in the spirit of state discrimination as applied to the hidden subgroup problem. We find the optimal query, the "character query", over a class of queries that are an equal superposition over the group, for oracles that take values in a finite abelian group. This query outperforms the query used in the "standard method" of the HSP. This approach has connections to other domains of quantum computation. We then extend the query selection idea to the case of multiple queries in the HSP and find examples in which this gives significant gains over the standard method. We consider the problems that the analysis of this more general problem entails, and outline a possible program to be followed. This is a part of continuing research
This dissertation concerns the Hidden Subgroup Problem (HSP) in quantum computation. We explore certain facets of the problem which, we expect, will lead towards a general framework for understanding such problems. We first present an implementation of an optimal measurement, the Pretty Good Measurement (PGM), for the problem of the hidden subgroup problem over the dihedral group. This is a problem for which no efficient algorithm is known. This problem is relevant to the shortest vector in a lattice problem (SVP) in cryptography. We give a representation theoretic implementation of the PGM, achievable with only abelian transforms. The subset sum problem, an NP-complete problem, is needed in identification of certain subspaces. There are some novel ideas and techniques used in the implementation that make it realizable. This brings into focus how a measurement specified through a POVM (positive operator valued measure) is achievable through a basis change in a particular representation. This has connections to the HSP for other groups. We also study the question of optimal query selection to maximize the probability of subgroup identification. This part of the research complements a well-researched topic of finding optimal measurements in the spirit of state discrimination as applied to the hidden subgroup problem. We find the optimal query, the "character query", over a class of queries that are an equal superposition over the group, for oracles that take values in a finite abelian group. This query outperforms the query used in the "standard method" of the HSP. This approach has connections to other domains of quantum computation. We then extend the query selection idea to the case of multiple queries in the HSP and find examples in which this gives significant gains over the standard method. We consider the problems that the analysis of this more general problem entails, and outline a possible program to be followed. This is a part of continuing research
We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups.
We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture.
For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem.
In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.We show that the optimal measurement for solving this problem is the so-called pretty good measurement.We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density ν = k/ log 2 N , where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.In particular, for ν < 1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N , while for ν > 1 the optimal measurement identifies the hidden subgroup with a probability of order unity.Thus the dihedral group provides an example of a group G for which Ω(log |G|) hidden subgroup states are necessary to solve the hidden subgroup problem.We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold.Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems.In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.
It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a new primitive in quantum algorithm design.
We provide a survey on the Hidden Subgroup Problem (HSP), which plays an important role in studying the security of public-key cryptosystems. We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP, recalling how classical problems (such as order finding, integer factorization, and discrete logarithm) can be formulated as abelian HSP instances. We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known, focusing on some relevant groups including dihedral group (connected to the shortest vector problem), symmetric groups (connected to the graph isomorphism problem), and semidirect product constructions (connected, in a special case, to the code equivalence problem). We also describe the main techniques for addressing the HSP in non-abelian cases, namely Fourier sampling and the black-box approach. Throughout the paper, we highlight the mathematical notions required and exploited in this context, providing a cryptography-oriented perspective.