# What is the complexity of the Hadamard test and the SWAP test?

How to calculate the complexity of both the Hadamard test and SWAP test with $$n$$ qubits?

• 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$. Apr 12 at 3:44
• 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 Apr 12 at 6:47
• 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/… Apr 12 at 15:31