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.
AI Summary
The paper studies function-dependent resource lower bounds for conditional disclosure of secrets (CDS) and non-local quantum computation’s $f$-routing task, motivated by quantum position verification. It treats robust classical CDS separately from routing with perfect recovery on one input class.
For an $\varepsilon$-correct, $\delta$-private CDS protocol with shared randomness supported on $q$ values, it proves $\log_2 q=\Omega(\log_2 D^{\|}(f))$ for fixed errors satisfying $2\varepsilon+\delta<1$. Communication and private randomness are unrestricted. The proof represents secret-dependent transcript distinguishability using functions on a $q$-dimensional domain, constructs a uniform covering family independent of message lengths, and bounds the number of distinguishable rows and columns of $f$. For $n$-bit equality, the resulting $\Omega(\log n)$ bound matches a hashing-based upper bound.
For routing, the paper derives $E\ge\frac14\log_2\max\{1,\operatorname{signrank}(S_f)-1\}$, where $E$ is logarithmic Schmidt rank and $S_f=2f-1$. It exploits nonnegativity of an existing low-rank protocol matrix: subtracting a small all-ones matrix produces the required sign pattern. For inner product, this gives $E\ge n/8-1/4$ when either input class is recovered perfectly and the other has error at most $0.05$, matching known $O(n)$ upper bounds asymptotically.
The robust CDS bound does not imply a robust routing bound through existing reductions, and yields at most logarithmic bounds in input length. The routing result retains the one-sided-perfect restriction. Independent work obtains an $\Omega(\log n)$ two-sided-error routing bound for inner product; polynomial robust CDS lower bounds remain open.
Little sign of AI-generated textAI use disclosedStrong assumptions
They also used ChatGPT 6 to assist in drafting this manuscript and improve the presentation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies function-dependent resource lower bounds for conditional disclosure of secrets (CDS) and non-local quantum computation’s f-routing task, motivated by quantum position verification. It treats robust classical CDS separately from routing with perfect recovery on one input class.
For an ε-correct, δ-private CDS protocol with shared randomness supported on q values, it proves log2q=Ω(log2D∥(f)) for fixed errors satisfying 2ε+δ<1. Communication and private randomness are unrestricted. The proof represents secret-dependent transcript distinguishability using functions on a q-dimensional domain, constructs a uniform covering family independent of message lengths, and bounds the number of distinguishable rows and columns of f. For n-bit equality, the resulting Ω(logn) bound matches a hashing-based upper bound.
For routing, the paper derives E≥41log2max{1,signrank(Sf)−1}, where E is logarithmic Schmidt rank and Sf=2f−1. It exploits nonnegativity of an existing low-rank protocol matrix: subtracting a small all-ones matrix produces the required sign pattern. For inner product, this gives E≥n/8−1/4 when either input class is recovered perfectly and the other has error at most 0.05, matching known O(n) upper bounds asymptotically.
The robust CDS bound does not imply a robust routing bound through existing reductions, and yields at most logarithmic bounds in input length. The routing result retains the one-sided-perfect restriction. Independent work obtains an Ω(logn) two-sided-error routing bound for inner product; polynomial robust CDS lower bounds remain open.
A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, f-routing and f-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y) in terms of the rank of a matrix g(x,y) whose entries are zero when f(x,y)=0, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of f(x,y). Because of a relationship between f-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.
A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, f-routing and f-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y) in terms of the rank of a matrix g(x,y) whose entries are zero when f(x,y) = 0, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of f(x,y). Because of a relationship between f-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.
Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, SWAP, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.
The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret z to a referee if and only if a Boolean function f has f ( x , y ) = 1 . Alice knows x , z , Bob knows y , and the referee knows x , y . Recently, a quantum analogue of this primitive called CDQS was defined and related to f -routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. We begin by looking for quantum analogues of results already established in the classical CDS literature. Doing so we establish a number of basic properties of CDQS, including lower bounds on entanglement and communication stated in terms of measures of communication complexity. Because of the close relationship to the f -routing position-verification scheme, our results have relevance to the security of these schemes.
In the private simultaneous message (PSM) setting, k players obtain inputs xi∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk) but no other information about (x1,...,xk). The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for k-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of f(x1,x2) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting s be the size of a quantum circuit computing f, df be the circuit depth, k the number of players, n the number of bits received by each player, and ε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅logO(df)(s/ε). 2) The square of the Fourier 1 norm of f, ∥f^∥12, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12). In proving the first upper bound, we generalize existing T-depth based techniques for NLQC from 2 to k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.
The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results:1) We prove a Ω ( log R 0 , A → B ( f ) + log R 0 , B → A ( f ) ) lower bound on quantum CDS where R 0 , A → B ( f ) is the classical one-way communication complexity with perfect correctness.2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs.3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of O ( log n ) and classical lower bound of Ω ( n ) .4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed.We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.