Swap test

Circuit implementing the swap test between two states $|\phi \rangle$ and $|\psi \rangle$

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 $|\phi \rangle$ and $|\psi \rangle$ and outputs a Bernoulli random variable that is 1 with probability $\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, ${|\langle \psi |\phi \rangle |}^{2}$, to $\varepsilon$ additive error using $O(\textstyle {\frac {1}{\varepsilon ^{2}}})$ copies of the state simply by taking the average over many runs of the swap test. This 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: $|\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.

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}$

1. For $j$ ranging from $1$ to $P$:
   1. Apply a Hadamard gate to the ancilla qubit
   2. For $i$ ranging from $1$ to $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}$)
2. 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.