Swap test

Circuit implementing the swap test between two states ${\displaystyle |\phi \rangle }$ and ${\displaystyle |\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 the work of Barenco et al. ^[1] and later rediscovered by Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. ^[2] It appears commonly in quantum machine learning, and is a circuit used for proofs-of-concept in implementations of quantum computers. ^{[3] [4]}

Formally, the swap test takes two input states ${\displaystyle |\phi \rangle }$ and ${\displaystyle |\psi \rangle }$ and outputs a Bernoulli random variable that is 1 with probability ${\displaystyle \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, ${\displaystyle {|\langle \psi |\phi \rangle |}^{2}}$, to ${\displaystyle \varepsilon }$ additive error by taking the average over ${\displaystyle O(\textstyle {\frac {1}{\varepsilon ^{2}}})}$ runs of the swap test. ^[5] This requires ${\displaystyle 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. ^[6]

Explanation of the circuit

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]

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

Below is the pseudocode for estimating the value of ${\displaystyle |\langle \psi |\phi \rangle |^{2}}$ using P copies of ${\displaystyle |\psi \rangle }$ and ${\displaystyle |\phi \rangle }$:

InputsP copies each of the n qubits quantum states ${\displaystyle |\psi \rangle }$ and ${\displaystyle |\phi \rangle }$Output An estimate of ${\displaystyle |\langle \psi |\phi \rangle |^{2}}$forj ranging from 1 to P:     initialize an ancilla qubit A in state ${\displaystyle |0\rangle }$     apply a Hadamard gate to the ancilla qubit Afori ranging from 1 to n:          apply CSWAP to ${\displaystyle \psi _{i}}$ and ${\displaystyle \phi _{i}}$ (the ith qubit of the jth copy of ${\displaystyle |\psi \rangle }$ and ${\displaystyle |\phi \rangle }$), with A as the control qubit     apply a Hadamard gate to the ancilla qubit A     measure A in the ${\displaystyle Z}$ basis and record the measurement Mj as either a 0 or 1 compute ${\displaystyle s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}}$. return${\displaystyle s}$ as our estimate of ${\displaystyle |\langle \psi |\phi \rangle |^{2}}$

References

1. Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, Chiara Macchiavello (1997). "Stabilization of Quantum Computations by Symmetrization". SIAM Journal on Computing. 26 (5): 1541–1557. arXiv: quant-ph/9604028 . doi:10.1137/S0097539796302452.
2. Harry Buhrman, Richard Cleve, John Watrous, Ronald de Wolf (2001). "Quantum Fingerprinting". Physical Review Letters. 87 (16): 167902. arXiv: quant-ph/0102001 . Bibcode:2001PhRvL..87p7902B. doi:10.1103/PhysRevLett.87.167902. PMID   11690244. S2CID   1096490.
3. Schuld, Maria; Sinayskiy, Ilya; Petruccione, Francesco (2015-04-03). "An introduction to quantum machine learning". Contemporary Physics. 56 (2): 172–185. arXiv: 1409.3097 . Bibcode:2015ConPh..56..172S. doi:10.1080/00107514.2014.964942. ISSN   0010-7514. S2CID   119263556.
4. 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): 6167. Bibcode:2019NatSR...9.6167K. doi: 10.1038/s41598-019-42662-4 . PMC   6468003 . PMID   30992536.
5. de Wolf, Ronald (2021-01-20). "Quantum Computing: Lecture Notes". pp. 117–119, 122. arXiv: 1907.09415 [quant-ph].
6. Wiebe, Nathan; Kapoor, Anish; Svore, Krysta M. (1 March 2015). "Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning". Quantum Information and Computation. 15 (3–4). Rinton Press, Incorporated: 316–356. arXiv: 1401.2142 . doi:10.26421/QIC15.3-4-7. S2CID   37339559.

External links

• Implementation of the Swap test procedure with Classiq