Hidden subgroup problem

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.

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 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}}}$.

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}}}\\&={\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 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,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.