Simultaneous-message equality by quantum fingerprints

Inputs: Integers $n\ge 1$, $N\ge 1$, and $r\ge 1$; a fixed binary code map $E:\{0,1{\}}^n\to \{0,1{\}}^N$ known to both senders and the referee; and inputs $x,y\in \{0,1{\}}^n$. The parties use no shared randomness or shared entanglement. State preparation and local computation are permitted and are not included in the communicated-qubit count.

Output: A bit $b\in \{0,1\}$, where $b=1$ means the referee declares $x=y$ and $b=0$ means the referee declares $x\mathrm{\ne }y$.

Set $m=\lceil {\log }_{2}N\rceil$ and $L=m+1$. Alice prepares $r$ copies of the fingerprint state $\mathrm{\mid }{h}_x⟩$ and sends the $r$ registers, each with $L$ qubits, to the referee. Bob prepares and sends $r$ copies of $\mathrm{\mid }{h}_y⟩$ in the same way. The referee groups the received registers as pairs $(A_j,B_j)$ in increasing order $j=1,\dots ,r$. For each pair, the referee appends a fresh control qubit $\mathrm{\mid }0⟩$, applies the Hadamard gate $H=2^{-1\mathrm{/}2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$, then applies one Fredkin gate to each of the $L$ corresponding pairs of message wires, using this fresh control qubit as the gate's control. The referee applies $H$ again and measures the control in the computational basis. If any test returns $1$, stop the loop and output $b=0$. If all $r$ tests return $0$, output $b=1$. Thus each sender transmits exactly $rL$ qubits, and the referee uses at most $rL$ Fredkin gates and $2r$ Hadamard gates.