Swap test
The swap test is a procedure in quantum computation that is used to check how much two quantum states differ, appearing first in a paper of Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. It appears commonly in quantum machine learning, and is a circuit used for proofs-of-concept in implementations of quantum computers. Formally, the swap test takes two input states formula_1 and formula_2 and outputs a Bernoulli random variable that is 1 with probability formula_3 (where the expressions here use bra–ket notation). This allows one to, for example, estimate the squared inner  product between the two states, formula_4, to formula_5 additive error by taking the average over formula_6 runs of the swap test. This requires formula_6 copies of the input states. The squared inner product roughly measures "overlap" between the two states, and can be used in linear-algebraic applications, including clustering quantum states. Explanation of the circuit. Consider two states: formula_1 and formula_2. The state of the system at the beginning of the protocol is formula_10. After the Hadamard gate, the state of the system is formula_11. The controlled SWAP gate transforms the state into formula_12. The second Hadamard gate results  in formula_13 The measurement gate on the first qubit ensures that it's 0 with a probability of formula_14 when measured. If formula_15 and formula_16 are orthogonal formula_17, then the probability that 0 is measured is formula_18. If the states are equal formula_19, then the probability that 0 is measured is 1. In general, for formula_20 trials of the swap test using formula_20 copies of formula_1 and formula_20 copies of formula_2, the fraction of measurements that are zero is formula_25, so by taking formula_26, one can get arbitrary precision of this value. Below is the pseudocode for estimating the value  of formula_27 using "P" copies of formula_2 and formula_1: