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

  • 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$
    – KAJ226
    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$ 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$
    – KAJ226
    Apr 12, 2022 at 15:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.