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 {Re} \langle \psi |U|\psi \rangle$, where $|\psi \rangle$ is a quantum state and $U$ is a unitary gate acting on the space of $|\psi \rangle$. The Hadamard test produces a random variable whose image is in $\{\pm 1\}$ and whose expected value is exactly $\mathrm {Re} \langle \psi |U|\psi \rangle$. It is possible to modify the circuit to produce a random variable whose expected value is $\mathrm {Im} \langle \psi |U|\psi \rangle$ by applying an $S^{\dagger }$ gate after the first Hadamard gate.

Description of the circuit

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

Measuring the first qubit, the result is $\left|0\right\rangle$ with probability ${\frac {1}{4}}\langle \psi |(I+U^{\dagger })(I+U)|\psi \rangle$, in which case we output $1$. The result is $\left|1\right\rangle$ with probability ${\frac {1}{4}}\langle \psi |(I-U^{\dagger })(I-U)|\psi \rangle$, 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}}\langle \psi |(U^{\dagger }+U)|\psi \rangle =\mathrm {Re} \langle \psi |U|\psi \rangle$

To obtain a random variable whose expectation is $\mathrm {Im} \langle \psi |U|\psi \rangle$ follow exactly the same procedure but start with ${\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)\otimes \left|\psi \right\rangle$.

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 $|\phi _{1}\rangle$ and $|\phi _{2}\rangle$: instead of starting from a state $|\psi \rangle$ it suffice to start from the ground state $|0\rangle$, and perform two controlled operations on the ancilla qubit. Controlled on the ancilla register being $|0\rangle$, we apply the unitary that produces $|\phi _{1}\rangle$ in the second register, and controlled on the ancilla register being in the state $|1\rangle$, we create $|\phi _{2}\rangle$ in the second register. The expected value of the measurements of the ancilla qubits leads to an estimate of $\langle \phi _{1}|\phi _{2}\rangle$. The number of samples needed to estimate the expected value with absolute error $\epsilon$ is $O\left({\frac {1}{\epsilon ^{2}}}\right)$, because of a Chernoff bound. This value can be improved to $O\left({\frac {1}{\epsilon }}\right)$ using amplitude estimation techniques.

References

,