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 $ρ_{LR}$ shared before the inputs arrive contributes to the resource cost. We define this cost by $E_{\dim}(ρ_{LR})=\log_2\min\{\operatorname{rank}ρ_L,\operatorname{rank}ρ_R\}$, where $ρ_L$ and $ρ_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)=\bigoplus_{i=1}^n x_iy_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)=Ω(n)$, where $d=\min\{\operatorname{rank}ρ_L,\operatorname{rank}ρ_R\}$. Consequently, $d=Ω(n/\log n)$ and $E_{\dim}(ρ_{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.