New lower bounds for CDS and f-routing
Abstract
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is f-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and f-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect f-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.
Related
- Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- Robust logarithmic entanglement lower bound for f-routing
- Computational Bounds for f-Routing
- Elementary proofs of quantum lower bounds for element distinctness and k-sum
- Separability and lower bounds of concurrence via symmetric measurement correlations
BibTeX
@misc{hasegawa2026lower,
title = {{New lower bounds for CDS and $f$-routing}},
author = {Atsuya Hasegawa and Ranitha Mataraarachchi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.24291},
eprint = {2609.24291},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24291},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - New lower bounds for CDS and f-routing
AU - Atsuya Hasegawa
AU - Ranitha Mataraarachchi
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2609.24291
UR - https://arxiv.org/abs/2609.24291
AB - Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is f-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and f-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect f-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.
ER -