Return to Colloquia & Seminar listing
The Quantum Algorithm for Simon's Problem
Student-Run Discrete Mathematics| Speaker: | Sonya Berg, UC Davis |
| Location: | 1147 MSB |
| Start time: | Tue, Apr 17 2007, 1:10PM |
Description
There are two classes of useful quantum algorithms, i.e. algorithms for which the quantum version achieves a faster time complexity than the
classical counterpart. One class is based on an efficient algorithm for the quantum Fourier Transform, and can be described broadly as algorithms which solve the hidden subgroup problem. I will focus on Simon's Algorithm since it has a simple QFT, namely the Hadamard Transform. This algorithm solves the hidden subgroup problem for the group $(\mathbb{Z}_2)^n$ in quantum polynomial time.