Fingerprint swap-test error and communication cost

Assume $0<\delta \le 1$. If $x=y$, then [F1] gives $\mathrm{\mid }⟨h_x\mathrm{\mid }{h}_y⟩\mathrm{\mid }=1$, so [F2] gives anti probability zero. If $x\mathrm{\ne }y$, their agreement fraction is at most $1-\delta$, so the one-test anti probability $p$ satisfies $p=\frac{1-\mathrm{\mid }⟨h_x\mathrm{\mid }{h}_y⟩{\mathrm{\mid }}^2}{2}\ge p_0:=\frac{1-(1-\delta {)}^2}{2}=\delta -{\delta }^2\mathrm{/}2>0.$ Because $0<\delta \le 1$, $p_0\le 1\mathrm{/}2$; hence $-\ln (1-p_0)>0$, and the displayed formula in the Statement defines a finite positive integer $r$.

For one pair, let $F$ swap the two $L$-qubit message registers, so $P_{\pm }=(I\pm F)\mathrm{/}2$ by [F9]. The $L$ controlled Fredkin gates in [F3] realize $\mathrm{\mid }0⟩⟨0\mathrm{\mid }\otimes I+\mathrm{\mid }1⟩⟨1\mathrm{\mid }\otimes F$ by [F13]. After the first Hadamard, this operation, and the second Hadamard, $\mathrm{\mid }0⟩\otimes v$ becomes $\mathrm{\mid }0⟩\otimes P_{+}v+\mathrm{\mid }1⟩\otimes P_{-}v$ for $v=\psi \otimes \varphi$; thus the control measurement implements [F2]. Put $u=h_x\otimes h_y$ and $\mathrm{\Omega }=\mathrm{\mid }u⟩⟨u\mathrm{\mid }$. By [F1], [F5], and [F8], $u$ is unit and $\mathrm{\Omega }$ is a density operator. Reordering the $r$ Alice and $r$ Bob message registers by the wire permutation of [F5] gives the paired state $u^{\otimes r}$. By [F10], [F12], and the product inner product [F5], ${\mathrm{\Omega }}^{\otimes r}$ acts on each elementary tensor $z_1\otimes \cdots \otimes z_r$ as $⟨z_1\otimes \cdots \otimes z_r,u^{\otimes r}⟩u^{\otimes r}$. Since elementary tensors span, this is the rank-one projector of $u^{\otimes r}$, so [F8] makes the paired state a density operator.

For $s=(s_1,\dots ,s_r)\in \{+,-{\}}^r$, let $Q_s=P_{s_1}\otimes \cdots \otimes P_{s_r}$. The tests act on separate pairs, so the branch effect is $Q_s$. By [F2] and [F11], these effects are pairwise orthogonal projections and ${\sum }_s{Q}_s={⨂}_{j=1}^r(P_{+}+P_{-})=I$, with all-plus effect $P_{+}^{\otimes r}$. The outcome law [F7] and tensor-map composition [F11] give $\mathrm{Pr}[\text{all symmetric}]=\mathrm{tr}({\mathrm{\Omega }}^{\otimes r}{P}_{+}^{\otimes r})=\mathrm{tr}((\mathrm{\Omega }{P}_{+}{)}^{\otimes r})=(\mathrm{tr}(\mathrm{\Omega }{P}_{+}){)}^r=(1-p{)}^r$; the trace factorization follows by summing product-basis diagonal entries using [F6] and [F10], and the last equality uses the two-outcome law.

The loop in [F3] stops with unequal exactly when an anti outcome occurs, so equal inputs never err and unequal inputs err with probability $(1-p{)}^r\le (1-p_0{)}^r\le ϵ$ by [step 1.1] and [step 2.1]. Each party sends exactly $r(\lceil {\log }_{2}N\rceil +1)$ qubits. If $N\le Cn$ for fixed $C$ and $\delta$ is fixed positive, then $r=O(1+\ln (1\mathrm{/}ϵ))$ and $\lceil {\log }_{2}N\rceil +1=O(1+\log n)$, giving the stated product bound. Efficient uniform preparation needs a separate explicit code construction; [F4] supplies only a nonuniform family.