Computer Science editorial
Open AccessOA2026
New Lower Bounds for CDS and f-Routing
A digest of Hasegawa & Mataraarachchi (2026) on entanglement cost, robust CDS, and one-sided-perfect f-routing
Atsuya Hasegawa; Ranitha Mataraarachchiยท 2026ยท DOI 10.48550/arXiv.2609.24291
The core problem
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and related areas. A central special case is -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, the authors establish two related lower bounds. First, they study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and -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. Second, they consider one-sided-perfect -routing, in which the protocol is exact on one input class and has constant error on the other.
Innovation
The paper presents two main results. First, for robust CDS, the shared-randomness cost is lower bounded by the logarithm of deterministic SMP communication complexity. Formally, for any robust CDS protocol for a function , the shared randomness cost satisfies:
where
is the deterministic SMP communication complexity of . This bound holds even when communication and private randomness are unrestricted. The bound is tight for the equality function. Second, for one-sided-perfect -routing, the entanglement cost is lower bounded by the sign rank of the associated matrix. In particular, for the inner-product function, this yields a linear lower bound on the entanglement cost in both one-sided-perfect settings, matching the known upper bound. Specifically, for the inner-product function on -bit strings, the entanglement cost is ebits, which matches the known upper bound of ebits.
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and related areas. A central special case is -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, the authors establish two related lower bounds. First, they study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and -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. Second, they consider one-sided-perfect -routing, in which the protocol is exact on one input class and has constant error on the other.
The authors employ two distinct techniques. For robust CDS, they show that the shared-randomness cost is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. This lower bound is tight for the equality function. For one-sided-perfect -routing, they exploit the positivity of the low-rank matrix arising in the method of Asadi, Culf, and May (ITCS 2025) to derive a general lower bound on the entanglement cost in terms of sign rank. The sign rank of a matrix is defined as:
Why it matters
The results provide significant progress on the open problem of proving lower bounds for fully robust -routing. The connection between robust CDS and -routing suggests that understanding the randomness complexity of robust CDS is a natural step toward lower bounds for the fully robust routing problem. The tightness of the CDS bound for the equality function indicates that the bound is optimal in some cases. The sign rank lower bound for one-sided-perfect -routing, particularly the linear bound for inner-product, matches the known upper bound, thus resolving the entanglement cost for this function in the one-sided-perfect setting. The techniques introduced, such as exploiting the positivity of the low-rank matrix, may be applicable to other problems in NLQC. The authors' work also highlights the role of sign rank as a complexity measure in quantum information. Future work could extend these lower bounds to the fully robust setting or to other functions. The following diagram illustrates the relationship between the concepts:
Who should read this
CS practitioners and researchers
Opening member contentโฆ