Quantum Communication and Fingerprinting

If $t\ge 1$, then $1\mathrm{/}u\le 1$ for $u\in [1,t]$. Thus $\ln t={\int }_1^{t}du\mathrm{/}u\le t-1$, with strict inequality for $t>1$ because $1\mathrm{/}u<1$ on the nonempty interval $(1,t)$.

If $0<t<1$, then $1\mathrm{/}u>1$ on $(t,1)$, so $\ln t=-{\int }_t^{1}du\mathrm{/}u<-(1-t)=t-1$. At $t=1$ both sides are zero. This proves the claim and equality case.

If $D(Q\mathrm{\parallel }P)=+\mathrm{\infty }$, the result holds. Otherwise form distributions on $[m]\times \{0,1\}$ by $\tilde{Q}(i,1)=Q_i{X}_i$, $\tilde{Q}(i,0)=Q_i(1-X_i)$ and the analogous formulas for $\tilde{P}$. Expanding the defining finite sum and summing the common two-outcome kernel gives $D(\tilde{Q}\mathrm{\parallel }\tilde{P})=D(Q\mathrm{\parallel }P)$.

Group the terms of this divergence according to the second coordinate $z$. For each $z$, the group equals $q_z\ln (q_z\mathrm{/}{p}_z)+q_{z}D(\tilde{Q}(\cdot \mid z)\mathrm{\parallel }\tilde{P}(\cdot \mid z))$, where $q_z=\tilde{Q}(z)$ and $p_z=\tilde{P}(z)$; the conditional divergence is nonnegative by applying [F2] to each ratio, and zero-mass cases follow by the stated $+\mathrm{\infty }$ convention. Hence $D(Q\mathrm{\parallel }P)\ge D_{\mathrm{B}\mathrm{e}\mathrm{r}}(Q{X}^{\mathsf{T}}\mathrm{\parallel }P{X}^{\mathsf{T}})$.

For $0<q<p<1$, the binary divergence $K(p,q)=p\ln (p\mathrm{/}q)+(1-p)\ln ((1-p)\mathrm{/}(1-q))$ has ${\mathrm{\partial }}_{p}K=\ln \frac{p(1-q)}{q(1-p)}>0$ and ${\mathrm{\partial }}_{q}K=\frac{q-p}{q(1-q)}<0$. Therefore the hypotheses imply $K(Q{X}^{\mathsf{T}},P{X}^{\mathsf{T}})\ge K(0.94,0.06)=0.88\ln (47\mathrm{/}3)>1$, since $47\mathrm{/}3>9>e^2$. Boundary values follow by limits or give infinite divergence. Combining with step 2.1 proves $D(Q\mathrm{\parallel }P)\ge 1$.

For each message index $j$, set $q_j={\sum }_x{D}_x{B}_{xj}$. If $q_j>0$, put $D_x^{(j)}=D_x{B}_{xj}\mathrm{/}{q}_j$; if $q_j=0$, put $D^{(j)}=D$. Then each $D^{(j)}$ is a probability vector, ${\sum }_j{q}_j=1$, and ${\sum }_j{q}_j{D}^{(j)}=D$, because ${\sum }_j{B}_{xj}=1$; zero-weight terms contribute nothing.

Let $X_j=(M_{ij}{)}_{i=1}^m$ be the transpose of column $j$ of $M$. Reordering finite sums gives ${\sum }_j{q}_j(D^{(j)}A)X_j^{\mathsf{T}}={\sum }_x{D}_x(AM{B}^{\mathsf{T}}{)}_{xx}\ge \mathrm{0.99.}$ Also ${\sum }_j{q}_j(DA)X_j^{\mathsf{T}}=DAM{B}^{\mathsf{T}}{D}^{\mathsf{T}}$. Write $C=I+E$. Since all entries of $C$ are probabilities, $\mathrm{\mid }{E}_{xy}\mathrm{\mid }\le 0.01$; hence this last quantity is at most ${\sum }_x{D}_x^2+0.01({\sum }_x{D}_x{)}^2\le 0.02$. These are the required decomposition and acceptance bounds.

