Rank Lower Bounds on Non-Local Quantum Computation

Asadi, Vahid R.; Culf, Eric; May, Alex

doi:10.4230/LIPIcs.ITCS.2025.11

Rank Lower Bounds on Non-Local Quantum Computation

Vahid R. Asadi

University of Waterloo, Canada Eric Culf University of Waterloo, Canada Alex May

Perimeter Institute for Theoretical Physics, Waterloo, Canada
University of Waterloo, Canada

Abstract

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.

Keywords and phrases:

Non-local quantum computation, quantum position-verification, conditional disclosure of secrets

Funding:

Alex May: Supported by the Perimeter Institute for Theoretical Physics. Research at Perimeter Institute is supported in part by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Colleges and Universities.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum information theory

Acknowledgements:

We thank Richard Cleve for helpful discussions during the development of this project. Harry Buhrman and François Le Gall suggested a connection between our bounds and non-deterministic rank, and consequently to non-deterministic quantum communication complexity.

DOI:

10.4230/LIPIcs.ITCS.2025.11

Event:

16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Editors:

Raghu Meka

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A non-local quantum computation (NLQC) replaces a local interaction with entanglement and a single simultaneous round of communication. See Figure 1. NLQC has applications in a number of areas, including quantum position-verification [19, 18, 20], Hamiltonian simulation [3], the AdS/CFT correspondence [21, 24, 22, 23], and information theoretic cryptography [2]. In all of these settings, we are interested in understanding the resources necessary to implement a given computation in the non-local form. Lower bounds on the entanglement necessary to complete a non-local computation are so far poorly understood but are central to these applications.

Two important classes of non-local computations are $f$ -routing and $f$ -BB84, both initially studied in the context of quantum position-verification [18, 10]. These computations involve classical inputs of size $n$ and $O(1)$ size quantum inputs. The local implementation of these computations involves computing a classical function $f$ from the classical inputs, then doing $O(1)$ quantum operations conditioned on the outcome. A longstanding goal has been to prove that the non-local implementation of the same computation requires growing quantum resources, and in particular growing entanglement. Recently, a bound on the quantum system size was proven in [10], but this assumes a purified view that absorbs classical processing into the quantum part of the computation.¹¹1See [6] for more discussion of this point. Another approach appears in [6], which bounds the number of quantum gates required in the non-local implementation. Here, we achieve the goal of lower bounding entanglement, at least as quantified by the Schmidt rank of the shared system, but at the cost of only considering protocols that complete $f$ -routing or $f$ -BB84 with perfect fidelity.²²2Actually, we will see that in the case of $f$ -routing we only need zero error on either $(x,y)\in f^{-1}(0)$ with bounded error for $(x,y)\in f^{-1}(1)$ , or vice versa.

(a)

(b)

Figure 1: Local and non-local computations. a) A channel

\mathcal{T}_{AB\rightarrow AB}

is implemented by directly interacting the input systems. b) A non-local quantum computation. The goal is for the action of this circuit on the

A B

systems to approximate the channel

\mathcal{T}_{AB\rightarrow AB}

.

It is a striking feature of non-local quantum computation that these mostly classical local computations require large quantum entanglement to implement non-locally. Beyond this, establishing this quantum-classical separation is relevant for quantum position-verification and for information theoretic cryptography. In a QPV scheme, we want to find operations that are as easy as possible for the honest player (who acts locally) to implement, but as hard as possible for the dishonest player (who implements an NLQC). Proving entanglement lower bounds for $f$ -routing or $f$ -BB84 gives a verification scheme where the honest player implements a nearly classical computation, while the dishonest player needs large quantum resources. This establishes the security of such QPV schemes under a bounded entanglement assumption. Our bound is only in the perfect setting and hence not immediately relevant to practical schemes, but represents a step towards proving entanglement lower bounds in the robust setting.³³3Many entanglement lower bounds apply in the robust setting, see e.g. [25, 16, 23, 9], but none grow with the classical input size. We achieve growth with classical input size at the expense of robustness.

Also relevant to our work is the connection between NLQC and information theoretic cryptography. In information theoretic cryptography, we wish to understand the communication and randomness cost to establish information theoretic privacy in various cryptographic settings. A primitive known as conditional disclosure of secrets (CDS) has been identified as one of the simplest settings where one can hope to understand the cost of privacy. CDS was initially studied in the context of private information retrieval [17], has applications in secret sharing [4], and shares a number of connections to communication complexity and interactive proofs [5]. In [2], $f$ -routing was shown to be closely related to CDS: lower bounds on entanglement cost in $f$ -routing give lower bounds on randomness in CDS. This opens a new avenue for quantum information techniques to make contributions to classical information theoretic cryptography.

1.1 Summary of our results

An $f$ -routing task is defined by a choice of Boolean function $f:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$ . In the task, Alice, on the left, receives a quantum system $Q$ of $O(1)$ size and a classical string $x\in\{0,1\}^{n}$ . Bob, on the right, receives $y\in\{0,1\}^{n}$ . Their goal is to bring $Q$ to Alice if $f(x,y)=0$ , and to Bob if $f(x,y)=1$ . In the setting of non-local computation, Alice and Bob may only use shared entanglement and a single round of communication to accomplish this. A difficulty in accomplishing this task arises since quantum mechanics prevents the system in register $Q$ from being copied, and hence apparently Alice is forced to decide alone whether to keep or send $Q$ . Furthermore, she doesn’t know where $Q$ is needed until learning $y$ , at which point the single round of communication has already passed.

Despite the difficulty, the $f$ -routing task can be completed for arbitrary functions $f$ , with the most efficient known protocols using $2^{\Theta(\sqrt{n\log n})}$ entanglement and communication for arbitrary functions [2], and efficient protocols known for some low complexity classes of functions [13, 12]. So far, only an $O(1)$ lower bound is known on entanglement in $f$ -routing, as we review in Appendix A. Here, we prove a new lower bound on $f$ -routing with one-sided perfection. We define a $(\epsilon_{0},\epsilon_{1})$ -correct $f$ -routing scheme as one which brings $Q$ to the left with fidelity at least $1-\epsilon_{0}$ when $(x,y)\in f^{-1}(0)$ and brings $Q$ to the right with fidelity at least $1-\epsilon_{1}$ when $(x,y)\in f^{-1}(1)$ . Define $FR_{0}(f)$ as the log of the minimal Schmidt rank of any entangled state that suffices to complete $f$ -routing with $\epsilon_{0}=0$ , $\epsilon_{1}>0$ for the function $f$ , and $FR_{1}(f)$ as the analogous quantity with $\epsilon_{0}>0,\epsilon_{1}=0$ . We prove the bounds

	$\displaystyle\textnormal{FR}_{0}(f)$	$\displaystyle\geq\frac{1}{4}\log\rank(g\|_{f})\enspace,$
	$\displaystyle\textnormal{FR}_{1}(f)$	$\displaystyle\geq\frac{1}{4}\log\rank(g\|_{\neg f})\enspace,$		(1)

where $g|_{f}(x,y)$ is a real-valued function that satisfies $f(x,y)=0\leftrightarrow g(x,y)=0$ . For some natural functions, this provides explicit strong lower bounds. For instance, taking $f=EQ$ to be the equality function, we are assured $g(x,y)$ is diagonal with non-zero entries on the diagonal and hence is of full rank, therefore $FR_{0}(EQ)\geq n/4$ . Similarly, we obtain linear lower bounds on $FR_{1}(NEQ)$ where $N E Q$ is the non-equality function.

As mentioned above, $f$ -routing is related closely to the conditional disclosure of secrets (CDS) primitive. A CDS instance is defined by a choice of Boolean function $f:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$ . In CDS, Alice and Bob receive inputs $x\in\{0,1\}^{n}$ and $y\in\{0,1\}^{n}$ respectively, while Alice additionally holds a secret string $s\in\{0,1\}^{k}$ . Alice and Bob share randomness, and send messages to a referee. Their goal is for the referee to be able to determine $s$ if and only if $f(x,y)=1$ .

