Hadamard test

Short description: Technique in quantum computation

Circuit for the Hadamard test

In quantum computation, the Hadamard test is a method used to create a random variable whose expected value is the expected real part $\mathrm{R}\mathrm{e}⟨\psi |U|\psi ⟩$, where $|\psi ⟩$ is a quantum state and $U$ is a unitary gate acting on the space of $|\psi ⟩$. The Hadamard test produces a random variable whose image is in $\{\pm 1\}$ and whose expected value is exactly $\mathrm{R}\mathrm{e}⟨\psi |U|\psi ⟩$. It is possible to modify the circuit to produce a random variable whose expected value is $\mathrm{I}\mathrm{m}⟨\psi |U|\psi ⟩$ by applying an $S^{†}$ gate after the first Hadamard gate.

Description of the circuit

To perform the Hadamard test we first calculate the state $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)\otimes |\psi ⟩$. We then apply the unitary operator on $|\psi ⟩$ conditioned on the first qubit to obtain the state $\frac{1}{\sqrt{2}}(|0⟩\otimes |\psi ⟩+|1⟩\otimes U|\psi ⟩)$. We then apply the Hadamard gate to the first qubit, yielding $\frac{1}{2}(|0⟩\otimes (I+U)|\psi ⟩+|1⟩\otimes (I-U)|\psi ⟩)$.

Measuring the first qubit, the result is $|0⟩$ with probability $\frac{1}{4}⟨\psi |(I+U^{†})(I+U)|\psi ⟩$, in which case we output $1$. The result is $|1⟩$ with probability $\frac{1}{4}⟨\psi |(I-U^{†})(I-U)|\psi ⟩$, in which case we output $-1$. The expected value of the output will then be the difference between the two probabilities, which is $\frac{1}{2}⟨\psi |(U^{†}+U)|\psi ⟩=\mathrm{R}\mathrm{e}⟨\psi |U|\psi ⟩$

To obtain a random variable whose expectation is $\mathrm{I}\mathrm{m}⟨\psi |U|\psi ⟩$ follow exactly the same procedure but start with $\frac{1}{\sqrt{2}}(|0⟩-i|1⟩)\otimes |\psi ⟩$.

The Hadamard test has many applications in quantum algorithms such as the Aharonov-Jones-Landau algorithm. Via a very simple modification it can be used to compute inner product between two states $|{\varphi }_1⟩$ and $|{\varphi }_2⟩$: instead of starting from a state $|\psi ⟩$ it suffice to start from the ground state $|0⟩$, and perform two controlled operations on the ancilla qubit. Controlled on the ancilla register being $|0⟩$, we apply the unitary that produces $|{\varphi }_1⟩$ in the second register, and controlled on the ancilla register being in the state $|1⟩$, we create $|{\varphi }_2⟩$ in the second register. The expected value of the measurements of the ancilla qubits leads to an estimate of $⟨{\varphi }_1|{\varphi }_2⟩$. The number of samples needed to estimate the expected value with absolute error $ϵ$ is $O\left(\frac{1}{{ϵ}^2}\right)$, because of a Chernoff bound. This value can be improved to $O\left(\frac{1}{ϵ}\right)$ using amplitude estimation techniques.

References

,