Category: cryptography | Difficulty: advanced | Qubits: 3 | Gates: 4 | Depth: 4
Quantum fingerprinting encodes an n-bit classical string into a O(log n)-qubit quantum state such that two parties can test string equality using only a constant number of qubits of communication. The referee runs a SWAP test on the two fingerprints. This circuit shows fingerprints for strings '0' and '0' (identical): the SWAP test ancilla should measure 0 with certainty. For different strings, it measures 1 with probability (1 - |⟨f₁|f₂⟩|²)/2 > 0.
c[0]=0 with certainty (identical fingerprints → |⟨f|f⟩|²=1 → P(1)=0)
The OpenQASM 2.0 circuit is in circuit.qasm.
OPENQASM 2.0;
include "qelib1.inc";
// Quantum fingerprinting via SWAP test
// q[0]: ancilla, q[1]: fingerprint of string A=0 (|0>), q[2]: fingerprint of string B=0 (|0>)
qreg q[3];
creg c[1];
// Both fingerprints are |0> (identical strings)
// SWAP test
h q[0];
cswap q[0],q[1],q[2];
h q[0];
// P(1) = (1 - |<A|B>|^2) / 2 = 0 for identical strings
measure q[0] -> c[0];
fingerprinting equality-testing communication-complexity swap-test
MIT — part of the OpenQC Algorithm Catalog.