⚛️ quantum physics

New lower bounds for CDS and $f$ -routing

This paper establishes new lower bounds for the shared-randomness cost of robust conditional disclosure of secrets and the entanglement cost of one-sided-perfect $f$ -routing by relating them to deterministic SMP communication complexity and sign rank, respectively, thereby advancing the understanding of entanglement costs in non-local quantum computation.

Original authors: Atsuya Hasegawa, Ranitha Mataraarachchi

Published 2026-09-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Atsuya Hasegawa, Ranitha Mataraarachchi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the strange realm of quantum physics, particles can become linked in a way that defies our everyday experience. When two particles share this connection, known as entanglement, a change to one instantly influences the other, no matter how far apart they are. This phenomenon is the engine behind a futuristic field called non-local quantum computation. Imagine two scientists, Alice and Bob, who are far apart and cannot touch or send signals to each other faster than light. They want to perform a complex calculation together using a shared quantum system. To do this, they must rely on their pre-shared entanglement and a single, simultaneous exchange of information. The central question for physicists is simple yet profound: how much of this mysterious entanglement is actually required to make the calculation work?

This question is not just theoretical. It touches on the security of future communication systems and even our understanding of gravity and space-time. A specific task, called f-routing, serves as a critical test case. In this scenario, Alice holds a secret quantum object and a piece of data, while Bob holds a different piece of data. Depending on how their data matches up, the quantum object must end up with either Alice or Bob. If they are honest and standing next to each other, they can simply check the data and hand the object over. But if they are separated, they must use their entanglement to route the object correctly without ever meeting. The goal is to prove that as the data gets larger, the amount of entanglement needed grows so large that it becomes impossible for separated parties to simulate the process.

A team of researchers at Nagoya University in Japan has taken a significant step toward answering this by looking at a simpler, classical version of the problem first. They studied a game called conditional disclosure of secrets. In this version, Alice and Bob still have data, but instead of a quantum object, they are trying to reveal a simple secret bit only when their data matches a certain rule. They share a random number to help coordinate their messages, but they cannot talk to each other. The researchers wanted to know: how much of this shared randomness is needed to ensure the secret is revealed only when it should be, and remains hidden otherwise?

The team discovered a firm mathematical limit on this randomness. They proved that the amount of shared randomness required is directly tied to the complexity of the data they are processing. Specifically, the more complex the data patterns are, the more randomness is needed. They showed that for certain types of data, the amount of randomness must grow at least as fast as the logarithm of the data size. This finding is crucial because it establishes a baseline. If you cannot do the simple classical version without a certain amount of shared resource, you certainly cannot do the complex quantum version without a comparable amount of entanglement. Their proof holds even if Alice and Bob are allowed to use unlimited private randomness and send messages of any length, making the result robust and difficult to bypass.

Turning their attention back to the quantum world, the researchers tackled the f-routing problem under a specific condition: what if the protocol is perfect for one type of data but allows for a tiny, constant error for the other? This "one-sided perfect" scenario is more realistic than demanding perfection for everything, as real-world quantum systems always have some noise. By analyzing the mathematical structure of the matrices that describe these quantum interactions, the team derived a new lower bound on the entanglement cost. They found that the entanglement required is linked to a property called sign rank, which measures how complex the relationship between the inputs is.

For a specific and important function known as the inner product, which involves combining two strings of bits, their analysis revealed a linear lower bound for this specific one-sided case. This means that as the input size increases, the amount of entanglement needed grows in direct proportion for these protocols. This result is a major improvement over previous estimates, which had only suggested a constant or much weaker growth for this specific function. It matches the best-known upper limits for this specific scenario, suggesting that the researchers have likely found the true cost for this class of restricted quantum problems. However, for the more general case where errors are allowed on both sides of the input, the exact growth rate remains an open question.

