On the wikipedia entry for the Hadamard test, it mentions the test can be used with amplitude estimation to only require $O(\frac{1}{\epsilon})$ samples, rather than $O(\frac{1}{\epsilon^2})$ samples. The wikipedia entry cites https://quantumalgorithms.org/chapter-intro.html#modified-hadamard-test, however I see no description of the circuit or explanation to support this. Can someone help me understand the circuit or procedure for how to implement this and understand mathematically how the $O(\frac{1}{\epsilon})$ complexity is achieved?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider the usual Hadamard test circuit:
The obtained state at the end of this circuit is $|\phi\rangle = \frac{|0\rangle}{2} \otimes (|\psi\rangle + U |\psi\rangle) + \frac{|1\rangle}{2} \otimes (|\psi\rangle - U |\psi\rangle)$, with $|\psi \rangle = U_{\psi} |0^{n}\rangle$. What we wish to obtain from the Hadamard test is the probability of finding the ancillary qubit in state $|0\rangle$, $p_0$, since we can extract the real part of the desired expectation value from it, as in $\textrm{Re}(\langle \psi | U | \psi \rangle) = 2p_0 - 1$. A similar result would follow for the imaginary part upon measuring the ancilla in the Y-basis instead of the X-basis.
Given that $p_0$ is really what we are after in the Hadamard test, we can express the outcome of the circuit above in an alternative but instructive way:
$|\phi\rangle = \frac{|0\rangle}{2} \otimes (|\psi\rangle + U |\psi\rangle) + \frac{|1\rangle}{2} \otimes (|\psi\rangle - U |\psi\rangle) = \sqrt{p_0} |\psi_{\textrm{good}}\rangle + \sqrt{1-p_0} |\psi_{\textrm{bad}}\rangle$.
This form makes the connection to quantum amplitude estimation clear. The Hadamard test amounts to finding the amplitude of $|\psi_{\textrm{good}}\rangle$, and we can accomplish this with $\mathcal{O}(\frac{1}{\epsilon})$ samples for a precision target $\epsilon$ (i.e., the quadratic speed-up corresponding to the Heisenberg limit) via quantum amplitude estimation instead of the $\mathcal{O}(\frac{1}{\epsilon^2})$ of the standard approach.
Quantum amplitude estimation corresponds to quantum phase estimation with the Grover operator, $G = R_{\phi} R_{\textrm{good}}$. The reflector $R_{\phi}$ can be constructed as usual, with the circuit that prepares the input state $|\phi\rangle$ being just the Hadamard test circuit above. As for the reflector $R_{\textrm{good}}$, it amounts to just a Z gate on the ancillary qubit (as in oblivious amplitude amplification) since the ancilla is only found in state $|0\rangle$ for $|\psi_{\textrm{good}}\rangle$.
