1 Introduction↩︎

What is the cost of information-theoretic privacy? This is a fundamental question in cryptography which reappears across many settings, and which is closely related to understanding the complexity of Boolean functions. In this work, we make progress on understanding this problem in both the classical and quantum settings by giving several new upper and lower bounds on the private simultaneous message (PSM) model [1], [2].

The PSM setting is illustrated in 1. The setting involves \(k\) parties, who we label player 1, player 2, etc, and a referee. Player \(i\) receives input \(x_i\in\{0,1\}^n\). All parties including the referee agree in advance on a choice of Boolean function \(f:\{0,1\}^{kn}\rightarrow \{0,1\}\). Classically, the players share randomness that is inaccessible to the referee, and send classical messages to the referee. The goal is for the referee to compute \(f(x_1,...,x_k)\) without learning anything further about the value of \((x_1,...,x_k)\). We consider this model in both quantum and classical variants. When \(n=1\), so that each of \(k\) players receives a single bit of input, this setting is also an example of a decomposable randomized encoding. Another special case we often consider fixes \(k=2\).

1.1 Related work↩︎

The PSM model was introduced in a classical context in [1] as a simple toy model for secure multi-party computation. Since then, several applications and connections to other primitives in cryptography have appeared [2].

The definition of PSM is information-theoretic and does not refer to complexity theory. Nonetheless, a relationship between PSM and complexity emerges: known protocols for implementing PSM have a communication and randomness cost set by the complexity of the function \(f\). For instance, in [1] an efficient protocol for functions in \(\mathsf{NL}\) was given, based on a reduction to a PSM protocol for group products. This was improved in [2] to give efficient protocols for functions in \(\mathsf{Mod}_p\mathsf{L}\)¹ as well as other ‘counting’ variants of log-space classes.

Without the privacy condition, PSM complexity would be at most linear, since Alice and Bob can simply send their inputs to the referee. Meanwhile, most notions of Boolean function complexity can be as large as exponential, so it is clear that without privacy PSM complexity and Boolean function complexity can only be loosely related. With privacy however, the relationship may be much tighter. Better understanding the relationship between privacy and the complexity of Boolean functions is one motivation for studying the cost of privacy in PSM.

Only a few lower bound techniques that make use of the privacy condition are known for PSM. In the classical setting, one such technique was proposed in [1] and then corrected in [3]. This technique, when we have \(k=2\) players, gives a lower bound in terms of a condition on rectangles in the communication matrix for \(f\); for random functions, it leads to a \(3n-o(1)\) lower bound. This can be seen to make non-trivial use of privacy in that without privacy, the cost is at most \(2n\), the total input length.

In the classical context, a lower bound on \(k\)-party PSM was proven in [4], [5]. This lower bound is in terms of Nečiporuk’s measure, an object previously known to lower bound formula size for Boolean functions. Concretely, [4], [5] prove that for perfectly correct and perfectly secure PSM, \[\begin{align} \mathsf{PSM}(f)\geq \frac{1}{2}G^*(f) \end{align}\] where \(G^*(f)\) is Nečiporuk’s measure. A similar bound holds with perfect security relaxed. Heuristically, Nečiporuk’s measure can be understood as the logarithm of the number of distinct functions that appear when fixing subsets of the variables. In more detail, we sum over a partition of the variables and consider the number of distinct functions that arise when fixing all but the variables in the current subset of the partition. For some explicit functions on \(k\) inputs each of length \(n\), Nečiporuk’s measure evaluates to \(\frac{k^2n}{2\log(kn)}\), so when (for instance) \(n=1\), this is a nearly quadratic lower bound. This bound also necessarily uses privacy, since it is super-linear.

Recently [6], [7] a new perspective on PSM and related primitives has emerged, which considers quantum variants of these settings. This provides a new setting in which to explore the relationship between privacy, complexity, and communication cost. In [6], quantum PSM was first studied. In that context, with \(k=2\) players, a lower bound of \(3n-o(1)\) for random functions was proven in the context of quantum communication but restricting to classical shared randomness. In [6] it was shown that for some relations, communication cost in PSM can be exponentially smaller when allowing shared entanglement; this was later proven for a partial function in [8].

Quantum PSM exhibits a relationship between privacy and notions of quantum complexity. In particular, in [7] it was pointed out that communication and entanglement cost in PSM with shared entanglement allowed is upper bounded in terms of the \(T\)-depth of any unitary that computes the relevant Boolean function. Later [9], similar techniques were used to observe that certain communication complexity protocols can be transformed into PSM protocols. In particular, let \(\mathsf{PSM}^*(f)\) denote the communication cost of PSM when allowing shared entanglement but restricting to classical messages, and let \(\mathsf{Q}\|^*\) be the communication cost in the simultaneous message model, allowing quantum communication and shared entanglement. Then [9] showed that \[\begin{align} \mathsf{PSM}^*(f) \leq \left(\mathsf{Q}\|^*(f)+a\right)^{d_T} \end{align}\] where \(d_T\) is the \(T\)-depth of the unitary applied by the referee in the \(\mathsf{Q}\|^*\) protocol, and \(a\) is the number of qubits of ancilla used by the referee. In practice, this leads to new efficient PSM\(^*\) protocols constructed from existing \(\mathsf{Q}\|^*\) protocols in several interesting cases, and in particular leads to new separations between communication complexity classes. Furthermore, this shows that a separation between \(\mathsf{PSM}^*\) and \(\mathsf{Q}\|^*\) implies a T-depth lower bound.

1.2 Our results↩︎

We contribute to the understanding of the cost of privacy in quantum and classical PSM by proving two new lower bounds on entanglement cost, and two new upper bounds. One of each of our lower and upper bounds is new to even classical PSM. Our lower bounds are the first lower bounds on fully quantum PSM which make use of the privacy condition, where by fully quantum we mean that both entanglement and quantum communication are allowed. Previously, lower bounds that used privacy only applied to the case where the messages are quantum, but no shared entanglement is allowed [6].

Our first lower bound is in terms of the rank of the communication matrix of the target function \(f\), and applies to two player quantum PSM, \[\begin{align} \boxed{\mathsf{pp}\overline{\mathsf{PSQM}}^*(f)\geq \frac{1}{4}\log \rank f - \frac{1}{4}.} \end{align}\] Here, the left hand side denotes the entanglement cost of fully quantum PSM (allowing entanglement and quantum messages), and requiring perfect privacy. The communication matrix \(M_f\) of \(f\) is a \(2^n\times 2^n\) matrix with entries \(f(x,y)\). We compute the rank over the complex numbers. Notice that this lower bound follows without using privacy if we assume perfect correctness, because quantum communication complexity with perfect correctness is lower bounded by the log-rank [10]. Our result holds with imperfect correctness however, and relies instead on the perfect privacy condition. Because \(\mathsf{pp}\overline{\mathsf{PSM}}(f) \geq \mathsf{pp}\overline{\mathsf{PSQM}}^*(f)\), we obtain the same lower bound on perfectly private classical PSM. This result appears to be new to the classical setting, but is proven from the quantum perspective.

Our second lower bound applies to \(k\)-player quantum PSM, with perfect correctness. Then, denoting the total entanglement shared among all players by \(\mathsf{pc}\overline{\mathsf{PSQM}}_k^*(f)\), we find that \[\begin{align} \boxed{\mathsf{pc}\overline{\mathsf{PSQM}}_k^*(f) \geq \frac{1}{2}\alpha_\delta G^*(f)-\beta_\delta.} \end{align}\] Here the object \(G^*(f)\) appearing in the lower bound is Nečiporuk’s measure, and the \(\alpha_\delta, \beta_\delta\) are functions of the security parameter \(\delta\) for the protocol. Because Nečiporuk’s measure can be quadratic in \(k\), and hence larger than the input size, it is clear that this bound also relies on the privacy condition.

For upper bounds, we prove two new results. First, we prove an upper bound in the \(k\) player setting based on a Clifford+\(T\) decomposition of any circuit computing the function \(f\). We find the upper bound \[\begin{align} \mathsf{PSM}_k^*(f)\leq O((K\ell)^{d_T-1}\cdot kn \cdot \min\{k,\ell\}) \end{align}\] where \(d_T\) is the \(T\)-depth of the circuit computing \(f\), \(k\) is the number of players, \(n\) is the number of input bits per player, and \(\ell\) measures how much any single Clifford layer spreads the support of an operator. This result generalizes the \(T\)-depth upper bound of [11], to allow for \(k>2\) players and restricted Clifford layers.

As an application of this upper bound, we show that functions with low-depth quantum circuits [12] can be computed efficiently in the \(\mathsf{PSM}^*\) model. In particular, we consider circuits with gates that only act on a constant number of qubits. Letting \(d_f\) be the minimal depth of any quantum circuit computing \(f\), we find \[\begin{align} \boxed{\mathsf{PSM}^*_k(f) \leq (kn + s) \cdot \log^{O(d_f)}(s/\epsilon).} \end{align}\] Thus we find that functions computable in depth \(\log(nk)/ \log\log(nk)\) can be computed by a polynomial-cost \(\mathsf{PSM}^*_k\) protocol. It is interesting to compare this with the classical seting: a combination of Barrington’s theorem [13] and the PSM construction of [1] for branching programs implies that there are polynomial-cost classical PSM protocols for all functions computable by logarithmic-depth (classical) circuits. We leave it as an interesting open question of improving our bound to get polynomial-cost \(\mathsf{PSM}^*\) protocols for quantum circuits with depth \(\Omega(\log n)\).

