Jump to content

Swap test

From Wikipedia, the free encyclopedia
Circuit implementing the swap test between two states and

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 and and outputs a Bernoulli random variable that is 1 with probability (where the expressions here use bra–ket notation). This allows one to, for example, estimate the squared inner product between the two states, , to additive error by taking the average over runs of the swap test.[5] This requires 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

[edit]

Consider two states: and . The state of the system at the beginning of the protocol is . After the Hadamard gate, the state of the system is . The controlled SWAP gate transforms the state into . The second Hadamard gate results in

The measurement gate on the first qubit ensures that it's 0 with a probability of

when measured. If and are orthogonal , then the probability that 0 is measured is . If the states are equal , then the probability that 0 is measured is 1.[2]

In general, for trials of the swap test using copies of and copies of , the fraction of measurements that are zero is , so by taking , one can get arbitrary precision of this value.

Below is the pseudocode for estimating the value of using P copies of and :

Inputs P copies each of the n qubits quantum states  and 
Output An estimate of 

for j ranging from 1 to P:
    initialize an ancilla qubit A in state 
    apply a Hadamard gate to the ancilla qubit A
    for i ranging from 1 to n: 
        apply CSWAP to  and  (the ith qubit of the jth copy of  and ), with A as the control qubit
    apply a Hadamard gate to the ancilla qubit A
    measure A in the  basis and record the measurement Mj as either a 0 or 1
compute .
return  as our estimate of 

References

[edit]
  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.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  2. ^ a b 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.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  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.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  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.