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 the work of Barenco et al.^[1] and later rediscovered by Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.^[2] It appears commonly in quantum machine learning, and is a circuit used for proofs-of-concept in implementations of quantum computers.^[3][4]

Formally, the swap test takes two input states ${\displaystyle |\phi \rangle }$ and ${\displaystyle |\psi \rangle }$ and outputs a Bernoulli random variable that is 1 with probability ${\displaystyle \textstyle {\frac {1}{2}}-{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}}$ (where the expressions here use bra–ket notation). This allows one to, for example, estimate the squared inner product between the two states, ${\displaystyle {|\langle \psi |\phi \rangle |}^{2}}$, to ${\displaystyle \varepsilon }$ additive error by taking the average over ${\displaystyle O(\textstyle {\frac {1}{\varepsilon ^{2}}})}$ runs of the swap test.^[5] This requires ${\displaystyle O(\textstyle {\frac {1}{\varepsilon ^{2}}})}$ 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.^[6]