Swap test

File:Quantum-swap-test-circuit-correct.png

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.

{{cite journal

| author =Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, Chiara Macchiavello

| title = Stabilization of Quantum Computations by Symmetrization

| journal = SIAM Journal on Computing

| volume = 26

| issue = 5

| year = 1997

| pages = 1541–1557

| doi = 10.1137/S0097539796302452

| arxiv = quant-ph/9604028

}}

and later rediscovered by Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.

{{cite journal

| author = Harry Buhrman, Richard Cleve, John Watrous, Ronald de Wolf

| title = Quantum Fingerprinting

| journal = Physical Review Letters

| volume = 87

| issue = 16

| year = 2001

| page = 167902

| doi = 10.1103/PhysRevLett.87.167902

| pmid = 11690244

| arxiv = quant-ph/0102001

| bibcode = 2001PhRvL..87p7902B

| s2cid = 1096490

}}

It appears commonly in quantum machine learning, and is a circuit used for proofs-of-concept in implementations of quantum computers.{{Cite journal|last1=Schuld|first1=Maria|last2=Sinayskiy|first2=Ilya|last3=Petruccione|first3=Francesco|date=2015-04-03|title=An introduction to quantum machine learning|url=https://doi.org/10.1080/00107514.2014.964942|journal=Contemporary Physics|volume=56|issue=2|pages=172–185|doi=10.1080/00107514.2014.964942|arxiv=1409.3097|bibcode=2015ConPh..56..172S|s2cid=119263556|issn=0010-7514}}{{cite journal

| author = Kang Min-Sung, Heo Jino, Choi Seong-Gon, Moon Sung, Han Sang-Wook

| title = Implementation of SWAP test for two unknown states in photons via cross-Kerr nonlinearities under decoherence effect

| journal = Scientific Reports

| volume = 9

| issue = 1

| year = 2019

| page = 6167

| doi = 10.1038/s41598-019-42662-4

| pmid = 30992536

| pmc = 6468003

| bibcode = 2019NatSR...9.6167K

| doi-access = free

}}

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 by taking the average over

O(\textstyle\frac{1}{\varepsilon^2})

runs of the swap test.{{cite arXiv|last=de Wolf|first=Ronald|date=2021-01-20|title=Quantum Computing: Lecture Notes|eprint=1907.09415|pages=117–119, 122|class=quant-ph}} This requires

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.{{Cite journal|last1=Wiebe|first1=Nathan|last2=Kapoor|first2=Anish|last3=Svore|first3=Krysta M.|author3-link= Krysta Svore |date=1 March 2015|title=Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning|url=https://dl.acm.org/doi/10.5555/2871393.2871400|journal=Quantum Information and Computation|publisher=Rinton Press, Incorporated|volume=15|issue=3–4|pages=316–356|doi=10.26421/QIC15.3-4-7|arxiv=1401.2142|s2cid=37339559}}

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

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.

In general, for $P$ trials of the swap test using $P$ copies of $|\phi\rangle$ and $P$ copies of $|\psi\rangle$ , the fraction of measurements that are zero is $1 - \textstyle\frac{1}{P} \textstyle\sum_{i = 1}^{P} M_i$ , so by taking $P \rightarrow \infty$ , one can get arbitrary precision of this value.

Inputs P copies each of the n qubits quantum states $|\psi\rangle$ and $|\phi\rangle$

Output An estimate of $|\langle \psi | \phi \rangle |^2$

for j ranging from 1 to P:

initialize an ancilla qubit A in state $|0\rangle$

apply a Hadamard gate to the ancilla qubit A

for i ranging from 1 to n:

apply CSWAP to $\psi_i$ and $\phi_i$ (the ith qubit of the jth copy of $|\psi\rangle$ and $|\phi\rangle$ ), with A as the control qubit

apply a Hadamard gate to the ancilla qubit A

measure A in the $Z$ basis and record the measurement ''M_j as either a 0 or 1

compute $s = 1 - \textstyle\frac{2}{P} \textstyle\sum_{i = 1}^{P} M_i$ .

return $s$ as our estimate of $|\langle \psi | \phi \rangle |^2$

References

Category:Quantum algorithms