Simple quantum algorithm

I write this article in order to record some basic quantum algorithms which I might forget.

Deutsch–Jozsa algorithm and Simon's algorithm:

Go back to Main page Notes for Complexity theory
Go back to the main quantum computing page

Suppose, we have a black box function called (f): and there are only two case:

We want to find which case is the right case.  In classical, at least we need two oracles. If we are very lucky, we get the different output compare to the result we get at the beginning. If we are at very bad situation, we have to do at least 2^{n-1}+1 times to find the answer.

Simon's algorithm

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