• Quick access
  • Homepage (fr)
  • International
  • François's Blog
  • Frédéric's Blog
  • Maths (fr)
  • Computer Science (fr)
  • Programming (fr)
  • Our games (fr)
  • Video games (fr)
• Special pages
  • Log in (fr)
  • Forum
  • Authors (fr)
  • Site Map (fr)
• Parent directories
  • International
  • The Hidden Subgroup Problem
  • Efficient Quantum Algorithms and The Hidden Subgroup Problem
• Current directory
  • Index
  • Report
  • Introduction
  • Prerequisites
  • Efficient Quantum Algorithms and The Hidden Subgroup Problem
  • The Standard Method for The Hidden Subgroup Problem
  • The Dihedral and Symmetric Hidden Subgroup Problems
  • The General Hidden Subgroup Problem
  • Conclusion
  • Appendix A
  • Appendix B
  • Appendix C
  • Appendix D
  • Appendix E
  • Appendix F
  • Appendix G
  • Bibliography

Efficient Quantum Algorithms and The Hidden Subgroup Problem

Simon's Problem

This problem imagined by Simon [Sim1994] demonstrates a quantum algorithm solving a black-box problem exponentially faster than any probabilistic classical algorithm. Contrary to Deutsch–Jozsa algorithm [DeuJoz1992], it is even exponentially faster than probabilistic classical algorithms.

The quantum solution to the problem is to repeat enough time the procedure given by the following circuit:

After applying $U_f$, we are in the state:

$$\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}\mid x⟩\mid f(x)⟩$$

Measuring the second register gives a value $y$ and makes the first register collapse to the superposition of its two preimages $x,x\oplus s$ :

After the second Hadamard gate, the state in the first register is

$$\frac{1}{\sqrt{2}}\frac{1}{\sqrt{N}}\sum _{z=0}^{N-1}((-1{)}^{z.x}+(-1{)}^{z.(x\oplus s)})\mid z⟩$$

Performing a standard measurement on the first register yields a random $n$-bits vector $z$ such that $z.s=0$ i.e. in the subspace orthogonal to $s$. Repeating the procedure $O\left(n\right)$ times gives a set of generators $z^1,\dots z^{O\left(n\right)}$ for this subspace with probability exponentially close to 1. Said otherwise, we have a system of equations $\sum _{i=1}^n{z}_i^j{s}_i\equiv 0\mathrm{ mod }\left(2\right)$ of rank the dimension of the subspace and $n$ unknowns $s_1,\dots s_n$. If $s=0$, then the rank of the system is $n$, so we get the unique solution $s=0$. Otherwise $s\ne 0$ and the rank of the system is $n-1$, so solving the system gives a subspace of dimension $n-\left(n-1\right)=1$, which is simply $\{0,s\}$. In either case, we have obtained $s$ as expected. The procedure is repeated $O\left(n\right)$ times, so a polynomial number of queries to the oracle $f$ are used.

What about (probabilistic) classical algorithm? Consider the special case $m=n.$ Let's choose randomly $f$ to be a permutation ($s=0$) or a two-to-one function ($s\ne 0$). In the former case, we randomly choose a permutation $f$ and in the latter case a nonzero string $s$. Simon proved that a classical algorithm calling $f$ no more than $2^{\raisebox{1ex}{$n$}\!\left/ \!\raisebox{-1ex}{$4$}\right.}$ times can not determine whether $s$ is zero or not with success probability greater than $\frac{1}{2}+2^{-\raisebox{1ex}{$n$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}$. Hence for a fixed minimal probability of success $\frac{1}{2}+\delta$, no classical algorithm using a polynomial number of queries can solve Simon's problem.

Shor's Factoring Algorithm

Shor's algorithm [Sho1995] allows to factor an integer $N_0$ in $\text{poly}\left(\log N_0\right)$ time. No classical algorithm are currently known to run this task in polynomial time. Actually, some cryptographic protocols are based on the assumption that no efficient algorithm exists for integer factoring and hence Shor's algorithm shows that they can be broken by quantum computation.