Put $P=DA$ and $Q_j=D^{(j)}A$. These are probability vectors and $P={\sum }_j{q}_j{Q}_j$. The weighted acceptance gap in [F1] is at least $0.97$. Since every difference ${\beta }_j=(Q_j-P)X_j^{\mathsf{T}}$ lies in $[-1,1]$, the set $U=\{j:{\beta }_j\ge 0.94\}$ has weight at least $1\mathrm{/}2$: otherwise the weighted average is less than $0.94+0.06\cdot (1\mathrm{/}2)=0.97$. For $j\in U$, $Q_j{X}_j^{\mathsf{T}}\ge 0.94$ and $P{X}_j^{\mathsf{T}}=Q_j{X}_j^{\mathsf{T}}-{\beta }_j\le 0.06$.

By [F2], $D(Q_j\mathrm{\parallel }P)\ge 1$ for each $j\in U$. Direct expansion of the finite sums, using $P_i={\sum }_j{q}_j(Q_j{)}_i$, gives $H(P)-{\sum }_j{q}_{j}H(Q_j)={\sum }_j{q}_{j}D(Q_j\mathrm{\parallel }P)\mathrm{.}$ If $P_i=0$, every positive-weight $(Q_j{)}_i$ is zero, so no undefined logarithm enters. The right side is at least the weight of $U$, hence at least $1\mathrm{/}2$. Substituting $P=DA$ and $Q_j=D^{(j)}A$ proves the entropy drop.

Let $D$ be any probability row with $\mathrm{\parallel }D{\mathrm{\parallel }}_2\le 0.1$. For every probability vector $p$, each coordinate lies in $[0,1]$, so $-p_i\ln p_i\ge 0$ when $p_i>0$, and the defined zero terms are also nonnegative; hence $H(p)\ge 0$. In particular this holds for $DA$ and each $D^{(j)}A$. The output entropy satisfies $H(DA)\le \ln m$, because $D(DA\mathrm{\parallel }u)=\ln m-H(DA)\ge 0$ for uniform $u$, and nonnegativity follows by summing [F3]. Apply [F2]. Set $L=\{j:H(D^{(j)}A)\le H(DA)-1\mathrm{/}4\}$ and $s={\sum }_{j\in L}{q}_j$. Since the average child entropy is nonnegative and at most $H(DA)-1\mathrm{/}2$, first $H(DA)\ge 1\mathrm{/}2$; then we have $(1-s)(H(DA)-1\mathrm{/}4)\le H(DA)-1\mathrm{/}2$, so $s\ge 1\mathrm{/}(4\ln m)$.

Nonnegative coordinates and $D={\sum }_j{q}_j{D}^{(j)}$ imply ${\sum }_{j\in L}{q}_j\mathrm{\parallel }{D}^{(j)}{\mathrm{\parallel }}_2\le \sqrt{m}\mathrm{\parallel }D{\mathrm{\parallel }}_2\mathrm{.}$ Indeed Cauchy–Schwarz bounds the left side by $\sqrt{m}({\sum }_j{q}_j^2\mathrm{\parallel }{D}^{(j)}{\mathrm{\parallel }}_2^2{)}^{1\mathrm{/}2}$, and the square under the radical is at most $\mathrm{\parallel }{\sum }_j{q}_j{D}^{(j)}{\mathrm{\parallel }}_2^2$ because all pairwise coordinate inner products are nonnegative. Dividing by $s$ shows some $j\in L$ with positive weight has both entropy drop at least $1\mathrm{/}4$ and $\mathrm{\parallel }{D}^{(j)}{\mathrm{\parallel }}_2\le R\mathrm{\parallel }D{\mathrm{\parallel }}_2$, where $R=4\sqrt{m}\ln m$.

Start from the uniform distribution $D^{(0)}$ on $[N]$, of norm $N^{-1\mathrm{/}2}$. While the norm is at most $0.1$, step 2.1 selects a child with entropy reduced by at least $1\mathrm{/}4$ and norm multiplied by at most $R$. Since the initial entropy is at most $\ln m$, after at most $K=\lfloor 4\ln m\rfloor +1$ such reductions the entropy would be negative; therefore either $N<100$ initially, or some $D^{(k)}$ with $k\le K$ has norm greater than $0.1$. In the latter case $0.1<N^{-1\mathrm{/}2}{R}^K$, so $N<100R^{2K}$.

For $m\ge 2$, $K\le 5.45\ln m$, $\ln R=\ln 4+\frac{1}{2}\ln m+\ln \ln m\le 3.5\ln m$, and $\ln 100\le 9.6(\ln m{)}^2$. Thus $\ln (100R^{2K})\le 47.8(\ln m{)}^2<60(\ln m{)}^2$. The initial case $N<100$ also satisfies this bound. Therefore $N\le \exp (60(\ln m{)}^2)$.

