Hidden subgroup problem

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-1}\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 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\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:

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.