Jump to content

# Hidden subgroup problem

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 algorithms for factoring and finding discrete logarithms in quantum computing are instances of the hidden subgroup problem for finite abelian groups, while the other problems correspond to finite groups that are not abelian.

## Problem statement

Given a group ${\displaystyle G}$, a subgroup ${\displaystyle H\leq 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 each coset of H, while it is different between the different cosets of H.

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\leq G}$. The function ${\displaystyle f}$ is given via an oracle, which uses ${\displaystyle O(\log |G|+\log |X|)}$ bits. Using information gained from evaluations of ${\displaystyle f}$ via its oracle, determine a generating set for ${\displaystyle H}$.

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

## Motivation

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

## Algorithms

There is an efficient quantum algorithm for solving HSP over finite abelian 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 some abelian groups.

### Algorithm for abelian groups

The algorithm for abelian groups uses representations, i.e. homomorphisms from ${\displaystyle G}$ to ${\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}$, the general linear group over the complex numbers. A representation is irreducible if it cannot be expressed as the direct product of two or more representations of ${\displaystyle G}$. For an abelian group, all the irreducible representations are the characters, which are the representations of dimension one; there are no irreducible representations of larger dimension for abelian groups.

#### Defining the quantum fourier transform

The quantum fourier transform can be defined in terms of ${\displaystyle \mathrm {Z} _{N}}$, the additive cyclic 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\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N}\chi _{j}(k)|k\rangle .}$Furthermore we define ${\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }$. 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 \ldots \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},\ldots ,N_{m}}$ respectively, and the overall quantum fourier transform is ${\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}$.

#### Procedure

The set of characters of ${\displaystyle G}$ forms a group ${\displaystyle {\widehat {G}}}$ called the dual group of ${\displaystyle G}$. We also have a subgroup ${\displaystyle H^{\perp }\leq {\widehat {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 a 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\rangle |0\rangle }$, 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 ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }$.
3. Query the function ${\displaystyle f}$. The state afterwards is ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }$.
4. Measure the output register. This gives some ${\displaystyle f(s)}$ for some ${\displaystyle s\in G}$, and collapses the state to ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }$ because ${\displaystyle f}$ has the same value for each element of the coset ${\displaystyle s+{H}}$. We discard the output register to get ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }$.
5. Perform the quantum fourier transform, getting the state ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }$.
6. This state is equal to ${\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }$, 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:{\displaystyle {\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi _{g}(h)\right)|g\rangle \\&={\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle \end{aligned}}}For the last equality, we use the following identity:

Theorem — ${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}}$

Proof

This can be derived from the orthogonality of characters. The characters of ${\displaystyle G}$ form an orthonormal basis:${\displaystyle {\frac {1}{\vert H\vert }}\sum _{h\in H}\chi _{g}(h)\chi _{g'}(h)={\begin{cases}1&g=g'\\0&g\neq g'\end{cases}}}$We let ${\displaystyle \chi _{g'}}$ be the trivial representation, which maps all inputs to ${\displaystyle 1}$, to get${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}}$Since the summation is done over ${\displaystyle H}$, ${\displaystyle \chi _{g}}$ also being trivial only matters for if it is trivial over ${\displaystyle H}$; that is, if ${\displaystyle \chi _{g}\in H^{\perp }}$. Thus, we know that the summation will result in ${\displaystyle \vert H\vert }$ if ${\displaystyle \chi _{g}\in H^{\perp }}$ and will result in ${\displaystyle 0}$ if ${\displaystyle \chi _{g}\notin H^{\perp }}$.

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 \langle T\rangle =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 \langle \{t\}\cup T\rangle }$. Therefore, the size of a generating set ${\displaystyle |T|}$ satisfies${\displaystyle |T|\leq \log |H|\leq \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.

## Instances

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.

Problem Quantum Algorithm Abelian? Polynomial time solution?
Deutsch's problem Deutsch's algorithm; Deutsch-Jozsa algorithm Yes Yes
Simon's problem Simon's algorithm Yes Yes
Order finding Shor's order finding algorithm Yes Yes
Discrete logarithm Shor's algorithm § Discrete logarithms Yes Yes
Period finding Shor's algorithm Yes Yes
Abelian stabilizer Kitaev's algorithm[4] Yes Yes
Graph Isomorphism None No No
Shortest vector problem None No No

## References

1. ^ Mark Ettinger; Peter Høyer (1999). "A quantum observable for the graph isomorphism problem". arXiv:quant-ph/9901029.
2. ^ Oded Regev (2003). "Quantum computation and lattice problems". arXiv:cs/0304005.
3. ^ Mark Ettinger; Peter Hoyer; Emanuel Knill (2004). "The quantum query complexity of the hidden subgroup problem is polynomial". Information Processing Letters. 91: 43–48. arXiv:quant-ph/0401083. Bibcode:2004quant.ph..1083E. doi:10.1016/j.ipl.2004.01.024. S2CID 5520617.
4. ^ Kitaev, Alexei (November 20, 1995). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.