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: $|\phi \rangle$ and $|\psi \rangle$ . The state of the system at the beginning of the protocol is $|0,\phi ,\psi \rangle$ . After the Hadamard gate, the state of the system is ${\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle )$ . The controlled SWAP gate transforms the state into ${\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\psi ,\phi \rangle )$ . The second Hadamard gate results in

{\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

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 $\psi$ and $\phi$ are orthogonal $({|\langle \psi |\phi \rangle |}^{2}=0)$ , then the probability that 0 is measured is ${\frac {1}{2}}$ . If the states are equal $({|\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

|\psi \rangle

and

|\phi \rangle

, stored in two separate qubit registers, each containing

n

qubits (We denote the $i$ -th qubit in the two registers, respectively, by $\psi _{i}$ and $\phi _{i}$ )

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

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

Output Compute

|\langle \psi |\phi \rangle |^{2}

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

Return

s

(Note that $s\approx |\langle \psi |\phi \rangle |^{2}$ , with equality occurring as $P\rightarrow \infty$ , as in this limit, $P(a=0)=1-\textstyle {\frac {1}{P}}\textstyle \sum _{i=1}^{P}M_{i}$ , so the result follows from above.)

"←" 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[]

^ 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)
^ 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)

[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)

[BCWW01-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)

[1]

[2]