In [2], it was shown that the randomness cost of CDS for a function $f$ upper bounds the entanglement cost of an $f$ -routing scheme for the same function. Because of this, our lower bounds on entanglement in $f$ -routing imply the same lower bounds on randomness in CDS. Because we only need one sided perfection for our bounds to apply, it is possible to bound CDS with imperfect correctness and perfect privacy (ppCDS), or perfect correctness but imperfect privacy (pcCDS)

	$\displaystyle\textnormal{pp}{\textnormal{CDS}}(f)$	$\displaystyle\geq\Omega(\log\rank(g\|_{f}))\enspace,$
	$\displaystyle\textnormal{pc}{\textnormal{CDS}}(f)$	$\displaystyle\geq\Omega(\log\rank(g\|_{\neg f}))\enspace.$

The expressions on the left hand side denote randomness costs. This provides a new technique for bounding randomness in CDS, which is proven using the quantum information perspective but can be phrased purely in terms of classical quantities.

We also prove lower bounds against the $f$ -BB84 class of non-local quantum computations. An $f$ -BB84 task is defined by a choice of Boolean function $f(x,y)$ with $x\in\{0,1\}^{n}$ given to Alice and $y\in\{0,1\}^{n}$ given to Bob. The system $Q$ is in one of the BB84 states $\{H^{f(x,y)}\ket{b}\}$ , with $b\in\{0,1\}$ and $f(x,y)\in\{0,1\}$ . Alice and Bob should both output $b$ .

The $f$ -BB84 task can be completed for arbitrary functions $f$ , with the most efficient known protocols using $2^{\Theta(n)}$ entanglement and communication for arbitrary functions [12].⁴⁴4Note that [12] deals with the $f$ -routing task, but their protocol is easily adapted to $f$ -BB84. We prove lower bounds on the log of the Schmidt rank of any resource state that suffices to complete $f$ -BB84 with probability $1$ . In particular, the same bound as in the $f$ -routing case applies,

\displaystyle\textnormal{FBB}84(f)\geq\frac{1}{4}\log\rank(g|_{f})\enspace,

where again $g$ is a function with zeros exactly at the zeros of $f$ . In a practical setting, $f$ -BB84 is of particular interest because it can be made loss-tolerant [1]. Unfortunately, our bound does not carry over to the noisy setting, so is not of immediate practical value. Nonetheless, our bound is the first non-trivial entanglement bound on $f$ -BB84. For $f$ -BB84, the bound above leads to linear lower bounds for the equality, non-equality, set-disjointness, and greater-than functions.

We can better understand our lower bounds by relating them to communication complexity. In a quantum communication complexity protocol, Alice holds $x\in\{0,1\}^{n}$ , Bob holds $y\in\{0,1\}^{n}$ , and Alice and Bob communicate qubits to determine $f(x,y)$ . The number of qubits of communication needed for Alice and Bob to output $1$ with non-zero probability when $f(x,y)=1$ , and never output $1$ when $f(x,y)=0$ is known as the quantum non-deterministic communication complexity, $QNP^{cc}(f)$ . Using the characterization of $QNP^{cc}$ in terms of the non-deterministic rank [14, 15], we obtain

	$\displaystyle\log\rank g\|_{f}$	$\displaystyle\geq(\textnormal{QNP}^{\textnormal{cc}}(f)-1)\enspace,$
	$\displaystyle\log\rank g\|_{\neg f}$	$\displaystyle\geq(\textnormal{coQNP}^{\textnormal{cc}}(f)-1)\enspace.$

This relates our lower bounds on CDS, $f$ -routing, and $f$ -BB84 to communication complexity.

2 Preliminaries

We let $\Psi^{+}_{AB}$ denote the maximally entangled state on $A B$ , so that

\displaystyle\ket{\Psi^{+}}_{AB}=\frac{1}{\sqrt{d}}\sum_{i=1}^{d}\ket{i}_{A}% \ket{i}_{B}\enspace,

and $\Psi^{+}_{AB}=\outerproduct{\Psi^{+}}{\Psi^{+}}_{AB}$ .

Given two density matrices $\rho,\sigma$ , we define the fidelity by

\displaystyle F(\rho,\sigma)=\tr\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}\enspace.

The fidelity is related to the one-norm distance by the Fuchs–van de Graff inequalities,

\displaystyle 1-F(\rho,\sigma)\leq\frac{1}{2}||\rho-\sigma||_{1}\leq\sqrt{1-(F% (\rho,\sigma))^{2}}\enspace.

The von Neumann entropy is defined by

\displaystyle S(A)=-\tr(\rho\log\rho)\enspace.

The quantum mutual information is defined by

\displaystyle I(A:B)_{\rho}=S(A)_{\rho}+S(B)_{\rho}-S(AB)_{\rho}\enspace,

and the conditional mutual information is defined by

\displaystyle S(A|B)_{\rho}=S(AB)_{\rho}-S(B)_{\rho}\enspace.

We will also make use of the following statement of continuity of the conditional entropy [26],

Theorem 1 ([26]).

Suppose that

\displaystyle\frac{1}{2}||\rho_{AB}-\sigma_{AB}||_{1}\leq\epsilon\enspace,

and let $h(x)=-x\log x-(1-x)\log(1-x)$ be the binary entropy function. Then

\displaystyle|S(A|B)_{\rho}-S(A|B)_{\sigma}|\leq 2\epsilon\log d_{A}+(1+% \epsilon)h\left(\frac{\epsilon}{1+\epsilon}\right)\enspace.

We will also make use of the following observation.

Observation 2.

Let $\rho_{AB}$ be a density matrix on the $A B$ system, $d$ be the dimension of subsystem $A$ , and $\rho_{B}$ be the marginal of $\rho_{AB}$ on the subsystem $B$ . Then we have

	$\displaystyle\tr(\rho_{AB}-\frac{\mathcal{I}_{A}}{d}\otimes\rho_{B})^{2}$	$\displaystyle=\tr(\rho^{2}_{AB}+\frac{\mathcal{I}_{A}}{d^{2}}\otimes\rho^{2}_{% B}-2\rho_{AB}(\frac{\mathcal{I}_{A}}{d}\otimes\rho_{B}))$
		$\displaystyle=\tr(\rho^{2}_{AB})+\frac{1}{d^{2}}\tr(\mathcal{I}_{A})\tr(\rho^{% 2}_{B})-\frac{2}{d}\tr_{B}(\rho^{2}_{B})$
		$\displaystyle=\tr(\rho^{2}_{AB})-\frac{1}{d}\tr(\rho^{2}_{B})$
		$\displaystyle=\tr(\rho^{2}_{AB})-\tr(\frac{\mathcal{I}_{A}}{d^{2}}\otimes\rho^% {2}_{B})\enspace.$

2.1 Communication complexity

We need some definitions and results from communication complexity. Consider two parties, Alice and Bob, with Alice given input $x\in\{0,1\}^{n}$ and Bob given input $y\in\{0,1\}^{n}$ . Alice and Bob exchange messages and Alice outputs a bit $z$ . The non-deterministic quantum communication complexity $\textnormal{QNP}^{cc}(f)$ , introduced in [14], is the minimal number of qubits Alice and Bob need to exchange to both output $1$ with probability larger than zero when $f(x,y)=1$ and both output $0$ with probability $1$ when $f(x,y)=0$ .

A matrix $M$ is called a non-deterministic communication complexity matrix for $f$ exactly when $M(x,y)\neq 0$ when $f(x,y)=1$ . The non-zero entries are allowed to be any complex numbers. The minimal rank of any non-deterministic communication complexity matrix for $f$ is denoted by $nrank(f)$ and called the non-deterministic rank. We have the following result from [15].

Theorem 3 ([15]).

The non-deterministic rank and the non-deterministic quantum communication complexity are related by

\displaystyle\textnormal{QNP}^{\textnormal{cc}}(f)=\lceil{\log(\textnormal{% nrank}(f))\rceil}+1\enspace.

3 Lower bounds from function rank

In this section, we first start by defining and analyzing the $f$ -routing task, and then prove our result in this setting. Next, we will show similar lower bounds for $f$ -BB84.

