Robust logarithmic entanglement lower bound for $f$-routing

Abstract

In one-round $f$-routing, Alice receives an $n$-bit string $x$ and an unknown qubit, and Bob receives an $n$-bit string $y$. They exchange one simultaneous message each and cannot communicate afterwards; the party selected by a Boolean function $f(x,y)$ must then recover the qubit. The parties may share unlimited entanglement in advance. When $f$ is the inner product modulo $2$, we prove that every protocol with worst-case error at most $0.09$ must use a shared state whose entanglement of formation grows at least logarithmically in $n$. The lower bound is robust: it tolerates constant error on both routing cases and covers arbitrary mixed states shared between Alice and Bob. Earlier growing lower bounds in this model, in contrast, require perfect recovery on at least one routing case. The bound is only logarithmic: a polynomial lower bound remains open.

24 pages, 1 figure. v3: adds the robust entanglement-of-formation lower bound as the main theorem; the previous shared-resource-cost bound is now the companion result