Hadamard test
In-game article clicks load inline without leaving the challenge.
In quantum computation, the Hadamard test is a method used to create a random variable whose expected value is the expected real part R e ⟨ ψ | U | ψ ⟩ {\displaystyle \mathrm {Re} \langle \psi |U|\psi \rangle }, where | ψ ⟩ {\displaystyle |\psi \rangle } is a quantum state and U {\displaystyle U} is a unitary gate acting on the space of | ψ ⟩ {\displaystyle |\psi \rangle }. The Hadamard test produces a random variable whose image is in { ± 1 } {\displaystyle \{\pm 1\}} and whose expected value is exactly R e ⟨ ψ | U | ψ ⟩ {\displaystyle \mathrm {Re} \langle \psi |U|\psi \rangle }. It is possible to modify the circuit to produce a random variable whose expected value is I m ⟨ ψ | U | ψ ⟩ {\displaystyle \mathrm {Im} \langle \psi |U|\psi \rangle } by applying an S † {\displaystyle S^{\dagger }} gate after the first Hadamard gate.
Description of the circuit
To perform the Hadamard test we first calculate the state 1 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ | ψ ⟩ {\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 1 2 ( | 0 ⟩ ⊗ | ψ ⟩ + | 1 ⟩ ⊗ U | ψ ⟩ ) {\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 1 2 ( | 0 ⟩ ⊗ ( I + U ) | ψ ⟩ + | 1 ⟩ ⊗ ( I − U ) | ψ ⟩ ) {\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 | 0 ⟩ {\displaystyle \left|0\right\rangle } with probability 1 4 ⟨ ψ | ( I + U † ) ( I + U ) | ψ ⟩ {\displaystyle {\frac {1}{4}}\langle \psi |(I+U^{\dagger })(I+U)|\psi \rangle }, in which case we output 1 {\displaystyle 1}. The result is | 1 ⟩ {\displaystyle \left|1\right\rangle } with probability 1 4 ⟨ ψ | ( I − U † ) ( I − U ) | ψ ⟩ {\displaystyle {\frac {1}{4}}\langle \psi |(I-U^{\dagger })(I-U)|\psi \rangle }, in which case we output − 1 {\displaystyle -1}. The expected value of the output will then be the difference between the two probabilities, which is 1 2 ⟨ ψ | ( U † + U ) | ψ ⟩ = R e ⟨ ψ | U | ψ ⟩ {\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 I m ⟨ ψ | U | ψ ⟩ {\displaystyle \mathrm {Im} \langle \psi |U|\psi \rangle } follow exactly the same procedure but start with 1 2 ( | 0 ⟩ − i | 1 ⟩ ) ⊗ | ψ ⟩ {\displaystyle {\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 | ϕ 1 ⟩ {\displaystyle |\phi _{1}\rangle } and | ϕ 2 ⟩ {\displaystyle |\phi _{2}\rangle }: instead of starting from a state | ψ ⟩ {\displaystyle |\psi \rangle } it suffice to start from the ground state | 0 ⟩ {\displaystyle |0\rangle }, and perform two controlled operations on the ancilla qubit. Controlled on the ancilla register being | 0 ⟩ {\displaystyle |0\rangle }, we apply the unitary that produces | ϕ 1 ⟩ {\displaystyle |\phi _{1}\rangle } in the second register, and controlled on the ancilla register being in the state | 1 ⟩ {\displaystyle |1\rangle }, we create | ϕ 2 ⟩ {\displaystyle |\phi _{2}\rangle } in the second register. The expected value of the measurements of the ancilla qubits leads to an estimate of ⟨ ϕ 1 | ϕ 2 ⟩ {\displaystyle \langle \phi _{1}|\phi _{2}\rangle }. The number of samples needed to estimate the expected value with absolute error ϵ {\displaystyle \epsilon } is O ( 1 ϵ 2 ) {\displaystyle O\left({\frac {1}{\epsilon ^{2}}}\right)}, because of a Chernoff bound. This value can be improved to O ( 1 ϵ ) {\displaystyle O\left({\frac {1}{\epsilon }}\right)} using amplitude estimation techniques.
,