3.1 $𝒇$ -routing bounds from function rank

(a)

(b)

Figure 2: a) General NLQC implementing a

f

-routing position-verification scheme. The first round operations are quantum channels that depend on the inputs

x\in\{0,1\}^{n}

and

y\in\{0,1\}^{n}

. In the second round, Alice and Bob apply channels mapping to qubit systems

A

,

B

. If

f(x,y)=0

A

should be maximally entangled with the reference

\bar{Q}

. If

f(x,y)=1

then

B

should be maximally entangled with

R

. b) Non-local quantum computation implementing a

f

-BB84 position-verification scheme. The first round operations are quantum channels that depend on the inputs

x\in\{0,1\}^{n}

and

y\in\{0,1\}^{n}

. They communicate in one simultaneous exchange, and then apply measurements to their local systems. They succeed if

b=b^{\prime}=b^{\prime\prime}

, with

b

determined by measuring a reference maximally entangled with

Q

.

We begin with a definition of an $f$ -routing task.

Definition 4.

A qubit $𝐟$ -routing task is defined by a choice of Boolean function $f:\{0,1\}^{2n}\rightarrow\{0,1\}$ , and a $2$ dimensional Hilbert space $\mathcal{H}_{Q}$ . Inputs $x\in\{0,1\}^{n}$ and system $Q$ are given to Alice, and input $y\in\{0,1\}^{n}$ is given to Bob. Alice and Bob exchange one round of communication, with the combined systems received or kept by Bob labelled $M^{\prime}$ and the systems received or kept by Alice labelled $M$ . Label the combined actions of Alice and Bob in the first round as $\mathcal{N}^{x,y}_{Q\rightarrow MM^{\prime}}$ . The qubit $f$ -routing task is completed $(\epsilon_{0},\epsilon_{1})$ -correctly on an input $(x,y)$ if there exists a channel $\mathcal{D}^{x,y}_{M\rightarrow Q}$ such that,

\displaystyle\text{when}\,\,\,f(x,y)=0,\,\,\,F(\mathcal{D}^{x,y}_{M\rightarrow Q% }\circ\tr_{M^{\prime}}\circ\mathcal{N}^{x,y}_{Q\rightarrow MM^{\prime}}(\Psi^{% +}_{\bar{Q}Q}),\Psi^{+}_{\bar{Q}Q})\geq 1-\epsilon_{0}\enspace,

and there exists a channel $\mathcal{D}^{x,y}_{M^{\prime}\rightarrow Q}$ such that

\displaystyle\text{when}\,\,\,f(x,y)=1,\,\,\,F(\mathcal{D}^{x,y}_{M^{\prime}% \rightarrow Q}\circ\tr_{M}\circ\mathcal{N}^{x,y}_{Q\rightarrow MM^{\prime}}(% \Psi^{+}_{\bar{Q}Q}),\Psi^{+}_{\bar{Q}Q})\geq 1-\epsilon_{1}\enspace.

In words, Alice can recover $Q$ if $f(x,y)=0$ and Bob can recover $Q$ if ${f(x,y)=1}$ .

See the system labels shown in Figure 2(a). Note that we label $M_{0}M_{1}=M$ , $M_{0}^{\prime}M_{1}^{\prime}=M^{\prime}$ .

We will focus on $f$ -routing with $\epsilon_{0}=0$ , $\epsilon_{1}\geq 0$ so that the protocol is perfectly correct on zero instances of $f(x,y)$ , or with $\epsilon_{0}>0$ and $\epsilon_{1}=0$ so that the protocol is perfectly correct on $1$ instances. We define the entanglement cost of an $f$ -routing protocol to be the log of the minimal Schmidt rank of any resource system that can be used to perform the $f$ -routing task. In notation, we define $\textnormal{FR}_{0}(f)$ to be entanglement cost for $f$ -routing with $\epsilon_{0}=0$ , $\epsilon_{1}=0.05$ , $\textnormal{FR}_{1}(f)$ to be the entanglement cost when $\epsilon_{0}=0.05$ , $\epsilon_{1}=0$ .

Towards a lower bound in this setting, we first observe that $\rho_{\bar{Q}M^{\prime}}=\rho_{\bar{Q}}\otimes\rho_{M^{\prime}}$ iff $f(x,y)=0$ . We show this in the following lemma.

Lemma 5.

Suppose an $f$ -routing protocol is perfectly correct on zero instances, and $\epsilon_{1}<\epsilon_{1}^{*}$ correct on $1$ instances, where $\epsilon_{1}^{*}$ depends on $d_{Q}$ but is lower bounded by a constant. Then the mid-protocol state it produces, $\rho_{\bar{Q}M^{\prime}}$ , satisfies $\rho_{\bar{Q}M^{\prime}}=\rho_{\bar{Q}}\otimes\rho_{M^{\prime}}$ if and only if $f(x,y)=0$ .

Proof.

By correctness on $0$ instances, we have that

\displaystyle\text{when}\,\,\,f(x,y)=0,\,\,\,F(\mathcal{D}^{x,y}_{M\rightarrow Q% }\circ\tr_{M^{\prime}}\circ\mathcal{N}^{x,y}_{Q\rightarrow MM^{\prime}}(\Psi^{% +}_{\bar{Q}Q}),\Psi^{+}_{\bar{Q}Q})=1\enspace,

hence $f(x,y)=0$ implies Alice can produce a Bell state $\ket{\Psi^{+}}_{\bar{Q}Q}$ . By data processing we have

\displaystyle 2n=I(\bar{Q}:Q)_{\Psi^{+}_{\bar{Q}Q}}\leq I(\bar{Q}:M)_{\rho_{% \bar{Q}M}}\enspace,

but we also have the inequality

\displaystyle I(\bar{Q}:M)_{\rho}+I(\bar{Q}:M^{\prime})_{\rho}\leq 2S(\bar{Q})\enspace,

so that $I(\bar{Q}:M^{\prime})=0$ , which implies

\displaystyle\rho_{\bar{Q}M^{\prime}}=\rho_{\bar{Q}}\otimes\rho_{M^{\prime}}\enspace,

as needed. Conversely, if $f(x,y)=1$ we cannot have $\rho_{\bar{Q}M^{\prime}}=\rho_{\bar{Q}}\otimes\rho_{M^{\prime}}$ . To see why, first recall that $f$ -routing which is $\epsilon_{1}$ -correct on $1$ instances has that there exists a family of channels $\{D^{x,y}_{M^{\prime}\rightarrow Q}\}_{x,y}$ such that

\displaystyle\text{when}\,\,\,f(x,y)=1,\,\,\,F(\mathcal{D}^{x,y}_{M^{\prime}% \rightarrow Q}\circ\tr_{M}\circ\mathcal{N}^{x,y}_{Q\rightarrow MM^{\prime}}(% \Psi^{+}_{\bar{Q}Q}),\Psi^{+}_{\bar{Q}Q})\geq 1-\epsilon_{1}\enspace.

Define

\displaystyle\sigma_{\bar{Q}Q}=\mathcal{D}^{x,y}_{M^{\prime}\rightarrow Q}(% \rho_{\bar{Q}M^{\prime}})\enspace,

and use that by data processing,

\displaystyle I(\bar{Q}:M^{\prime})_{\rho_{\bar{Q}M}}\geq I(\bar{Q}:Q)_{\sigma% _{\bar{Q}Q}}\enspace.

But then by the Fuchs–van de Graff inequalities $\sigma_{\bar{Q}Q}$ is close in trace distance to $\Psi^{+}_{\bar{Q}Q}$ ,

\displaystyle\frac{1}{2}||\Psi^{+}_{\bar{Q}Q}-\sigma_{\bar{Q}Q}||_{1}\leq\sqrt% {2\epsilon_{1}-\epsilon_{1}^{2}}\equiv\mu\enspace,

and by continuity of the conditional entropy,

	$\displaystyle I(\bar{Q}:Q)_{\Psi^{+}}-I(\bar{Q}:Q)_{\sigma_{\bar{Q}Q}}$	$\displaystyle=S(\bar{Q}\|Q)_{\Psi^{+}}-S(\bar{Q}\|Q)_{\sigma}$
		$\displaystyle\leq 2\mu\log d_{\bar{Q}}+(1+\mu)h\left(\frac{\mu}{1+\mu}\right)\enspace,$

