Swap test

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

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 different qubit registers, each comprised of $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$)

• "←" 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.

Example

An implementation of the Swap test in Cirq.

"""Demonstrates Swap test.
=== EXAMPLE OUTPUT ===
0: ───H───@───H───M('Results')───
          │
1: ───H───×──────────────────────
          │
2: ───H───×──────────────────────
Results are all 0 because the states are equal.
Results=0000000000
0: ───H───────@───H───M('Results')───
              │
1: ───X───H───×──────────────────────
              │
2: ───H───────×──────────────────────
Not all the results are 0 because the states are not equal.
Results=1111000011
"""
import cirq


def swap_test(q0, q1, q2, circuit):
    circuit.append(
        [
            cirq.H(q0),
            cirq.CSWAP(q0, q1, q2),
            cirq.H(q0),
            cirq.measure(q0, key="Results"),
        ]
    )
    simulator = cirq.Simulator()
    print(circuit)
    result = simulator.run(circuit, repetitions=10)
    return result


def main():
    q0, q1, q2 = cirq.LineQubit.range(3)
    equal_states = cirq.Circuit.from_ops(cirq.H(q1), cirq.H(q2),)
    results = swap_test(q0, q1, q2, equal_states)
    print("Results are all 0 because the states are equal.")
    print(results)

    non_equal_states = cirq.Circuit.from_ops(cirq.X(q1), cirq.H(q1), cirq.H(q2),)
    results = swap_test(q0, q1, q2, non_equal_states)
    print("Not all the results are 0 because the states are not equal.")
    print(results)


if __name__ == "__main__":
    main()