Hadamard test explained

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 .^[1] The Hadamard test produces a random variable whose image is in \{\pm 1 \} and whose expected value is exactly Re \langle\psi| U|\psi\rangle . It is possible to modify the circuit to produce a random variable whose expected value is 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

(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 (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 (1)/(2) \left(\left| 0 \right\rangle ⊗ (I + U)\left|\psi\right\rangle + \left| 1 \right\rangle ⊗ (I - U)\left|\psi\right\rangle \right) .

Measuring the first qubit, the result is

\left| 0 \right\rangle with probability (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 (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 (1)/(2) \langle\psi| (U ^{\dagger+U)|} \psi \rangle = Re \langle\psi | U| \psi \rangle

To obtain a random variable whose expectation is

Im \langle\psi | U | \psi \rangle follow exactly the same procedure but start with (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

|\phi _{1\rangle} and |\phi _{2\rangle} :^[3] 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( (1)/(\epsilon ^{2}) \right) , because of a Chernoff bound. This value can be improved to O\left( (1)/(\epsilon) \right) using amplitude estimation techniques.

References

,

Notes and References

1. Dorit Aharonov Vaughan Jones, Zeph Landau . A Polynomial Quantum Algorithm for Approximating the Jones Polynomial . Algorithmica . 55 . 3 . 395–421 . 2009 . 10.1007/s00453-008-9168-0 . quant-ph/0511096 . 7058660 .
2. Book: quantumalgorithms.org - Hadamard test . Open Publishing . 27 February 2022.
3. Book: quantumalgorithms.org - Modified hadamard test . Open Publishing . 27 February 2022.