so that

\displaystyle 2\log d_{\bar{Q}}-2\mu\log d_{\bar{Q}}+(1+\mu)h\left(\frac{\mu}{% 1+\mu}\right)\leq I(\bar{Q}:Q)_{\sigma}\enspace.

We have that $\sigma$ is not a tensor product whenever the left hand side of the equation above is strictly positive. For $d_{Q}=2$ , this occurs for $\epsilon_{1}>\epsilon_{1}^{*}\approx 0.08$ , and $\epsilon_{1}^{*}$ approaches $1$ as $d_{Q}\rightarrow\infty$ . $\hfill\blacktriangleleft$

Next, we define what we call a structure function for a protocol. The structure function is computed from the mid-protocol density matrix $\rho_{\bar{Q}MM^{\prime}}$ , and (as we will see) captures the zeros in $f(x,y)$ .

Definition 6.

Given an $f$ -routing protocol with mid-protocol density matrix $\rho_{\bar{Q}MM^{\prime}}$ , define the structure function $g(x,y)$ according to

\displaystyle g(x,y)=\tr(\rho_{\bar{Q}M^{\prime}}-\frac{\mathcal{I}}{d_{\bar{Q% }}}\otimes\rho_{M^{\prime}})^{2}\enspace.

We claim that $g(x,y)$ captures some aspect of the structure in the function $f$ which must be present in a correct $f$ -routing protocol. More concretely we have the following.

Lemma 7.

In a perfectly correct $f$ -routing protocol, the structure function $g(x,y)$ is zero if and only if $f(x,y)=0$ .

Proof.

This follows because $g(x,y)=0$ is zero if and only if $\rho_{\bar{Q}M^{\prime}}=\frac{\mathcal{I}}{d_{\bar{Q}}}\otimes\rho_{M^{\prime}}$ , and Lemma 5 shows we have this tensor product form if and only if $f(x,y)=0$ . $\hfill\blacktriangleleft$

Our next job is to relate the function $g(x,y)$ to the entanglement available to Alice and Bob. We prove the following lemma.

Lemma 8.

An $f$ -routing protocol that uses a resource system with Schmidt rank $d_{E}$ has a structure function of the form

\displaystyle g(x,y)=\sum_{I=1}^{d_{E}^{4}}f_{I}(x)f_{I}^{\prime}(y)\enspace.

Proof.

From the general form of a non-local quantum computation protocol, the density matrix $\rho_{\bar{Q}M_{0}^{\prime}M_{1}^{\prime}}(x,y)$ can be expressed as

\displaystyle\rho_{\bar{Q}M_{0}^{\prime}M_{1}^{\prime}}=\mathcal{N}^{x}_{QL% \rightarrow M_{0}^{\prime}}\otimes\mathcal{M}^{y}_{\bar{Q}\rightarrow M_{1}^{% \prime}}(\Psi^{+}_{\bar{Q}Q}\otimes\outerproduct{\Psi}{\Psi}_{LR})\enspace.

We will write $\ket{\Psi}_{LR}$ in the Schmidt basis,

\displaystyle\ket{\Psi}_{LR}=\sum_{i=1}^{d_{E}}\ket{i}_{L}\ket{i}_{R}\enspace,

with un-normalized vectors $\ket{i}_{L},\ket{i}_{R}$ . Then we get

	$\displaystyle\rho_{\bar{Q}M_{0}^{\prime}M_{1}^{\prime}}$	$\displaystyle=\sum_{i,j=1}^{d_{E}}\mathcal{N}^{x}_{QL\rightarrow M_{0}^{\prime% }}(\Psi^{+}_{Q\bar{Q}}\otimes\outerproduct{i}{j}_{L})\otimes\mathcal{M}^{y}_{R% \rightarrow M_{1}^{\prime}}(\outerproduct{i}{j}_{R})$
		$\displaystyle=\sum_{i,j=1}^{d_{E}}A^{x,i,j}_{\bar{Q}M_{0}^{\prime}}\otimes B^{% y,i,j}_{M_{1}^{\prime}}\enspace.$

We can also compute the trace over $\bar{Q}$ where we define $A$ and $B$ in the second line of the previous equation and get

\displaystyle\rho_{M_{0}^{\prime}M_{1}^{\prime}}

\displaystyle=\sum_{i,j=1}^{d_{E}}A^{x,i,j}_{M_{0}^{\prime}}\otimes B^{y,i,j}_% {M_{1}^{\prime}}\enspace.

Next, we compute $g(x,y)$ . It is convenient to make use of 2 to write

\displaystyle g(x,y)=\tr(\rho_{\bar{Q}M^{\prime}}^{2}-\frac{\mathcal{I}}{d_{% \bar{Q}}^{2}}\otimes\rho_{M^{\prime}}^{2})\enspace.

Inserting the forms of $\rho_{\bar{Q}M^{\prime}}$ and $\rho_{M^{\prime}}$ into this, we obtain

	$\displaystyle g(x,y)$	$\displaystyle=\sum_{i,j,i^{\prime},j^{\prime}=1}^{d_{E}}\tr\left(\left(A^{x,i,% j}_{QM_{0}^{\prime}}A^{x,i^{\prime},j^{\prime}}_{QM_{0}^{\prime}}-\frac{% \mathcal{I}}{d_{Q}^{2}}\otimes A^{x,i,j}_{M_{0}^{\prime}}A^{x,i^{\prime},j^{% \prime}}_{M_{0}^{\prime}}\right)\otimes B^{y,i,j}_{M_{1}^{\prime}}B^{y,i^{% \prime},j^{\prime}}_{M_{1}^{\prime}}\right)$
		$\displaystyle=\sum_{I=1}^{d_{E}^{4}}f_{I}(x)f^{\prime}_{I}(y)\enspace,$

as needed. $\hfill\blacktriangleleft$

We can view $g(x,y)$ as a matrix, and $f_{I}(x)$ , $f_{I}^{\prime}(y)$ as vectors so that the minimal number of terms appearing in this sum is the rank of the matrix $g(x,y)$ . Thus we obtain the lower bound

\displaystyle\boxed{\textnormal{FR}_{0}(f)\geq\frac{1}{4}\log\rank g|_{f}% \enspace.}

(2)

We know that $g$ is zero and non-zero for the same inputs as $f$ , for which we have given the $g|_{f}$ notation as a reminder. In some cases, this is enough to let us lower bound the rank of $g$ , as we discuss below.

We can also notice that we can reverse the role of $M$ and $M^{\prime}$ , and assume perfect correctness on $1$ instances, leading to a similar bound,

\displaystyle\boxed{\textnormal{FR}_{1}(f)\geq\frac{1}{4}\log\rank g|_{\neg f}% \enspace,}

(3)

where $\neg f$ is the negation of $f$ .

We can also rephrase the above bounds in terms of the non-deterministic quantum communication complexity. Observe that

\displaystyle\rank g|_{f}\geq\text{nrank}(f)\enspace.

(4)

Because the non-deterministic rank considers matrices with arbitrary complex values where $f(x,y)=1$ , while $g|_{f}$ has the further constraint that it has positive real values when $f(x,y)=1$ , it is possible there are functions for which $\rank g|_{f}>\text{nrank}(f)$ . We have not looked for such examples.

Using Equation 4 and Theorem 3, we obtain

	$\displaystyle\textnormal{FR}_{0}(f)$	$\displaystyle\geq\frac{1}{4}(\textnormal{QNP}^{\textnormal{cc}}(f)-1)\enspace,$
	$\displaystyle\textnormal{FR}_{1}(f)$	$\displaystyle\geq\frac{1}{4}(\textnormal{coQNP}^{\textnormal{cc}}(f)-1)\enspace.$

Further, for $f$ -routing which has two sided perfection, we have

