How to calculate the complexity of both the Hadamard test and SWAP test with $n$ qubits?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ The complexity of Hadamard test is directly dependent on the complexity that you need to implement $U$ since you need to perform controlled-U. The complexity of the SWAP test is $N$ swap gates where $N$ is the number of qubits on the two states $|\psi \rangle$ and $|\phi\rangle$. $\endgroup$– KAJ226Commented Apr 12, 2022 at 3:44
-
$\begingroup$ May I ask in which authoritative paper or book can these complexity statements be found? I've always wanted to understand these complexity theories so that I can compare quantum circuits I've designed with classical algorithms to derive quantum advantage $\endgroup$– Ren-Xin ZhaoCommented Apr 12, 2022 at 6:47
-
4$\begingroup$ I don't know exactly where these statements are stated explicitly but you probably can find them in some standard texts... But you can see this just from looking at the circuit structure to implement the Hadamard test en.wikipedia.org/wiki/Hadamard_test_(quantum_computation) and the SWAP test quantumcomputing.stackexchange.com/questions/16146/… $\endgroup$– KAJ226Commented Apr 12, 2022 at 15:31
Add a comment
|