Our second upper bound is in terms of the Fourier 1 norm of \(f\), denoted \(\Vert \hat{f}\Vert_1\). Recall that we define the Fourier transform of \(f\) by defining functions \(\chi_S(x)=(-1)^{S\cdot x}\) where \(S\) labels a subset of the bits of \(x\), and then expressing \(f(x)\) as \[\begin{align} f(x) = \sum_S \hat{f}(S) \chi_S(x). \end{align}\] The Fourier 1 norm is then \[\begin{align} \Vert\hat{f}\Vert_1 = \sum_S |\hat{f}(S)|. \end{align}\] The Fourier 1 norm appears in several contexts [14]; most relevantly [15] proved a \(O(\Vert \hat{f}\Vert^2_1)\) upper bound on the simultaneous message passing (SMP) model (which is the same as PSM, but without privacy imposed). This was then used to prove a number of circuit lower bounds. We upgrade this upper bound on the SMP model to the PSM model, proving \[\begin{align} \boxed{\mathsf{PSM}(f) \leq O(\Vert \hat{f}\Vert^2_1).} \end{align}\] It may be interesting to explore applications of this upper bound to proving circuit lower bounds.

1.2.0.1 Acknowledgments.

Research at the Perimeter Institute is supported by the Government of Canada through the Department of Innovation, Science and Industry Canada and by the Province of Ontario through the Ministry of Colleges and Universities. UG, NP, and HY are supported by AFOSR award FA9550-23-1-0363, NSF awards CCF-2530159, CCF-2144219, and CCF-2329939, and by the Sloan Foundation. NP is supported by the Google PhD Fellowship.

2 Model definitions and quantum information tools↩︎

2.1 Quantum information tools↩︎

Unless otherwise noted, by \(\log\) we always mean the base 2 logarithm. We define the von Neumann entropy by \[\begin{align} S(A)_\rho = -\tr \left(\rho_A \log \rho_A\right). \end{align}\] We define the mutual information as \[\begin{align} I(A:B)_\rho = S(A)_\rho + S(B)_\rho - S(AB)_\rho. \end{align}\] We make use of the following continuity property of the mutual information, which follows from the Alicki-Fannes-Winter inequality [16], [17].

2.2 Communication models↩︎

In this section we define the relevant classical and quantum communication models. In all cases we are interested in the simultaneous message passing scenario, so that the communication pattern allows only for the players to send messages to a referee. The models we consider can then be divided into models without privacy, and those with privacy. We begin by defining the non-private models.

Next we take up the private variations of these models.

If we enforce that the protocol is perfectly correct we add the suffix \(\mathsf{pc}\); if we enforce that the protocol is perfectly private we add \(\mathsf{pp}\). Thus for example the communication cost of perfectly correct PSQM\(^*\) protocol for function \(f\) is \(\mathsf{pc}\mathsf{PSQM}^*(f)\).

We also consider PSM settings where the input is split among \(k\) parties, rather than two. The definition is similar to the above, but we replace the input space \(X\times Y\) with \(X_1\times ...\times X_k\), and have messages computed separately from each of the inputs. In this case we add a subscript \(k\) to the model designation, for instance \(\mathsf{PSQM}^*_k\) is \(k\)-player PSM with quantum communication and shared entanglement. The \(k\) players may share a \(k\)-partite entangled state. To define the entanglement cost in this case, suppose that a protocol uses resource state \({\Psi}_{E_1E_2...E_k}\). Then we define the correlation cost to be the log dimension of this state. Note that we allow arbitrary isometries in the PSQM\(^*\) protocol, so the correlation cost measure doesn’t count any ancilla used.

3 Lower bound from Nečiporuk’s measure↩︎

In this section we develop a lower bound technique on correlation cost in the PSQM\(^*\) model, in the setting where we give each of \(k\) parties \(n\) bits of the input. We start by developing the definition of Nečiporuk’s measure, which counts the number of distinct functions that appear when restricting a given function to a subset of its inputs. Our strategy is adapted from an analogous classical setting [5].

3.1 Nečiporuk’s measure↩︎

The variant of Nečiporuk’s measure that appears in our lower bounds involves the following notion of a restriction of a \(k\) input function.

Now we can define the modified Nečiporuk’s measure.

We will eventually prove a lower bound on the \(k\) party PSQM\(^*\) complexity in terms of the Nečiporuk measure. First, we need the following claim, which restricts the number of orthogonal states on the \(AB\) Hilbert space assuming that all of the density matrices on \(B\) (nearly) agree.

Proof. Consider the states \[\begin{align} \sigma_{XAB} &= \frac{1}{d_X} \sum_{i=1}^{d_X} \ketbra{i}{i}_X\otimes \rho_{AB}^i \nonumber \\ \tilde{\sigma}_{XB} &= \frac{1}{d_X} \sum_{i=1}^{d_X} \ketbra{i}{i}_X\otimes \rho_{B} \end{align}\] Then we have \[\begin{align} \Vert \sigma_{XB} - \tilde{\sigma}_{XB}\Vert_1 =\frac{1}{{d_X}}\sum_i \Vert \rho_{B}^i-\rho_B\Vert_1 \leq \delta \end{align}\] Using 1 and that \(I(X:B)_{\tilde{\sigma}}=0\), we can bound the mutual information \(I(X:B)_\sigma\), \[\begin{align} I(X:B)_\sigma = I(X:B)_\sigma - I(X:B)_{\tilde{\sigma}} \leq \frac{3}{2}\delta \log d_X + 2h(\delta/2). \end{align}\] But also, since the \(\rho_{AB}^i\) all have orthogonal support, we can measure \(AB\) and determine \(i\) so then also \(I(AB:X)=\log d_X\). But then we use \[\begin{align} \log d_X &= I(AB:X)_{\sigma} \nonumber \\ &= I(A:X|B)_{\sigma} + I(B:X)_{\sigma} \nonumber \\ &\leq 2S(A)_{\sigma} + I(B:X)_{\sigma} \nonumber \\ &\leq 2S(A) + \frac{3}{2}\delta \log d_X + 2h(\delta/2) \nonumber \\ &\leq 2 \log d_A + \frac{3}{2}\delta \log d_X + 2h(\delta/2) \end{align}\] which can be re-arranged to the desired inequality.  

---

For intuition, consider the case where \(\delta=0\) and \(A\), \(B\) are both qubits. Then the bound says that any set of orthogonal states on \(AB\) which all have the same marginal on \(A\) must be of size at most \(4\). We can saturate this bound by for instance choosing the four Bell states on \(AB\), which are orthogonal but all have \(\rho_B=\mathcal{I}_B/2\).

3.2 Lower bound from Nečiporuk’s measure↩︎

Finally, we are ready to prove the quantum PSM lower bound. The overall strategy is as follows. We partition the inputs into \(S\) and \(\bar{S}\). The inputs to \(\bar{S}\) are fixed to a string \(\alpha\in \{\{0,1\}^{n}\}^{|\bar{S}|}\). The last \(n-1\) bits of each input to the players in \(S\) is fixed to \(\beta\in\{\{0,1\}^{(n-1)}\}^{|S|}\), while the remaining inputs are taken to be \(y\in\{0,1\}^{|S|}\). We observe that the message \(M_{\bar{S}}\) from players in \(\bar{S}\), along with the initial entanglement on players in \(S\), call it \(E_S\), can be used to compute \(f_{S|(\alpha,\beta)}(y)\) for any choice of \(y\). See 2. Further, when the protocol is perfectly correct, we can copy out the value of \(y\), uncompute, and run forward again with a new choice of input. Thus in fact the state on \(S\bar{S}\) determines all values of \(f_{S|(\alpha,\beta)}\) and hence determines \(\alpha\). Naively, that means \(E_SM_{\bar{S}}\) needs to have a dimension lower bounded by the number of distinct functions. Alone, this isn’t strong enough to get our bound, and instead we want to lower bound the dimension of \(E_S\) alone. To achieve this, we use security to show that all the states on \(E_SM_{\bar{S}}\) have density matrices that agree on \(M_{\bar{S}}\), and then apply 1 to bound the dimension of \(E_S\) alone.

Proof. Consider a subset of players \(S\) and the complement set \(\bar{S}\). Considering the modified Nečiporuk measure, fix \(\beta\) to its maximizing value. Then choose a set of distinct \(\alpha\) that each lead to distinct first-bit restrictions \(f_{S|(\alpha,\beta)}\). Denote the remaining inputs to \(f_{S|(\alpha,\beta)}\) as \(y\). Let the message system sent by \(S\) be \(M_S\), and the message system sent by \(\bar{S}\) be \(M_{\bar{S}}\). Similarly, let the entangled resource systems held by \(S\) and \(\bar{S}\), before they act with their local operators, be \(E_S\) and \(E_{\bar{S}}\) respectively.