\displaystyle\text{p}\textnormal{FR}(f)\geq\frac{1}{4}\max\{\textnormal{QNP}^{% \textnormal{cc}}(f),\textnormal{coQNP}^{\textnormal{cc}}(f)\}-1\enspace.

Or, labelling the set of function families which can be $f$ -routed on with polylogarithmic entanglement by $p F R$ , we have

\displaystyle\text{p}\textnormal{FR}\subseteq\textnormal{QNP}^{\textnormal{cc}% }\cap\textnormal{coQNP}^{\textnormal{cc}}\enspace.

In the classical setting, $\textnormal{NP}^{\textnormal{cc}}\cap\textnormal{coNP}^{\textnormal{cc}}=\text% {P}^{\textnormal{cc}}$ [8], but (to our knowledge) it is not known if the quantum analogue holds.

3.2 $𝒇$ -BB84 bounds

Definition 9.

A qubit $𝐟$ -BB84 task is defined by a choice of Boolean function $f:\{0,1\}^{2n}\rightarrow\{0,1\}$ , and a $2$ dimensional Hilbert space $\mathcal{H}_{Q}$ . Inputs $x\in\{0,1\}^{n}$ and system $Q$ are given to Alice, and input $y\in\{0,1\}^{n}$ is given to Bob. The $Q$ system is in the maximally entangled state with a reference $\bar{Q}$ . Alice and Bob exchange one round of communication, with the combined systems received or kept by Bob labelled $M$ and the systems received or kept by Alice labelled $M^{\prime}$ . Define projectors

\displaystyle\Pi^{q,b}=H^{q}\outerproduct{b}{b}H^{q}\enspace.

The qubit $f$ -BB84 task is completed $\epsilon$ -correctly on input $(x,y)$ if there exist POVM’s $\{\Lambda^{x,y,0}_{M},\Lambda^{x,y,1}_{M}\}$ , $\{\Lambda^{x,y,0}_{M^{\prime}},\Lambda^{x,y,1}_{M^{\prime}}\}$ such that,

\displaystyle\tr(\Pi^{f(x,y),b}_{\bar{Q}}\otimes\Lambda^{x,y,b}_{M}\otimes% \Lambda^{x,y,b}_{M}\rho_{\bar{Q}MM^{\prime}})\geq 1-\epsilon\enspace.

That is, Alice and Bob succeed when they both obtain the same outcome as the referee.

We will focus here on perfectly correct $f$ -BB84, where $\epsilon=0$ .

As in the analysis of $f$ -routing, we look for a function of the density matrix prepared by the protocol which captures the structure of the function $f(x,y)$ . We define this next.

Definition 10.

Given a $f$ -BB84 protocol with mid-protocol density matrix $\rho_{\bar{Q}MM^{\prime}}$ , define the structure function by first defining the density matrices

	$\displaystyle\rho^{0}_{M}$	$\displaystyle=\bra{0}_{\bar{Q}}\rho_{\bar{Q}M}\ket{0}_{\bar{Q}}\enspace,$
	$\displaystyle\rho^{1}_{M}$	$\displaystyle=\bra{1}_{\bar{Q}}\rho_{\bar{Q}M}\ket{1}_{\bar{Q}}\enspace.$

These are the post measurement states on $M$ when the referee measures $R$ in the computational basis, and finds outcome $b=0,1$ . We similarly define $\rho^{0}_{M^{\prime}}$ and $\rho^{1}_{M^{\prime}}$ . Then define

\displaystyle g(x,y)=\tr(\rho_{M}^{0}\rho_{M}^{1})+\tr(\rho_{M^{\prime}}^{0}% \rho_{M^{\prime}}^{1})\enspace.

We show this has the same zeros as $f(x,y)$ next.

Lemma 11.

In a perfectly correct $f$ -BB84 protocol, the structure function $g(x,y)$ is zero if and only if $f(x,y)$ is zero.

Proof.

We first establish the following fact: $g(x,y)=0$ if and only if both $\rho_{M}^{0}$ and $\rho_{M}^{1}$ have non-overlapping support and $\rho_{M^{\prime}}^{0}$ and $\rho_{M^{\prime}}^{1}$ have non-overlapping support. To see this, first assume $g(x,y)=0$ . Then diagonalize $\rho^{0}_{M}$ and $\rho_{M}^{1}$ so that

	$\displaystyle\rho^{0}_{M}$	$\displaystyle=\sum_{i}\lambda_{i}\outerproduct{\psi_{i}}{\psi_{i}}\enspace,$
	$\displaystyle\rho^{1}_{M}$	$\displaystyle=\sum_{j}\mu_{j}\outerproduct{\phi_{j}}{\phi_{j}}\enspace,$

with $\lambda_{i},\mu_{j}>0$ and we have from $g(x,y)=0$ that $\tr(\rho^{0}_{M}\rho^{1}_{M})=0$ , so that

\displaystyle 0=\tr(\rho^{0}_{M}\rho^{1}_{M})=\sum_{i,j}\lambda_{i}\mu_{j}|% \innerproduct{\phi_{j}}{\psi_{i}}|^{2}\enspace.

But this occurs if and only if

\displaystyle\forall i,j,\,\,\,\,\,\innerproduct{\phi_{j}}{\psi_{i}}=0\enspace,

so that $\rho_{M}^{0}$ and $\rho^{1}_{M}$ have non-overlapping support, as needed. We can similarly conclude $\rho^{0}_{M^{\prime}}$ and $\rho^{1}_{M^{\prime}}$ have non-overlapping support. For the converse, a direct calculation shows both $\tr(\rho^{0}_{M}\rho^{1}_{M})$ and $\tr(\rho^{0}_{M^{\prime}}\rho^{1}_{M^{\prime}})$ are 0.

Now we use this fact to relate $g(x,y)=0$ and $f(x,y)=0$ . First, suppose that $f(x,y)=0$ . Then, the referee measures in the computational basis and so after the referee’s measurement, Alice holds either $\rho_{M}^{0}$ or $\rho_{M}^{1}$ depending on the referee’s measurement outcome. By assumption she can determine the measurement outcome perfectly, so she must be able to distinguish $\rho^{0}_{M}$ and $\rho_{M}^{1}$ perfectly. Thus $\rho_{M}^{0}$ and $\rho_{M}^{1}$ have orthogonal support. Considering the same line of reasoning but now considering Bob, whose post-measurement state is $\rho_{M^{\prime}}^{0}$ or $\rho_{M^{\prime}}^{1}$ , these density matrices too must have orthogonal support. But then from the fact above we have $g(x,y)=0$ .

Next suppose that $f(x,y)=1$ . Then the referee measures in the Hadamard basis, so Alice’s post-measurement state is one of

\displaystyle\rho^{\pm}_{M}=\bra{\pm}_{\bar{Q}}\rho_{\bar{Q}M}\ket{\pm}_{\bar{% Q}}\enspace.

For Alice to be able to determine the referee’s measurement outcome, $\rho_{M}^{+}$ and $\rho_{M}^{-}$ must have orthogonal support, so that

\displaystyle 0=\tr(\rho_{M}^{+}\rho_{M}^{-})\enspace.

(5)

We claim that this implies $\tr(\rho_{M}^{0}\rho_{M}^{1})>0$ . To see why, note

\displaystyle\rho_{M}^{\pm}=\frac{1}{2}\left(\rho_{M}^{0}+\rho_{M}^{1}\pm\bra{% 0}_{\bar{Q}}\rho_{\bar{Q}M}\ket{1}_{\bar{Q}}\pm\bra{1}_{\bar{Q}}\rho_{\bar{Q}M% }\ket{0}_{\bar{Q}}\right)\enspace.

Inserting this into Equation 5, we find that

\displaystyle\tr(\rho_{M}^{0}\rho_{M}^{1})=\frac{1}{2}\left(\tr((\rho_{M}^{0})% ^{2})+\tr((\rho_{M}^{1})^{2})\right)>0\enspace.

Again, repeating the argument considering Bob’s post-measurement state and his ability to determine the referee’s measurement outcome, we also find that

\displaystyle\tr(\rho_{M^{\prime}}^{0}\rho_{M^{\prime}}^{1})>0\enspace.