By [F4], [F2], and [F10], tensor products of orthonormal eigenbases diagonalize the tensor maps $\rho \otimes \tau$ and $\sigma \otimes \tau$ with nonnegative eigenvalues whose sums are $\mathrm{tr}(\rho )\mathrm{tr}(\tau )=1$ and $\mathrm{tr}(\sigma )\mathrm{tr}(\tau )=1$, respectively; hence both are density operators. The difference $\mathrm{\Delta }=\rho -\sigma$ is self-adjoint, hence normal by [F5], and has an orthonormal eigenbasis $(e_i)$ with real eigenvalues ${\lambda }_i$ by [F6]. Choose an orthonormal eigenbasis $(f_j)$ for $\tau$ with eigenvalues $t_j\ge 0$ and ${\sum }_j{t}_j=1$.

The product vectors $e_i\otimes f_j$ form an orthonormal basis by [F2], and [F10] shows that $\mathrm{\Delta }\otimes \tau$ is diagonal there with real eigenvalues ${\lambda }_i{t}_j$; therefore it is self-adjoint. In agreement, [F11] gives $(\mathrm{\Delta }\otimes \tau {)}^{\ast }={\mathrm{\Delta }}^{\ast }\otimes {\tau }^{\ast }=\mathrm{\Delta }\otimes \tau$. Applying the composition rule in [F11], its product with its adjoint is $({\mathrm{\Delta }}^{\ast }\mathrm{\Delta })\otimes ({\tau }^{\ast }\tau )$, diagonal in this basis with entries $({\lambda }_i{t}_j{)}^2$. Its unique nonnegative square root therefore has entries $\mathrm{\mid }{\lambda }_i\mathrm{\mid }{t}_j$ by [F7]. The same computation on $(e_i)$ gives $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_1={\sum }_i\mathrm{\mid }{\lambda }_i\mathrm{\mid }$. Therefore [F3] gives $\mathrm{\parallel }\mathrm{\Delta }\otimes \tau {\mathrm{\parallel }}_1={\sum }_{i,j}\mathrm{\mid }{\lambda }_i\mathrm{\mid }{t}_j={\sum }_i\mathrm{\mid }{\lambda }_i\mathrm{\mid }=\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_1$. Dividing by two and using [F8] proves $D(\rho \otimes \tau ,\sigma \otimes \tau )=D(\rho ,\sigma )$.

On the orthonormal product basis in [F2], $F(e_i\otimes e_j)=e_j\otimes e_i$. This basis permutation is unitary and is its own inverse, so $F^{\ast }=F$ and $F^2=I$. Direct expansion now gives $P_{\pm }^{\ast }=P_{\pm }$, $P_{\pm }^2=P_{\pm }$, $P_{+}{P}_{-}=0$, and $P_{+}+P_{-}=I$. Thus they form a complementary projective two-outcome measurement.

Put $v=\psi \otimes \varphi$, which is a unit vector by the tensor inner product. By [F3], $\mathrm{\mid }v⟩⟨v\mathrm{\mid }$ sends $z$ to $⟨z,v⟩v$, and [F4]–[F5] make this a density operator. In an orthonormal basis $(e_k)$, the diagonal coefficient of $\mathrm{\mid }v⟩⟨v\mathrm{\mid }{P}_{-}$ at $e_k$ is $⟨P_{-}{e}_k,v⟩⟨v,e_k⟩$. If $[P_{-}{]}_{ik}$ and $v_i$ are the matrix and vector coordinates, this coefficient is ${\sum }_i[P_{-}{]}_{ik}\overline{v_i}{v}_k$; summing over $k$ by [F7] gives ${\sum }_{i,k}[P_{-}{]}_{ik}{v}_k\overline{v_i}=⟨P_{-}v,v⟩$. This is the coordinate expansion asserted by [F8], and yields $\mathrm{tr}(\mathrm{\mid }v⟩⟨v\mathrm{\mid }{P}_{-})={\sum }_k⟨P_{-}{e}_k,v⟩⟨v,e_k⟩=⟨P_{-}v,v⟩,$ so [F6] makes this the outcome probability. Also $⟨Fv,v⟩=⟨\varphi ,\psi ⟩⟨\psi ,\varphi ⟩=\mathrm{\mid }⟨\psi ,\varphi ⟩{\mathrm{\mid }}^2$ by the tensor inner product and [F1]. Hence $\mathrm{Pr}[-]=⟨P_{-}v,v⟩=\frac{1-\mathrm{\mid }⟨\psi ,\varphi ⟩{\mathrm{\mid }}^2}{2}\mathrm{.}$ The complementary outcome has the remaining probability.

