Why does the Hadamard gate satisfy $H|xrangle=frac{1}{sqrt2}sum_{zin{0,1}}(-1)^{xz}lvert zrangle$?

Question

I'm studying Deutsch–Jozsa algorithm and I don't understand this passage about Hadamard gate result:
$$newcommand{ket}[1]{lvert #1rangle}Hket x=frac{1}{sqrt2}(ket0+(-1)^xket1)=frac{1}{sqrt2}sum_{zin{0,1}}(-1)^{xz}ket z$$
Why this equivalence is true? In particular, what is $z$?

C. Kang · Accepted Answer

This is just a compact way of representing the Hadamard operator. The summation operator can be expanded, yielding:
$$ frac{1}{sqrt{2}} Big( (-1)^{x cdot 0} | 0 rangle + (-1)^{x cdot 1} | 1 rangle Big) = frac{1}{sqrt{2}} Big( |0rangle + (-1)^x |1 rangle Big) $$
This occurs because the matrix representation of the Hadamard operator is:
$$ frac{1}{sqrt{2}} begin{bmatrix} 1 & 1 \ 1 & -1 end{bmatrix} $$

Gokul Alex · Answer

Hadamard gate is used in the Deutch - Jozsha algorithm to prepare a superposition representing all possible bit combinations.  It uses the quantum parallelism concept to compute all values of f(x) from the superposition in polynomial time, instead of growing exponentially with the number of bases. We can breakdown the algorithm into the following major steps.

We initially prepare two quantum registers. The first is an n-qubit
register initialized to |0>, and the second is a one-qubit register
initialized to |1>.

Then we apply a Hadamard gate to each qubit. At this stage, our input register is an equal superposition of all the states in the computational basis.

Then the quantum oracle is applied such that it does not decohere the inputs.

At this point, the second single qubit register may be ignored.

Then we apply a Hadamard gate to each qubit in the first register.

In this approach, we are constructing a constant and balanced oracle. When the oracle is constant, it has no effect on the input qubits, and the quantum states before and after querying the oracle are the same. The following quantum circuit diagram depicts the algorithm.

Why does the Hadamard gate satisfy $H|xrangle=frac{1}{sqrt2}sum_{zin{0,1}}(-1)^{xz}lvert zrangle$?

2 Answers

Add your own answers!

Ask a Question