Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Hidden subgroup problem
Summary
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems such as factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is an instance of the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.
Given a group , a subgroup , and a set , we say a function hides the subgroup if for all if and only if . Equivalently, is constant on the cosets of H, while it is different between the different cosets of H.
Hidden subgroup problem: Let be a group, a finite set, and a function that hides a subgroup . The function is given via an oracle, which uses bits. Using information gained from evaluations of via its oracle, determine a generating set for .
A special case is when is a group and is a group homomorphism in which case corresponds to the kernel of .
The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons.
Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the unique SVP.
There is an efficient quantum algorithm for solving HSP over finite Abelian groups in time polynomial in . For arbitrary groups, it is known that the hidden subgroup problem is solvable using a polynomial number of evaluations of the oracle.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.