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

Description of the circuit

To perform the Hadamard test we first calculate the state ${\displaystyle {\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 ${\displaystyle \left|\psi \right\rangle }$ conditioned on the first qubit to obtain the state ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle \left|0\right\rangle }$ with probability ${\displaystyle {\frac {1}{4}}\langle \psi |(I+U^{\dagger })(I+U)|\psi \rangle }$, in which case we output ${\displaystyle 1}$. The result is ${\displaystyle \left|1\right\rangle }$ with probability ${\displaystyle {\frac {1}{4}}\langle \psi |(I-U^{\dagger })(I-U)|\psi \rangle }$, in which case we output ${\displaystyle -1}$. The expected value of the output will then be the difference between the two probabilities, which is ${\displaystyle {\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 ${\displaystyle \mathrm {Im} \langle \psi |U|\psi \rangle }$ follow exactly the same procedure but start with ${\displaystyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)\otimes \left|\psi \right\rangle }$.^[2]

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