Hadamard test (quantum computation)

In quantum computation, the Hadamard test is a method used to create a random variable whose expected value is the expected real part of the observed value of a quantum state with respect to some unitary operator. 
Let formula_1 be a state which can be efficiently generated, and let formula_2 be a unitary gate. The Hadamard test produces a random variable whose image is in formula_3 and whose expected value is exactly formula_4. A variant of the test produces a random variable whose expected value is formula_5.
To perform the Hadamard test we first calculate the state formula_6. We then apply the unitary operator on formula_1 conditioned on the first qubit to obtain the state formula_8. We then apply the Hadamard gate to the first qubit, yielding formula_9.
Measuring the first qubit, the result is formula_10 with probability formula_11, in which case we output formula_12. The result is formula_13 with probability formula_14, in which case we output formula_15. The expected value of the output will then be the difference between the two probabilities, which is formula_16
To obtain a random variable whose expectation is formula_5 follow exactly the same procedure but start with formula_18.
The Hadamard test has many applications in quantum algorithms such as the Aharonov-Jones-Landau algorithm.