Why does the Hadamard gate satisfy $H|x\rangle=\frac{1}{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}\lvert z\rangle$?

Question

I'm studying Deutsch–Jozsa algorithm and I don't understand this passage about Hadamard gate result:

$$\newcommand{\ket}[1]{\lvert #1\rangle}H\ket x=\frac{1}{\sqrt2}(\ket0+(-1)^x\ket1)=\frac{1}{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}\ket z$$

Why this equivalence is true? In particular, what is $z$?

Answer 1

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( |0\rangle + (-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} $$

Answer 2

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.

1. 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>.

2. 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.

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

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

5. 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.