Shor's algorithm and Hidden subgroup problems

Quantum Fourier transform and periodic finding algorithm:
Simply speaking, quantum fourier transform is analog to discrete fourier transform which can solve the periodic algorithm


Go back to Main page Notes for Complexity theory

Go back to the main quantum computing page

Shor's algorithm:
If we can solve periodic problem in polynomial time, then we have chance to solve factoring problem in polynomial time. This algorithm is called shor's algorithm.

這可以證明 Factoring belongs to BQP.

BQP= all decision language 可以被 Quantum Turing machine 在 polynomial time 解出。

由此可見: BQP 可能不等於NP，產生潛力。

Hidden subgroup problems: 
more abstractly, one can generalize simon's algorithm, shor's algorithm to problem called hidden subgroup problem. But we can not solve this problem in polynomial time if the group is not commutative.

Reference:

(1) Quantum Computation and Quantum Information textbook by Nielsen 

 QC-textbook.pdf

(2)  Ryan O'Donnell lecture note on Quantum Computing

(3)  Andrew Child's : lecture note on Quantum algorithms