Shor's algorithm contains classical parts that can be executed in polynomial time and quantum computation is actually only used in a sub-procedure. More precisely, one step is to choose a random integer $a<N_0$ (which can be assumed to be coprime with $N_0$). The function defined on $\mathbb{Z}$ by $f\left(x\right)=a^x\text{ mod }\left(N_0\right)$ is $r$-periodic and the problem reduces to find the period $r$. We can restrict our study to the domain ${\mathbb{Z}}_N\subseteq \mathbb{Z}$ for some multiple $N$ of the period. Of course, we do not know how to choose $N$ precisely but it is possible to find some value $N=O\left({N_0}^2\right)$ for which the approximation does not change the final result. For simplicity, let's assume $N=rM$ is an exact multiple of the period. The period-finding submodule can be executed in $\text{poly}\left(\log N\right)=\text{poly}\left(\log N_0\right)$ using the circuit of figure 3.2, which is very similar to the one of Simon's problem. We define the Fourier transform $F_N$ to be the symmetric matrix

$$F_N=\frac{1}{\sqrt{N}}\sum _{i=0}^{N-1}\sum _{j=0}^{N-1}{e}^{\frac{2\pi i}{N}ij}\mid j⟩⟨i\mid$$

It can easily be shown to be unitary and hence a valid quantum operation. We assume that there exists an efficient implementation of $\text{poly}\left(\log N\right)$ elementary gates computing $F_N$. This implementation uses $n=\lceil \log N\rceil$ qubits, so we are working in an Hilbert Space of dimension $2^n\ge N$. Hence some basis states may not be used, they are just unchanged by the gate implementing $F_N$.

The first call to $F_N$ on $0^n$ returns the first column of $F_N$ i.e. a uniform superposition of basis vectors as in Simon's algorithm. Hence the state after $U_f$ is also

Measuring the second register gives a value $y$ and makes the first register collapse to the superposition of the preimages of $y$. If $x_0$ is such an image all the others are obtained by $x_0+ir$ for $i$ going from $0$ to $M-1$:

$$\frac{1}{\sqrt{M}}\sum _{i=0}^{M-1}\mid x_0+ir⟩\mid y⟩$$

After the second Fourier Transform gate, the state in the first register is $$\frac{1}{\sqrt{MN}}\sum _{j=0}^{N-1}\left(\sum _{i=0}^{M-1}{e}^{\frac{2\pi i}{N}(x_0+ir)j}\right)\mid j⟩$$

Each sum over $i$ is a geometric series of initial term $e^{\frac{2\pi i}{N}{x}_{0}j}$ and ratio $e^{\frac{2\pi i}{N}rj}$. So the sum is nonzero (and equal to ${Me}^{\frac{2\pi i}{N}{x}_{0}j}$) iff $e^{\frac{2\pi i}{N}rj}=1$ iff $j\equiv 0\text{ mod }\left(\frac{N}{r}\right)$ iff $j$ is multiple of $M$. Hence the state can be rewritten:

$$\frac{1}{\sqrt{r}}\sum _{j\text{multiple of}M}{e}^{\frac{2\pi i{x}_{0}j}{N}}\mid j⟩$$

