Thehidden subgroup problem (HSP) is a topic of research inmathematics andtheoretical computer science. The framework captures problems such asfactoring,discrete logarithm,graph isomorphism, and theshortest vector problem. This makes it especially important in the theory ofquantum computing becauseShor's algorithms for factoring and finding discrete logarithms inquantum computing are instances of the hidden subgroup problem forfinite abelian groups, while the other problems correspond tofinite groups that are not abelian.

Given agroup${\displaystyle G}$, asubgroup${\displaystyle H\le G}$, and a set${\displaystyle X}$, we say a function${\displaystyle f:G\to X}$hides the subgroup${\displaystyle H}$ if for all${\displaystyle g_1,g_2\in G,f(g_1)=f(g_2)}$ if and only if${\displaystyle g_{1}H=g_{2}H}$. Equivalently,${\displaystyle f}$ is constant on eachcoset ofH, while it is different between the different cosets ofH.

Hidden subgroup problem: Let${\displaystyle G}$ be a group,${\displaystyle X}$ a finite set, and${\displaystyle f:G\to X}$ a function that hides a subgroup${\displaystyle H\le G}$. The function${\displaystyle f}$ is given via anoracle, which uses${\displaystyle O(\log |G|+\log |X|)}$ bits. Using information gained from evaluations of${\displaystyle f}$ via its oracle, determine agenerating set for${\displaystyle H}$.

A special case is when${\displaystyle X}$ is a group and${\displaystyle f}$ is agroup homomorphism in which case${\displaystyle H}$ corresponds to thekernel of${\displaystyle f}$.

The hidden subgroup problem is especially important in the theory ofquantum computing for the following reasons.

• Shor's algorithm for factoring and for findingdiscrete logarithms (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP forfinite abelian groups.
• The existence of efficientquantum algorithms for HSPs for certainnon-abelian groups would imply efficient quantum algorithms for two major problems: thegraph isomorphism problem and certainshortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for thesymmetric group would give a quantum algorithm for the graph isomorphism.^[1] An efficient quantum algorithm for the HSP for thedihedral group would give a quantum algorithm for the${\displaystyle \mathrm{poly}(n)}$ unique SVP.^[2]

There is an efficientquantum algorithm for solving HSP over finiteabelian groups in time polynomial in${\displaystyle \log |G|}$. For arbitrary groups, it is known that the hidden subgroup problem is solvable using a polynomial number of evaluations of the oracle.^[3] However, the circuits that implement this may be exponential in${\displaystyle \log |G|}$, making the algorithm not efficient overall; efficient algorithms must be polynomial in the number of oracle evaluations and running time. The existence of such an algorithm for arbitrary groups is open. Quantum polynomial time algorithms exist for certain subclasses of groups, such as semi-direct products of someabelian groups.

The algorithm for abelian groups usesrepresentations, i.e. homomorphisms from${\displaystyle G}$ to${\displaystyle {\mathrm{G}\mathrm{L}}_k(\mathbb{C})}$, thegeneral linear group over thecomplex numbers. A representation is irreducible if it cannot be expressed as thedirect product of two or more representations of${\displaystyle G}$. For an abelian group, all theirreducible representations are thecharacters, which are the representations of dimension one; there are no irreducible representations of larger dimension for abelian groups.

Thequantum fourier transform can be defined in terms of${\displaystyle {\mathrm{Z}}_N}$, the additivecyclic group of order${\displaystyle N}$. Introducing the character$${\displaystyle {\chi }_j(k)={\omega }_N^{jk}=e^{2\pi i\frac{jk}{N}},}$$the quantum fourier transform has the definition of$${\displaystyle F_N|j⟩=\frac{1}{\sqrt{N}}\sum _{k=0}^N{\chi }_j(k)|k⟩.}$$Furthermore, we define${\displaystyle |{\chi }_j⟩=F_N|j⟩}$. Any finite abelian group can be written as the direct product of multiple cyclic groups${\displaystyle {\mathrm{Z}}_{N_1}\times {\mathrm{Z}}_{N_2}\times \dots \times {\mathrm{Z}}_{N_m}}$. On a quantum computer, this is represented as the tensor product of multiple registers of dimensions${\displaystyle N_1,N_2,\dots ,N_m}$ respectively, and the overall quantum fourier transform is${\displaystyle F_{N_1}\otimes F_{N_2}\otimes \dots \otimes F_{N_m}}$.

