Papers With

← All papers
First page of Robust logarithmic entanglement lower bound for $f$-routing

Robust logarithmic entanglement lower bound for $f$-routing

Kevin Bogner

quant-ph Aug 6, 2026 · v3
formalization quantum
Read PDF arXiv abstract Code
TL;DR
An accompanying Lean artifact formalizes every labeled theorem, lemma, proposition, and corollary of the f-routing entanglement lower bound.
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.
Problem

In one-round f-routing, the selected party must recover an unknown qubit after one simultaneous exchange of messages. The question is how much pre-shared entanglement this requires. Earlier growing lower bounds needed perfect recovery on at least one routing case, and a robust polynomial bound is an open problem.

Approach

An information-disturbance tradeoff gives a constant routing gap in an SLD-type statistic between the two routing cases at error 0.09. Product-state mixing, preconditioning and moment approximation then replace the statistic matrix with one whose approximate rank depends only on the Schmidt rank and n. The inner-product function has high approximate rank, which forces a large shared resource. Mixed states are handled through good components of pure-state ensembles. All labeled results are formalized in Lean.

Results

For inner product mod 2 and worst-case error at most 0.09, the entanglement of formation satisfies E_F ≥ (log2 n − log2 log2 n − C)/13750. A companion result shows the local support rank d satisfies d log2(2d) = Ω(n). A polynomial lower bound remains open.