Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.05775

Robust logarithmic entanglement lower bound for $f$-routing

Kevin Bogner

quant-phSubmitted Aug 6, 2026• Announced Aug 7, 2026• 0 citations• Revised Sep 1, 2026 (v3)
v1 · Aug 6, 2026v2 · Aug 17, 2026v3 · Sep 1, 2026
arXivHTMLPDF

Abstract

In one-round $f$-routing, Alice receives an $n$-bit string $x$ and an unknown qubit, and Bob receives an $n$-bit string $y$. They exchange one simultaneous message each and cannot communicate afterwards; the party selected by a Boolean function $f(x,y)$ must then recover the qubit. The parties may share unlimited entanglement in advance. When $f$ is the inner product modulo $2$, we prove that every protocol with worst-case error at most $0.09$ must use a shared state whose entanglement of formation grows at least logarithmically in $n$. The lower bound is robust: it tolerates constant error on both routing cases and covers arbitrary mixed states shared between Alice and Bob. Earlier growing lower bounds in this model, in contrast, require perfect recovery on at least one routing case. The bound is only logarithmic: a polynomial lower bound remains open.

Comments
24 pages, 1 figure. v3: adds the robust entanglement-of-formation lower bound as the main theorem; the previous shared-resource-cost bound is now the companion result

Related papers

New lower bounds for CDS and $f$-routing

Atsuya Hasegawa, Ranitha Mataraarachchi

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.

quant-pharXiv:2609.24291•Sep 22, 2026•0 citations

Communication complexity lower bounds by polynomials

Harry Buhrman, Ronald de Wolf

The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.

arXiv:cs/9910010•IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•127 citations

On the role of shared entanglement

Dmitry Gavinsky

Despite the apparent similarity between shared randomness and shared entanglement in the context of Communication Complexity, our understanding of the latter is not as good as of the former. In particular, there is no known ``entanglement analogue'' for the famous theorem by Newman, saying that the number of shared random bits required for solving any communication problem can be at most logarithmic in the input length (i.e., using more than $\asO[]{\log n}$ shared random bits would not reduce the complexity of an optimal solution). In this paper we prove that the same is not true for entanglement. We establish a wide range of tight (up to a polylogarithmic factor) entanglement vs.\ communication trade-offs for relational problems. The low end is:\ for any $t>2$, reducing shared entanglement from $log^tn$ to $\aso[]{log^{t-2}n}$ qubits can increase the communication required for solving a problem almost exponentially, from $\asO[]{log^tn}$ to $\asOm[]{\sqrt n}$. The high end is:\ for any $\eps>0$, reducing shared entanglement from $n^{1-\eps}\log n$ to $\aso[]{n^{1-\eps}/\log n}$ can increase the required communication from $\asO[]{n^{1-\eps}\log n}$ to $\asOm[]{n^{1-\eps/2}/\log n}$. The upper bounds are demonstrated via protocols which are \e{exact} and work in the \e{simultaneous message passing model}, while the lower bounds hold for \e{bounded-error protocols}, even in the more powerful \e{model of 1-way communication}. Our protocols use shared EPR pairs while the lower bounds apply to any sort of prior entanglement. We base the lower bounds on a strong direct product theorem for communication complexity of a certain class of relational problems. We believe that the theorem might have applications outside the scope of this work.

Quantum Information and Computation•Jan 1, 2008•15 citations

Towards the Communication Complexity of Entanglement Distillation Protocols

Andris Ambainis, Ke Yang

Quantum entanglement distillation protocols are LOCC protocols that, over ``imperfect'' EPR pairs shared between Alice and Bob as input, output perfect or near-perfect EPR pairs. In this paper, we study the communication complexity of these protocols, that is, the minimal number of (classical) bits needed for Alice and Bob. To our knowledge, it is the first paper that studies entanglemend distillation protocols in the resource-bounded case. We consider 3 models for imperfect EPR pairs. In the measure-$r$ model, $r$ out of $n$ EPR pairs are measured by an adversary (and thus become ``corrupted''); in the depolarization model, the qubits of Bob underwent a depolarization channel; in the fidelity model, the only information Alice and Bob possess is the fidelity of the shared state. For the first 2 models, we prove tight and almost-tight bounds on the base case, i.e., how well Alice and Bob can do if they are not allowed to communicate. For the fidelity model, we prove a very tight lower bound (up to an additive constant) on the communication complexity. This lower bound implies the optimality of the Random Hash protocol in [ASY02].