We claim that all the possible message density matrices (for each distinct input \(y\)) agree on \(M_{\bar{S}}\), up to an error set by \(\delta\). This is because for all \(\alpha, \alpha'\) the functions we get by restriction are still non-zero by assumption, so there exist choices of \(y,y'\) such that \(f_{S|(\alpha,\beta)}(y)=f_{S|(\alpha',\beta)}(y')\), so then by privacy \[\begin{align} \Vert\rho_{M_SM_{\bar{S}}}(y,\alpha,\beta)-\rho_{M_SM_{\bar{S}}}(y',\alpha',\beta)\Vert_1\leq \delta. \end{align}\] But by causality the reduced density matrix on \(M_{\bar{S}}\) can’t depend on \(y\), so we get \[\begin{align} \Vert\rho_{M_{\bar{S}}}(\alpha)-\rho_{M_{\bar{S}}}(\alpha')\Vert_1 \leq \delta \end{align}\] as claimed. Define \(\rho_{M_{\bar{S}}}(\alpha_0)\equiv \rho_{M_{\bar{S}}}\) for some fixed \(\alpha_0\), so all \(\rho_{M_{\bar{S}}}(\alpha)\) are \(\delta\) close to a fixed density matrix.

Next, we show that \(\alpha\) can be determined from \(E_S M_{\bar{S}}\), in other words we show that \(F(\rho_{E_SM_{\bar{S}}}(\alpha,\beta), \rho_{E_SM_{\bar{S}}}(\alpha',\beta))=\delta_{\alpha,\alpha'}\). To see this, consider a unitary extension of the operations of each of the \(S\) players acting on \(E_S\) and input \(I\), followed by the referee’s operations, to define a single unitary taking in \(E_SM_{\bar{S}}\) and a copy of the inputs and producing \[\begin{align} U_{IE_SM_{\bar{S}}\rightarrow \mathcal{O}R}(\ketbra{y}{y}_I\otimes \rho_{E_SM_{\bar{S}}})U_{IE_SM_{\bar{S}}\rightarrow \mathcal{O}R}^\dagger = \ketbra{f_{S|(\alpha,\beta)}(y)}{f_{S|(\alpha,\beta)}(y)}_{\mathcal{O}}\otimes \sigma_R \end{align}\] for some state \(\sigma_R\). We can CNOT the value of \(f_{S|(\alpha,\beta)}(y)\) into a separate register, then invert the unitary to get what we started with. We then pick a new value of \(y\) and repeat. In this way we can determine the truth table of \(f_{S|(\alpha,\beta)}\). Since there is just one \(\alpha\) that leads to \(f_{S|(\alpha,\beta)}\) by assumption, this determines \(\alpha\) as needed. Since the \(\alpha\) can be perfectly distinguished, we have \(F(\rho_{E_SM_{\bar{S}}}(\alpha,\beta), \rho_{E_SM_{\bar{S}}}(\alpha',\beta))=\delta_{\alpha,\alpha'}\) as claimed.

Now, we apply 1. In our setting, \(d_X\) is the total number of choices of \(\alpha\), so \(\log d_X\) is \(g^*_S(f)\). Thus we obtain \[\begin{align} \frac{1}{2}(1-3\delta/2)g^*_S(f) - h(\delta/2) \leq n_{E_S}. \end{align}\] We find that the entanglement held by \(S\) must consist of at least \(g^*_S(f)/2\) qubits, up to a multiplicative factor which is close to 1, and a small additive term. Then we consider a partition \(V=(V_1,...,V_m)\), use the above for each \(V_i\), sum over the \(V_i\), and optimize over partitions to get a lower bound in terms of \(G^*(f)\). Doing so leads to the claimed lower bound.  

---

We also remark that if \(\mathsf{PSQM}^*\) protocols can be amplified, then the above lower bound technique can be adapted to apply to imperfectly correct protocols. To see why, suppose the \(\mathsf{PSQM}^*\) protocol can be amplified in the sense that, with a factor of \(\ell\) overhead in resources, we have \(\epsilon\rightarrow 2^{-\ell}\epsilon\), and further that the security parameter is not increased by the amplification procedure. Then, we can consider a similar construction as used above, now applied to the amplified protocol. A complication arises when the referee wishes to determine \(\alpha\) from \(E_SM_{\bar{S}}\). To do so, they compute \(f_{S|(\alpha,\beta)}(y)\) for a given value of \(y\), measure the output qubit and store the value of \(f_{S|(\alpha,\beta)}(y)\), then reverse the procedure to try and return to the initial state on \(E_SM_{\bar{S}}\). With perfect correctness the measurement returns \(f_{S|(\alpha,\beta)}(y)\) with probability 1 and doesn’t change the state, so that the initial state on \(E_SM_{\bar{S}}\) is reproduced perfectly. Repeating, the referee learns all the values \(\{f_{S|(\alpha,\beta)}(y)\}_y\) correctly with probability 1. To ensure this works with probability of order 1 when the protocol is imperfectly correct, we need that each measurement fails to return \(f_{S|(\alpha,\beta)}(y)\) with probability at most \(2^{-|S|}\). Thus in the amplification step we should choose \(k=\Theta(|S|)\). This means our lower bound is weakened by a factor of \(|S|\), becoming, \[\begin{align} n_{E_S} \gtrsim g_S^*(f)/|S|. \end{align}\] Thus on the total dimension of the entangled state we obtain a lower bound of \(G^*(f)/\max_i |S_i|\) where the \(\{S_i\}_i\) are the subsets in the optimizing partition used in computing \(G^*(f)\).

Many functions have large Nečiporuk measure, and explicit functions can be identified with large Nečiporuk measure as well. A review of this can be found in [5]. To summarize briefly, we have that all functions have Nečiporuk measure bounded by \[\begin{align} G^*(f) \leq \frac{k^2n}{\log (kn)}. \end{align}\] Further, random functions nearly saturate this bound with high probability. Considering explicit functions, the \((n,k)\) set disjointness function (\(DISJ_{n,k}\)) and first-bit indirect storage access (\(FISA_{n,k}\)) function² have \[\begin{align} G^*(f)= \Omega\left(\frac{n^2k}{\log (kn)}\right) \end{align}\] which saturates the upper bound on \(G^*\). For these functions we obtain quadratic lower bounds on the entanglement cost of perfectly correct PSQM.

4 Rank lower bound↩︎

We will give a lower bound strategy based on the rank of the communication matrix for the function \(f(x,y)\). This technique will only apply to the case where the PSM protocol is perfectly secure, but correctness errors are allowed. This is similar to a technique given in [18], which deals with the related (quantum) CDS primitive [7], [19], [20], but for quantum PSM the technique gives a stronger bound. In this section we deal with \(2\)-player PSM, but note that for \(k\)-players we can apply the technique to any partition of the players into two subsets.

4.1 Lower bound↩︎

In this section we prove the rank lower bound on perfectly private PSM.

Proof. Consider a PSQM\(^*\) protocol. Let the density matrix describing the message systems \(M_AM_B=M\) be denoted \(\rho_M(x,y)\). For a perfectly secure PSQM protocol, there are just two possible density matrices that can be realized for different values of \((x,y)\); a 0 density matrix or a 1 density matrix, \[\begin{align} \rho_M(x,y)=\rho_0 \quad \text{if} \,\,\,\, f(x,y)=0,\nonumber \\ \rho_M(x,y)=\rho_1 \quad \text{if}\,\,\,\, f(x,y)=1. \end{align}\] This follows because if \(\rho(x,y)\neq \rho(x',y')\), the referee has some probability of distinguishing between \((x,y)\) and \((x',y')\), which shouldn’t be the case if \(f(x,y)=f(x',y')\).

This lets us express \(f(x,y)\) using the matrix valued function \(\rho(x,y)\), in particular define \[\begin{align} \alpha = \tr((\rho_1-\rho_0)^2) = \Vert \rho_1-\rho_0\Vert_2^2. \end{align}\] This is non-zero, because by correctness it must be the case that \(\rho_0\neq \rho_1\). Then we can notice \[\begin{align} \label{eq:f-as-rho} f(x,y) = \frac{1}{\alpha} \tr(\rho(x,y)-\rho_0)^2. \end{align}\tag{1}\] To see why the above holds, note that when \(f(x,y)=1\) we have \(\rho(x,y)=\rho_1\), so the right hand side is 1 as needed. Meanwhile, if \(f(x,y)=0\) then \(\rho(x,y)=\rho_0\) so the above is 0, as needed.

Next, we use an expression for \(\rho(x,y)\) that is constrained by the amount of entanglement used in the protocol. Suppose that the resource state used in the protocol is \(\Psi_{L'R}\), and purify this to \[\begin{align} \ket{\Psi}_{LR}=\sum_{i=1}^{r} \sqrt{\lambda_i}\ket{i}_L\ket{i}_R. \label{eq:ent-purification} \end{align}\tag{2}\] We will lower bound the log-dimension of the purified state, which never need be larger than twice the unpurified log-dimension. Thus beginning with a mixed state and purifying will loosen our bound by at most a factor of \(1/2\).

The mid-protocol density matrix \(\rho_{M_AM_B}(x,y)\) is produced by Alice and Bob acting separately on each end of the entangled state, so is of the form \[\begin{align} \rho_{M_AM_B}(x,y) &=\sum_{i,j=1}^{r} \sqrt{\lambda_i\lambda_j} \mathcal{N}_{L\rightarrow M_A}^x(\ketbra{i}{j})\otimes \mathcal{N}_{R\rightarrow M_B}^y(\ketbra{i}{j}) \nonumber \\ &= \sum_{i,j=1}^{r} A^{i,j}_{M_A}(x)\otimes B^{i,j}_{M_B}(y)\nonumber \\ &= \sum_{I=1}^{r^2} A^{I}_{M_A}(x)\otimes B^{I}_{M_B}(y). \end{align}\] The second line defines the matrices \(A^{i,j}_{M_A}(x), B^{i,j}_{M_B}(y)\). Pick any input \((x_0,y_0)\) with \(f(x_0,y_0)=0\). Then \[\begin{align} \rho_0 = \sum_{I=1}^{r^2} A^I_{M_A}(x_0)\otimes B^I_{M_B}(y_0) \end{align}\] and we can write \(f(x,y)\) as \[\begin{align} f(x,y) &= \frac{1}{\alpha} \tr(\rho(x,y)-\rho_0)^2 \nonumber \\ &= \frac{1}{\alpha}\tr\left((\rho(x,y))^2 - 2\rho(x,y) \rho_0 + \rho_0^2 \right)\nonumber \\ &= \frac{1}{\alpha} \tr \left( \sum_{I,J=1}^{r^2} A^I(x)A^J(x)\otimes B^I(y)B^J(y) - 2\sum_{I,J=1}^{r^2} A^I(x)A^J(x_0)\otimes B^I(y)B^J(y_0)\right. \nonumber \\ &\qquad \qquad \qquad + \left.\sum_{I,J=1}^{r^2} A^I(x_0)A^J(x_0)\otimes B^I(y_0)B^J(y_0)\right) \nonumber \\ &= \sum_{K=1}^{2r^4} f_{K}(x)f'_{K}(y) \end{align}\] where the last line defines two functions \(f_K(x)\) and \(f_K'(y)\). Therefore, we have that the rank of \(f\) over the complex numbers is at most \[\begin{align} \rank(f) \leq 2r^4. \label{eq:rank-bounds-ent} \end{align}\tag{3}\] Since \(r\) is the Schmidt rank of the purified state, \(\log r\) lower bounds the dimension of \(R\) and \(L\), which we want to translate to a bound on the dimension of \(\rho_{L'R}\). We know that \[\begin{align} \log d_{LR} \leq 2 \log d_{L'R} \label{eq:ent-dimension-blowup} \end{align}\tag{4}\] and that \(\log r \leq \log d_R, \log d_L\). Combining these statements we have \[\begin{align} \log r \leq \frac{1}{2}\log d_{LR} \leq \log d_{L'R} = \mathsf{pp}\overline{\mathsf{PSQM}}^*(f). \end{align}\] Finally, by 3 we have that \(\log(r) \geq \frac{1}{4} \log\rank(f) - \frac{1}{4}\). Combining this with the previous equation we get \[\begin{align} \boxed{\mathsf{pp}\overline{\mathsf{PSQM}}^*(f) \geq \frac{1}{4}\log \rank f - \frac{1}{4}.} \end{align}\] Here \(\mathsf{pp}\overline{\mathsf{PSQM}}^*(f)\) is the minimal number of qubits of shared resource state needed to execute PSQM with perfect security.  

---

Note that the rank lower bound does not apply to communication, but only to correlation cost. We could ask if the communication is also lower bounded by the rank, but considering the equality function shows such a bound cannot hold. To see this, consider that equality is full rank, so the log-rank is \(n\). Using linear randomness in the resource, Alice and Bob can take \(x\oplus r\) and \(y\oplus r\) and then send a constant length hash of those strings. This is perfectly secure and approximately correct, so we can compute equality in the PSQM\(^*\) model with perfect privacy and log communication, even while the log-rank is linear. Thus our bound cannot also apply to communication.

4.2 Comparison to related bounds↩︎

We should also compare the rank lower bound obtained here to similar lower bounds. We can notice first that the communication cost \(\mathsf{PSQM}^*(f)\) is lower bounded by two-way quantum communication complexity of \(f\). If we assume perfect correctness, this is lower bounded by the log-rank [10]. If we had assumed perfect correctness for our PSQM protocol then our lower bound would be immediate. Our result shows that perfect privacy (and relaxed correctness) also suffices to obtain a rank bound.

Note that our bound also applies to classical PSM, since classical PSM is lower bounded by quantum PSM. As well, our lower bound uses privacy — indeed our bound is on the shared randomness, which can be zero when there is no privacy requirement.

Another point of comparison are the similar lower bounds on quantum CDS obtained in [18]. There, the log Schmidt rank in perfectly private quantum CDS, denoted \(\mathsf{pp}\mathsf{CDQS}\), is lower bounded according to \[\begin{align} \mathsf{pp}\mathsf{CDQS}^*(f) &\geq \frac{1}{4}\log (\text{nrank}(f)). \end{align}\] The non-deterministic rank is the minimal rank of any matrix over the complex numbers which has the same zeros as the communication matrix of \(f\). In general this may be smaller than the usual notion of rank. Because CDS lower bounds PSM [7], we also obtain the same lower bound on perfectly private PSM, but since the nrank may be much smaller than the rank, our bound on PSM is stronger than the one inherited from CDS.

5 Upper bound from \(T\)-depth and quantum circuits↩︎

In this section we prove new upper bounds on the \(\mathsf{PSM}_k^*\) model. Our main strategy is to adapt techniques from non-local quantum computation [11], which involves two separated players, to the \(k\)-player setting. This gives an upper bound on \(\mathsf{PSM}^*_k(f)\) related to the \(T\)-depth of any unitary computing \(f\). With some further modifications to this technique, we show it can be used to realize an upper bound on \(\mathsf{PSM}^*_k\) based on the size and depth of a quantum circuit computing \(f\).

5.1 Computational models↩︎

Recall that the \(n\)-qubit Pauli group \(\mathcal{P}_n\) consists of \(n\)-fold tensor products of the four Pauli operators, \(\{I,X,Y,Z\}\), with an added overall phase of \(\pm 1\) or \(\pm i\). A Clifford unitary \(C\) is a unitary such that for any \(P\in \mathcal{P}_n\), there exists another \(P'\in \mathcal{P}_n\) such that \(CPC^\dagger=P'\).

Clifford unitaries are a subgroup of all possible unitaries. To generate the full unitary group, it suffices to consider the \(T\)-gate, \[\begin{align} T=\begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4}\end{pmatrix} \end{align}\] along with the Cliffords. \(T\)-gates are more difficult to apply in standard quantum computing architectures, and consequently understanding the number of \(T\)-gates required for a given computation has been a topic of interest.

We will be interested in decompositions of unitaries into Clifford layers interlaid with \(T\)-gate layers, \[\begin{align} U=C_{d}\bar{T}_dC_{d-1}...C_1\bar{T}_1C_0. \end{align}\] The operators \(\bar{T}_i\) consist of parallel \(T\)-gates on a subset \(S_i\) of the qubits, and identity on the remaining qubits. The operators \(C_i\) are Clifford. We call \(d_T\) the \(T\)-depth of the circuit.

We are also interested in restricted variants of the above decomposition into Clifford\(+T\) layers. To specify these, we define a unitary \(V\) to have a backward light-cone of size at most \(\ell\) if, taking a single qubit operator \(\mathcal{O}_i\), we have that \[\begin{align} V^\dagger \mathcal{O}_i V = \tilde{\mathcal{O}}_i \end{align}\] has support on at most \(\ell\) qubits. Note that we do not require any notion of geometric locality in these operators; we only consider the size of the non-trivial support. Returning to Clifford\(+T\) decompositions, we say that a Clifford\(+T\) decomposition is \(\ell\)-local if every Clifford \(C_i\) has backward light-cones of size at most \(\ell\).

5.2 Speelman’s instantaneous computation technique↩︎

To prove our upper bounds in this section, we borrow techniques developed in the context of non-local quantum computation (NLQC) [11]. In both NLQC and in the context of PSM protocols, it is useful to be able to implement the following transformation.

The entanglement cost of instantaneous computations can be upper bounded in terms of the complexity of the unitary \(U_{AB'}\). Consider a decomposition of \(U_{AB'}\) into Clifford layers and layers of \(T\)-gates, \[\begin{align} U=C_{d_{T}} \bar{T} C_{d_{T}-1} \bar{T} C_{d_{T}-2}... C_{1} \bar{T}C_0. \end{align}\] If we allow arbitrary Cliffords \(C_i\) at each layer, and consider only 2 players Alice and Bob\(_1\), [11] shows that \(U\) can be computed instantaneously using \(O((K_1n)^{d_T})\) shared EPR pairs where \(d_T\) is the \(T\)-depth, \(n\) is the number of qubits of input, and \(K_1\) is a constant. We will need an extension of this result.

Specifically, we consider the case where 1) We allow \(k\geq 2\) players. 2) The Clifford layers are further restricted, to only allow Cliffords with backward light cones of size \(\ell\). This is equivalent to the statement that the \(i\)th output qubit of the Clifford is only influenced by at most \(\ell\) input qubits.

We prove this theorem in Appendix 7.

Next we proceed to apply this result to \(\mathsf{PSM}^*_k\) upper bounds.

5.3 \(T\)-depth and circuit depth \(\mathsf{PSM}_k^*\) upper bounds↩︎

We first of all show the following \(\mathsf{PSM}^*\) upper bound from the \(T\)-depth.

Proof. Let the unitary computing \(f(x)\) be computed by applying a unitary \(U_{AB_1...B_{k-1}}\) to the inputs and advice state followed by a computational basis measurement on the first output qubit. By assumption the circuit computes \(f\) with probability \(1-\epsilon\).

The \(\mathsf{PSM}^*\) protocol is as follows. The players execute the instantaneous computation for \(U\), which uses entanglement upper bounded as in 4. At this point, Alice holds the output of \(U\), which has been corrupted by a Pauli string \(P[m_a, m_{b_1},...,m_{b_{k-1}}]\) with the \(b_i\) held by Bob\(_i\). Alice proceeds to measure the first qubit, obtaining outcome \(s\). All of the players then send the measurement outcomes \(m_a,m_{b_i}\) produced during the execution of the instantaneous computation protocol.

To see that this protocol is \(\epsilon\) correct, notice that the Pauli operator acting on the measured qubit will not change the measurement outcome if it is an \(I\) or \(Z\) operator, and will invert the outcome if it is an \(X\) or \(Y\) operator. Thus if the referee receives this final measurement outcome along with the strings \(m_a, m_{b_1},...m_{b_{k-1}}\), the referee can determine which Pauli acted on the measured qubit and inverts the result if it is \(X\) or \(Y\), then the resulting bit will be distributed just as if it were the outcome from the original circuit with no Pauli corrections, so will equal \(f(x,y)\) with probability at least \(1-\epsilon\).

Next we consider security. In the instantaneous computation protocol, all of the bits sent to the referee were from Bell basis measurements, call them \(r=(r_1,...,r_k)\), except one bit \(s\), which came from Alice measuring the final output qubit. The Bell basis measurement outcomes \(r\) are distributed as a uniformly random bit-string in \(\{0,1\}^{|r|}\). To design a simulator, consider that the message is of the form \[\begin{align} \rho_M(x,y)&=\frac{1}{2^{|r|}}\sum_r X^{p(r)} \sigma(x,y)X^{p(r)}\otimes \ketbra{r}{r}, \nonumber \\ \sigma(x,y) &= \alpha(x,y) \ketbra{f}{f} + (1-\alpha(x,y)) \ketbra{f\oplus 1}{f\oplus 1}. \end{align}\] Here \(p(r)\) is a function which determines if there is a Pauli \(X\) correction on the measured qubit. The probabilities \(\alpha(x,y)\) can in general leak information about \((x,y)\), but we have that \(\alpha(x,y) \geq 1-\epsilon\) for all \((x,y)\) which will ensure this leaked information is small. In particular we define the simulator distribution to be \[\begin{align} \text{Sim}(f) = \frac{1}{2^{|r|}}\sum_r X^{p(r)} \ketbra{f}{f} X^{p(r)}\otimes \ketbra{r}{r}. \end{align}\] Then to check security, we just need to calculate the trace distance between the message distribution and the simulator distribution, \[\begin{align} \Vert \rho_M(x,y) - \text{Sim}_M(f) \Vert_1 &= \left\Vert \frac{1}{2^{|r|}}\sum_r X^{p(r)}(\sigma(x,y)-\ketbra{f}{f})X^{p(r)}\otimes \ketbra{r}{r} \right\Vert_1 \nonumber \\ &= \frac{1}{2^{|r|}}\sum_r \Vert \sigma(x,y)-\ketbra{f}{f} \Vert_1 \nonumber \\ &= \frac{1}{2^{|r|}} \sum_r \|(\alpha(x,y)-1)\ketbra{f}{f} + (1-\alpha(x,y))\ketbra{f\oplus 1}{f\oplus 1} \|_1\nonumber \\ &\leq \frac{1}{2^{|r|}} \sum_r 2 |1-\alpha(x,y)| \nonumber \\ &\leq 2\epsilon \end{align}\] so that the protocol is \(\delta=2\epsilon\) secure, as claimed.  

---

As a special case of this result, it follows that low-depth quantum circuits, with gates of constant arity, provide a good upper bound on \(\mathsf{PSM}^*\) complexity.

Proof. First we convert the gates from the given quantum circuit to the Clifford + T gate set that consists only of one and two-qubit gates, in particular our gate set consists of: Hadamard, Phase, T, and CNOT. Using Solovay-Kitaev [21], [22] we could do this with a depth overhead factor of \(\log(s/\epsilon)\) where \(s\) is the size of the circuit. However, we will do better than this by making use of an additional catalytic [23] advice state. The catalytic advice state is provided as additional input to the circuit (does not depend on the input) and after the computation it must be returned to its original form so can be reused. Surprisingly, Kim showed that any Pauli \(Z\)-rotation can be \(\eta\)-approximated in depth 3 if a certain catalyst state is available, which has size \(O(\log^2(1/\eta))\) [23]. Kim and Laakkonen later improved this to be depth 1 with size \(O(\log(1/\eta))\) advice [23], [24]³. We will use this construction to convert our circuit to a Clifford + T circuit with low T-depth.

For each gate in the original circuit we do the following. Let \(b = O(1)\) be the bound on the number of qubits of fan-in the circuit’s gates have. It’s well-known that we can implement any unitary of dimension \(2^b\) exactly with a circuit of size \(4^{b}\) using only arbitrary single qubit rotations about \(Z\) and \(Y\), and CNOT gates [26]. Note that the Y-rotation gate is just a Z-rotation gate conjugated by the single-qubit Clifford gate, \(SH\). Thus, we can rewrite the gate with \(O(4^b)\) gates consisting only of Clifford and \(Z\)-rotations. Using Kim’s construction [23], [24] we then approximate each of the \(O(4^b)\) \(Z\)-rotation gates to within approximation error \(\eta\), which only requires \(T\)-depth 1 for each such \(Z\)-rotation. We implement each of the gates sequentially so that we can reuse the catalytic state. Now the overall T-depth for implementing this gate is \(O(4^b)\), uses a catalytic state on \(O( \log(1/\eta))\) qubits, and has approximation error \(\eta \cdot O(4^b)\).

We do the above for each of the gates. Let \(s\) be the total number of gates in the original circuit. So our constructed Clifford + T circuit then has T-depth \(d_T := O(d_f \cdot 4^b)\), approximation error \(\epsilon= O(s \eta 4^b)\) and requires a catalytic advice state on \(O(s \cdot \log(1/\eta))\) qubits.

Furthermore, note that each of the Clifford components act on at most \(O(b + \log(1/\eta))\) qubits: the original \(b\) input qubits and the \(\log(1/\eta)\) catalytic advice qubits. So each of the Clifford layers has lightcones bounded by \(\ell := O(b + \log(1/\eta))\).

We set \(\eta = \Theta(\epsilon s^{-1} 4^{-b})\) such that the total approximation error is \(\epsilon\), the catalytic state is on \(a:= O(s \cdot \log(s 4^b / \epsilon)) = O(s b \log(s/\epsilon))\) qubits, and the lightcones are bounded by \(\ell = O(b\log(s/\epsilon))\).

Let \(U\) be the unitary on \(n_{\text{tot}}' := (n_{\text{tot}}+ a) = nk + O(s b \log(s/\epsilon))\) qubits that implements this circuit, so it takes as input the input to the original circuit (\(nk\)-qubits) in addition to the (\(a\)-qubit) catalytic advice state, and it computes \(f\) to within approximation error \(\epsilon\). Using that \(n_{\text{tot}}= k n\) we get the claimed bound.

We can implement this unitary instantaneously using 4. Now, Alice will receive \(n\) bits of input in addition to the \(a\) qubits of advice. Applying 4 with \(n_{\text{tot}}'\) as the total number of qubits, we see that there is an instantaneous protocol for implementing \(U\) with the number of EPR pairs used at most \[\begin{align} E(U)&\leq O((K\ell)^{d_T-1}\cdot n_{\text{tot}}' \cdot \min\{k,\ell\})\\ &= (b\log(s/\epsilon))^{O(d_f 4^b)} \cdot (n_{\text{tot}}+ O(sb \log (s/\epsilon))) \cdot \min\{k, b\log(s/\epsilon) \} \\ &\leq (b\log(s/\epsilon))^{O(d_f 4^b)} \cdot (n_{\text{tot}}+s)\\ &\leq (n_{\text{tot}}+s) \cdot \log^{c\cdot d_f}(s/\epsilon) \end{align}\] for some constant \(c>0\). In the last line we used that \(b = O(1)\).

Now for the \(\mathsf{PSM}_k^*\) protocol, when each player is given the classical \(n\)-bit input, Alice can prepare the catalytic advice state herself, the players can apply the above protocol. Furthermore, following the same argument as in the proof of 5, this protocol is \(\epsilon\)-correct and \(2\epsilon\)-secure, and both communication cost and number of EPR pairs at most \((n_{\text{tot}}+s) \cdot \log^{c\cdot d_f}(s/\epsilon)\).

 

---

6 Upper bound from the Fourier 1 norm↩︎

In this section we give an upper bound on classical PSM complexity based on the one-norm of the Fourier transformation of \(f\). This upper bound appears to be new to the classical literature. As we discuss, the Fourier one-norm captures how the function \(f\) is related to parity functions.

6.1 Fourier transform for Boolean functions and the Fourier one-norm↩︎

We briefly introduce the Fourier transform of a Boolean function. Let \(x,S\) be \(n\) bit strings. We think of \(S\) as labelling a subset of the bits, where the \(i\)th bit of \(S\) is \(1\) iff bit \(i\) is included in the subset. Then define the parity function \[\begin{align} \chi_S(x)=(-1)^{S\cdot x} = (-1)^{\sum_{i\in S}x_i} \end{align}\] which is \(-1\) if the parity of the bits \(x_i\) in the subset \(S\) is odd, and \(+1\) otherwise. We study a Fourier transform of \(f\), which can also be understood as expressing \(f(x)\) as a sum over parity functions. Specifically, the Fourier transform \(\hat{f}(S)\) is defined such that \[\begin{align} f(x)=\sum_S \hat{f}(S)\chi_S(x) \end{align}\] Alternatively, we can use that \[\begin{align} \frac{1}{2^n}\sum_x \chi_S(x)\chi_T(x)= \delta_{S,T} \end{align}\] to express \(\hat{f}(S)\) in terms of \(f(x)\), \[\begin{align} \hat{f}(S)=\frac{1}{2^n}\sum_x f(x) \chi_S(x). \end{align}\]

Our upper bound will be expressed in terms of the Fourier 1 norm, which given a function \(f\) is defined from the Fourier coefficients \(\hat{f}(S)\) according to \[\begin{align} \Vert \hat{f} \Vert_1 = \sum_{S} |\hat{f}(S)| \end{align}\] The Fourier 1 norm captures, in a weighted sense, how many Fourier coefficients are needed to represent \(f(x)\).

6.2 Upper Bound↩︎

Proof. The starting point for the proof is the observation that \(f(x,y)\) can be expressed as the expected value of a random variable from a certain fixed distribution depending on the function \(f\). In more detail, define a probability distribution \(p\) from the Fourier coefficients of \(f\), \[\begin{align} p_S=\frac{|\hat{f}(S)|}{\Vert \hat{f} \Vert_1}. \end{align}\]

Observe that \(f(x,y)\) can be expressed in terms of the expectation of the random variable \(\text{sign}(\hat{f}(S))\cdot \chi_S(x,y)\) under this distribution. In more detail, \[\begin{align} \begin{aligned} f(x,y)&=\sum_S \hat{f}(S)\chi_S(x,y)\\ &=\|\hat{f}\|_1\cdot \sum_{S} p_S\cdot \text{sign}(\hat{f}(S))\cdot \chi_S(x,y)\\ &=\|\hat{f}\|_1\cdot \mathbb{E}_{S\sim p}[ \text{sign}(\hat{f}(S))\cdot \chi_S(x,y)].\end{aligned} \end{align}\] Next, we note that \(\chi_{S}(x,y)=\chi_S(x)\chi_S(y)\), as can be checked from its definition. Thus, \[\begin{align} \label{eq:bias} \frac{f(x,y)}{\|\hat{f}\|_1}=\mathbb{E}_{S\sim p}[\text{sign}(\hat{f}(S))\cdot \chi_S(x)\cdot \chi_S(y)]. \end{align}\tag{5}\] This naturally motivates a strategy for Alice and Bob as follows. Firstly, using shared private randomness, they sample a set \(S\sim p\) according to the aforementioned distribution \(p\), secondly, they sample a uniformly random bit \(b\in \{-1,1\}\). Then, Alice sends \(\chi_S(x)\cdot b\) to the referee and Bob sends \(\chi_S(y)\cdot b\cdot \text{sign}(\hat{f}(S))\). We then have the referee multiply these two quantities to get \(\text{sign}(\hat{f}(S))\cdot \chi_S(x,y)\).

Firstly, we observe that the expected output of the referee is precisely \(f(x,y)/\|\hat{f}\|_1\) from 5 . Furthermore, we will see that this protocol is perfectly private. But first, we would like to amplify the success probability to get perfect correctness. To determine whether \(f(x,y)\) is \(1\) or \(-1\) with probability \(1-\delta\), the idea is to have the players repeat this protocol \(m=10 \|\hat{f}\|_1^2\ln(2/\delta)\) times in parallel (using independent randomness) and have the referee output \(1\) or \(-1\) if the sum of all his outputs is positive or negative respectively. We now prove that this described protocol is correct. To do so, observe that expected sum of the outputs is \(m\cdot f(x,y)/\|\hat{f}\|_1\). As each output is \(\{\pm 1\}\)-valued, by Hoeffding’s inequality, the probability that the sum differs from its expectation by more than \(t\) is at most \(2\exp\left(-t^2/2m\right)\), which is at most \(\delta\) for \(t=\sqrt{2m \ln(2/\delta)}\). Thus, with all but \(\delta\) probability, the sum of all outputs is roughly \(m\cdot f(x,y)/\|\hat{f}\|_1\pm \sqrt{2m\ln(2/\delta)}\) which is roughly \(10\|\hat{f}\|_1\ln (2/\delta)\cdot f(x,y)\pm 5\|\hat{f}\|_1\ln(2/\delta)\) by our choice of \(m\). As the first term dominates, it is clear that this quantity is positive if and only if \(f(x,y)=1\). This completes the proof of correctness of the amplified protocol.

Perfect privacy of the original (not repeated) protocol, implies perfect privacy of the repeated protocol, so all that remains is to show that the original protocol is perfectly private. Recall that the referee receives a bit \(b_1\in \{-1,1\}\) from Alice and a bit \(b_2\in\{-1,1\}\) from Bob, where \(b_1=b\cdot \chi_S(x)\) for a uniformly random bit \(b\in\{-1,1\}\) and \(b_2=b\cdot \chi_S(y)\cdot \text{sign}(\hat{f}(S))\). The simulator for this protocol is as follows: Given \(f(x,y)\), the simulator samples a uniformly random bit \(b\in \{-1,1\}\) and an independent random bit \(c\in \{-1,1\}\) with bias given by \(f(x,y)/\|\hat{f}\|_1\) and outputs \(b_1':=b\) for Alice’s message and \(b_2':=b\cdot c\) for Bob’s message. We will show that the resulting distribution on \((b_1',b_2')\) is identical to that of \((b_1,b_2)\) in the original protocol. We will instead argue that the distribution of \((b_1',b_1'\cdot b_2')\) is identical to that of \((b_1,b_1\cdot b_2)\) and since \(b_1,b_1',b_2,b_2'\in\{-1,1\}\), this suffices. Firstly, observe that these are product distributions as the random variables \(b_1\cdot b_2\) and \(b_1'\cdot b_2'\) are independent of \(b_1\) and \(b_1'\) respectively. Thus, it suffices to argue that the marginal distributions are identical. Firstly, it is clear that \(b_1\) and \(b_1'\) are uniformly random bits. Secondly, observe that \(b_1'\cdot b_2'\) is by definition a random bit in \(\{-1,1\}\) with bias \(f(x,y)/\|\hat{f}\|_1\). In the original protocol, we observe that \(b_1\cdot b_2\) is a bit obtained by sampling \(S\sim p\) and returning \(\chi_S(x,y)\cdot \text{sign}(\hat{f}(S))\) – this is simply a random bit whose expectation is \(f(x,y)/\|\hat{f}\|_1\) by 5 . This completes the proof.  

---

7 \(k\)-player instantaneous computations based on the \(T\)-depth↩︎

In this appendix we give the proof of 4. Our techniques follow [11], but we make some generalizations to achieve the needed bound.

7.1 The garden-hose model↩︎

To give the proof, we first need to describe the garden-hose model and some associated instantaneous computation strategies. The garden-hose model [27] is most easily described in terms of the following setting. Alice and Bob are neighbours, and share a fence. Alice has an input string \(x\in\{0,1\}^n\), while Bob has an input string \(y\in\{0,1\}^n\). Alice has a tap, which she can turn on to produce a flow of water. Alice and Bob share a number of pipes which connect their yards, and they have hoses that they can use to connect pipes to one another, or the tap to a pipe. Alice and Bob wish to compute a Boolean function \(f(x,y)\), with the outcome determined by where the water spills. Typically, the model is defined so that water spilling on Alice’s side indicates \(f(x,y)=0\), while water spilling on Bob’s side indicates \(f(x,y)=1\). The garden-hose model can also be formalized in terms of path connectivity in a particular form of graph, see [27]. We won’t need this formalization though, and stick to the more informal water-based description.

We modify the definition of the garden-hose model somewhat and specify two pipes labelled “\(f=0\)” and “\(f=1\)”, and require the water to spill on Alice’s side out of the corresponding pipe. In fact, these models are not too different, as the following lemma from [28] shows.

The model where water spills from designated pipes will generalize better to the \(k\) player setting, so take the model with two designated pipes on Alice’s side as the defining setting. We denote the number of pipes needed to compute \(f\) in (this variant of) the garden-hose model by \(GH(f)\).

In the quantum context, the garden-hose model appears as a description of concatenated teleportations in some settings. In particular, consider an unknown quantum state \(\ket{\psi}\), which plays the role of the tap in the garden-hose description. Alice and Bob share a set of EPR pairs between them, which play the role of the pipes. Alice and Bob can then make Bell basis measurements, which act on either two ends of EPR pairs they hold in their own labs, or (in Alice’s case) on the input state plus the end of one EPR pair. To see why the water-flow analogy of the garden-hose model is relevant, consider that after the input state is measured with one EPR pair, the state has moved to the other end of the EPR pair, up to Pauli corrections. Each subsequent measurement moves the state to the other end of the measured EPR pair. To an observer with access to the measurement outcomes, it is as if the state is flowing along the path determined by the pipes in the garden-hose picture.

We generalize the garden-hose model to allow \(k\geq 2\) players, in which case we name the players Alice, Bob\(_1\), Bob\(_2\),..., Bob\(_{k-1}\). Each player receives a string of \(n\) bits, with \(x_0\) the string held by Alice and \(x_i\), \(k-1\geq i\geq 1\) held by Bob\(_i\). In this setting, pairs of players share pipes, and the actions of the players is as before: Alice may connect the tap to a pipe, and all players may connect open ends of pipes they have access to using hoses. Again the result of the computation is determined by considering two labelled pipes shared with Alice. This model can be instantiated as before in the quantum context with the tap replaced by an input state and the pipes replaced by EPR pairs. We define the minimal number of pipes used in a \(k\)-party garden-hose protocol by \(GH_k(f)\). Note that we allow any fixed configuration of pipe connections among the players.

We make use of the following lemma regarding the \(k\)-party garden-hose model. The proof is nearly the same as is given in [11], [28] for the case of two players. For completeness, we include the proof in our \(k\)-player setting.

Proof. Consider garden-hose protocols for each \(f_i\), which we label \(P_i\). We give a garden-hose protocol for \(\oplus_i f_i\) by wiring copies of the \(P_i\) together in an appropriate way. Concretely, we take 4 copies of \(P_i\), and connect them as shown in 3. The gadget has four open hoses, which we wire together with further gadgets: we wire the \(0\) output of the \(f_i\) gadget to the \(0\) input of the \(f_{i+1}\) gadget, and the \(1\) output of the \(f_i\) gadget to the \(1\) input of the \(f_{i+1}\) protocol. By inspection, one can check that the gadget flips the parity of the input if \(f_i=1\), and leaves the input unchanged if \(f_i=0\). To compute \(\oplus_i f_i\) then, we connect the tap to the \(0\) input of the \(f_1\) gadget, and label the \(0\) and \(1\) outputs of the final \(f_i\) as the \(0\) and \(1\) labelled output hoses of the protocol. After the water flows through gadgets for each \(f_i\), we’ve computed \(\oplus_i f_i\).  

---

7.2 A garden-hose gadget↩︎

Before stating the precise upper bound and its proof, we first need the following lemma, related to the garden-hose model. Specifically, we discuss the garden-hose complexity of implementing a controlled \(P^\dagger\) gate instantaneously, up to Pauli corrections, and the garden-hose complexity of the resulting corrections. The lemma is very similar to one in [11]; the only change is to point out that the proof there continues to apply in the context of the \(k>2\) party setting.

Proof. For the first part, run the garden hose protocol with \(S^{f(x)}\ket{\psi}\) as input, have Alice do \(S^\dagger\) to the \(f=1\) output hose, then wire the outputs to a copy of the protocol. The input qubit comes back out of the “input” wire of the second protocol, now with no \(S\) gate. This is illustrated in 4. Note that we incur Pauli corrections accumulated from all the Bell basis measurements along the path of the qubit.

Note that in the garden-hose protocol used to apply the conditional \(S^\dagger\) there is a sequence of teleportation measurements made, which create possible \(X\) and \(Z\) corrections. Call the bits determining if there is an \(X\) correction \(b_x^{i,j}\), where \(i,j\) label the two EPR pairs involved in the measurement. Similarly, there are corrections \(b_z^{i,j}\). Note that not all measurements contribute to these corrections, only those that occur in the unbroken chain of EPR pairs connected to the input state. Rather than obtain the input state with a \((S^\dagger)^{f(x,y)}\) applied, we actually end up applying, up to a global phase, the operator \[\begin{align} X^{\sum_{i\in A} b_x^{i,j}}Z^{\sum_{i\in A} b_z^{i,j}} (S^\dagger)^{f(x,y)} X^{\sum_{i\in B} b_x^{i,j}} Z^{\sum_{i\in B} b_z^{i,j}} \end{align}\] where the pairs of indices \((i,j)\in B\) correspond to measurements in the chain that occur before \((S^{-1})^{f(x,y)}\), while pairs \((i,j)\in A\) occur after. Using that (again up to a global phase) \[\begin{align} XZS^{\dagger} &= S^{\dagger}X \nonumber \\ S^{\dagger}Z &= ZS^{\dagger} \end{align}\] the above becomes \[\begin{align} X^{g(\hat{x})} Z^{h(\hat{x})} (S^{\dagger})^{f(x,y)} \end{align}\] where \[\begin{align} g(\hat{x}) &= \sum_{(i,j)\in A\cup B} b_x^{i,j}, \nonumber \\ h(\hat{x}) &= \sum_{(i,j)\in A\cup B} b_z^{i,j} + f(x,y) \sum_{(i,j)\in B} b_x^{i,j}. \end{align}\] Thus to compute \(g\), we just need to compute the parity of all of the \(b_x^{i,j}\) that occur in the chain. Note that which measurements are actually a part of the chain depends on \(x\), so this is a function of the original input \(x\) as well as the measurement outcomes \(b_x^{(i,j)}\). The function \(h\) is somewhat more involved, in particular there is an additional correction based on the \(b_{x}^{(i,j)}\) for measurements that occur before the conditional \(S^{\dagger}\).

Let’s begin with designing a garden-hose protocol to compute \(g(\hat{x})\). To do this, we create a “rail”, consisting of two EPR pairs, one for each EPR pair in the initial protocol. Then, we connect subsequent rails in the ordering defined by the sequence of EPR pairs used in the original protocol. We connect the rails end to end if \(b_x^{i,j}=0\), and we connect them cross-wise if \(b_x^{i,j}=1\). Thus after running over all \((i,j)\), the input is crossed if the parity of the \(b_x^{i,j}\) is odd, and left unchanged if the parity is even. This protocol uses twice the EPR pairs used in the protocol for applying \((S^{-1})^{f(x,y)}\), which itself was \(2GH(f)\), so the cost is \(4GH(f)\).

Now we consider the function \(h(\hat{x})\). We need a somewhat more involved protocol that treats EPR pairs before and after the conditional \(S^{\dagger}\) differently, and accounts for the value of \(f(x,y)\). To do this, we first run a garden-hose protocol to compute \(f(x,y)\), then feed the two output hoses into two different subsequent garden-hose protocols. The \(f=0\) pipe is input to a protocol computing the parity of just the \(Z\) corrections. We do this using the “rail” construction, just as in computing \(g(\hat{x})\). The \(f=1\) pipe is input to a similar rail protocol, which flips the rails if \(b_{x}^{(i,j)}\oplus b_z^{(i,j)}=1\) for pipes occurring before the \(S^{\dagger}\), and flips the pipes after the \(S^{\dagger}\) if \(b_z^{(i,j)}=1\). The garden-hose complexity of this protocol is composed of:

• The complexity of computing \(f(x,y)\), in a way that uses just two spilling pipes, which is \(3GH_k(f)\).

• The complexity of computing the \(Z\) corrections only, in the sub-protocol that is used when \(f(x,y)=0\). This is \(4GH_k(f)\), where the 4 comes from using the rail construction to double the pipes in the initial protocol, which itself was the protocol that involved computing \(f\), applying \(S^{\dagger}\), then running the protocol for \(f\) in reverse.

• The complexity of computing the parity of the \(b_{x}^{(i,j)}\oplus b_z^{(i,j)}\) for the first part of the protocol (before \(S^{\dagger}\)) along with the parity of the \(b_z^{(i,j)}\) in the later part of the protocol. This is \(4GH_k(f)\) again.

In total then the garden hose complexity of \(h(\hat{x})\) is \(11GH_k(f)\).  

---

7.3 Instantaneous \(k\)-party computations from \(T\)-depth↩︎

We are ready to prove our upper bound on the entanglement cost of implementing a unitary based on the \(T\)-depth. Before delving into the detailed proof, we give a heuristic understanding of where the dominant scaling of the entanglement cost comes from. The protocol involves first having all of the Bobs perform Bell basis measurements using EPR pairs shared with Alice, as if teleporting their states to her. This gives the full state in Alice’s lab, up to Pauli corrections which are determined by a distributed set of measurement outcomes. Alice then applies her first Clifford layer, then applies the first layer of \(T\) gates. We can conjugate the Pauli’s through the Clifford to give new Pauli’s, then through the \(T\) gates using the identities \[\begin{align} ZT &=TZ, \nonumber \\ TX &=SXT, \end{align}\] which hold up to a global phase. This leaves us in a state where one layer of the unitary has been applied, up to \(S\) corrections. We then use 4 to correct the \(S\) gates. There is an entanglement cost to doing this set by the garden-hose complexity of the function determining if there is an \(S\) gate or not. After correcting the \(S\) gates as needed, we begin again in the situation we started in, trying to apply a Clifford+\(T\) layer to a state with unknown Pauli corrections applied to it. We repeat the above procedure to apply the next layer. After each layer, the garden-hose complexity of the needed \(S\) corrections grows, and this growth controls the entanglement cost.

To capture the form of the \(S\) corrections more precisely and understand how their garden-hose complexity grows, define \(g_{i,j}=1\) if there is an \(X\) correction on the \(j\)th input wire and \(0\) otherwise, along with \(g_{i+1,j}=1\) if an \(X\) correction appears on the \(j\)th output wire after conjugation. Similarly, we define \(h_{i,j}\) and \(h_{i+1,j}\) to be 1 to indicate a \(Z\) correction on the input or output \(j\)th wire, respectively. Then, we can see that the output wire functions are related to the input wire functions by \[\begin{align} g_{i+1,k}&=\bigoplus_{j\in S_{g,k}} g_{i,j} \oplus \bigoplus_{j\in S_{g,k}'}h_{i,j},\nonumber \\ h_{i+1,k}&=\bigoplus_{j\in S_{h,k}} g_{i,j} \oplus \bigoplus_{j\in S_{h,k}'}h_{i,j}. \end{align}\] The subsets \(S_{g,k}^{(\prime)}\) and \(S_{h,k}^{(\prime)}\) depend on the choice of Clifford and the wire \(k\) being considered. For Clifford with backward light cones of size at most \(\ell\), we have that these sets are not larger than \(\ell\). From 3, we know how the garden-hose complexity of the XOR of many functions behaves, and in particular we can bound it by something of order \(\ell\) times the worst-case garden-hose complexity of the \(g_{i,j}\) and \(h_{i,j}\). The garden-hose complexity of the worst single qubit correction at layer \(i+1\), call it \(t_{i+1}\), then is related to the complexity at the previous layer by \(t_{i+1}\lesssim \ell \,t_i\). An added complication is that these Pauli corrections move through the \(T\) gates at this layer to give \(S\) gates, and then to correct the \(S\) gates we apply 4. This increases the garden-hose complexity of the Pauli corrections on that wire, but only by a constant factor that contributes to the value of \(K\). It is the XOR functions determined by the choice of Clifford that give the dominant scaling of the entanglement cost.

Finally, to solve the recursive relation \(t_{i+1}\lesssim t_i \ell\) we need to know the garden-hose complexity at the \(0\)th layer, which means the garden-hose complexity of the Pauli corrections right after the initial teleportation into Alice’s lab. These have constant garden-hose complexity, since they depend on just one bit held in one of the Bobs’ labs. After the first Clifford, denoted \(C_0^\ell\) then, the garden-hose complexity is at most \(\ell\), since the functions \(g_{1,i}\), \(h_{1,i}\) are XOR’s of \(\ell\) bits. However, it is possible some of those bits are held together in one lab, in which case the parity functions \(g_{1,i}\), \(h_{1,i}\) only depend on a parity of a subset of them, which the local party can pre-compute. For instance if we have \(k\)-parties, \(g_{1,i}\), \(h_{1,i}\) are XOR functions of at most \(k\) distributed bits. This means \(t_1=O( \min\{k,\ell\})\), and hence \(t_{d}\lesssim \min\{k,\ell\} (K\ell)^{d-1}\). Letting \(n_{\text{tot}}\) be the total number of qubits the unitary acts on, the entanglement cost for each layer is then bounded by \(n_{\text{tot}}\), the maximal number of possible \(S\) corrections at each layer, times \(t_i\), the worst-case correction complexity. The total entanglement cost is then the sum of the cost for each layer, \[\begin{align} E\leq \sum_{i=1}^d t_{i} n_{\text{tot}}\leq O((K\ell)^{d-1}\cdot n_{\text{tot}}\cdot \min\{k,\ell\}) \end{align}\] which is the claimed scaling. We give a formal proof and more detailed accounting in the theorem proof below.

Proof. We first have each of the Bobs ‘teleport’⁴ their systems \(B\) to Alice, who then holds \[\begin{align} X^{\vec{g}_{0}(y)}Z^{\vec{h}_0(y)}\ket{\psi}_{AB} \end{align}\] where, less succinctly, we mean \[\begin{align} X^{\vec{g}_0(y)}&=X_1^{g_{0,1}(y)}...X_n^{g_{0,n}(y)}\nonumber \\ Z^{\vec{h}_0(y)}&=Z_1^{h_{0,1}(y)}...Z_n^{h_{0,n}(y)} \end{align}\] where \(X_i\) and \(Z_i\) act on the \(i\)th qubit. Note that the entries of both \(\vec{h}\) and \(\vec{g}\) all have constant garden-hose complexity, since they are functions of single bits held in one of the Bobs labs.

This will serve as our base case in an inductive argument. We induct on the level \(i\), and assume Alice holds the state \[\begin{align} X^{\vec{g}_i(x,y)}Z^{\vec{h}_i(x,y)}\bar{T}_iC_i...\bar{T}_1C_1\ket{\psi}_{AB}. \end{align}\] where Alice holds \(x\) and Bob holds \(y\), and the entries of \(\vec{g}_i\) and \(\vec{h}_i\) have known garden-hose complexities. Define \[\begin{align} t_i=\max\{\max_j\{GH(g_{i,j})\},\max_j\{ GH(h_{i,j})\}\}. \end{align}\] In words \(t_i\) is the worst-case garden-hose complexity of any single \(X\) or \(Z\) correction in the \(i\)th layer. We have from above that \(t_0=2\).

To induct have Alice apply \(\bar{T}_{i+1}C_{i+1}\), obtaining \[\begin{align} \bar{T}_{i+1}C_{i+1}X^{\vec{g}_i(x,y)}Z^{\vec{h}_i(x,y)}\bar{T}_iC_i...\bar{T}_1C_1\ket{\psi}_{AB} = \bar{S}^{\vec{f}_i(x,y)}X^{\vec{g}_i'(x,y)}Z^{\vec{h}_i'(x,y)}\bar{T}_{i+1}C_{i+1}...\bar{T}_1C_1\ket{\psi}_{AB} \nonumber \end{align}\] Then, we use the procedure of 4 to undo the phase gates, obtaining \[\begin{align} X^{\vec{g}_{i}''(x,y)\oplus\vec{g}_i'(x,y)}Z^{\vec{h}_i''(x,y)\oplus\vec{h}_i'(x,y)}\bar{T}_{i+1}C_{i+1}...\bar{T}_1C_1\ket{\psi}_{AB}. \end{align}\] The functions \(\vec{g}'_{i}, \vec{h}'_{i}\) arise from commuting the \(X, Z\) operators through \(\bar{T}_{i+1}C_{i+1}\), while the \(\vec{g}''_{i}, \vec{h}''_{i}\) operators appear when correcting the phase gates. The singly-primed operators are of the form \[\begin{align} \label{eq:parityform} g'_{i,j}&=\bigoplus_{l\in S_{g,j}}{g}_{i,l}\oplus\bigoplus_{k\in S'_{g,j}}{h}_{i,k} \nonumber \\ h'_{i,j}&=\bigoplus_{l\in S_{h,j}}{g}_{i,l}\oplus\bigoplus_{k\in S'_{h,j}}{h}_{i,k} \end{align}\tag{6}\] where the subsets \(S_{g/h,j}^{(\prime)}\) depend on the Clifford, and have size at most \(\ell\).

The functions \(\vec{g}''_{i}, \vec{h}''_{i}\) appear when undoing the \(S^{\vec{f}(x,y)}\) operator, which we do using the procedure in 4. We are also provided with upper bounds on the garden-hose complexity of these functions from that lemma. We want to determine the garden-hose complexity of \(g_{i+1,j}=g_{i,j}''\oplus g_{i,j}'\) and \(h_{i+1,j}=h_{i,j}''\oplus h_{i,j}'\). Starting with \(g_{i+1,j}\), we have \[\begin{align} GH(g_{i+1,j})&=GH\left(\bigoplus_{l\in S_{g,j}}{g}_{i,l}\oplus\bigoplus_{k\in S'_{g,j}}{h}_{i,k}\oplus g_{i,j}'' \right)\nonumber \\ &\leq 4\left(\sum_{l}GH\left(g_{i,l} \right)+\sum_k GH(h_{i,k}) + GH(g''_{i,j})\right) \nonumber \\ &\leq 4\left(\sum_{l}GH\left(g_{i,l} \right)+\sum_k GH(h_{i,k}) + 4GH(f_{i,j})\right) \nonumber \\ &\leq 4\left(\ell t_i+ \ell t_i + 4GH(f_{i,j})\right) \end{align}\] where the first inequality uses 3 (the XOR lemma), the second line uses that \(GH(g''_{i,j})\leq 4GH(f_{i,j})\) which comes from 4, and the last uses the definition of \(t_i\).

It remains to bound the garden-hose complexity of \(f_{i,j}\). Notice that since \(f_{i,j}\) is itself a parity function of the \(g_{i,j}\) and \(h_{i,j}\) (it is of the form 6 ), so again its garden hose complexity is at most \(4\ell t_i\) by a use of the XOR lemma. Overall then this gives \[\begin{align} \label{eq:gupper} GH(g_{i+1,j})&\leq 4(\ell t_i+\ell t_i + 4\cdot 4\ell t_i) = 72\ell t_i \end{align}\tag{7}\] An upper bound can be determined for \(GH(h_{i+1,j})\) in a similar way. The only difference is that where before we used \(GH(g''_{i,j})\leq 4GH(f_{i,j})\), we now need \(GH(h''_{i,j})\leq 11GH(f_{i,j})\), which is given in 4. This changes the constant but gives a similar upper bound, \[\begin{align} \label{eq:hupper} GH(h_{i+1,j})&\leq 184 \ell t_i. \end{align}\tag{8}\] Using equations 7 and 8 , we get that \[\begin{align} t_{i+1}\leq 184 \ell t_i. \end{align}\] Our numerical constant is not optimal, but we lose the optimal constants in favour of a simpler presentation. We will write \(t_{i+1}=K\ell t_i\) to summarize the above. This relation and our earlier computation showing that \(t_1=\min\{\ell,k\}\) is solved by \[\begin{align} t_d\leq O((K\ell )^{d-1} \min\{\ell,k\}). \end{align}\] Summing over the corrections at each of the \(d\) layers, which each involve \(n_{\text{tot}}\) qubits, leads to the claimed upper bound.  

---

8 Newman’s Theorem for PSM↩︎

The following theorem shows that the randomness complexity in the PSM model is never much larger than the communication complexity. The proof is straightforward and similar to the well-known Newman’s theorem in communication complexity [29]; however we have not seen it recorded explicitly for PSM, so we give a proof here for completeness. A similar statement for the related conditional disclosure of secrets setting was proven in [30].

Proof.   Let \(D\) be the distribution from which the players sample their randomness (independently of their inputs). Sample \(r_1,\ldots,r_K\sim D\) where we take \(K=2^c\cdot (c+n)\cdot \log(1/\delta')/\epsilon^2\). We will think of \(r_1,\ldots,r_K\) being the common source of randomness for all inputs and in the new protocol, the players will instead sample \(k\sim [K]\) and run the original protocol with \(r_k\) as the randomness. We will now analyze the correctness and privacy of this protocol.

Privacy.

Fix any inputs \(x,y\). Now, each fixed random string \(r_i\) induces a fixed transcript \(m_{x,y}(r_i)\) and we consider the distribution \(M'_{x,y}\) on transcripts obtained by sampling \(i\sim[K]\) and outputting \(m_{x,y}(r_i)\). Compare it to the ideal distribution \(M_{x,y}\) on transcripts obtained by sampling a random \(r\sim D\) and outputting \(m_{x,y}(r)\). For any \(\tau\) in the support of the message space, we want that with high probability, the probabilities assigned to \(\tau\) by \(M_{x,y}\) and by \(M’_{x,y}\) differ very little — by at most \(t=\delta'/2^c\). By Hoeffding’s inequality, these probabilities differ by at least \(t\) with probability at most \(\exp(-t^2K)\). This means, by a union bound over all possible transcripts \(\tau\), that the total variation distance between \(M_{x,y}\) and \(M_{x,y}'\), given by \[\begin{align} \frac{1}{2}\sum_\tau |M_{x,y}[\tau]-M_{x,y}'[\tau]| \end{align}\] is at most \(t\cdot 2^{c}/2\) with probability at least \(1- \exp(-t^2K)\cdot 2^c\). Further, we want that these distributions are \(\delta'\)-close for all input pairs \(x,y\), which (by the union bound again) occurs with probability at least \(1-\exp(-t^2K)\cdot 2^c\cdot 2^n\). If this happens, then it would follow from the Triangle Inequality that the new protocol is \((\delta+2\delta')\)-private. Setting \(t=\delta'/2^c\) so that the total variation distance is at most \(\delta'\), we obtain that the bad event has probability at most \(\exp(-\delta'^2K/2^{2c})\cdot 2^c\cdot 2^n\). We want this to be strictly smaller than 1, so that by linearity of expectation, we can fix some random strings \(r_1,\ldots,r_K\) such that the distributions \(M'_{x,y}\) and \(M_{x,y}\) are \(\delta'\)-close in total variation distance for all \(x,y\). To achieve this bound, we only need to set \(K=\Theta(2^{2c}\cdot (c+n)/\delta'^2)\).

Correctness.

The correctness of this protocol follows immediately from the guarantee from earlier that the distribution \(M'_{x,y}\) is \(\delta'\)-close to \(M_{x,y}\) for all \(x,y\) – indeed, the referee’s output only depends on the distribution of the transcript, and since the original protocol is \(\epsilon\)-correct, the new protocol is \(\epsilon+\delta'\)-correct.  

---

References↩︎

---

1. \(\mathsf{Mod}_p\mathsf{L}\) contains \(\mathsf{NL}\), and this containment is believed to be strict.↩︎

2. See [5], section 4 for definitions of these functions.↩︎

3. Kim notes in v2 of [23] that after the release of the first version of the paper, Craig Gidney observed that it could be done in T-depth 2 [25].↩︎

4. By this we mean have each Bob measure their system in the Bell basis along with one end of a maximally entangled state, with the other end held by Alice.↩︎