Swap test


The Swap test is a procedure in quantum computation that is used to check how much two quantum states differ.
Consider two states: and. The state of the system at the beginning of the protocol is. After the Hadamard gate, the state of the system is. The controlled SWAP gate transforms the state into. The second Hadamard gate results in
The Measurement gate on the first qubit ensures that it's 0 with a probability of
when measured. If and are orthogonal, then the probability that 0 is measured is. If the states are equal, then the probability that 0 is measured is 1.

Pseudocode

Below is the pseudocode for implementing the Swap test:
An ancilla qubit, initialized as
Some, representing the number of times the algorithm will be executed
  1. For ranging from to :
  2. # Apply a Hadamard gate to the ancilla qubit
  3. # For ranging from to :
  4. ## Apply
  5. # Apply a Hadamard gate to the ancilla qubit
  6. # Measure the ancilla qubit in the basis and record the result of the measurement
  7. Compute