Thus, $g(x,y)>0$ as needed. $\hfill\blacktriangleleft$

Lemma 12.

An $f$ -BB84 protocol that uses a resource system with Schmidt rank $d_{E}$ has a structure function of the form

\displaystyle g(x,y)=\sum_{I=1}^{2d_{E}^{4}}f_{I}(x)f_{I}^{\prime}(y)\enspace.

Proof.

From the general form of a non-local quantum computation protocol, the density matrix $\rho_{\bar{Q}M_{0}^{\prime}M_{1}^{\prime}}(x,y)$ can be expressed as

\displaystyle\rho_{\bar{Q}M_{0}^{\prime}M_{1}^{\prime}}=\mathcal{N}^{x}_{QL% \rightarrow M_{0}^{\prime}}\otimes\mathcal{M}^{y}_{R\rightarrow M_{1}^{\prime}% }(\Psi_{\bar{Q}Q}\otimes\outerproduct{\Psi}{\Psi}_{LR})\enspace.

We will write $\ket{\Psi}_{LR}$ in the Schmidt basis,

\displaystyle\ket{\Psi}_{LR}=\sum_{i=1}^{d_{E}}\ket{i}_{L}\ket{i}_{R}\enspace,

with un-normalized vectors $\ket{i}_{L},\ket{i}_{R}$ . Then we get

	$\displaystyle\rho_{\bar{Q}M_{0}^{\prime}M_{1}^{\prime}}$	$\displaystyle=\sum_{i,j=1}^{d_{E}}\mathcal{N}^{x}_{QL\rightarrow M_{0}^{\prime% }}(\Psi^{+}_{\bar{Q}Q}\otimes\outerproduct{i}{j}_{L})\otimes\mathcal{M}^{y}_{R% \rightarrow M_{1}^{\prime}}(\outerproduct{i}{j}_{R})$
		$\displaystyle=\sum_{i,j=1}^{d_{E}}A^{x,i,j}_{\bar{Q}M_{0}^{\prime}}\otimes B^{% y,i,j}_{M_{1}^{\prime}}\enspace.$

We can also project $\bar{Q}$ into $\ket{b}_{\bar{Q}}$ , $b\in\{0,1\}$ to get $\rho_{M^{\prime}}^{i}$ ,

\displaystyle\rho_{M_{0}^{\prime}M_{1}^{\prime}}^{b}

\displaystyle=\sum_{i,j=1}^{d_{E}}A^{b,x,i,j}_{M_{0}^{\prime}}\otimes B^{y,i,j% }_{M_{1}^{\prime}}\enspace.

A similar calculation gives $\rho_{M}^{b}$ . Inserting these expressions into $g(x,y)$ , we obtain an expression of the form

\displaystyle g(x,y)=\sum_{I=1}^{2d_{E}^{4}}f_{I}(x)f^{\prime}_{I}(y)\enspace.

where the $d_{E}^{4}$ appears because each of the two trace terms in $g(x,y)$ comes with a product of two density matrices, each of which involves two sums running from $1$ to $d_{E}$ . We collect all of these sums into the index $i$ appearing here, which now runs 1 to $2d_{E}^{4}$ . $\hfill\blacktriangleleft$

Similarly to the case of $f$ -routing, the above lemma implies that

\displaystyle\boxed{\textnormal{FBB}84(f)\geq\frac{1}{4}(\log\rank g|_{f}-1)% \enspace.}

(6)

where the notation $g|_{f}$ indicates as before that $g$ is zero and non-zero on the same inputs as $f(x,y)$ .

Also similarly to the case of $f$ -routing, we can use Equation 4 and Theorem 3, we obtain

\displaystyle\textnormal{FBB}84(f)\geq\frac{1}{4}(\textnormal{QNP}^{% \textnormal{cc}}(f)-2)\enspace.

4 A new lower bound technique for CDS

It was recently understood [2] that $f$ -routing is closely related to a classical information theoretic primitive known as conditional disclosure of secrets. As a consequence, our new lower bounds on $f$ -routing imply lower bounds on CDS. In this work, we will informally describe these lower bounds, but see [7] for a more complete treatment.

The conditional disclosure of secrets primitive involves three parties, Alice, Bob, and the referee. Alice receives input $x\in\{0,1\}^{n}$ , and Bob receives $y\in\{0,1\}^{n}$ . Alice additionally holds a secret string $z$ , and Alice and Bob share a random string $r$ . Alice and Bob do not communicate, but each sends a message to the referee. The goal is for the referee to be able to learn $z$ if and only if a function $f(x,y)=1$ , where the choice of the function $f$ is known to all parties, and the referee knows both inputs $x$ and $y$ .

The quantum generalization of CDS, conditional disclosure of quantum secrets or CDQS, was recently defined [2]. In the quantum setting, Alice and Bob share a quantum state (rather than a random string) and can send quantum messages to the referee. The secret can now also be taken to be a quantum system $Q$ rather than a classical string. The security and privacy conditions are similar to the classical case: correctness means that the referee can invert the map on $Q$ applied by Alice and Bob when $f(x,y)=1$ , and security means the map applied by Alice and Bob is close to completely depolarizing when $f(x,y)=0$ . In general, we allow small correctness and privacy errors. See [2] for a formal definition.

We define the minimal number of qubits in Alice and Bob’s shared resource system in a CDQS scheme for function $f$ by $\textnormal{CDQS}(f)$ . If we require the protocol to be perfectly correct we write $\textnormal{pc}{\textnormal{CDQS}}(f)$ , and when perfectly private we write $\textnormal{pp}{\textnormal{CDQS}}(f)$ . Similarly, for classical CDS, we use ${\textnormal{CDS}}(f)$ to denote the randomness cost of classical CDS. Again we modify this to $\textnormal{pc}\textnormal{CDS}(f)$ , $\textnormal{pp}\textnormal{CDS}(f)$ for perfectly correct and perfectly private CDS randomness cost.⁵⁵5The reader should be warned that the same notation is used to denote the communication cost in other papers on CDS.

In [2], it was shown that a good classical CDS protocol for a function $f$ implies a good quantum CDS protocol for the same function. This leads to⁶⁶6In fact, to obtain this we also need an amplification result which appears in [7]. These bounds are proved formally there.

\displaystyle\textnormal{CDS}(f)=\Omega(\textnormal{CDQS}(f))\enspace,

and the same relationships hold for the perfectly correct and perfectly private variants. Also in [2], it was shown that a good CDQS leads to a good $f$ -routing protocol, and vice versa. This leads to

\displaystyle\textnormal{CDQS}(f)=\Theta(\textnormal{FR}(f))\enspace,

Also, the perfectly private and perfectly correct variants are related to $f$ -routing with one-sided errors,

	$\displaystyle\textnormal{pp}\textnormal{CDQS}(f)=\Theta(\textnormal{FR}_{0}(f)% )\enspace,$
	$\displaystyle\textnormal{pc}\textnormal{CDQS}(f)=\Theta(\textnormal{FR}_{1}(f)% )\enspace.$

This implies our lower bounds from Equation 2 and Equation 3 apply to CDS,

	$\displaystyle\textnormal{pp}\textnormal{CDQS}(f)=\Omega(\log\rank{g\|_{f}})\enspace,$
	$\displaystyle\textnormal{pc}\textnormal{CDQS}(f)=\Omega(\log\rank{g\|_{\neg f}}% )\enspace.$

This also gives lower bounds in terms of $\textnormal{QNP}^{\textnormal{cc}}(f)$ and $\textnormal{coQNP}^{\textnormal{cc}}(f)$ , and the upper bound can be written in terms of classical CDS. In this way, we can obtain the lower bound

\displaystyle\boxed{\textnormal{pc}\textnormal{CDS}(f)\geq\Omega(\textnormal{% coQNP}^{\textnormal{cc}}(f))\enspace.}

This is similar to a lower bound obtained in [5],

\displaystyle\textnormal{pc}\textnormal{CDS}(f)\geq\frac{1}{2}\textnormal{coNP% }^{\textnormal{cc}}(f)\enspace.

