# The Hidden Subgroup Problem

Master's Project
Frédéric Wang

Supervisor: Ivan Damgård

22 July 2010
Datalogisk Institut
Det Naturvidenskabelige Fakultet
Aarhus Universitet
Danmark École Nationale Supérieure
d'Informatique pour l'Industrie et l'Entreprise
Evry
France # Introduction

1. A Framework for Exponentially Fast Quantum Algorithms
2. Input States to find the Hidden Subgroup
3. The Symmetric Hidden Subgroup Problem
4. The Dihedral Hidden Subgroup Problem
5. Iterative Simplification of the Hidden Subgroup Problem

# A Framework for Exponentially Fast Quantum Algorithms

• Shor's Factoring Algorithm

Cyclic HSP 0 r 2r ℤ/Nℤ

• ${ℤ}_{N}$
• $r\mid N$
• function $f$ $r$-periodic

↝ find $r$ in complexity $\text{poly}\left(\mathrm{log}N\right)$

• The Hidden Subgroup Problem

G H 1+H 2+H 3+H 4+H 5+H

• finite group $G$
• hidden subgroup $H$
• oracle $f$, left cosets $gH$

↝ find $H$ in complexity $\text{poly}\left(\mathrm{log}\mid G\mid \right)$

# Input States to find the Hidden Subgroup

• Coset Sampling: $\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\mid {g}^{0}h⟩$

$O\left(\mathrm{log}\mid G\mid \right)$ entangled coset states

• Fourier Sampling: ${\rho }_{1},\dots ,{\rho }_{m}$ (morphisms from $G$ to matrix groups)

↝ Dedekindian Groups

• Combined-And-Measure Pipeline Coset States ... Final State Combine-and-Measure Pipeline

# The Symmetric Hidden Subgroup Problem

• $G={S}_{n}$, $\mathrm{log}\mid G\mid \underset{n\to \infty }{\sim }n\mathrm{log}n$
• Hard Problem on Graphs of $n$ vertices

Isomorphic Graphs

• graph isomorphism problem
• graph automorphism problem
• ↝ HSP over ${S}_{n}$, determine whether $H=\left\{\mathrm{Id}\right\}$?
• rigid graph isomorphism problem
• ↝ HSP over ${A}_{2n}$, determine whether $H=\left\{\mathrm{Id}\right\}$ or $H=\left\{\mathrm{Id},\sigma \right\}$?
• Negative Results
• Fourier Sampling
• $\Omega \left(\mathrm{log}\mid G\mid \right)$ entangled coset states
• Combine-and-Measure Pipeline

# The Dihedral Hidden Subgroup Problem

• $G={D}_{N}\cong {ℤ}_{N}⋊{ℤ}_{2}$, $\mathrm{log}\mid G\mid \underset{N\to \infty }{\sim }\mathrm{log}N$, $H=⟨\left(d,1\right)⟩$
• Hard Problem on Lattices of dimension $n$

A lattice V Vmin

• $g\left(n\right)$-unique Shortest Vector Problem: $‖V‖\ge g\left(n\right)‖{V}_{min}‖$
• Regev's Algorithm for $g\left(n\right)=\text{poly}\left(n\right)$

↝ find $d$ using coset sampling

• Extension $g\left(n\right)=\Theta \left({n}^{\frac{1}{2}+2p}\right)$
• Oracle complexity is $O\left({\left(\mathrm{log}N\right)}^{p}\right)$
• $N={2}^{m}$, recursive algorithm

• Partial Solutions
• reductions to Subset Sum Problem
• Combine-and-Measure Pipeline

# Iterative Simplification of the Hidden Subgroup Problem

• Group Decomposition

$\left\{1\right\}={G}_{0}⊲{G}_{1}⊲{G}_{2}⊲\dots ⊲{G}_{m}=G$ where ${G}_{i+1}}{{G}_{i}}$ is non-trivial simple group.

↝ general HSP if

• HSP over simple groups
• Construction of oracles over $G}{N}$ and $N$, for $N⊲G$
• Group Reductions
• subgroup reduction: $H\subseteq K\subseteq G$
• quotient reduction: $N\subseteq H$ and $N⊲G$
• Applications
• Dedekindian HSP
• Symmetric HSP
• Dihedral HSP

# Conclusion

• Facts on HSP
• natural extension of exponentially fast quantum algorithms
• related to hard problems on graphs and lattices
• resistant to coset sampling over $G$
• Future Directions
• HSP-based algorithms
• Input states
• Group Simplifications
• Questions?