Swap test

The Swap test is a procedure in quantum computation that is used to check how much two quantum states differ.[1]

Consider two states: ${\displaystyle |\phi \rangle }$ and ${\displaystyle |\psi \rangle }$. The state of the system at the beginning of the protocol is ${\displaystyle |0,\phi ,\psi \rangle }$. After the Hadamard gate, the state of the system is ${\displaystyle {\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle )}$. The controlled SWAP gate transforms the state into ${\displaystyle {\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\psi ,\phi \rangle )}$. The second Hadamard gate results in ${\displaystyle {\frac {1}{2}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle +|0,\psi ,\phi \rangle -|1,\psi ,\phi \rangle )={\frac {1}{2}}|0\rangle (|\phi ,\psi \rangle +|\psi ,\phi \rangle )+{\frac {1}{2}}|1\rangle (|\phi ,\psi \rangle -|\psi ,\phi \rangle )}$

The Measurement gate on the first qubit ensures that it's 0 with a probability of

${\displaystyle P({\text{First qubit}}=0)={\frac {1}{2}}{\Big (}\langle \phi |\langle \psi |+\langle \psi |\langle \phi |{\Big )}{\frac {1}{2}}{\Big (}|\phi \rangle |\psi \rangle +|\psi \rangle |\phi \rangle {\Big )}={\frac {1}{2}}+{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}}$

when measured. If ${\displaystyle \psi }$ and ${\displaystyle \phi }$ are orthogonal ${\displaystyle ({|\langle \psi |\phi \rangle |}^{2}=0)}$, then the probability that 0 is measured is ${\displaystyle {\frac {1}{2}}}$. If the states are equal ${\displaystyle ({|\langle \psi |\phi \rangle |}^{2}=1)}$, then the probability that 0 is measured is 1.[2]

Pseudocode

Below is the pseudocode for implementing the Swap test:

Algorithm Swap Test

Inputs Two quantum states ${\displaystyle |\psi \rangle }$ and ${\displaystyle |\phi \rangle }$, stored in two separate qubit registers, each containing ${\displaystyle n}$ qubits (We denote the ${\displaystyle i}$-th qubit in the two registers, respectively, by ${\displaystyle \psi _{i}}$ and ${\displaystyle \phi _{i}}$)

                  An ancilla qubit, initialized as ${\displaystyle |0\rangle }$ (We denote the ancilla qubit by ${\displaystyle a}$)

                  Some ${\displaystyle P\in \mathbb {N} }$, representing the number of times the algorithm will be executed

Output Compute ${\displaystyle |\langle \psi |\phi \rangle |^{2}}$

1. For ${\displaystyle j}$ ranging from ${\displaystyle 1}$ to ${\displaystyle P}$:
   1. Apply a Hadamard gate to the ancilla qubit
   2. For ${\displaystyle i}$ ranging from ${\displaystyle 1}$ to ${\displaystyle n}$ (iterating over each pair of qubits in the two registers):
      1. Apply ${\displaystyle CSWAP(a,\ \psi _{i},\ \phi _{i})}$ (${\displaystyle a}$ is the control qubit, while ${\displaystyle \psi _{i}}$ and ${\displaystyle \phi _{i}}$ are the targets)
   3. Apply a Hadamard gate to the ancilla qubit
   4. Measure the ancilla qubit in the ${\displaystyle Z}$ basis and record the result of the measurement (we assume that measurements yield either ${\displaystyle 0}$ or ${\displaystyle 1}$, and we denote the outcome of the measurement by ${\displaystyle M_{j}}$)
2. Compute ${\displaystyle s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}}$

Return ${\displaystyle s}$ (Note that ${\displaystyle s\approx |\langle \psi |\phi \rangle |^{2}}$, with equality occurring as ${\displaystyle P\rightarrow \infty }$)

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

References

1. Kang Min-Sung, Heo Jino, Choi Seong-Gon, Moon Sung, Han Sang-Wook (2019). "Implementation of SWAP test for two unknown states in photons via cross-Kerr nonlinearities under decoherence effect". Scientific Reports. 9 (1). doi:10.1038/s41598-019-42662-4.CS1 maint: multiple names: authors list (link)
2. Harry Buhrman, Richard Cleve, John Watrous, Ronald de Wolf (2001). "Quantum Fingerprinting". Physical Review Letters. 87 (16). arXiv:quant-ph/0102001. doi:10.1103/PhysRevLett.87.167902.CS1 maint: multiple names: authors list (link)