Fix a promised input. Let $X_i$ indicate that copy $i$ is correct. The independent private random tapes make these Bernoulli variables independent with common success probability $p\ge 2\mathrm{/}3$. Thus $\mu =pt\ge 2t\mathrm{/}3$. Since $t$ is odd, majority is wrong only if $S<t\mathrm{/}2$, an event contained in $S\le (3\mathrm{/}4)\mu$ because $(3\mathrm{/}4)\mu \ge t\mathrm{/}2$.

Apply [F1] with $\alpha =1\mathrm{/}4$: the error is at most $\exp (-\mu \mathrm{/}32)\le \exp (-t\mathrm{/}48)$. Each original message is a binary string of length at most $c$, so has fewer than $2^{c+1}$ possibilities. A tuple of $t$ such messages has at most $2^{t(c+1)}$ possibilities and can be injectively encoded by a fixed-length string of at most $t(c+1)$ bits. Thus repetition preserves private independence, yields the stated error, and charges at most $t(c+1)$ bits to each sender.

Alice's message map must be injective. If $x\mathrm{\ne }{x}^{\mathrm{\prime }}$ had the same Alice message, compare inputs $(x,x)$ and $(x^{\mathrm{\prime }},x)$. Bob's message is the same on both because Bob's input is $x$, and Alice's messages agree by assumption; the referee therefore receives identical transcripts although [F1] requires outputs $1$ and $0$. This contradiction proves injectivity.

With fixed length $b$, Alice has at most $2^b$ messages, so injectivity gives $2^n\le 2^b$ and $b\ge n$. If all strings of length at most $b$ are allowed, their number is ${\sum }_{j=0}^b{2}^j=2^{b+1}-1$; injectivity gives $2^n\le 2^{b+1}-1$, which forces $b\ge n$. Alice alone therefore sends at least $n$ bits in the worst case.

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)$.

Fix distinct $x,y$. In each coordinate, the independent random bits $E_i(x),E_i(y)$ disagree with probability $1\mathrm{/}2$, independently across the $32n$ coordinates. Thus their Hamming distance $S$ is a sum of independent Bernoulli$(1\mathrm{/}2)$ variables with mean $16n$. By [F1] with $\alpha =1\mathrm{/}2$, $\mathrm{Pr}(S\le 8n)\le e^{-2n}$.

Order the $2^n$ inputs lexicographically and index the $\left(\genfrac{}{}{0px}{}{2^n}{2}\right)<2^{2n}$ unordered pairs by $x<y$. For each such pair, let $B_{xy}$ be the event that its distance is below $8n$. On every codebook, the indicator of ${\bigcup }_{x<y}{B}_{xy}$ is at most ${\sum }_{x<y}{\mathbf{1}}_{B_{xy}}$; summing this pointwise inequality against the finite probability weights in [F2] gives the union bound $\mathrm{Pr}({\bigcup }_{x<y}{B}_{xy})\le {\sum }_{x<y}\mathrm{Pr}(B_{xy})$. By step 1.1 this is at most $2^{2n}{e}^{-2n}=e^{(2\ln 2-2)n}<1$, since $\ln 2={\int }_1^{2}du\mathrm{/}u<1$. Hence some finite codebook has every pairwise distance at least $8n$, which is relative distance at least $1\mathrm{/}4$. For each $n$, order all finite codebooks lexicographically and choose the first one with this property; this defines a nonuniform family without an arbitrary-choice axiom. The exhaustive selection gives no polynomial-time construction or efficient uniform encoder.

The $N$ summands in [F1] are distinct orthonormal basis vectors by [F2]–[F3], even when code bits repeat, because their index labels differ. Therefore $\mathrm{\parallel }{h}_x{\mathrm{\parallel }}^2=N^{-1}{\sum }_{i<N}1=1$. Its ambient register has $m+1=\lceil {\log }_{2}N\rceil +1$ qubits by [F1].