CS Paper Radar

New lower bounds for CDS and $f$-routing

Atsuya Hasegawa, Ranitha Mataraarachchi

cs.CR quant-ph ·submitted 2026-09-21 08:50 UTC · v2
theory

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.

Comment
30 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Computational Bounds for $f$-Routing

cs.CC quant-ph ·2026-09-30 ·Oren Renard, Nicholas Spooner
theory similarity 0.73
Abstract · Improved writing and exposition

The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and a sufficiently small constant $ε>0$, a uniform strategy running in time $T$ and succeeding with probability at least $1-ε$ on every input implies the following computational bounds on $f$. 1. If the strategies are arbitrary quantum channels, then $f\in \mathrm{QSZK}(\mathrm{poly}(T))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time $T$ and the simulator in time $\mathrm{poly}(T)$. 2. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in \mathrm{DTIME}(\mathrm{poly}(T2^t))$. 3. If the strategies are explicit Pauli-sparse unitaries acting on at most $T$ qubits and having at most $s$ nonzero Pauli coefficients, then $f\in \mathrm{DTIME}(\mathrm{poly}(Ts))$. Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound $q\leq\log n$ of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.

0.23

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

cs.CC quant-ph ·2026-10-05 ·Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova
similarity 0.68
Abstract

We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.

0.06

Constant-round quantum advantage in communication complexity for total functions

cs.CC quant-ph ·2026-08-20 ·Atsuya Hasegawa, François Le Gall
similarity 0.68
Abstract · 13 pages

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

0.39

Optimal and Verifiable Quantum Advantages in Communication Complexity

cs.CC quant-ph ·2026-10-04 ·Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
hot direction similarity 0.68
Abstract · 65 pages

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.

0.47

A Cheat-Sensitive Primitive for Destination-Private Quantum Routing

cs.CR quant-ph ·2026-10-03 ·S. F. E. Oliviero, S. Onofri, V. Giovannetti
similarity 0.68
Abstract

Quantum networks will rely on intermediate nodes to distribute entanglement, but the same nodes may learn which users are being connected. We introduce a minimal two-call routing primitive in which a user, Alice, establishes an entangled link with one of several clients while testing whether the provider, Bob, has disturbed a coherently encoded request. The construction adapts the hidden-order mechanism of quantum private queries: one call contains a direct request, the other a coherent superposition of the desired and null addresses, and Alice keeps their order secret. A private matching qubit held by the selected client restores the coherent test state after a favorable Bell-measurement outcome, so that Alice can test the returned query without any further operation by Bob. The claim is deliberately limited. The protocol shows that a routing request can carry a physical cheating test, and it detects an explicit destination-reading attack with nonzero probability. It does not yet provide a quantitative information-disturbance tradeoff, composable security, or certification of an unmeasured output against arbitrary attacks. We also characterize the exact perfect-pass limit, in which Bob's residual state, averaged over the private matching states, is independent of the destination.

0.30

On the Limits of Quantum Multiparty Simultaneous Communication

cs.CC quant-ph ·2026-09-09 ·Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
theory similarity 0.67
Abstract · 27 pages, 1 figure

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\min\{n,k^2\})$ on total communication and $Ω(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $Ω(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

0.25

High quantum local differential privacy breaks entanglement

cs.CR quant-phcs.IT ·2026-09-11 ·Sujeet Bhalerao, Theshani Nuradha, Felix Leditzky
theory similarity 0.67
Abstract · 25 pages

Differential privacy provides a mathematical framework for guaranteeing privacy for sensitive data. In quantum information processing, the interaction of privacy constraints with quantum resources such as entanglement remains a question of interest. Given that the utility of many protocols, and often the presence of a quantum advantage, relies on quantum resources such as entanglement, it is crucial to understand when a privacy requirement for a quantum channel is compatible with the channel's ability to preserve entanglement. We study this question for quantum local differential privacy (QLDP). Our main result shows that every $\varepsilon$-QLDP channel with a $d$-dimensional input is entanglement-breaking whenever $\varepsilon\leq\log\frac{d}{d-1}$. We also prove an approximate version for $(\varepsilon,δ)$-QLDP, where channels in the same high-privacy regime are close in diamond norm to an entanglement-breaking channel. We further prove a composition result for a collection of private quantum channels having entangled inputs and global measurements in the high-privacy regime. Finally, we apply our results to private quantum learning theory. We prove that any learning protocol using arbitrary quantum memory on copies of the output of an entanglement-breaking channel can be simulated by a protocol that measures the corresponding unprocessed input copies one at a time while storing only classical information. Combining this result with our high-privacy entanglement-breaking theorem, we show that under sufficiently private local noise, a learning protocol with quantum memory for purity testing and bipartite product testing is subject to the sample complexity lower bounds for protocols with single-copy measurements on the noiseless tasks. We also obtain stronger sample complexity lower bounds when a single highly private channel acts on the entire multipartite input.

0.31

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

cs.DS quant-ph ·2026-10-05 ·Nadezhda Voronova
theory similarity 0.67
Abstract

How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.

0.29