The set of characters of${\displaystyle G}$ forms a group${\displaystyle \hat{G}}$ called thedual group of${\displaystyle G}$. We also have a subgroup${\displaystyle H^{\perp }\le \hat{G}}$ of size${\displaystyle |G|/|H|}$ defined by$${\displaystyle H^{\perp }=\{{\chi }_g:{\chi }_g(h)=1\text{ for all }h\in H\}}$$For each iteration of the algorithm, the quantum circuit outputs an element${\displaystyle g\in G}$ corresponding to a character${\displaystyle {\chi }_g\in H^{\perp }}$, and since${\displaystyle {\chi }_g(h)=1}$ for all${\displaystyle h\in H}$, it helps to pin down what${\displaystyle H}$ is.

The algorithm is as follows:

1. Start with the state${\displaystyle |0⟩|0⟩}$, where the left register's basis states are each element of${\displaystyle G}$, and the right register's basis states are each element of${\displaystyle X}$.
2. Create a superposition among the basis states of${\displaystyle G}$ in the left register, leaving the state$\frac{1}{\sqrt{|G|}}\sum _{g\in G}|g⟩|0⟩$.
3. Query the function${\displaystyle f}$. The state afterwards is$\frac{1}{\sqrt{|G|}}\sum _{g\in G}|g⟩|f(g)⟩$.
4. Measure the output register. This gives some${\displaystyle f(s)}$ for some${\displaystyle s\in G}$, and collapses the state to$\frac{1}{\sqrt{|H|}}\sum _{h\in H}|s+h⟩|f(s)⟩$ because${\displaystyle f}$ has the same value for each element of the coset${\displaystyle s+H}$. We discard the output register to get$\frac{1}{\sqrt{|H|}}\sum _{h\in H}|s+h⟩$.
5. Perform the quantum fourier transform, getting the state$\frac{1}{\sqrt{|H|}}\sum _{h\in H}|{\chi }_{s+h}⟩$.
6. This state is equal to$\sqrt{\frac{|H|}{|G|}}\sum _{{\chi }_g\in H^{\perp }}{\chi }_g(s)|g⟩$, which can be measured to learn information about${\displaystyle H}$.
7. Repeat until${\displaystyle H}$ (or a generating set for${\displaystyle H}$) is determined.

The state in step 5 is equal to the state in step 6 because of the following:For the last equality, we use the following identity:

Each measurement of the final state will result in some information gained about${\displaystyle H}$ since we know that${\displaystyle {\chi }_g(h)=1}$ for all${\displaystyle h\in H}$.${\displaystyle H}$, or a generating set for${\displaystyle H}$, will be found after a polynomial number of measurements. The size of a generating set will be logarithmically small compared to the size of${\displaystyle G}$. Let${\displaystyle T}$ denote a generating set for${\displaystyle H}$, meaning${\displaystyle ⟨T⟩=H}$. The size of the subgroup generated by${\displaystyle T}$ will at least be doubled when a new element${\displaystyle t\notin T}$ is added to it, because${\displaystyle H}$ and${\displaystyle t+H}$ are disjoint and because${\displaystyle H\cup t+H\subseteq ⟨\{t\}\cup T⟩}$. Therefore, the size of a generating set${\displaystyle |T|}$ satisfies$${\displaystyle |T|\le \log |H|\le \log |G|}$$Thus a generating set for${\displaystyle H}$ will be able to be obtained in polynomial time even if${\displaystyle G}$ is exponential in size.

Many algorithms where quantum speedups occur in quantum computing are instances of the hidden subgroup problem. The following list outlines important instances of the HSP, and whether or not they are solvable.

• Hidden shift problem
• Pontryagin duality

• Richard Jozsa: Quantum factoring, discrete logarithms and the hidden subgroup problem
• Chris Lomont: The Hidden Subgroup Problem - Review and Open Problems
• Hidden subgroup problem on arxiv.org
• Complete implementation of Shor's algorithm for finding discrete logarithms with Classiq

• Group theory
• Quantum algorithms
• Quantum computing
• Theoretical computer science

• Articles with short description
• Short description is different from Wikidata
• Use American English from January 2019
• All Wikipedia articles written in American English