•Jul 17, 2002•0 citations

On the Role of Shared Entanglement

Gavinsky, Dmytro

Despite the apparent similarity between shared randomness and shared entanglement in the context of Communication Complexity, our understanding of the latter is not as good as of the former. In particular, there is no known "entanglement analogue" for the famous theorem by Newman, saying that the number of shared random bits required for solving any communication problem can be at most logarithmic in the input length (i.e., using more than O(log n) shared random bits would not reduce the complexity of an optimal solution). In this paper we prove that the same is not true for entanglement. We establish a wide range of tight (up to a polylogarithmic factor) entanglement vs. communication tradeoffs for relational problems. The low end is: for any t>2, reducing shared entanglement from log^t(n) to o(log^{t-2}(n)) qubits can increase the communication required for solving a problem almost exponentially, from O(log^t(n)) to Ω(\sqrt n). The high end is: for any \eps>0, reducing shared entanglement from n^{1-\eps}log(n) to o(n^{1-\eps}/log(n)) can increase the required communication from O(n^{1-\eps}log(n)) to Ω(n^{1-\eps/2}/log(n)). The upper bounds are demonstrated via protocols which are exact and work in the \e{simultaneous message passing model}, while the lower bounds hold for \e{bounded-error protocols}, even in the more powerful \e{model of 1-way communication}. Our protocols use shared EPR pairs while the lower bounds apply to any sort of prior entanglement. We base the lower bounds on a strong direct product theorem for communication complexity of a certain class of relational problems. We believe that the theorem might have applications outside the scope of this work.

arXiv:quant-ph/0604052•Apr 8, 2006•1 citation

New bounds on private simultaneous quantum message passing

Uma Girish, Alex May, Natalie Parham +1 more

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then each send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. 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(x_1,x_2)$ 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$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $ε$ a correctness parameter, we obtain $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones.

