# Modified hadamard test with $O(\frac{1}{\epsilon})$ samples using amplitude estimation

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?

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$$.