Английская Википедия: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 <math>\mathrm{Re}\langle\psi| U|\psi\rangle</math>, where <math> |\psi\rangle </math> is a quantum state and <math>U</math> is a unitary gate acting on the space of <math>|\psi\rangle</math>.[1] The Hadamard test produces a random variable whose image is in <math>\{\pm 1\}</math> and whose expected value is exactly <math>\mathrm{Re}\langle\psi| U|\psi\rangle</math>. It is possible to modify the circuit to produce a random variable whose expected value is <math>\mathrm{Im}\langle\psi| U|\psi\rangle</math> by applying an <math> S^{\dagger} </math> gate after the first Hadamard gate.[1]
Description of the circuit
To perform the Hadamard test we first calculate the state <math>\frac{1}{\sqrt{2}}\left(\left|0\right\rangle +\left|1\right\rangle \right)\otimes\left|\psi\right\rangle </math>. We then apply the unitary operator on <math>\left|\psi\right\rangle </math> conditioned on the first qubit to obtain the state <math>\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)</math>. We then apply the Hadamard gate to the first qubit, yielding <math>\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)</math>.
Measuring the first qubit, the result is <math>\left|0\right\rangle </math> with probability <math>\frac{1}{4}\langle\psi| (I+U^\dagger)(I+U)|\psi \rangle</math>, in which case we output <math>1</math>. The result is <math>\left|1\right\rangle </math> with probability <math>\frac{1}{4}\langle\psi | (I-U^\dagger)(I-U)| \psi \rangle</math>, in which case we output <math>-1</math>. The expected value of the output will then be the difference between the two probabilities, which is <math>\frac{1}{2} \langle\psi| (U^\dagger+U)| \psi \rangle = \mathrm{Re}\langle\psi | U| \psi \rangle</math>
To obtain a random variable whose expectation is <math>\mathrm{Im}\langle\psi | U | \psi \rangle</math> follow exactly the same procedure but start with <math>\frac{1}{\sqrt{2}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)\otimes\left|\psi\right\rangle </math>.[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 <math>|\phi_1\rangle</math> and <math>|\phi_2\rangle</math>:[3] instead of starting from a state <math>|\psi\rangle</math> it suffice to start from the ground state <math>|0\rangle</math>, and perform two controlled operations on the ancilla qubit. Controlled on the ancilla register being <math>|0\rangle</math>, we apply the unitary that produces <math>|\phi_1\rangle</math> in the second register, and controlled on the ancilla register being in the state <math>|1\rangle</math>, we create <math>|\phi_2\rangle</math> in the second register. The expected value of the measurements of the ancilla qubits leads to an estimate of <math>\langle \phi_1|\phi_2\rangle</math>. The number of samples needed to estimate the expected value with absolute error <math>\epsilon</math> is <math>O\left(\frac{1}{\epsilon^2}\right)</math>, because of a Chernoff bound. This value can be improved to <math>O\left(\frac{1}{\epsilon}\right)</math> using amplitude estimation techniques.[3]
References