The lower bound on perfectly private CDS randomness cost seems to be new,

\displaystyle\boxed{\textnormal{pp}\textnormal{CDS}(f)\geq\Omega(\textnormal{% QNP}^{\textnormal{cc}}(f))\enspace.}

For perfect CDS, we can bound the randomness cost by the maximum of the $\textnormal{QNP}^{\textnormal{cc}}$ and $\textnormal{coNP}^{\textnormal{cc}}$ cost. If we let pCDS denote the set of families of functions for which CDS can be implemented with perfect correctness and perfect privacy using polylogarithmic randomness. Then we obtain

\displaystyle\text{p}\textnormal{CDS}\subseteq\textnormal{QNP}^{\textnormal{cc% }}\cap\textnormal{coNP}^{\textnormal{cc}}\enspace.

5 Application to concrete functions

We detail lower bounds for equality, non-equality, greater than and less than, set-disjointness, and set-intersection below. We were not able to use our technique to lower bound inner product.

Our results are summarized succinctly in Figure 3.

Function	pFR	$\textnormal{FR}_{1}$	$\textnormal{FR}_{0}$	FR
Equality	${\Theta(n)}$	$\Theta(1)$	${\Theta(n)}$	$\Theta(1)$
Non-Equality	$\Theta(n)$	$\Theta(n)$	$\Theta(1)$	$\Theta(1)$
Inner-Product	$O(n)$ , $\Omega(1)$	$O(n)$ , $\Omega(1)$	$O(n)$ , $\Omega(1)$	$O(n)$ , $\Omega(1)$
Greater-Than	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$O(n)$ , $\Omega(1)$
Set-Intersection	$\Theta(n)$	$\Theta(n)$	$O(n)$ , $\Omega(1)$	$O(n)$ , $\Omega(1)$
Set-Disjointness	$\Theta(n)$	$O(n)$ , $\Omega(1)$	$\Theta(n)$	$O(n)$ , $\Omega(1)$

Figure 3: Known upper and lower bounds on entanglement cost (quantified by the log Schmidt rank) in

f

-routing for natural functions. No non-trivial lower bounds on entanglement were known prior to this work. Linear upper bounds on all of these functions follow from [12, 13]. The

\Omega(1)

lower bounds follow from Appendix A.

Equality and non-equality

Choose $f(x,y)$ to be the equality function,

\displaystyle EQ(x,y)=\begin{cases}0,&x\neq y\\ 1,&x=y\end{cases}\enspace.

Then $g(x,y)$ is zero except on the diagonal, which forces it to have full rank, so from Equation 2 and Equation 6

\displaystyle\textnormal{FR}_{0}(EQ)\geq\frac{n}{4},\,\,\,\,\,\,\,\,\,\,\,\,% \text{p}\textnormal{FBB}84(EQ)\geq\frac{1}{4}(n-1)\enspace.

For the not-equals function, we can use bound from Equation 3 to obtain

\displaystyle\textnormal{FR}_{1}(NEQ)\geq\frac{n}{4}\enspace.

Greater and less than

Similarly, the “greater than” function,

\displaystyle GT(x,y)=\begin{cases}0,&x<y\\ 1,&x\geq y\end{cases}\enspace.

is upper triangular with non-zero elements on the diagonal, so it also has full rank, and we obtain a linear lower bound.

\displaystyle\textnormal{FR}_{0}(GT)\geq\frac{n}{4},\,\,\,\,\,\,\,\,\,\,\,\,% \text{p}\textnormal{FBB}84(GT)\geq\frac{1}{4}(n-1)\enspace.

Further, because the negation of Greater-Than is also full rank, we can also bound $fR_{1}$ ,

\displaystyle\textnormal{FR}_{1}(GT)\geq\frac{n}{4}\enspace.

The same bounds hold for the “less than” function.

Set-Intersection and set-disjointness

Set disjointness is upper left triangular.⁷⁷7To see why, consider that on the diagonal of the truth table running top right to bottom left, we have that $x+y=11...11$ , the all $1$ ’s string. This means $x$ and $y$ must have non-zero values in non-overlapping locations, e.g. for two bits this diagonal consists of $(x=00,y=11)$ , $(x=01,y=10)$ , $(x=10,y=01)$ and $(x=11,y=00)$ . Moving downward from any entry on that diagonal $y$ becomes larger, so must now have an overlapping entry with the $x$ string. This implies it is full rank, therefore

\displaystyle\textnormal{FR}_{0}(DISJ)\geq\frac{n}{4},\,\,\,\,\,\,\,\,\,\,\,% \text{p}\textnormal{FBB}84(DISJ)\geq\frac{1}{4}(n-1)\enspace.

Since the negation of set intersection is set disjointness and hence of full rank, we also obtain

\displaystyle\textnormal{FR}_{1}(INT)\geq\frac{n}{4}\enspace.

6 Discussion

In this article, we have given the first non-trivial lower bounds on entanglement in the $f$ -routing and $f$ -BB84 tasks. For some natural functions, including equality, greater than, and set-disjointness, our lower bounds are linear in the classical input size. This realizes a long standing aspiration for $f$ -routing and $f$ -BB84 based position-verification schemes: that an honest party can compute a simple, classical function and perform $O(1)$ quantum operations, while a dishonest party must use entanglement that grows with the size of the classical input strings. However, this result comes at the unfortunate cost of requiring perfect correctness for the lower bounds to apply. Nonetheless, even proving bounds in this perfect case has so far been elusive, and we hope that our progress may open future avenues toward robust linear lower bounds.

An interesting observation is that our bounds lead to relations among operational quantities, e.g.

\displaystyle\textnormal{FR}_{0}(f)\geq\textnormal{QNP}^{cc}(f)\enspace

but are derived by separately relating $\textnormal{FR}_{0}$ and $\textnormal{QNP}^{cc}$ to the non-deterministic rank. Given this result, it would be natural to expect a reduction at an operational level from $f$ -routing to quantum non-deterministic communication complexity, but we know of no such reduction.

As a consequence of our lower bounds, we also obtain a new lower bound technique for randomness complexity in CDS with either perfect privacy or perfect correctness. We highlight the bound

\displaystyle\boxed{\textnormal{pp}\textnormal{CDS}(f)\geq\Omega(\textnormal{% QNP}^{\textnormal{cc}}(f))\enspace.}

which appears to be new and incomparable to earlier bounds on ppCDS. It would be interesting to construct explicit functions for which this lower bound is tighter than earlier ones, for instance, bounds from the $\text{PP}^{\textnormal{cc}}$ cost of $f$ [4].

References

[1] Rene Allerstorfer, Andreas Bluhm, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel. Making existing quantum position verification protocols secure against arbitrary transmission loss. arXiv preprint, 2023. arXiv:2312.12614.
[2] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. arXiv preprint, 2023. arXiv:2306.16462.
[3] Harriet Apel, Toby Cubitt, Patrick Hayden, Tamara Kohler, and David Pérez-García. Security of position-based quantum cryptography limits hamiltonian simulation via holography. arXiv preprint, 2024. arXiv:2401.09058.
[4] Benny Applebaum and Barak Arkis. On the power of amortization in secret sharing: d-uniform secret sharing and cds with constant information rate. ACM Transactions on Computation Theory (TOCT), 2020. doi:10.1145/3417756.
[5] Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe. Journal of Cryptology, 2021. doi:10.1007/s00145-021-09376-1.
[6] Vahid R. Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification. arXiv preprint, 2024. arXiv:2402.18648.
[7] Vahid R Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources. arXiv preprint, 2024. arXiv:2404.14491.
[8] László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (SFCS 1986). IEEE, 1986. doi:10.1109/SFCS.1986.15.
[9] Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 2011. doi:10.1088/1367-2630/13/9/093036.
[10] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, 2022. doi:10.1038/s41567-022-01577-0.
[11] 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. doi:10.1137/130913687.
[12] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, 2013. doi:10.1145/2422436.2422455.
[13] Joy Cree and Alex May. Code-routing: a new attack on position verification. Quantum, 2023. doi:10.22331/q-2023-08-09-1079.
[14] Ronald de Wolf. Characterization of non-deterministic quantum query and quantum communication complexity. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000. doi:10.1109/CCC.2000.856758.
[15] Ronald De Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 2003. doi:10.1137/S0097539702407345.
[16] Llorenç Escolà-Farràs, Léo Colisson Palais, and Florian Speelman. A quantum cloning game with applications to quantum position verification. arXiv preprint, 2024. arXiv:2410.22157.
[17] Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. Journal of Computer and System Sciences, 2000. doi:10.1006/jcss.1999.1689.
[18] Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 2011. doi:10.1103/PhysRevA.84.012326.
[19] Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, 2006. US Patent 7,075,438.
[20] Robert Malaney. The quantum car. IEEE Wireless Communications Letters, 2016. doi:10.1109/LWC.2016.2607740.
[21] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019. doi:10.1007/JHEP10(2019)233.
[22] Alex May. Holographic quantum tasks with input and output regions. Journal of High Energy Physics, 2021. doi:10.1007/JHEP08(2021)055.
[23] Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 2022. doi:10.22331/q-2022-11-28-864.
[24] Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020. doi:10.1007/JHEP08(2020)132.
[25] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 2013. doi:10.1088/1367-2630/15/10/103002.
[26] Andreas Winter. Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints. Communications in Mathematical Physics, 2016. doi:10.1007/s00220-016-2609-8.