The implications of these findings extend beyond just the numbers. By establishing that the cost of these quantum tasks is fundamentally tied to the complexity of the underlying data patterns, the researchers provide a new tool for evaluating the security of quantum position verification. This is a method used to prove that a person is physically located at a specific spot. If a party tries to simulate their location from afar, they would need to share an enormous amount of entanglement, potentially more than is physically feasible. The researchers' work suggests that for certain complex tasks, the cost of simulation is prohibitively high, reinforcing the security of these protocols.

While the paper does not claim to have solved every aspect of quantum communication, it provides a clear, rigorous foundation for understanding the resources required. The authors explicitly note that for the most general case, where errors are allowed on both sides of the input, the exact growth rate remains an open question. However, their new bounds for the one-sided perfect case and the robust classical case represent a substantial advance. They have moved the field from vague possibilities to concrete, provable limits, showing that the universe demands a specific, non-negotiable price for non-local quantum computation.

Technical Summary: New Lower Bounds for CDS and f-routing

Problem Statement
This paper addresses the fundamental limits of resource costs in two related quantum and classical information tasks: Non-Local Quantum Computation (NLQC), specifically the f-routing problem, and Conditional Disclosure of Secrets (CDS).

f-routing: In this task, Alice and Bob receive classical inputs $x$ and $y$ and a shared entangled state. Alice holds an unknown quantum system $Q$ . They must perform local operations and a single round of simultaneous quantum communication such that if $f(x,y)=0$ , Alice recovers $Q$ , and if $f(x,y)=1$ , Bob recovers $Q$ . The primary goal is to establish lower bounds on the entanglement cost (Schmidt rank of the shared state) required for this task. While upper bounds exist (e.g., $2^{O(\sqrt{n \log n})}$ ), proving lower bounds for robust protocols (allowing constant error on both input classes) has been a major open problem. Previous results by Asadi, Culf, and May (ACM25) provided growing lower bounds only for one-sided perfect protocols (perfect recovery on one input class, constant error on the other).
CDS: A classical primitive where Alice holds $(x, s)$ and Bob holds $y$ , sharing randomness $R$ . They send messages to a referee who knows $(x,y)$ . If $f(x,y)=1$ , the referee recovers $s$ ; if $f(x,y)=0$ , the messages reveal no information about $s$ . The paper investigates the shared-randomness cost in the robust setting (allowing constant error in both correctness and privacy), a setting where previous lower bounds were limited or non-existent under unrestricted communication and private randomness.

Methodology
The authors employ two distinct technical approaches to derive their lower bounds:

Robust CDS via Transcript Distributions and Covering Numbers:
- The authors analyze the total variation distance $D(x,y)$ between the transcript distributions corresponding to secrets $s=0$ and $s=1$ .
- Correctness and privacy constraints force $D(x,y)$ to be large when $f(x,y)=1$ and small when $f(x,y)=0$ .
- They represent the row and column distance functions of $f$ as expectations of functions belonging to a specific class $\mathcal{F}_q$ , where $q$ is the support size of the shared randomness. These functions are defined on the probability simplex $\Delta_q$ .
- Using a covering number argument (constructing an $\eta$ -net for $\mathcal{F}_q$ ), they bound the number of distinct functions that can be generated by a shared randomness of size $q$ .
- By relating the separation of these distance functions to the number of distinct rows and columns in the communication matrix of $f$ , they link the shared randomness cost to the deterministic Simultaneous Message Passing (SMP) communication complexity, denoted $D_{\parallel}(f)$ .
One-Sided-Perfect f-routing via Sign Rank:
- The authors revisit the rank method introduced by Asadi, Culf, and May (ACM25), which associates a non-negative matrix $G$ with the protocol, where $G_{x,y}=0$ for $f(x,y)=0$ and $G_{x,y}>0$ for $f(x,y)=1$ , with $\text{rank}(G) \le d_E^4$ ( $d_E$ being the Schmidt rank).
- They exploit the positivity of $G$ to construct a matrix $A = G - \tau J$ (where $J$ is the all-ones matrix and $\tau$ is a small constant). This matrix $A$ has the same sign pattern as the sign matrix $S_f$ of the function $f$ .
- Using the subadditivity of matrix rank, they show that $\text{signrank}(S_f) \le \text{rank}(A) \le \text{rank}(G) + 1 \le d_E^4 + 1$ .
- This establishes a direct lower bound on the entanglement cost in terms of the sign rank of $f$ . They further relate this to the unbounded-error communication complexity ( $UPP_{cc}$ ) via known results.

