Robust logarithmic lower bound on shared-resource cost for $f$-routing

Abstract

In one-round $f$-routing, Alice receives an $n$-bit string $x$ and an unknown qubit, while Bob receives a separate $n$-bit string $y$. A Boolean function $f$ determines the recipient: they must route the qubit to Alice if $f(x,y)=0$ and to Bob if $f(x,y)=1$. They exchange one simultaneous message each, while message lengths, local systems, and local operations remain unrestricted. Only the state ${\rho }_{LR}$ shared before the inputs arrive contributes to the resource cost. We define this cost by $E_{\dim }({\rho }_{LR})={\log }_2\min \{\mathrm{rank}{\rho }_L,\mathrm{rank}{\rho }_R\}$, where ${\rho }_L$ and ${\rho }_R$ are Alice's and Bob's local states. Thus $E_{\dim }$ is the logarithm of the smaller local rank, and the shared state may be arbitrary and mixed. We consider the family of Boolean functions $f_n(x,y)={⨁}_{i=1}^n{x}_i{y}_i$, given by the inner product modulo $2$. We prove that every protocol for $f_n$ allowing the designated recipient to recover the qubit with diamond-norm error at most $0.09$ for every $(x,y)$ satisfies $d{\log }_2(2d)=\Omega (n)$, where $d=\min \{\mathrm{rank}{\rho }_L,\mathrm{rank}{\rho }_R\}$. Consequently, $d=\Omega (n/\log n)$ and $E_{\dim }({\rho }_{LR})\ge {\log }_{2}n-{\log }_2{\log }_{2}n-O(1)$. Earlier growing lower bounds use a different measure of the shared resource and require perfect recovery on either all inputs with $f(x,y)=0$ or all inputs with $f(x,y)=1$. A lower bound polynomial in $n$ on $E_{\dim }$ remains open.

14 pages, 1 figure. Explanations revised. Main result unchanged