Appendix A $\Omega(1)$ lower bounds on entanglement in $𝒇$ -routing

It is straightforward to establish an $\Omega(1)$ lower bound on entanglement for $f$ -routing, though to our knowledge this lower bound is not recorded elsewhere in the literature, so we give it here. Note that for $f$ -BB84 a $\Omega(1)$ lower bound follows from theorem 6.1 in [11].

To show the lower bound in the $f$ -routing setting, we will first notice that in a $f$ -routing task we can always replace a mixed resource state $\Psi_{LR}$ with a pure state $\ket{\Psi}_{LR}$ . Our lower bound will apply whenever $f(x,y)$ has an input $x=x_{0}$ such that $f(x_{0},y)=F(y)$ is non-constant. We will assume perfect correctness of the $f$ -routing protocol in our arguments but the generalization to the robust setting is immediate.

Considering the perfect protocol, we allow Alice and Bob to complete the easier task of performing $f$ -routing when they know $x=x_{0}$ . Alice, on the left, applies a quantum channel $\mathcal{N}_{QL\rightarrow AB}$ , she keeps system $A$ and sends $B$ to Bob. Without decreasing their success probability we can take the isometric extension of this channel and have Alice keep the purifying system so that the state on $A B R$ is pure. Bob, who knows $y$ , knows where system $Q$ should be brought so can, without decreasing their success probability, always simply forward the $R$ system to whichever party should receive $Q$ . Correctness of the protocol then requires that both $A R$ and $B R$ can recover $Q$ .

Let $Q$ be in the maximally entangled state $\Psi^{+}_{\bar{Q}Q}$ with reference system $\bar{Q}$ . Then correctness of the protocol implies that

	$\displaystyle I(\bar{Q}:AR)=2\log d_{R}\enspace,$
	$\displaystyle I(\bar{Q}:BR)=2\log d_{R}\enspace.$		(7)

We claim this implies that $S(R)\geq\log d_{R}$ . First notice that purity of $\bar{Q}ABR$ and the second line above implies $I(\bar{Q}:A)=0$ . Then we apply the inequality,

\displaystyle I(\bar{Q}:AR)\leq I(\bar{Q}:A)+2S(R)\enspace,

which can be proven from strong subadditivity, and using the first line of Appendix A we are done. In the robust setting, we can prove a similar bound by applying the above argument along with the continuity of the von Neumann entropy.

[bib.bib1] [1] Rene Allerstorfer, Andreas Bluhm, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel. Making existing quantum position verification protocols secure against arbitrary transmission loss. arXiv preprint, 2023. arXiv:2312.12614.

[bib.bib2] [2] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. arXiv preprint, 2023. arXiv:2306.16462.

[bib.bib3] [3] Harriet Apel, Toby Cubitt, Patrick Hayden, Tamara Kohler, and David Pérez-García. Security of position-based quantum cryptography limits hamiltonian simulation via holography. arXiv preprint, 2024. arXiv:2401.09058.

[bib.bib4] [4] Benny Applebaum and Barak Arkis. On the power of amortization in secret sharing: d-uniform secret sharing and cds with constant information rate. ACM Transactions on Computation Theory (TOCT), 2020. doi:10.1145/3417756.

[bib.bib5] [5] Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe. Journal of Cryptology, 2021. doi:10.1007/s00145-021-09376-1.

[bib.bib6] [6] Vahid R. Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification. arXiv preprint, 2024. arXiv:2402.18648.

[bib.bib7] [7] Vahid R Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources. arXiv preprint, 2024. arXiv:2404.14491.

[bib.bib8] [8] László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (SFCS 1986). IEEE, 1986. doi:10.1109/SFCS.1986.15.

[bib.bib9] [9] Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 2011. doi:10.1088/1367-2630/13/9/093036.

[bib.bib10] [10] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, 2022. doi:10.1038/s41567-022-01577-0.

[bib.bib11] [11] 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. doi:10.1137/130913687.

[bib.bib12] [12] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, 2013. doi:10.1145/2422436.2422455.

[bib.bib13] [13] Joy Cree and Alex May. Code-routing: a new attack on position verification. Quantum, 2023. doi:10.22331/q-2023-08-09-1079.

[bib.bib14] [14] Ronald de Wolf. Characterization of non-deterministic quantum query and quantum communication complexity. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000. doi:10.1109/CCC.2000.856758.

[bib.bib15] [15] Ronald De Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 2003. doi:10.1137/S0097539702407345.

[bib.bib16] [16] Llorenç Escolà-Farràs, Léo Colisson Palais, and Florian Speelman. A quantum cloning game with applications to quantum position verification. arXiv preprint, 2024. arXiv:2410.22157.

[bib.bib17] [17] Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. Journal of Computer and System Sciences, 2000. doi:10.1006/jcss.1999.1689.

[bib.bib18] [18] Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 2011. doi:10.1103/PhysRevA.84.012326.

[bib.bib19] [19] Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, 2006. US Patent 7,075,438.

[bib.bib20] [20] Robert Malaney. The quantum car. IEEE Wireless Communications Letters, 2016. doi:10.1109/LWC.2016.2607740.

[bib.bib21] [21] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019. doi:10.1007/JHEP10(2019)233.

[bib.bib22] [22] Alex May. Holographic quantum tasks with input and output regions. Journal of High Energy Physics, 2021. doi:10.1007/JHEP08(2021)055.

[bib.bib23] [23] Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 2022. doi:10.22331/q-2022-11-28-864.

[bib.bib24] [24] Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020. doi:10.1007/JHEP08(2020)132.

[bib.bib25] [25] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 2013. doi:10.1088/1367-2630/15/10/103002.

[bib.bib26] [26] Andreas Winter. Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints. Communications in Mathematical Physics, 2016. doi:10.1007/s00220-016-2609-8.

Rank Lower Bounds on Non-Local Quantum Computation

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Summary of our results

2 Preliminaries

Theorem 1 ([26]).

Observation 2.

2.1 Communication complexity

Theorem 3 ([15]).

3 Lower bounds from function rank

3.1 𝒇-routing bounds from function rank

Definition 4.

Lemma 5.

Proof.

Definition 6.

Lemma 7.

Proof.

Lemma 8.

Proof.

3.2 𝒇-BB84 bounds

Definition 9.

Definition 10.

Lemma 11.

Proof.

Lemma 12.

Proof.

4 A new lower bound technique for CDS

5 Application to concrete functions

Equality and non-equality

Greater and less than

Set-Intersection and set-disjointness

6 Discussion

References

Appendix A 𝛀⁢(𝟏) lower bounds on entanglement in 𝒇-routing

3.1 $𝒇$ -routing bounds from function rank

3.2 $𝒇$ -BB84 bounds

Appendix A $\Omega(1)$ lower bounds on entanglement in $𝒇$ -routing