Key Contributions and Results

Lower Bound for Robust CDS (Theorem 1.1):
- The paper proves that for any $\epsilon$ -correct and $\delta$ -private CDS protocol (with $2\epsilon + \delta < 1$ ), the shared-randomness cost $\log_2 q$ satisfies:
  $\log_2 q = \Omega(\log_2 D_{\parallel}(f))$
- This bound holds even when private randomness and message lengths are unrestricted.
- Tightness: For the equality function ( $n$ -bit), $D_{\parallel}(f) = \Theta(n)$ , yielding an $\Omega(\log n)$ lower bound. The authors provide a matching upper bound in Appendix A, showing this result is tight up to constant factors for equality.
Sign-Rank Lower Bounds for One-Sided-Perfect f-routing (Theorem 1.2):
- For protocols that are exact on one input class (0-inputs or 1-inputs) and have constant error on the other, the entanglement cost is lower bounded by:
  $\text{Cost} \ge \frac{1}{4} \log_2(\max\{1, \text{signrank}(S_f) - 1\})$
- This implies a bound in terms of unbounded-error communication complexity: $\text{Cost} \ge \frac{1}{4} UPP_{cc}(f) - O(1)$ .
- Application to Inner Product: For the inner-product function $IP_n$ , the sign rank is known to be exponential ( $2^{n/2}$ ). This yields a linear lower bound:
  $\text{Cost} \ge \frac{n}{8} - \frac{1}{4}$
- This matches the known $O(n)$ upper bound derived from the garden-hose construction, resolving the complexity for $IP_n$ in the one-sided-perfect setting. The authors note that their coefficient ( $1/4$ ) improves upon the $1/8$ coefficient derived from combining previous nondeterministic rank bounds with sign-rank relations.
Corollaries for Related Tasks:
- Using reductions from f-routing to f-BB84 and CDS, the authors derive corresponding lower bounds for these tasks in terms of sign rank and $UPP_{cc}$ . Specifically, they establish $\Omega(\log(\text{signrank}(S_f)))$ lower bounds for CDS with perfect privacy or perfect correctness.

Significance and Claims
The paper claims to make the following contributions to the field:

Resolution of an Open Problem for CDS: It provides the first lower bound on shared randomness for robust CDS that allows constant error in both correctness and privacy, with unrestricted communication and private randomness. The result is tight for the equality function.
Improved Bounds for f-routing: While previous work (ACM25) could not derive a growing lower bound for the inner-product function in the one-sided-perfect setting (yielding only a constant bound via nondeterministic rank), this paper's sign-rank approach successfully yields a linear lower bound ( $\Omega(n)$ ), matching the known upper bound.
Methodological Distinction: The authors emphasize that their sign-rank formulation does not replace the nondeterministic rank argument of ACM25 but provides a complementary and sometimes stronger perspective (e.g., for $IP_n$ ). Conversely, their robust CDS bound (based on deterministic SMP complexity) applies to functions like equality where sign-rank is constant, demonstrating that the two methods capture different aspects of complexity.
Independence: The authors acknowledge independent work by Bogner (2026) which proved a logarithmic lower bound for f-routing with inner product in the two-sided error regime. The authors clarify that their robust CDS result is distinct and not subsumed by Bogner's, as it applies to functions with constant sign rank but linear deterministic SMP complexity.

The paper concludes by noting that obtaining polynomial lower bounds for f-routing in the fully robust (two-sided error) setting remains an open problem, and that developing stronger techniques for CDS shared-randomness lower bounds may provide insights for the quantum setting.

Technical Summary: New Lower Bounds for CDS and f-routing

More like this