Both Simon's algorithm and the algorithm for period finding begin by placing qubits in the equal superposition state, but Simon's algorithm uses the n-qubit Hadamard $H^{\otimes n}$ while the period finding algorithm uses the quantum Fourier transform. My understanding is both QFT and the n-qubit Hadamard perform the same operation on the $|00...0\rangle$ state, creating the $\frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n}|x\rangle$ state. I'm reading this from the Qiskit textbook.

When the result is the same, why do the two algorithms use different ways to achieve the equal superposition? More generally, when would one use the n-qubit Hadamard, and when would one use the QFT?


As you pointed out correctly, both $H^{\otimes n}$ and QFT applied on input state $|0\rangle^{\otimes n}$ return state

$$ |\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n}|i\rangle. $$

There is no special reason why $n$ qubit Hadamard gate cannot replace QFT for $|0\rangle^{\otimes n}$ input. Maybe, an author of article about Simon's algorithm wanted to be more precise.

Overall, it does not matter which approach you use. Both return same result for $|0\rangle^{\otimes n}$ input.

EDIT (based on DaftWullie comment): However, in practice $n$ qubits Hadamard is prefered as it is very simple circuit in comparison with QFT.

  • 3
    $\begingroup$ But the hadamard transform is easier to implement than the Fourier, so for the initialisation step, you would always use the hadamard transform. $\endgroup$ – DaftWullie Jul 22 '20 at 6:47
  • $\begingroup$ @DaftWullie: Yes, absolutely agree in practice. However, the question was if there is any difference from theoretical point of view (at least, I understood it in this way). $\endgroup$ – Martin Vesely Jul 22 '20 at 6:50
  • 1
    $\begingroup$ well, the last part was "when would one use..." $\endgroup$ – DaftWullie Jul 22 '20 at 7:56
  • $\begingroup$ @DaftWullie: Right, I edited the answer accordingly. $\endgroup$ – Martin Vesely Jul 23 '20 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.