All the vectors in the sum have same amplitude, so measuring the first register yields a uniformly random multiple of $M$ between $0$ and $N-1$. Using $k$ trials gives $j_1,\dots j_k$ multiples of $M$. One can show that $\gcd \left(j_1,\dots j_k\right)=M$ with success probability $\ge 1-2^{-\raisebox{1ex}{$k$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}$ (see Appendix E of [Lom2004] applied to $t_i=\frac{j_i}{M}$) and thus we get $r=\frac{N}{M}$.

Shor's Discrete Logarithm Algorithm

Similarly to Shor's algorithm, some cryptographic protocols are based on the difficulty of computing discrete logarithms. In [Sho1995], Shor describes a quantum algorithm to compute these logarithms in polynomial time. So suppose $x,g$ are given and that we want to find $y$.

We first define the function $f\left(a,b\right)=g^a{x}^b\text{ mod }\left(p\right)$ going from ${\mathbb{Z}}_{p-1}\times {\mathbb{Z}}_{p-1}$ to ${\mathbb{Z}}_p$. Each call to $f$ is clearly done in time $\mathrm{poly}\left(\log \left(p\right)\right)$. Note that we can rewrite $f$ using the discrete logarithm $y$: $f\left(a,b\right)=g^{a+yb}\text{ mod }\left(p\right)$. Hence $(a_1,b_1)\equiv (a_2,b_2)+\lambda \left(y,-1\right)\text{ mod }(p-1)$ implies $f(a_1,b_1)=f(a_2,b_2)$. Conversely, if this equality is true, we have $a_2-a_1\equiv y(b_1-b_2)\text{ mod }(p-1)$ and we can take $\lambda \in {\mathbb{Z}}_{p-1}$ to be the unique element congruent with $b_2-b_1$ modulo $p-1$ to recover the previous equality. As a consequence, we can say that $\left(y,-1\right)$ is the period of $f$ and all the values are obtained when $\lambda$ varies from $0$ to $p-2$.

We now define a circuit which is really similar to those we saw earlier. Here, the first register is the tensor product of two $\lceil \log (p-1)\rceil$-qubits state and the second a $\lceil \log \left(p\right)\rceil$-qubits state. On the first register we apply $F_{p-1}\otimes F_{p-1}$ i.e. a Fourier transform on each state of the tensor product:

On the first register applying the first $F_{p-1}\otimes F_{p-1}$ gives, as in Shor's algorithm, a superposition over the whole group

$$\left(\frac{1}{\sqrt{p-1}}\sum _{a=0}^{p-2}\mid a⟩\right)\left(\frac{1}{\sqrt{p-1}}\sum _{b=0}^{p-2}\mid b⟩\right)=\frac{1}{p-1}\sum _{a,b=0}^{p-2}\mid a⟩\mid b⟩$$

Then, applying the $U_f$ operator gives the superposition

$$\frac{1}{p-1}\sum _{a,b=0}^{p-2}\mid a⟩\mid b⟩\mid f(a,b)⟩$$

Measuring the second register yields a $f(a_0,b_0)$ and makes the first register collapse to the superposition of the preimages. By the discussion above it is:

$$\frac{1}{\sqrt{p-1}}\sum _{\lambda =0}^{p-2}\mid a_0+\lambda y⟩\mid b_0-\lambda ⟩\mid f(a_0,b_0)⟩$$

Now, we apply $F_{p-1}\otimes F_{p-1}$ on the first register, giving the state

$$\frac{1}{\sqrt{p-1}}\sum _{\lambda =0}^{p-2}\left(\frac{1}{\sqrt{p-1}}\sum _{u=0}^{p-2}{e}^{\frac{2\pi i\left(a_0+\lambda y\right)u}{p-1}}\mid u⟩\right)\left(\frac{1}{\sqrt{p-1}}\sum _{v=0}^{p-2}{e}^{\frac{2\pi i\left(b_0-\lambda \right)v}{p-1}}\mid v⟩\right)$$

which we can further simplify to

$$\frac{1}{{\left(\sqrt{p-1}\right)}^3}\sum _{\lambda ,u,v=0}^{p-2}{e}^{\frac{2\pi i((a_{0}u+b_{0}v)+\lambda (yu-v))}{p-1}}\mid u⟩\mid v⟩=\frac{1}{{\left(\sqrt{p-1}\right)}^3}\sum _{u,v=0}^{p-2}{e}^{\frac{2\pi i(a_{0}u+b_{0}v)}{p-1}}\left(\sum _{\lambda =0}^{p-2}{\left[e^{\frac{2\pi i(yu-v)}{p-1}}\right]}^{\lambda }\right)\mid u⟩\mid v⟩$$

The sum over lambda is a geometric series, and its value is nonzero (and of value $p-1$) iff $yu-v\equiv 0\text{ mod}\left(p-1\right)$. Replacing $v$ by $yu$ in the expression gives the final state:

$$\frac{1}{\sqrt{p-1}}\sum _{u=0}^{p-1}{e}^{\frac{2\pi i(a_0+b_{0}y)u}{p-1}}\mid u⟩\mid yu⟩$$

A measurement in the standard basis gives $u$ and $yu$ modulo $p-1$. If $u$ and $p-1$ are coprime, using the euclidean algorithm we can find $v$ such that $uv=1$ modulo $p-1$ from the first state. Then, we get $y=yuv$ modulo $p-1$ from the second state. So we have obtained $y={\log }_{g}x$ as expected. Note that u and $p-1$ are coprime with probability $\frac{\phi \left(p-1\right)}{p}=\Omega \left(\frac{1}{\log \left(\log \left(p\right)\right)}\right)$ so we only need to repeat the procedure about $\log \left(\log \left(p\right)\right)$ times to ensure a success with high probability.

The Hidden Subgroup Problem

In this section, we interpret the algorithms seen in previous sections in a common framework. The hope is to find new algorithms exponentially faster than their classical counterparts.

In the remaining of this document, we are only considering the case of a finite group $G$. In particular, the set $S$ may also be taken to be finite and we may even assume $\mid S\mid \le \mid G\mid$. Consequently, we can formulate the problem in terms of circuits: we encode the elements of the two sets with at most $n=\lceil \log \mid G\mid \rceil$ bits and hence $f$ can be viewed as a function $f:{{\mathbb{Z}}_2}^n\to {{\mathbb{Z}}_2}^n$ and represented by a quantum logic gate $U_f$. A naive algorithm for the hidden subgroup problem is the following:

1. compute $s_0=f\left(0\right)$
2. compute $f\left(g\right)$ for all $g\in G$ and return those for which $f\left(g\right)=s_0$ i.e. the elements of $H$.

The runtime complexity of this algorithm is $O\left(\mid G\mid \text{comp}\left(f\right)\right)$ so at least $O\left(\exp \left(n\right)\right)$. This is really bad compared with the efficient quantum algorithms previously seen. For instance Shor's algorithm run in $\text{poly}\left(\log N\right)=\text{poly}\left(n\right)$ i.e. exponentially faster. Hence we are lead to the following definition:

In particular, we have the following requirements for an efficient solution:

1. $f$ has a polynomial complexity.
2. $f$ is called a polynomial number of times.
3. the set generating $H$ has a polynomial size.

Note that not all functions $f:{{\mathbb{Z}}_2}^n\to {{\mathbb{Z}}_2}^n$ have a polynomial complexity, as indicated in exercise 3.16 of [NieChu2007]. The idea is that there are ${\left(2^n\right)}^{\left(2^n\right)}$ such functions so one can note encode all of them using only a polynomial number of elementary gates. As a consequence, $f$ has to be chosen carefully to satisfy the first property.

The argument given in appendix A.2.1.1 of [NieChu2007] shows that there is a set of size at most $\log \left(\mid H\mid \right)\le \log \left(\mid G\mid \right)$ that generates $H$. Actually, for any group $K$, if we pick uniformly at random $t+\log \left(\mid K\mid \right)$ elements of $K$ (for some integer $t\ge 0$) then the set obtained generates $K$ with probability $\ge 1-2^{-t}$ (see Appendix D of [Lom2004]).

Ettinger, Høyer and Knill [EttHøyKni1999] proved that the second requirement can always be satisfied i.e. only a polynomial number of calls to $f$ is needed to identify $H$. The idea is to prepare the state

$$\frac{1}{\sqrt{\mid G{\mid }^m}}\sum _{g_1,\dots ,g_m\in G}\mid g_1,\dots ,g_m⟩\mid f(g_1),\dots ,f(g_m)⟩$$

and measure the second register to get a tensor product of $m$ coset states (see definition 4.8). Then they apply measurements for each $g\in G$, that check whether $g\in H$. They prove that the answers given by the algorithm are correct with high probability for some $m=O\left(n\right)$. However, the whole algorithm is not $\text{poly}\left(n\right)$ since we test $\mid G\mid =\Omega \left(\exp \left(n\right)\right)$ elements.

In the particular examples of previous sections, there are natural encoding of the elements and algorithm to compute the product of two elements. For instance, for the cyclic HSP ${G=\mathbb{Z}}_N$ the elements are encoded as binary number of length $\lceil \log \left(N\right)\rceil$ and there are well-known algorithms of complexity polynomial in $\lceil \log \left(N\right)\rceil$ for the group operations. To study the general HSP, it is often useful to see the group $G$ as a black-box where the operations are performed by a group oracle. As in the case of the HSP oracle computing $f$, replacing the group oracles by polynomial-time operations yields an efficient algorithm.

This page is W3C-compliant - Author: Frédéric WANG