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.

Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
Yen-Huan Li, Wei-Fu Tseng
arXiv15 Oct 2026PreprintarXiv licenceFull textStatistics Quantum physics & quantum informationarXiv
The shadow radius lower bound is more robust than the photon sphere radius lower bound in n-dimensional Einstein gravity
Jiaqi Fu, Yong Song
arXiv8 Oct 2026PreprintCC BY 4.0Full textGravitation & general relativityarXiv
Efficient routing and spectrum allocation in arbitrary flex-grid entanglement networks
Zachary Goisman, Matthew L. Stevens, Maxwell Goisman +7
Optics Express28 Oct 2026Peer-reviewedPublisher termsFull textOptics & photonicsCrossref
Efficient routing and spectrum allocation in arbitrary flex-grid entanglement networks
Zachary Goisman, Matthew L. Stevens, Maxwell Goisman +7
arXiv16 Jul 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
A Neutral Atom-Based Hybrid Classical-Quantum Approach for the Entanglement Routing Problem
M. Yassine Naghmouchi, Quentin Ma, Agathe Blaise +2
arXiv29 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{bogner2026robust,
  title = {{Robust logarithmic entanglement lower bound for $f$-routing}},
  author = {Kevin Bogner},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.05775},
  eprint = {2608.05775},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.05775},
}

RIS

TY  - UNPB
TI  - Robust logarithmic entanglement lower bound for f-routing
AU  - Kevin Bogner
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2608.05775
UR  - https://arxiv.org/abs/2608.05775
AB  - 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.
ER  -

Abstract

Related

Cite