Swap test
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Quantum-swap-test-circuit-correct.png/220px-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.[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]- ^ 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) - ^ 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) - ^ 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.
- ^ 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) - ^ de Wolf, Ronald (2021-01-20). "Quantum Computing: Lecture Notes". pp. 117–119, 122. arXiv:1907.09415 [quant-ph].
- ^ 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.