Entanglement-free, randomness-free quantum fingerprints require Ω(log n) qubits

Fix Bob's input $y$. On inputs $(y,y)$ and $(x,y)$ with $x\mathrm{\ne }y$, the referee receives ${\rho }_y\otimes {\sigma }_y$ and ${\rho }_x\otimes {\sigma }_y$ by [F1]. Group all referee outcomes assigned answer $1$ into one effect and the remaining outcomes into its complement, giving the protocol's two-outcome POVM. Its accepting probabilities differ by at least $1\mathrm{/}3$ by [F2] and the worst-case error bound. The total variation of this binary law is that absolute difference, so [F3]–[F5] imply $D({\rho }_x,{\rho }_y)\ge 1\mathrm{/}3$. As $x,y$ were arbitrary, the $2^n$ states ${\rho }_x$ are pairwise separated by at least $1\mathrm{/}3$.

Fix an orthonormal basis of the $d=2^{q_A}$ dimensional message space. By [F11], $\rho$ is self-adjoint, and by [F1] and [F10] its diagonal entries are nonnegative and sum to one, so each lies in $[0,1]$. Let $R=\sqrt{\rho }$, which exists by [F9]. For basis vectors $e_i,e_j$, ${\rho }_{ij}=⟨\rho e_j,e_i⟩=⟨R{e}_j,R{e}_i⟩$; [F8] gives $\mathrm{\mid }{\rho }_{ij}{\mathrm{\mid }}^2\le \mathrm{\parallel }R{e}_j{\mathrm{\parallel }}^2\mathrm{\parallel }R{e}_i{\mathrm{\parallel }}^2={\rho }_{jj}{\rho }_{ii}\le 1$. Thus the $d^2$ real coordinates (diagonal, and real and imaginary parts above the diagonal) lie in $[-1,1]$.

Partition each coordinate interval into half-open cells of width at most $h=1\mathrm{/}(12d^{3\mathrm{/}2})$, assigning the endpoint $1$ to the last cell. There are at most $\lceil 2\mathrm{/}h\rceil +1\le 26d^{3\mathrm{/}2}$ choices per coordinate and thus at most $(26d^{3\mathrm{/}2}{)}^{d^2}$ matrix cells. If two states lie in one cell, their diagonal entries differ by at most $h$, and each off-diagonal real and imaginary part differs by at most $h$. Therefore their difference $Z$ satisfies $\mathrm{\parallel }Z{\mathrm{\parallel }}_F\le \sqrt{2}dh$.

By [F6]–[F8] and Cauchy–Schwarz on the at most $d$ singular values, $\mathrm{\parallel }Z{\mathrm{\parallel }}_1\le \sqrt{d}\mathrm{\parallel }Z{\mathrm{\parallel }}_F$. Their trace distance is consequently at most $\frac{1}{2}\sqrt{d}(\sqrt{2}dh)=\sqrt{2}\mathrm{/}24<1\mathrm{/}3$, contradicting step 1.1. Each cell contains at most one code state, so $2^n\le (26d^{3\mathrm{/}2}{)}^{d^2}\mathrm{.}$ For $d=2^{q_A}$ this gives $n\ln 2\le 4^{q_A}(\ln 26+\frac{3}{2}{q}_A\ln 2)$. If $q_A<\frac{1}{4}{\log }_{2}n$, the right side is $O(\sqrt{n}\log n)<n\ln 2$ for all sufficiently large $n$, a contradiction. Hence $q_A=\mathrm{\Omega }(\log n)$. For any $x\mathrm{\ne }y$, fixing Alice's input at $x$ and comparing $(x,x)$ with $(x,y)$ gives $D({\rho }_x\otimes {\sigma }_x,{\rho }_x\otimes {\sigma }_y)\ge 1\mathrm{/}3$ by the same binary measurement argument as in step 1.1. Put $\mathrm{\Gamma }={\sigma }_x-{\sigma }_y$. Their difference is ${\rho }_x\otimes \mathrm{\Gamma }$. By the eigenbasis calculation in [F5] with the fixed density factor first, choose orthonormal eigenbases of ${\rho }_x$ and $\mathrm{\Gamma }$ with eigenvalues $t_i\ge 0$ and ${\lambda }_j\in \mathbb{R}$. The product basis diagonalizes ${\rho }_x\otimes \mathrm{\Gamma }$ with eigenvalues $t_i{\lambda }_j$, so the trace norm is $\mathrm{\parallel }{\rho }_x\otimes \mathrm{\Gamma }{\mathrm{\parallel }}_1={\sum }_{i,j}{t}_i\mathrm{\mid }{\lambda }_j\mathrm{\mid }={\sum }_j\mathrm{\mid }{\lambda }_j\mathrm{\mid }=\mathrm{\parallel }\mathrm{\Gamma }{\mathrm{\parallel }}_1$, since ${\sum }_i{t}_i=1$. Thus $D({\rho }_x\otimes {\sigma }_x,{\rho }_x\otimes {\sigma }_y)=D({\sigma }_x,{\sigma }_y)\ge 1\mathrm{/}3$. The same packing bound with $d=2^{q_B}$ yields $q_B=\mathrm{\Omega }(\log n)$.