Kuperberg's Algorithm

In this article we denote DN=⟨x,y∣xN=y2=yxyx=1⟩D_N=\langle x,y\mid x^N=y^2=yxyx=1\rangle. Or equivalently we have xy=yxN−1xy=yx^{N-1} and yx=xN−1yyx=x^{N-1}y.

We use DN={ytxs:t∈{0,1},s∈ZN}D_N=\{y^tx^s:t\in\{0,1\},s\in\mathbb{Z}_N\}.

All the subgroups of DND_N is either a rotational group ⟨xd⟩\langle x^d\rangle, or a dihedral group ⟨xd,yxs⟩\langle x^d,yx^s\rangle, where d∣Nd\mid N and 0≤s<d0\le s< d.

For instance, when d=Nd=N, the subgroup is ⟨yxs⟩≅C2\langle yx^s\rangle\cong C_2.

Definition. Dihedral Hidden Subgroup Problem

Given NN and a subgroup H=⟨yxd⟩H=\langle yx^d\rangle a function ff which is stable on every right (or left) coset of H≤DNH\le D_N.

The goal is to output dd.

Kuperberg’s Algorithm for N=2nN=2^n

Step1. Create the uniform superposition over DND_N.

Take initial state ∣0⟩∣0⟩|0\rangle|0\rangle, the first state is of nn qubits and the second is of 11 qubits. Then we apply QFT on ZN\mathbb{Z}_N

FN:∣x⟩↦1N∑k=0N−1e2πikxN∣k⟩\begin{align*} F_N:|x\rangle\mapsto\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{\frac{2\pi ikx}{N}}|k\rangle \end{align*}

to both register and obtain

12N∑s∈ZN∑t∈{0,1}∣s⟩∣t⟩\begin{align*} \frac{1}{\sqrt{2N}}\sum_{s\in \mathbb{Z}_N}\sum_{t\in\{0,1\}}|s\rangle|t\rangle \end{align*}

which is recognized as a ‘constant pure state’ in Hilbert space C[DN]\mathbb{C}[D_N].

Step 2. Compute ff and obtain.

12N∑s∈ZN∑t∈{0,1}∣s⟩∣t⟩∣f(ytxs)⟩\begin{align*} \frac{1}{\sqrt{2N}}\sum_{s\in \mathbb{Z}_N}\sum_{t\in\{0,1\}}|s\rangle|t\rangle|f(y^tx^s)\rangle \end{align*}

Step 3. Measure the third register and record the output.

Suppose we measured the result rr , there are 22 possible (s,t)(s,t) ’s satisfying f(ytxs)=rf(y^tx^s)=r. To conclude, if f(xs)=rf(x^s)=r then f(ytxs+d)=rf(y^tx^{s+d})=r. So the remaining state is proportional to

∣s⟩∣0⟩+∣(s+d) mod N⟩∣1⟩\begin{align*} |s\rangle|0\rangle+|(s+d)\text{ mod }N\rangle|1\rangle \end{align*}

for some ss.

Step 4. Apply QFT on the first register, obtaining

∑k=0N−1e2πiksN∣k⟩∣0⟩+∑k=0N−1e2πik(s+d)N∣k⟩∣1⟩∝∑k=0N−1∣k⟩(∣0⟩+e2πikdN∣1⟩)\begin{align*} \sum_{k=0}^{N-1}e^{\frac{2\pi iks}{N}}|k\rangle|0\rangle+\sum_{k=0}^{N-1}e^{\frac{2\pi ik(s+d)}{N}}|k\rangle|1\rangle\propto\sum_{k=0}^{N-1}|k\rangle\left(|0\rangle+e^{\frac{2\pi ikd}{N}}|1\rangle\right) \end{align*}

Step 5. Measure the first register and record it, we have

∣0⟩+e2πikdN∣1⟩:=∣ψk⟩\begin{align*} |0\rangle+e^{\frac{2\pi ikd}{N}}|1\rangle:=|\psi_k\rangle \end{align*}

for some kk.

Now we have to ponder on this state. If k=2n−1=N2k=2^{n-1}=\frac{N}{2}, then the state is exactly ∣0⟩+(−1)d∣1⟩|0\rangle+(-1)^d|1\rangle. By measuring on the basis {∣+⟩,∣−⟩}\{|+\rangle,|-\rangle\} we know the parity of dd.

The trick is as follows: