Hidden subgroup problem
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. It is a generalization of problems including 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.
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. It is a generalization of problems including 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. Given a group G , a subgroup H \leq G , and a set X , we say a function f : G \to X hides the subgroup H if for all g_1, g_2 \in G, f(g_1) = f(g_2) if and only if g_1 H = g_2 H . Equivalently, f is constant on each coset of H, while it is different between the different cosets of H. Hidden subgroup problem: Let G be a group, X a finite set, and f : G \to X a function that hides a subgroup H \leq G . The function f is given via an oracle, which uses O(\log |G| + \log |X|) bits. Using information gained from evaluations of f via its oracle, determine a generating set for H . A special case is when X is a group and f is a group homomorphism in which case H corresponds to the kernel of f . The quantum fourier transform can be defined in terms of \mathrm{Z}_N , the additive cyclic group of order N . Introducing the character \chi_j(k) = \omega^{jk}_N = e^{2\pi i \frac{jk}{N}}, the quantum fourier transform has the definition of F_N |j\rangle = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N-1} \chi_j(k) |k\rangle. Furthermore, we define |\chi_j\rangle = F_N |j\rangle . Any finite abelian group can be written as the direct product of multiple cyclic groups \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 N_1, N_2, \ldots, N_m respectively, and the overall quantum fourier transform is F_{N_1} \otimes F_{N_2} \otimes \ldots \otimes F_{N_m} . The set of characters of G forms a group \widehat{G} called the dual group of G . We also have a subgroup H^\perp \leq \widehat{G} of size |G|/|H| defined by 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 g \in G corresponding to a character \chi_g \in H^\perp , and since \chi_g(h) = {1} for all h \in H , it helps to pin down what H is. The algorithm is as follows: Start with the state |0\rangle |0\rangle , where the left register's basis states are each element of G , and the right register's basis states are each element of X . Create a superposition among the basis states of G in the left register, leaving the state \frac{1}{\sqrt } \sum_{g \in G} |g\rangle |0\rangle . Query the function f . The state afterwards is \frac{1}{\sqrt } \sum_{g \in G} |g\rangle |f(g)\rangle . Measure the output register. This gives some f(s) for some s \in G , and collapses the state to \frac{1}{\sqrt } \sum_{h \in H} |s + h\rangle |f(s)\rangle because f has the same value for each element of the coset s + {H} . We discard the output register to get \frac{1}{\sqrt } \sum_{h \in H} |s + h\rangle . Perform the quantum fourier transform, getting the state \frac{1}{\sqrt } \sum_{h\in H} |\chi_{s + h}\rangle . This state is equal to \sqrt{\frac } \sum_{\chi_g \in H^\perp} \chi_g(s) |g\rangle , which can be measured to learn information about H . Repeat until H (or a generating set for H ) is determined. The state in step 5 is equal to the state in step 6 because of the following: \begin{align} \frac{1}{\sqrt } \sum_{h \in H} |\chi_{s + h}\rangle &=\frac{1}{\sqrt } \sum_{h \in H} \sum_{g \in G} \chi_{s + h}(g)|g\rangle \\ &=\frac{1}{\sqrt } \sum_{g \in G} \chi_s(g) \sum_{h \in H} \chi_h(g)|g\rangle \\ &=\frac{1}{\sqrt } \sum_{g \in G} \chi_g(s) \left(\sum_{h \in H} \chi_g(h)\right) |g\rangle \\ &=\sqrt{\frac } \sum_{\chi_g \in H^\perp} \chi_g(s) |g\rangle \end{align} For the last equality, we use the following identity: Each measurement of the final state will result in some information gained about H since we know that \chi_g(h) = 1 for all h \in H . H , or a generating set for 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 G . Let T denote a generating set for H , meaning \langle T\rangle = H . The size of the subgroup generated by T will at least be doubled when a new element t \notin T is added to it, because H and t + H are disjoint and because H \cup t+H \subseteq \langle \{t\}\cup T\rangle . Therefore, the size of a generating set |T| satisfies |T| \leq \log|H| \leq \log|G| Thus a generating set for H will be able to be obtained in polynomial time even if G is exponential in size. Hidden subgroup problem on arxiv.org Complete implementation of Shor's algorithm for finding discrete logarithms with Classiq
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370171150 under CC BY-SA 4.0; modifications have been made.