quant-pharXiv:2606.12557•Jun 12, 2026•0 citations
Robust logarithmic entanglement lower bound for fff-routing
In one-round fff-routing, Alice receives an nnn-bit string xxx and an unknown qubit, and Bob receives an nnn-bit string yyy. They exchange one simultaneous message each and cannot communicate afterwards; the party selected by a Boolean function f(x,y)f(x,y)f(x,y) must then recover the qubit. The parties may share unlimited entanglement in advance. When fff is the inner product modulo 222, we prove that every protocol with worst-case error at most 0.090.090.09 must use a shared state whose entanglement of formation grows at least logarithmically in nnn. The lower bound is robust: it tolerates constant error on both routing cases and covers arbitrary mixed states shared between Alice and Bob. Earlier growing lower bounds in this model, in contrast, require perfect recovery on at least one routing case. The bound is only logarithmic: a polynomial lower bound remains open.
New lower bounds for CDS and fff-routing
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 fff-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 fff-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 fff-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 quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.
Despite the apparent similarity between shared randomness and shared entanglement in the context of Communication Complexity, our understanding of the latter is not as good as of the former. In particular, there is no known ``entanglement analogue'' for the famous theorem by Newman, saying that the number of shared random bits required for solving any communication problem can be at most logarithmic in the input length (i.e., using more than $\asO[]{\log n}$ shared random bits would not reduce the complexity of an optimal solution). In this paper we prove that the same is not true for entanglement. We establish a wide range of tight (up to a polylogarithmic factor) entanglement vs.\ communication trade-offs for relational problems. The low end is:\ for any t>2t>2t>2, reducing shared entanglement from logtnlog^tnlogtn to $\aso[]{log^{t-2}n}$ qubits can increase the communication required for solving a problem almost exponentially, from $\asO[]{log^tn}$ to $\asOm[]{\sqrt n}$. The high end is:\ for any $\eps>0$, reducing shared entanglement from $n^{1-\eps}\log n$ to $\aso[]{n^{1-\eps}/\log n}$ can increase the required communication from $\asO[]{n^{1-\eps}\log n}$ to $\asOm[]{n^{1-\eps/2}/\log n}$. The upper bounds are demonstrated via protocols which are \e{exact} and work in the \e{simultaneous message passing model}, while the lower bounds hold for \e{bounded-error protocols}, even in the more powerful \e{model of 1-way communication}. Our protocols use shared EPR pairs while the lower bounds apply to any sort of prior entanglement. We base the lower bounds on a strong direct product theorem for communication complexity of a certain class of relational problems. We believe that the theorem might have applications outside the scope of this work.
Quantum entanglement distillation protocols are LOCC protocols that, over ``imperfect'' EPR pairs shared between Alice and Bob as input, output perfect or near-perfect EPR pairs. In this paper, we study the communication complexity of these protocols, that is, the minimal number of (classical) bits needed for Alice and Bob. To our knowledge, it is the first paper that studies entanglemend distillation protocols in the resource-bounded case. We consider 3 models for imperfect EPR pairs. In the measure-rrr model, rrr out of nnn EPR pairs are measured by an adversary (and thus become ``corrupted''); in the depolarization model, the qubits of Bob underwent a depolarization channel; in the fidelity model, the only information Alice and Bob possess is the fidelity of the shared state. For the first 2 models, we prove tight and almost-tight bounds on the base case, i.e., how well Alice and Bob can do if they are not allowed to communicate. For the fidelity model, we prove a very tight lower bound (up to an additive constant) on the communication complexity. This lower bound implies the optimality of the Random Hash protocol in [ASY02].
Despite the apparent similarity between shared randomness and shared entanglement in the context of Communication Complexity, our understanding of the latter is not as good as of the former. In particular, there is no known "entanglement analogue" for the famous theorem by Newman, saying that the number of shared random bits required for solving any communication problem can be at most logarithmic in the input length (i.e., using more than O(log n) shared random bits would not reduce the complexity of an optimal solution). In this paper we prove that the same is not true for entanglement. We establish a wide range of tight (up to a polylogarithmic factor) entanglement vs. communication tradeoffs for relational problems. The low end is: for any t>2, reducing shared entanglement from log^t(n) to o(log^{t-2}(n)) qubits can increase the communication required for solving a problem almost exponentially, from O(log^t(n)) to Ω(\sqrt n). The high end is: for any \eps>0, reducing shared entanglement from n^{1-\eps}log(n) to o(n^{1-\eps}/log(n)) can increase the required communication from O(n^{1-\eps}log(n)) to Ω(n^{1-\eps/2}/log(n)). The upper bounds are demonstrated via protocols which are exact and work in the \e{simultaneous message passing model}, while the lower bounds hold for \e{bounded-error protocols}, even in the more powerful \e{model of 1-way communication}. Our protocols use shared EPR pairs while the lower bounds apply to any sort of prior entanglement. We base the lower bounds on a strong direct product theorem for communication complexity of a certain class of relational problems. We believe that the theorem might have applications outside the scope of this work.
In the private simultaneous message (PSM) setting, kkk players obtain inputs xi∈{0,1}nx_i\in\{0,1\}^nxi​∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk)f(x_1,...,x_k)f(x1​,...,xk​) but no other information about (x1,...,xk)(x_1,...,x_k)(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 kkk-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)f(x_1,x_2)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 sss be the size of a quantum circuit computing fff, dfd_fdf​ be the circuit depth, kkk the number of players, nnn the number of bits received by each player, and εεε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅log⁡O(df)(s/ε)\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)PSMk∗​(f)≤(kn+s)⋅logO(df​)(s/ε). 2) The square of the Fourier 1 norm of fff, ∥f^∥12\Vert \hat{f}\Vert_1^2∥f^​∥12​, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12)\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)PSM(f)≤O(∥f^​∥12​). In proving the first upper bound, we generalize existing TTT-depth based techniques for NLQC from 222 to k≥2k\geq 2k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.