New lower bounds for CDS and f -routing Atsuya Hasegawa∗1 and Ranitha Mataraarachchi†1
arXiv:2609.24291v1 [quant-ph] 21 Sep 2026
1
Graduate School of Mathematics, Nagoya University, Japan
Abstract 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 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 sharedrandomness 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 arising in the method of Asadi, Culf, and May (ITCS 2025), we derive a general 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.
∗ †
[email protected] [email protected]
1
Contents 1 Introduction 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Proof overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Independent work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 5 6 7 8 8
2 Preliminaries 2.1 Basic notation and tools from probability theory . . . . . . . . . . . . . . . . . . . . 2.2 Deterministic one-way and SMP communication complexity . . . . . . . . . . . . . . 2.3 Conditional disclosure of secrets (CDS) . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Rank measures and unbounded-error communication complexity . . . . . . . . . . . 2.5 f -routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 The inner-product function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 9 10 11 11 12
3 A lower bound for shared randomness in robust CDS 3.1 Distance between transcript distributions . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Low-dimensional representations of row and column distance functions . . . . . . . . 3.3 Covering the function class Fq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Lower bound for shared randomness . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 13 14 17 20
4 Lower bounds for f -routing
21
5 Concluding remarks
24
A A matching upper bound for equality
27
B Direct connection between sign-rank and nondeterministic rank
28
2
A
A
B
WL
WR
VL
VR
A
B
B
T
A
B
(a)
(b)
Figure 1: Local and non-local computations. a) A channel TAB→AB is implemented by directly interacting the input systems. b) A non-local quantum computation. The goal is for this circuit’s action on the AB systems to approximate the channel TAB→AB . Figure reproduced from [ACM25].
1
Introduction
1.1
Background
NLQC and f -routing. A bipartite quantum operation can be implemented directly by bringing the two input systems together and allowing them to interact. In non-local quantum computation (NLQC), however, the systems remain spatially separated and cannot interact directly. Instead, the parties implement the desired operation using local operations, a pre-shared entangled state, and a single simultaneous round of quantum communication. See Figure 1 for an illustration. A central question in NLQC is, therefore, how much entanglement is required to implement a given operation in this form. NLQC appears in a wide range of settings, including quantum position verification (QPV) [KMS11, BCF+ 14, BK11], the AdS/CFT correspondence [May19, MPS20, May22], Hamiltonian simulation [ACH+ 24], and information-theoretic cryptography [ABM+ 24, AKL+ 25], computational and communication complexity [BFSS13, Spe16, GMPY26]. See also [May26] for a recent survey on NLQC. A particularly interesting family of NLQC tasks is f -routing. Alice receives a classical input x and an unknown quantum system Q, while Bob receives a classical input y. For a fixed Boolean function f : X × Y → {0, 1}, they must ensure that Alice can recover Q when f (x, y) = 0, while Bob can recover Q when f (x, y) = 1. The motivation for this task is rooted in quantum position verification (QPV) [KMS11, BCF+ 14, BK11]. An honest prover (who acts locally) can evaluate f (x, y) classically and then redirect the quantum system Q according to the result. Thus, when Q has fixed dimension, the honest prover requires only O(1) quantum operations. By contrast, spatially separated cheating agents must implement an f -routing protocol. One main goal in f routing is to prove that the entanglement required by such agents grows with the input size. This is precisely the type of separation desired in QPV: the honest prover performs an almost entirely classical computation, whereas successful cheating agents could require a large shared quantum resource [BCS22, ACM25]. 3
s if and only if f (x, y) = 1
A
x, s
B
R
y
Figure 2: The CDS task. Alice (left) receives (x, s) and Bob (right) receives y. Using a shared random variable R, they send messages a and b to the referee (top), who recovers s if and only if f (x, y) = 1. √
Every f -routing task on two n-bit inputs can be completed with entanglement cost 2O( n log n) [ABM+ 24].1 In contrast, entanglement lower bounds for f -routing remain poorly understood. Asadi, Culf, and May obtained growing lower bounds on the Schmidt rank of the pre-shared entangled state [ACM25]. However, their bounds apply only to one-sided perfect protocols, where recovery must be perfect either on every 0-input or on every 1-input. Physical implementations of f -routing protocols inevitably involve noise and imperfect operations, and thus one generally expects a small probability of error on both input classes. A lower bound that requires perfect recovery on one class therefore does not directly apply to such implementations. Obtaining entanglement lower bounds for robust f -routing, where constant error is allowed on both input classes, has been a major open problem.2 Conditional disclosure of secrets (CDS). In this paper, we also consider the classical primitive known as conditional disclosure of secrets (CDS) [GIKM00]. In a CDS protocol, Alice receives an input x and a secret s, Bob receives an input y, and they share a random variable R. Without communicating with one another, they send messages A and B to a referee who knows (x, y). If f (x, y) = 1, the referee should recover s; if f (x, y) = 0, the pair of messages should reveal essentially no information about s. See Figure 2 for an illustration. The shared randomness allows Alice and Bob to coordinate their messages; therefore, the secret is recoverable on the 1-inputs while remaining hidden on the 0-inputs. An important question is therefore how much shared randomness is required to satisfy both conditions. CDS is connected to NLQC through conditional disclosure of quantum secrets (CDQS), a quantum analogue of CDS in which the secret and messages may be quantum and shared randomness is replaced by entanglement [ABM+ 24, AKL+ 25]. A classical CDS protocol can be converted into a CDQS protocol, which can in turn be converted into an f -routing protocol with controlled overhead in the resource cost and error parameters [ABM+ 24], and the entanglement cost upper bound 1
A simpler argument known as the garden-hose construction yields a 2O(n) upper bound [BFSS13]. In independent work, Bogner [Bog26] recently showed an entanglement lower bound for f -routing with the inner product function on the two-sided error setting. See also Section 1.5. 2
4
√
2O( n log n) [ABM+ 24] was shown from the randomness upper bound for CDS in [LVW17]. This conversion direction allows entanglement lower bounds for f -routing to yield randomness lower bounds for CDS. The converse does not follow from these reductions; therefore, a randomness lower bound for CDS does not by itself imply an entanglement lower bound for f -routing. Nevertheless, robust CDS retains the same function-dependent resource question in a simpler classical setting, making it a natural place to develop ideas toward robust f -routing lower bounds. Applebaum and Vasudevan established lower bounds on shared randomness for perfectly correct CDS protocols [AV21]. However, obtaining shared-randomness lower bounds that tolerate constant error in both correctness and privacy remained open in the model with unrestricted communication and unlimited free private randomness.
1.2
Our results
We prove two related lower bounds for the goal obtaining the error-robust entanglement lower bound for f -routing. Robust lower bounds for CDS. Consider an ϵ-correct and δ-private CDS protocol for f whose shared random variable R has support size q. We place no restrictions on the parties’ private randomness or on the lengths of the messages sent to the referee. Our resource measure is the shared-randomness cost log2 q.3 Let D∥ (f ) denote the deterministic communication complexity of f in the simultaneously message passing (SMP) model. Our theorem for robust CDS gives the following bound. Theorem 1.1 (Informal version of Theorem 3.6). Let f : X × Y → {0, 1}. Suppose that f admits an ϵ-correct and δ-private CDS protocol where ϵ, δ > 0 are fixed constants satisfying 2ϵ + δ < 1. Then, log2 q = Ω log2 D∥ (f ) . In particular, the deterministic SMP communication complexity of n-bit equality is Θ(n). Hence Theorem 1.1 gives an Ω(log n) shared-randomness lower bound for the equality function in the robust setting, which is tight up to constant factors. In Appendix A, we give a perfectly correct δ-private protocol for equality using O(log n) shared random bits for a constant δ > 0. Sign-rank lower bounds for one-sided-perfect f -routing. Our second result revisits the rank lower-bound method for one-sided f -routing introduced by Asadi, Culf, and May [ACM25]. A one-sided perfect f -routing protocol uses a shared pure state of Schmidt rank dE , is exact on the 0-inputs, and has error at most 0.05 on the 1-inputs. The symmetric setting, with the roles of the two input classes reversed, is defined analogously. We write FR0 (f ), FR1 (f ), and pFR(f ) for the minimum value of log2 dE over one-sided and two-sided perfect protocols. Let Sf be the sign matrix defined by Sf (x, y) := 2f (x, y) − 1. We obtain lower bounds for one-sided f -routing in terms of the sign rank of Sf . 3
log2 q corresponds to the number of shared random bits.
5
(1)
Theorem 1.2 (Informal version of Theorem 4.2). FR0 (f ), FR1 (f ), pFR(f ) ≥
1 log2 (max{1, signrank(Sf ) − 1}) . 4
As a consequence of the relationship between the sign rank and the unbounded-error communication complexity [PS86], we also obtain 1 FR0 (f ), FR1 (f ), pFR(f ) ≥ UPPcc (f ) − O(1), 4 where UPPcc (f ) is the unbounded-error communication complexity of f . For the modulo-2 inner-product function IPn , the sign-rank lower bound in [For02] yields FR0 (IPn ), FR1 (IPn ), pFR(IPn ) ≥
n 1 − . 8 4
The lower bound in Asadi, Culf and May is characterized by the nondeterministic rank of f , and their analysis yielded only a constant lower bound for this function [ACM25, Figure 3]. Our lower bounds match the O(n) upper bound obtained from the garden-hose construction, which gives a perfectly correct routing protocol for IPn [BFSS13]. The two lower bounds behave differently on concrete functions. Their argument, for example, gives a linear lower bound for equality, whereas equality has constant sign rank. Thus, our sign-rank formulation does not replace the original argument in [ACM25], but provides a different way to derive lower bounds. Finally, combining Theorem 1.2 with known reductions [ABM+ 24, BHM+ 26] yields corresponding lower bounds in terms of sign rank and unbounded-error communication complexity for onesided-perfect f -BB84 and for CDS with perfect privacy or perfect correctness (Corollaries 4.4 and 4.5).
1.3
Proof overview
Robust CDS lower bound. The proof relates the number of distinct rows of f to the support size of the shared random variable R. For each input pair (x, y), let Tsx,y be the transcript distribution when the secret is s, and define D(x, y) := TV T0x,y , T1x,y . Privacy and correctness give f (x, y) = 0 =⇒ D(x, y) ≤ δ,
f (x, y) = 1 =⇒ D(x, y) ≥ 1 − 2ε.
Thus, if x and x′ define distinct rows of f , then for some y, |D(x, y) − D(x′ , y)| ≥ γ,
γ := 1 − 2ε − δ.
We next use the assumption that the shared random variable R has support size q. Conditioning on Bob’s message produces a posterior distribution p ∈ ∆q on R. For each Alice input x, we define a function ϕx (p) that measures how distinguishable Alice’s messages are for the two possible secrets when the posterior on R is p. This gives the representation D(x, y) = Ep∼µy ϕx (p) , 6
where µy is the distribution of the posterior on R induced by Bob’s encoder on input y. Our main technical lemma constructs a finite family H such that every ϕx is η-close to some hx ∈ H in the ∞-norm, with q4 2 cq log2 |H| ≤ c 2 log2 , η η for some universal constant c. Importantly, this bound is independent of the parties’ private randomness and message lengths. If two inputs x and x′ have the same approximation hx = hx′ , then |D(x, y) − D(x′ , y)| ≤ 2η
for every y.
Taking η = γ/4, this is impossible when x and x′ define distinct rows of f . Hence the number of distinct rows of f is at most |H|. Applying the analogous argument to the columns gives the same bound on the number of distinct columns. Together, these bounds give the desired upper bound on the deterministic SMP communication complexity and complete the proof. Sign-rank lower bound for f -routing. Consider first a protocol that is exact on the 0-inputs. The rank method of Asadi, Culf, and May [ACM25] associates with the protocol a real matrix G satisfying Gx,y = 0 when f (x, y) = 0, Gx,y > 0 when f (x, y) = 1, and rank(G) ≤ d4E . For nonconstant f , choose τ > 0 smaller than every positive entry of G, let J be the all-ones matrix, and set A := G − τ J. Then A is negative on the 0-inputs and positive on the 1-inputs. Thus A has sign pattern Sf , where Sf was defined as in (1). Consequently, signrank(Sf ) ≤ rank(A) ≤ rank(G) + 1 ≤ d4E + 1. The case in which the protocol is exact on the 1-inputs follows by applying the same argument to 1 − f . Taking logarithms gives the claimed routing-cost bound. In Appendix B, we derive the same asymptotic lower bounds by combining the nondeterministicrank lower bound of Asadi, Culf, and May [ACM25] with a general relation between nondeterministic rank and sign rank. This approach yields a coefficient of 1/8 in the sign-rank bound. By directly exploiting the nonnegativity of G, our argument improves this coefficient to 1/4, strengthening the lower bound for inner product from n/16 − 1/8 to n/8 − 1/4. We believe that such constantfactor improvements are important in QPV, where the concrete number of shared entangled qubits required by cheating strategies matters.
1.4
Related work
Conditional disclosure of secrets. Previous work established lower bounds on the communication cost of robust CDS using one-way communication complexity and interactive-proof measures [GKW15, AARV21, AV21]. Our theorem instead lower-bounds the shared randomness in the robust setting. Lower bounds on shared randomness were also known under one-sided-perfect conditions [AV21, KY21, ACM25]. More recently, Girish, May, Orshansky, and Waddell [GMOW26] 7
proved robust lower bounds for quantum CDS in terms of deterministic one-way communication complexity and studied separations between classical and quantum CDS. Their one-way lower bound concerns the combined communication and entanglement cost of quantum CDS, rather than directly bounding the shared-randomness cost of a classical CDS protocol. In contrast, our result allows constant error in both correctness and privacy, arbitrary private randomness, and messages of unrestricted length. To our knowledge, our result is the first lower bound on shared randomness in a model that simultaneously permits all three features. f -routing. Robust lower bounds were previously obtained for the size of a purified adversarial system and for the number of quantum gates [BCS22, ACCM25], but these measures do not isolate the initially shared entanglement. Asadi, Culf, and May obtained the first growing lower bounds on the Schmidt rank of the shared state, under the assumption of perfect recovery on one input class [ACM25].
1.5
Independent work
In recent independent work, Bogner [Bog26] proved a logarithmic shared-entanglement lower bound for f -routing with the inner product function in the two-sided bounded-error regime. The result implies CDS(IP) = Ω(log n) and other functions that have high sign-rank. Our robust CDS lower bound is characterized by the logarithm of the deterministic SMP communication complexity. Bogner’s result does not subsume our result. In particular, our theorem applies to the equality function, whose sign rank is constant but whose deterministic SMP communication complexity is linear. We additionally showed FR0 (IP) = FR1 (IP) = Ω(n) where the one-sided perfect assumption is needed.
1.6
Organization
In Section 2, we introduce the notation and definitions used throughout the paper. In Section 3, we prove our shared-randomness lower bound for robust CDS. In Section 4, we establish our sign-rank lower bounds for one-sided-perfect f -routing and derive their consequences for f -BB84 and CDS. In Section 5, we conclude our work discussing open problems and future directions.
2
Preliminaries
In this section, we introduce some notation and preliminary results useful for our analysis. Throughout, all sets are finite, and all logarithms are base-2. For a positive integer q, we write [q] := {1, . . . , q}. Let ∆(Ω) denote the set of probability distributions on a finite set Ω.
2.1
Basic notation and tools from probability theory
For a vector z ∈ Rq and a function g : Ω → R, define ∥z∥1 :=
q X
|zr |,
∥z∥∞ := max |zr |, r∈[q]
r=1
8
and ∥g∥1 :=
X
|g(ω)|,
∥g∥∞ := max |g(ω)|. ω∈Ω
ω∈Ω
If the domain of g is not finite, we use ∥g∥∞ := supω |g(ω)|. For P, Q ∈ ∆(Ω), their total variation distance is 1 1X TV(P, Q) := ∥P − Q∥1 = |P (ω) − Q(ω)|. 2 2 ω∈Ω
We use the following operational interpretation of total variation distance. Fact 2.1 (Binary hypothesis testing). Let P, Q ∈ ∆(Ω). Suppose that one of P and Q is chosen uniformly at random and a sample is drawn from the chosen distribution. The optimal success and error probabilities for identifying the chosen distribution are ∗ Psucc =
1 + TV(P, Q) , 2
∗ Perr =
1 − TV(P, Q) . 2
Proof. For each observation ω, the optimal rule chooses the distribution assigning the larger probability to ω. Thus 1X ∗ Psucc = max{P (ω), Q(ω)}. 2 ω∈Ω
The claim follows from max{a, b} = (a + b + |a − b|)/2. We will also use the following concentration bound. Fact 2.2 (Hoeffding’s inequality). Let X1 , . . . , Xm be independent random variables taking values in a common interval [a, b], and let m 1 X X := Xj . m j=1
Then, for every t > 0, 2mt2 . Pr X − E[X] ≥ t ≤ 2 exp − (b − a)2
2.2
Deterministic one-way and SMP communication complexity
Let f : X × Y → {0, 1} be a total function. Define its numbers of distinct rows and columns by Nrow (f ) := {f (x, ·) : x ∈ X} ,
Ncol (f ) := {f (·, y) : y ∈ Y } .
We denote by D→ (f ) and D← (f ) the deterministic one-way communication complexities in the two directions. We also let D∥ (f ) denote the deterministic SMP communication complexity, measured as the total number of bits sent by Alice and Bob. We will use the following standard relations. Fact 2.3. For every total Boolean function f , D→ (f ) = ⌈log2 Nrow (f )⌉ ,
D← (f ) = ⌈log2 Ncol (f )⌉ ,
and D∥ (f ) = D→ (f ) + D← (f ). 9
Proof. In a deterministic one-way protocol from Alice to Bob, inputs defining distinct rows must produce distinct messages. Conversely, Alice can send the index of the row defined by her input. This proves the first equality, and the column equality follows symmetrically. In a deterministic SMP communication protocol, Alice’s message must distinguish all distinct rows and Bob’s message must distinguish all distinct columns. The resulting lower bound is achieved by having them send their row and column indices, respectively.
2.3
Conditional disclosure of secrets (CDS)
We use a one-sided CDS model in which only Alice receives the secret. The referee knows the input pair (x, y). Definition 2.4. Let f : X ×Y → {0, 1}. A one-bit-secret CDS protocol consists of a shared random variable R with supp(R) = [q], together with independent private randomness for Alice and Bob. Alice receives (x, s) ∈ X × S where S = {0, 1}, Bob receives y ∈ Y , and both parties receive the shared value r ∈ [q]. They send messages in finite alphabets MA and MB , respectively. After averaging over the private randomness, Alice’s and Bob’s encoders are described by conditional output distributions x Ps,r ∈ ∆(MA ),
Qyr ∈ ∆(MB ),
where x Ps,r (a) = Pr[A = a | X = x, S = s, R = r],
Qyr (b) = Pr[B = b | Y = y, R = r].
Writing πr := Pr[R = r], the transcript distribution for secret s and inputs (x, y) is Tsx,y (a, b) :=
q X
x πr Ps,r (a)Qyr (b).
(2)
r=1
The protocol is ε-correct if, for every (x, y) such that f (x, y) = 1, there exists a decoder Decx,y : MA × MB → {0, 1} such that, for each s ∈ {0, 1}, Pr x,y Decx,y (A, B) = s ≥ 1 − ε.
(A,B)∼Ts
It is δ-private if, for every (x, y) such that f (x, y) = 0, there exists a distribution Simx,y ∈ ∆(MA × MB ), independent of s, such that Tsx,y − Simx,y 1 ≤ δ for both s ∈ {0, 1}. We define the shared-randomness cost as log2 | supp(R)| = log2 q.
10
2.4
Rank measures and unbounded-error communication complexity
Sign rank.
We use the standard subadditivity of matrix rank, rank(A + B) ≤ rank(A) + rank(B).
(3)
For a nonzero real number z, let sign(z) ∈ {−1, +1} denote its sign. For a real matrix with no zero entries, sign(A) is obtained by applying sign entrywise. The sign matrix of a Boolean function f is Sf (x, y) := 2f (x, y) − 1 ∈ {−1, +1}. For a sign matrix S ∈ {±1}X×Y , its sign rank is signrank(S) := min rank(A) : A ∈ RX×Y , sign(Ax,y ) = Sx,y for all x, y .
(4)
Unbounded-error communication. An unbounded-error communication protocol for f is a private-coin randomized protocol that outputs f (x, y) with probability strictly greater than 1/2 on every input. No prescribed constant lower bound on the advantage over 1/2 is required.4 The minimum worst-case communication cost over all such protocols is denoted by UPPcc (f ). Lemma 2.5 (Paturi–Simon [PS86]). There exists a universal constant c ≥ 0 such that, for every Boolean function f , log2 signrank(Sf ) ≥ UPPcc (f ) − c. (5)
2.5
f -routing
For density operators ρ and σ, we define their fidelity by q √ √ F (ρ, σ) := Tr σρ σ. Let Q be initially maximally entangled with a reference qubit Q, such that QQ are in the Bell state 1 |Ψ+ ⟩QQ := √ |0⟩Q |0⟩Q + |1⟩Q |1⟩Q , Ψ+ := |Ψ+ ⟩⟨Ψ+ |QQ . QQ 2 The reference system Q remains untouched throughout the protocol. Consequently, all channels acting on Q are implicitly tensored with the identity channel on Q. We use the following f -routing model of Asadi, Culf, and May [ACM25, Definition 3.1]. Definition 2.6 (f -routing). Let f : X × Y → {0, 1}. Alice and Bob initially share a bipartite pure state |ψ⟩. Alice receives x ∈ X and a qubit Q, while Bob receives y ∈ Y . Alice applies a channel depending only on x to Q and her share of |ψ⟩, and Bob applies a channel depending only on y to his share of |ψ⟩. They then perform one simultaneous round of quantum communication. Let MA and MB be the systems held by Alice and Bob, respectively, after this communication round, and let x,y NQ→M A MB be the induced channel before final decoding. The protocol is (ε0 , ε1 )-correct if the following hold for every (x, y): 4
In contrast, bounded-error communication conventionally requires a success probability of at least 2/3 on every input.
11
x,y • If f (x, y) = 0, there exists a decoding channel DA : MA → Q such that x,y + F DA ◦ TrMB ◦N x,y (Ψ+ ), Ψ ≥ 1 − ε0 . QQ QQ x,y • If f (x, y) = 1, there exists a decoding channel DB : MB → Q such that x,y + F DB ◦ TrMA ◦N x,y (Ψ+ ), Ψ ≥ 1 − ε1 . QQ QQ
Let Eε0 ,ε1 (f ) be the minimum of log2 SR(|ψ⟩) over all (ε0 , ε1 )-correct f -routing protocols using a shared initial pure state |ψ⟩, where SR(|ψ⟩) denotes its Schmidt rank across the Alice-Bob bipartition. Following [ACM25], define FR0 (f ) := E0,0.05 (f ),
2.6
FR1 (f ) := E0.05,0 (f ),
pFR(f ) := E0,0 (f ).
The inner-product function
For x, y ∈ {0, 1}n , define IPn (x, y) :=
n X
xi yi
(mod 2).
i=1
Let Hn be the 2n × 2n Walsh–Hadamard sign matrix Hn (x, y) := (−1)x·y . Under the convention Sf = 2f − 1, we have SIPn = −Hn . Multiplying a matrix by −1 does not change its sign rank. Since Hn is a Hadamard matrix, Forster’s spectral lower bound [For02] gives signrank(SIPn ) = signrank(Hn ) ≥ 2n/2 .
3
(6)
A lower bound for shared randomness in robust CDS
In this section, we show a lower bound for the randomness cost of CDS in the robust setting. In Section 3.1, we define the distance D(x, y) between the transcript distributions corresponding to secrets 0 and 1. Correctness and privacy force this distance to be large when f (x, y) = 1 and small when f (x, y) = 0. It follows that distinct rows or columns of f produce distance functions separated by at least γ = 1 − 2ε − δ. In Section 3.2, we represent these row and column distance functions using a function class Fq . In Section 3.3, we present a net argument for Fq . Intuitively, when q is small, this class cannot produce too many distinguishable distance functions. Finally, in Section 3.4, we compare the size of the net with the separation between distance functions.
12
3.1
Distance between transcript distributions
Fix an ε-correct and δ-private CDS protocol for f : X × Y → {0, 1}, as in Definition 2.4. For each input pair (x, y), the protocol induces two transcript distributions, T0x,y and T1x,y , corresponding to the two possible values of the secret. Define D(x, y) := TV T0x,y , T1x,y . Correctness forces these distributions to be far apart on inputs of f resulting in 1, whereas privacy forces them to be close on inputs resulting in 0. Set γ := 1 − 2ε − δ, and assume that γ > 0. Lemma 3.1. For every (x, y) ∈ X × Y , f (x, y) = 0
=⇒
D(x, y) ≤ δ,
whereas f (x, y) = 1
D(x, y) ≥ 1 − 2ε.
=⇒
Proof. Suppose first that f (x, y) = 0. By δ-privacy, there is a distribution Simx,y , independent of s, such that Tsx,y − Simx,y 1 ≤ δ for both s ∈ {0, 1}. The triangle inequality gives D(x, y) =
1 1 x,y T0 − T1x,y 1 ≤ 2 2
T0x,y − Simx,y 1 + Simx,y − T1x,y 1 ≤ δ.
Now suppose that f (x, y) = 1. Choose s uniformly from {0, 1} and apply the CDS decoder to the resulting transcript. By ε-correctness, its average error probability is at most ε. On the other hand, by Fact 2.1, the minimum possible error in distinguishing T0x,y from T1x,y is 1 − D(x, y) . 2 Consequently, 1 − D(x, y) ≤ ε, 2 which gives D(x, y) ≥ 1 − 2ε.
We next regard the rows and columns of D as functions. For each x ∈ X, define Dx : Y → [0, 1],
Dx (y) := D(x, y),
Dy : X → [0, 1],
Dy (x) := D(x, y).
and, for each y ∈ Y , define
13
Lemma 3.2. If x, x′ ∈ X determine distinct rows of f , then Dx − Dx′ ∞ ≥ γ. Similarly, if y, y ′ ∈ Y determine distinct columns of f , then Dy − Dy
′
∞
≥ γ.
Proof. Suppose that f (x, ·) ̸= f (x′ , ·). Then there is some y0 ∈ Y such that f (x, y0 ) ̸= f (x′ , y0 ). One of these two values is 0, and the other is 1. By Lemma 3.1, one of D(x, y0 ) and D(x′ , y0 ) is at most δ, whereas the other is at least 1 − 2ε. Hence D(x, y0 ) − D(x′ , y0 ) ≥ 1 − 2ε − δ = γ. Taking the maximum over y ∈ Y yields Dx − Dx′ ∞ ≥ γ. The column statement follows identically. If f (·, y) ̸= f (·, y ′ ), choose x0 ∈ X such that f (x0 , y) ̸= f (x0 , y ′ ) and apply the same reasoning. Thus the distinct rows of the communication matrix of f give a pairwise γ-separated family of row-distance functions {Dx : x ∈ X}. Likewise, the distinct columns give a pairwise γ-separated family of column-distance functions {D y : y ∈ Y }. To bound the sizes of these families, we next express both kinds of distance functions using a class of functions Fq .
3.2
Low-dimensional representations of row and column distance functions
We now show that the row and column distance functions defined in Section 3.1 are generated by a class of functions whose domain has dimension q, the support size of the shared random variable. Let B1q := {u ∈ Rq : ∥u∥1 ≤ 1} denote the set of vectors in Rq whose ℓ1 norm is at most 1, and let ( ) q X q ∆q := p ∈ R≥0 : pr = 1 ⊆ B1q r=1
be the set of probability distributions on [q]. Define Fq to be the class of functions g : B1q → [0, 1] of the form g(u) =
1X ⟨u, zi ⟩ , 2
(7)
i∈I
where I is an arbitrary finite index set, the vectors zi ∈ Rq satisfy X |zi (r)| ≤ 2 for every r ∈ [q], i∈I
14
(8)
and ⟨·, ·⟩ denotes the standard inner product on Rq . The bound in (8) ensures that these functions take values in [0, 1]. Indeed, for every u ∈ B1q , q
g(u) ≤
q
q
X X 1X 1 XX |ur | ≤ 1. |ur | |zi (r)| = |ur | |zi (r)| ≤ 2 2 i∈I r=1
r=1
r=1
i∈I
Moreover, every g ∈ Fq is 1-Lipschitz with respect to the ℓ1 -norm. For u, v ∈ B1q , q
|g(u) − g(v)| ≤
X 1X 1X |ur − vr | |zi (r)| ≤ ∥u − v∥1 . ⟨u − v, zi ⟩ ≤ 2 2 r=1
i∈I
(9)
i∈I
Posterior representation for row-distance functions. We next give two representations of the transcript distance D(x, y). The first controls its row-distance functions, while the second controls its column-distance functions. For each x ∈ X and a ∈ MA , define a vector zax ∈ Rq by x x zax (r) := P0,r (a) − P1,r (a).
For every r ∈ [q], X
|zax (r)| ≤
a∈MA
X
x x P0,r (a) + P1,r (a) = 2.
a∈MA
Consequently, the function ϕx (u) :=
1 X ⟨u, zax ⟩ 2 a∈MA
belongs to Fq . For fixed y ∈ Y , define the distribution of Bob’s message on MB , averaged over the shared randomness, by q X νy (b) := πr Qyr (b) = Pr[B = b|Y = y], r=1
for b ∈ MB . Whenever νy (b) > 0, define πr Qyr (b) py,b (r) := = Pr[R = r|Y = y, B = b], νy (b) for r ∈ [q]. The second equality follows from Bayes’ rule, since the shared randomness R is independent of the input Y . The vector py,b belongs to ∆q ; it is the conditional distribution of R given Y = y and B = b. When νy (b) = 0, define py,b arbitrarily in ∆q . Let µy be the distribution of py,b obtained by sampling b according to νy . Lemma 3.3. For every x ∈ X, the function ϕx belongs to Fq , and the row-distance function of x satisfies Dx (y) = Ep∼µy ϕx (p) for every y ∈ Y.
15
Proof. Using the definition of the transcript distributions in (2), we have Dx (y) =
1 X 2
X
|T0x,y (a, b) − T1x,y (a, b)| =
1 X 2
q X X
πr zax (r)Qyr (b) .
a∈MA b∈MB r=1
a∈MA b∈MB
For every b with νy (b) > 0, πr Qyr (b) = νy (b)py,b (r). Messages satisfying νy (b) = 0 contribute nothing to the sum. Therefore, q X X X X 1 Dx (y) = D(x, y) = νy (b) py,b (r)zax (r) = νy (b)ϕx (py,b ) = Ep∼µy ϕx (p) . 2 a∈MA r=1
b∈MB
b∈MB
Thus each x determines a function ϕx ∈ Fq , while each y determines a distribution µy . The entire row-distance function Dx is obtained by evaluating ϕx against these distributions. Dual representation for column-distance functions. The preceding representation is adapted to rows. To control columns, we consider a second representation in which y determines a function in Fq and x determines a distribution. For each x ∈ X, define νx as the average of Alice’s message distributions for the two secret values s = 0 and s = 1: q 1X x x νx (a) := πr P0,r (a) + P1,r (a) . 2 r=1
Whenever νx (a) > 0, define wx,a
∈ Rq by wx,a (r) :=
πr zax (r) . 2νx (a)
If νx (a) = 0, set wx,a = 0. For every a with νx (a) > 0, Pq Pq x (a) + P x (a) x (r)| π P π |z r 0,r 1,r r r=1 a ∥wx,a ∥1 = r=1 ≤ = 1. 2νx (a) 2νx (a) Hence wx,a ∈ B1q . Let λx be the distribution of wx,a obtained by sampling a according to νx . For each y ∈ Y , define ψy (w) :=
q X X
wr Qyr (b) ,
w ∈ B1q .
b∈MB r=1
This function belongs to Fq . To observe this, for each b ∈ MB , define zby ∈ Rq by zby (r) := 2Qyr (b). Then ψy (w) =
1 X ⟨w, zby ⟩ , 2 b∈MB
16
and, for every r ∈ [q], X
|zby (r)| = 2
b∈MB
X
Qyr (b) = 2.
b∈MB
Lemma 3.4. For every y ∈ Y , the function ψy belongs to Fq , and the column-distance function of y satisfies D y (x) = Ew∼λx ψy (w) for every x ∈ X. Proof. If νx (a) = 0, then πr zax (r) = 0 for every r ∈ [q]. Therefore, q X X X πr zax (r) y Ew∼λx ψy (w) = νx (a) Q (b) 2νx (a) r b∈MB r=1
a∈MA νx (a)>0
=
1 X 2
q X X
πr zax (r)Qyr (b)
a∈MA b∈MB r=1 y
= D(x, y) = D (x).
Having represented both the row and column distance functions using functions from the same class Fq , we next bound the uniform covering number of this class.
3.3
Covering the function class Fq
We now construct a finite family that approximates every function in Fq in the ∞-norm. For 0 < η ≤ 1, let N∞ (η, Fq ) denote the smallest cardinality of a finite family H of functions on B1q such that, for every g ∈ Fq , there exists h ∈ H satisfying ∥g − h∥∞ ≤ η. The functions in H are not required to belong to Fq . Lemma 3.5. There is a constant c > 0 such that, for every q ≥ 1 and 0 < η ≤ 1, q4 2 cq log2 N∞ (η, Fq ) ≤ c 2 log2 . η η Proof. Fix an integer q ≥ 1 and 0 < η ≤ 1. Let η Γ := Z ∩ [−1, 1]. 4q Every point of [−1, 1] can be rounded to a point of Γ with error at most η/(4q), and |Γ| ≤ 1 +
8q 10q ≤ . η η
17
Let U ⊆ B1q be an η/(8q)-net in the ℓ1 -norm. By the standard volumetric bound (see, e.g., Proposition C.3 in [FR13]), we may choose 17q q 16q q ≤ . |U| ≤ 1 + η η Set
8q 2 M := ln 4|U| . η2
For each w = (w1 , . . . , wM ) ∈ (Γq )M , define hw : B1q → R by M
q X hw (u) := |⟨u, wj ⟩|. M j=1
Consider the finite family H := hw : w ∈ (Γq )M . This family depends only on q and η, and |H| ≤ |Γ|
qM
≤
10q η
qM .
We show that H is an η-cover of Fq with respect to the ∞ norm ∥g − h∥∞ := sup |g(u) − h(u)|. u∈B1q
Fix g ∈ Fq , and write g(u) =
1X |⟨u, zi ⟩|, 2
X
i∈I
for every r ∈ [q].
i∈I
Then X
|zi (r)| ≤ 2
∥zi ∥∞ ≤
q X X
|zi (r)| ≤ 2q.
r=1 i∈I
i∈I
Define V by selecting a nonzero term zi with probability ∥zi ∥∞ /(2q) and setting V = zi /∥zi ∥∞ ; with the remaining probability, set V = 0. Then, for every u ∈ B1q , X ∥zi ∥∞ zi u, q E|⟨u, V ⟩| = q 2q ∥zi ∥∞ i∈I zi ̸=0
=
1X |⟨u, zi ⟩| = g(u). 2 i∈I
Round each coordinate of V to a point of Γ, obtaining a random vector W ∈ Γq such that ∥V − W ∥∞ ≤ 18
η . 4q
For every u ∈ B1q , it follows that |g(u) − q E|⟨u, W ⟩|| ≤ q E|⟨u, V − W ⟩| ≤ q∥u∥1 E∥V − W ∥∞ ≤
η . 4
Now draw independent copies W1 , . . . , WM of W and let M
h(u) :=
q X |⟨u, Wj ⟩|. M j=1
Every realization of h belongs to H. For each fixed u ∈ B1q , the independent random variables q|⟨u, Wj ⟩| lie in [0, q]. Hence Hoeffding’s inequality (Fact 2.2) and a union bound give M η2 1 η ≤ 2|U| exp − 2 ≤ . Pr max |h(u) − q E|⟨u, W ⟩|| > u∈U 4 8q 2 Consequently, there exists a realization h ∈ H such that max |g(u) − h(u)| ≤ u∈U
η . 2
We next observe that both g and h are q-Lipschitz with respect to the ℓ1 -norm. Indeed, for all u, v ∈ B1q , |g(u) − g(v)| ≤ q E ||⟨u, V ⟩| − |⟨v, V ⟩|| ≤ q E|⟨u − v, V ⟩| ≤ q∥u − v∥1 E∥V ∥∞ ≤ q∥u − v∥1 , since V ∈ [−1, 1]q . Similarly, |h(u) − h(v)| ≤
M
M
j=1
j=1
q X q X |⟨u − v, Wj ⟩| ≤ ∥u − v∥1 ∥Wj ∥∞ ≤ q∥u − v∥1 , M M
since Wj ∈ [−1, 1]q for every j. For an arbitrary u ∈ B1q , choose u0 ∈ U with ∥u − u0 ∥1 ≤ η/(8q). Then |g(u) − h(u)| ≤ |g(u) − g(u0 )| + |g(u0 ) − h(u0 )| + |h(u0 ) − h(u)| η ≤ 2q∥u − u0 ∥1 + 2 3η ≤ < η. 4 Thus H is an η-cover of Fq in the ∞-norm. Finally, the bounds on |U | and M imply 8q 2 17q 17q 3 17q M ≤ 2 ln 4 + q ln + 1 ≤ 2 ln . η η η η Therefore, log2 N∞ (η, Fq ) ≤ log2 |H| ≤ qM log2 This proves the claimed bound. 19
10q η
17q 4 ≤ 2 log22 η
17q η
.
3.4
Lower bound for shared randomness
We now combine the separation of distance functions in Lemma 3.2 with the covering bound for Fq in Section 3.3 to prove the main theorem in this section. Theorem 3.6. Let f : X × Y → {0, 1}, and suppose that f admits an ε-correct and δ-private CDS protocol using a shared random variable supported on [q]. Set γ := 1 − 2ε − δ, and suppose that γ > 0. Then there is a universal constant C > 0 such that q4 2 Cq ∥ + 1. D (f ) ≤ C 2 log2 γ γ
(10)
Consequently, for every fixed constant γ > 0, log2 q = Ω log2 D∥ (f ) . Proof. Set η :=
γ , 4
and let H be an η-net for Fq with |H| = N∞ (η, Fq ), as proved in Lemma 3.5. We first bound the number of distinct rows of f . For h ∈ H, define a function Rh : Y → R by Rh (y) := Ep∼µy [h(p)]. For every x ∈ X, choose hx ∈ H such that ∥ϕx − hx ∥∞ ≤ η. By Lemma 3.3, Dx (y) = Ep∼µy [ϕx (p)]. Hence, for every y ∈ Y , |Dx (y) − Rhx (y)| = Ep∼µy [ϕx (p) − hx (p)] ≤ ∥ϕx − hx ∥∞ ≤ η. Therefore, ∥Dx − Rhx ∥∞ ≤ η. According to Lemma 3.2, distinct rows of f give distance functions separated by at least γ. Since γ 2η = < γ, 2 two distinct rows cannot be approximated by the same function Rh . It follows that Nrow (f ) ≤ |H|. 20
We apply the same argument for columns of f . For h ∈ H, define Ch : X → R by Ch (x) := Ew∼λx [h(w)]. Using Lemma 3.4 and Lemma 3.2, we similarly obtain Ncol (f ) ≤ |H|. It now follows from Fact 2.3 that D∥ (f ) = D→ (f ) + D← (f ) ≤ 2 log2 |H| + 2 = 2 log2 N∞ (η, Fq ) + 2. Applying Lemma 3.5 and substituting η = γ/4 gives q4 q4 q4 2 cq 2 4cq 2 Cq ∥ + 2 ≤ 32c 2 log2 + 2 ≤ C 2 log2 +1 D (f ) ≤ 2c 2 log2 η η γ γ γ γ for a sufficiently large universal constant C. This proves (10). For every fixed constant γ > 0, the preceding bound gives D∥ (f ) = q O(1) . Taking logarithms therefore yields log2 q = Ω log2 D∥ (f ) .
4
Lower bounds for f -routing
We use the following rank method of Asadi, Culf, and May [ACM25]. Proposition 4.1 (Adapted from Definition 3.3, Lemma 3.4 and Lemma 3.5 in [ACM25]). Suppose that an f -routing protocol is perfect on the 0-inputs and has recovery error at most 0.05 on the 1-inputs. Suppose further that its shared pure resource state has Schmidt rank dE . Then there exists a real matrix G ∈ RX×Y such that Gx,y = 0
if f (x, y) = 0,
Gx,y > 0
if f (x, y) = 1,
and rank(G) ≤ d4E . The symmetric statement holds for protocols perfect on the 1-inputs and having error at most 0.05 on the 0-inputs. x,y For the joint state ρQM of the reference system and Bob’s system after the communication B round and before decoding, Asadi, Culf, and May [ACM25] defined !2 I Q x,y Gx,y := tr ρQM − ⊗ ρx,y MB B dQ
where dQ := dim Q. This is a squared Hilbert–Schmidt norm, and it is a real nonnegative value and vanishes exactly when Q and MB are uncorrelated. Their decoupling argument shows that this occurs exactly on the 0-inputs under the assumptions of Proposition 4.1. Therefore, Gx,y > 0 exactly when f (x, y) = 1. 21
Theorem 4.2 (Sign-rank lower bounds for f -routing). Let f : X × Y → {0, 1}. Any protocol covered by Proposition 4.1, using a shared state of Schmidt rank dE , satisfies d4E ≥ signrank(Sf ) − 1. Consequently, FR0 (f ), FR1 (f ), pFR(f ) ≥
1 log max{1, signrank(Sf ) − 1} . 4
Proof. First suppose the protocol is perfect on the 0-inputs, and let G be the matrix from Proposition 4.1. We define m := min Gx,y > 0. f (x,y)=1
Let J be the all-ones matrix, choose 0 < δ < m, and define A := G − δJ. If f (x, y) = 0, then Ax,y = −δ < 0; if f (x, y) = 1, then Ax,y ≥ m − δ > 0. Hence sign(A) = Sf . Therefore signrank(Sf ) ≤ rank(A) ≤ rank(G) + rank(J) ≤ d4E + 1. The first inequality holds from the definition of the sign rank (4), and the second one follows from the subadditivity of the rank of matrices (3). This proves d4E ≥ signrank(Sf ) − 1. If the protocol is perfect on the 1-inputs, apply the same argument to 1 − f . Since S1−f = −Sf and a global sign change does not alter sign rank, the same bound follows. Exact routing is a special case of both one-sided-perfect settings. Taking logarithms proves the cost bound. Combining the theorem with the standard facts recalled above gives the following operational form and its basic application. Corollary 4.3. There exists a constant c′ such that, for every non-constant Boolean function f , 1 FR0 (f ), FR1 (f ), pFR(f ) ≥ UPPcc (f ) − c′ . 4 In particular, FR0 (IPn ), FR1 (IPn ), pFR(IPn ) ≥
n 1 − . 8 4
Proof. The first statement follows from Theorem 4.2 and (5). For inner product, use the sign-rank lower bound (6): n 1 1 log signrank(SIPn ) − 1 ≥ − . 4 8 4
22
Lower bounds for f -BB84. In the f -BB84 task, Alice receives x and a qubit in the BB84 state H f (x,y) |b⟩, while Bob receives y; after one simultaneous round of communication, both parties must output b. A protocol is (ε0 , ε1 )-correct if it succeeds with probability at least 1 − ε0 whenever f (x, y) = 0, and with probability at least 1 − ε1 whenever f (x, y) = 1. Let FBB840 (f ), FBB841 (f ), pFBB84(f ) denote the minimum logarithmic Schmidt-rank costs of f -BB84 protocols that are respectively (0, ε)-correct, (ε, 0)-correct, and (0, 0)-correct, where ε > 0 is a sufficiently small constant. Corollary 4.4. For every Boolean function f , FBB840 (f ), FBB841 (f ), pFBB84(f ) = Ω log2 max{1, signrank(Sf ) − 1}
.
Consequently, there exist constants c0 , c1 such that, FBB840 (f ), FBB841 (f ), pFBB84(f ) ≥ c0 UPPcc (f ) − c1 . Proof. The f -BB84 task is called the f -measure task in [BHM+ 26]. The reductions proven in [BHM+ 26, Theorem 1, Section 4.1] transform f -BB84 protocols into f -routing protocols using only a constant number of copies of the shared resource state. Moreover, the reduction preserves zero error and sufficiently small constant error. Hence, FBB840 (f ) = Ω FR0 (f ) , FBB841 (f ) = Ω FR1 (f ) , pFBB84(f ) = Ω pFR(f ) . The sign-rank bounds now follow from Theorem 4.2. The UPP bounds follow from (5). Lower bounds for CDS. We next transfer our f -routing lower bounds to classical CDS. Fix a sufficiently small constant η > 0. Let ppCDS(f ),
pcCDS(f ),
pCDS(f )
denote the minimum shared-randomness costs of CDS protocols for f that are, respectively, ηcorrect and perfectly private, perfectly correct and η-private, and both perfectly correct and perfectly private. Corollary 4.5. For every nonconstant Boolean function f , ppCDS(f ), pcCDS(f ), pCDS(f ) = Ω log2 max{1, signrank(Sf ) − 1}
.
Consequently, there exist constants c1 , c0 such that, ppCDS(f ), pcCDS(f ), pCDS(f ) ≥ c0 UPPcc (f ) − c1 . Proof. The CDS-to-CDQS reduction of Allerstorfer et al. [ABM+ 24, Theorem 22], followed by their CDQS-to-routing reduction [ABM+ 24, Theorem 23], preserves the shared-resource cost up to constant factors and therefore gives ppCDS(f ) = Ω FR0 (f ) , pcCDS(f ) = Ω FR1 (f ) , pCDS(f ) = Ω pFR(f ) . The sign-rank bounds now follow from Theorem 4.2. The UPP bounds follow from (5). 23
5
Concluding remarks
We studied lower bounds on shared randomness in CDS and on shared entanglement in f -routing. Our robust CDS lower bound is expressed in terms of the logarithm of exact deterministic SMP complexity and holds even when communication and private randomness are unrestricted. For equality, this bound is tight up to constant factors. For f -routing, we used the structure matrix of Asadi, Culf, and May [ACM25] to obtain a sign-rank lower bound, or equivalently a lower bound in terms of UPP communication complexity. In particular, this yields an Ω(n) entanglement lower bound for the inner product function when recovery is perfect on either the 0-inputs or the 1-inputs and has constant error on the other input class. In independent work, Bogner [Bog26] proved an Ω(log n) entanglement lower bound for f routing with the inner product function, allowing constant error on both input classes. Obtaining a polynomial lower bound in this regime remains open. A natural related question is whether CDS for the inner product function requires nΩ(1) bits of shared randomness when constant correctness and privacy errors are allowed, with unrestricted communication and private randomness. To our knowledge, such a lower bound remains open. We believe developing stronger techniques for shared-randomness lower bounds in CDS will provide useful ideas for the quantum setting. Finally, it would be interesting to obtain a direct operational understanding of the relationship between UPP, CDS, and f -routing. Our entanglement lower bound relates f -routing and CDS to unbounded-error communication through sign rank. Can this relation be explained directly in terms of protocol operations, and is there an analogous interpretation for CDS? A similar question related to QNP communication protocols [dW03] was asked in [ACM25].
AI disclosure The authors first observed that if a CDS protocol for f uses no randomness, then f (x, y) = g(x) holds for some function g. They developed its generalization on for which f there is a CDS protocol with small randomness using ChatGPT 5.6 Sol. They also found that the authors in [ACM25] did not obtain a lower bound for the inner product function using their rank method. ChatGPT 5.6 Sol then found that the tight lower bound can be shown using the sign rank. They also used ChatGPT 6 Astra to assist in drafting this manuscript and improve the presentation. They take full responsibility for the content.
Acknowledgments AH thanks Vahid Asadi, Richard Cleve, and Alex May for telling him about non-local quantum computation, Philip Verduyn Lunel for discussions about quantum position verification, Harumichi Nishimura for discussions about CDS, and Daiki Suruga for pointing out Fact 2.3. AH and RM thank Alex May for comments on the manuscript, and François Le Gall for his generous support. AH is supported by JSPS KAKENHI grant No. 24H00071, 25K24674, 25K24465. RM is supported by the JST CREST grant JPMJCR24I4.
24
References [AARV21]
Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan. Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations. SIAM Journal on Computing, 50(1):32–67, 2021.
[ABM+ 24] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. Quantum, 8:1387, 2024. [ACCM25] Vahid Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification. Quantum, 9:1604, January 2025. [ACH+ 24]
Harriet Apel, Toby Cubitt, Patrick Hayden, Tamara Kohler, and David Pérez-Garcı́a. Security of quantum position-verification limits Hamiltonian simulation via holography. Journal of High Energy Physics, 2024(8):1–40, 2024.
[ACM25]
Vahid R. Asadi, Eric Culf, and Alex May. Rank lower bounds on non-local quantum computation. arXiv preprint arXiv:2402.18647, 2025. Also appeared in the proceedings of ITCS 2025.
[AKL+ 25]
Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources. Quantum, 9:1885, 2025.
[AV21]
Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe. Journal of Cryptology, 2021.
[BCF+ 14]
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 2014.
[BCS22]
Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, 2022.
[BFSS13]
Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The gardenhose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science (ITCS 2013), pages 145–158, 2013.
[BHM+ 26] Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen. A complexity theory for non-local quantum computation. Quantum, 10:2152, 2026. [BK11]
Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 2011.
[Bog26]
Kevin Bogner. Robust logarithmic entanglement lower bound for f -routing. arXiv preprint arXiv:2608.05775, 2026.
25
[dW03]
Ronald de Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 32(3):681–699, 2003.
[For02]
Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4):612–625, 2002.
[FR13]
Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, 2013.
[GHIS25]
Mika Göös, Nathaniel Harms, Valentin Imbach, and Dmitry Sokolov. Sign-rank of k-hamming distance is constant. In Proceedings of 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), pages 2353–2368, 2025.
[GIKM00]
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. Journal of Computer and System Sciences, 2000.
[GKW15]
Romain Gay, Iordanis Kerenidis, and Hoeteck Wee. Communication complexity of conditional disclosure of secrets and attribute-based encryption. In Proceedings of Annual Cryptology Conference (CRYPTO 2015), pages 485–502, 2015.
[GMOW26] Uma Girish, Alex May, Leo Orshansky, and Chris Waddell. Comparing classical and quantum conditional disclosure of secrets. Quantum, 10:2049, 2026. [GMPY26] Uma Girish, Alex May, Natalie Parham, and Henry Yuen. Magic and communication complexity. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), pages 845–856, 2026. [Jus72]
Jørn Justesen. A class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18(5):652–656, 1972.
[KMS11]
Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 2011.
[KY21]
Akinori Kawachi and Maki Yoshida. Randomness bounds for private simultaneous messages and conditional disclosure of secrets. Cryptology ePrint Archive, Paper 2021/1037, 2021.
[LVW17]
Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Conditional disclosure of secrets via non-linear reconstruction. In Proceedings of Annual International Cryptology Conference (CRYPTO 2017), pages 758–790, 2017.
[May19]
Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019.
[May22]
Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 2022.
[May26]
Alex May. Entanglement cost in non-local quantum computation. arXiv preprint arXiv:2605.02840, 2026.
26
[MPS20]
Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020.
[PS86]
Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106–123, 1986.
[Spe16]
Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of LIPIcs, pages 9:1–9:24, 2016.
A
A matching upper bound for equality
The logarithmic lower bound for equality is tight for fixed privacy error. Proposition A.1 (CDS for equality via hashing). For every fixed constant 0 < δ < 1, equality on n-bit strings, with a one-bit secret s ∈ {0, 1}, has a perfectly correct and δ-private CDS protocol using O(log n) shared-randomness bits and one-bit messages from each party. Proof. By the existence of asymptotically good binary linear codes, such as Justesen codes [Jus72], there are constants α ∈ (0, 1) and c > 0 such that, for every n, one can choose an injective linear encoding E : Fn2 −→ FM M ≤ cn, 2 , satisfying dH (E(x), E(y)) ≥ αM
whenever x ̸= y.
By padding the codewords with zeros and adjusting α by a constant factor if necessary, we may assume that M is a power of two. This preserves M = O(n). Choose log(1/δ) t= . − log(1 − α) Since δ is fixed, t = O(1). Alice and Bob share independent uniform coordinates I1 , . . . , It ∈ [M ] and define h(x) := E(x)I1 , . . . , E(x)It ∈ {0, 1}t . Equal inputs always have equal fingerprints. For any fixed x ̸= y, the relative-distance guarantee and independence of the sampled coordinates imply Pr[h(x) = h(y)] ≤ (1 − α)t ≤ δ. We next apply a perfectly correct and perfectly private CDS protocol for equality to the fingerprints. Independently of the sampled coordinates, Alice and Bob share independent uniform bits (Rz )z∈{0,1}t . All shared randomness is independent of the inputs and the secret and is hidden from the referee. On inputs x, y and a one-bit secret s ∈ {0, 1}, Alice and Bob send A = s ⊕ Rh(x) , 27
B = Rh(y) ,
respectively. The referee outputs A ⊕ B. If x = y, then h(x) = h(y) for every choice of the sampled coordinates, and hence A ⊕ B = s. Thus, correctness is perfect. For privacy, fix x ̸= y and let p := Pr[h(x) = h(y)] ≤ δ. Conditioned on any choice of coordinates for which h(x) ̸= h(y), the masks Rh(x) and Rh(y) are independent uniform bits. The transcript is therefore uniform on {0, 1}2 , independently of s. Conditioned on a collision, it is uniform over the two pairs whose XOR equals s. Let Ps denote the transcript distribution for secret s, let U2 denote the uniform distribution on {0, 1}2 , and let Qs denote the uniform distribution on {(u, v) : u ⊕ v = s}. Since Ps = (1 − p)U2 + pQs and ∥Qs − U2 ∥1 = 1, we obtain ∥Ps − U2 ∥1 = p∥Qs − U2 ∥1 = p ≤ δ. Thus U2 provides a simulator independent of the secret, and the protocol is δ-private. Finally, sampling the coordinates and the random table uses t log2 M + 2t = O(log n) shared-randomness bits, since t is constant.
B
Direct connection between sign-rank and nondeterministic rank
The following relation is known over R (see, e.g., [GHIS25, Section 2.1]). For completeness, we prove it over C, following the definition of nondeterministic rank in [ACM25]. Lemma B.1. Let f : X × Y → {0, 1}, where X and Y are finite nonempty sets, and let Sf (x, y) := 2f (x, y) − 1. Then signrank(Sf ) ≤ nrank(f )2 + 1, where nrank(f ) is the minimum rank over C of a matrix M satisfying Mx,y ̸= 0 if and only if f (x, y) = 1. Proof. The claim is immediate if f ≡ 0, and assume that f has at least one 1-input. Let M be a nondeterministic matrix for f with rank(M ) = nrank(f ) =: r. Define the real matrix Bx,y = |Mx,y |2 ,
B := M ◦ M , 28
where ◦ denotes the entrywise product and M denotes the entrywise complex conjugate of M . Thus Bx,y = 0 when f (x, y) = 0, and Bx,y > 0 when f (x, y) = 1. By the rank inequality for entrywise products, rank(B) ≤ rank(M ) rank(M ) = r2 . Here the real and complex ranks of B coincide because B is real. Let J be the all-ones matrix, and choose 0<δ<
min Bx,y .
f (x,y)=1
Then B − δJ is negative on the 0-inputs of f and positive on its 1-inputs. Hence sign(B − δJ) = Sf . Consequently, signrank(Sf ) ≤ rank(B − δJ) ≤ rank(B) + 1 ≤ r2 + 1, as claimed. Corollary B.2. For every nonconstant Boolean function f : X × Y → {0, 1}, 1 FR0 (f ), FR1 (f ), pFR(f ) ≥ log2 max{1, signrank(Sf ) − 1} . 8 In particular, for every n ≥ 1, n 1 FR0 (IPn ), FR1 (IPn ), pFR(IPn ) ≥ − . 16 8 Proof. The lower bounds of Asadi, Culf, and May [ACM25] imply 1 1 FR1 (f ) ≥ log2 nrank(1 − f ). FR0 (f ) ≥ log2 nrank(f ), 4 4 Write s := signrank(Sf ). Since S1−f = −Sf , we have signrank(S1−f ) = s. Applying Lemma B.1 to both f and 1 − f gives nrank(f )2 ≥ s − 1,
nrank(1 − f )2 ≥ s − 1.
Moreover, both nondeterministic ranks are at least one, because f is nonconstant. Consequently, for h ∈ {f, 1 − f }, 1 log2 nrank(h) ≥ log2 max{1, s − 1} . 2 Combining these inequalities proves the bounds for FR0 (f ) and FR1 (f ). The same bound holds for pFR(f ), since pFR(f ) ≥ max{FR0 (f ), FR1 (f )}. For inner product, the standard sign-rank lower bound gives signrank(SIPn ) ≥ 2n/2 . Using max{1, s − 1} ≥ s/2 for every s ≥ 1, we obtain 1 n 1 n 1 log2 max{1, signrank(SIPn ) − 1} ≥ −1 = − . 8 8 2 16 8
29