I noticed that in many quantum algorithms, you apply a layer of uniform Hadamard transformation before and after the operations in between. For example, Deutsch-Josza, Simon's, and Grover's search. But why is this?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The first Hadamard gates applied to a fiducial all-zero's ket on $n$ qubits serve to prepare your input register into the uniform superposition over all $2^n$ basis states. The last Hadamard gates serve to close the interference generated by the oracle in between.
The Hadamard gates are the "rotate" part of the "rotate, compute, rotate" paradigm of quantum computing.
Indeed even Shor's algorithm can be thought of in the same paradigm - the modular squaring circuit is sandwiched between Hadamard-like gates. Although in Shor, while the first gates are actually Hadamard gates the closing gates implement the Inverse Fourier Transform (which, morally, can be thought of as Hadamard-like gates).
answered Dec 20, 2023 at 20:29
-
1$\begingroup$ Just to add to QFT. If input qubits are all in state $|0\rangle$, then QFT and application of Hadamard on each qubit are equivalent. This is the case in Short or HHL algorithms. $\endgroup$ Commented Dec 21, 2023 at 7:00
$\begingroup$
$\endgroup$
1
On a basic level, I always thought of it as using Quantum Parallelism.
Applying a Hadamard on each input qubit transforms your 'classical' input (e.g. 00) to a quantum input consisting of every possible classical version (e.g. 00, 01, 10, 11).
Then the algorithm you're applying affects certain states differently from others (e.g. phase difference), and you pick up these differences through other manipulations and eventual measurements to get an output.
-
1$\begingroup$ After reading the other answer more, I believe my answer to be a simpler version of the first three lines of Mark Spinelli's answer. $\endgroup$– K0mp0t1kCommented Dec 21, 2023 at 3:31