Let \(f : \{ 0,1\} ^n \times \{ 0,1\} ^n \to \{ 0,1\} \) be a (partial or total) Boolean function and \(\epsilon \in [0,1]\). A simultaneous message passing protocol \(P\) for \(f\) has three parties: Alice (input \(x\)), Bob (input \(y\)), and a referee. Alice and Bob send the referee message systems \(M_A, M_B\) respectively, the referee outputs a bit \(c = P(x,y)\), and the parties do not otherwise communicate. The protocol is \(\epsilon \)-correct if \(\Pr [P(x,y)=f(x,y)] \ge 1-\epsilon \) for all \((x,y)\) in the support of \(f\). The cost \(\mathrm{cost}(P)\) is the total number of bits (classical) or qubits (quantum) sent by Alice and Bob; the complexity of \(f\) is the minimum cost over \(\epsilon \)-correct protocols. The variants are:

• messages classical = \(\mathsf{R}\| \), quantum = \(\mathsf{Q}\| \);

• \(\mathsf{D}\| \) = classical, deterministic, \(\epsilon = 0\);

• shared public randomness \(r\) available to all three parties: superscript \(\mathsf{pub}\), giving \(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon , \mathsf{Q}\| ^{\mathsf{pub}}_\epsilon \);

• Alice and Bob share entanglement: superscript \(*\), giving \(\mathsf{R}\| ^{*}, \mathsf{Q}\| ^{*}\).

When the subscript \(\epsilon \) is dropped, \(\epsilon = 1/3\). The complexities are \(\mathsf{D}\| (f), \mathsf{R}\| _\epsilon (f), \mathsf{Q}\| _\epsilon (f), \mathsf{R}\| ^{\mathsf{pub}}_\epsilon (f), \mathsf{Q}\| ^{\mathsf{pub}}_\epsilon (f), \mathsf{R}\| ^{*}(f), \mathsf{Q}\| ^{*}(f)\).

A private simultaneous message task is given by a Boolean function \(f:\{ 0,1\} ^n\times \{ 0,1\} ^n\to \{ 0,1\} \) and parameters \(\epsilon ,\delta \in [0,1]\). Alice (input \(x\)) sends a message system \(M_0\) and Bob (input \(y\)) sends \(M_1\) to the referee; from \(M = M_0 M_1\) the referee prepares an output bit \(z\) on a system \(Z\). Writing \(\rho _M(x,y)\) for the density operator on \(M\) produced on inputs \((x,y)\) and \(f_{x,y} = f(x,y)\), the task requires:

• \(\epsilon \)-correctness: there is a decoding map \(\mathbf{V}_{M\to Z\bar M}\) with, for all \((x,y)\) in the support of \(f\),

  \[ \lVert \operatorname {Tr}_{\bar M}\! \big(\mathbf{V}_{M\to Z\bar M}\, \rho _M(x,y)\, \mathbf{V}^\dagger _{M\to Z\bar M}\big) - \lvert f_{x,y}\rangle \langle f_{x,y}\rvert _Z \rVert _{1} \le \epsilon ; \]

• \(\delta \)-security: there is a simulator channel \(\mathcal{S}_{Z\to M}\) with, for all \((x,y)\) on which \(f\) is defined,

  \[ \lVert \rho _M(x,y) - \mathcal{S}_{Z\to M} (\lvert f_{x,y}\rangle \langle f_{x,y}\rvert _Z) \rVert _{1} \le \delta . \]

Classical messages give \(\mathsf{PSM}\); quantum messages give \(\mathsf{PSQM}\); shared entanglement adds the superscript \(*\) giving \(\mathsf{PSM}^{*}, \mathsf{PSQM}^{*}\). The cost is the total number of bits (resp. qubits) sent; \(\mathsf{PSM}_{\epsilon ,\delta }(f)\) etc. denote the minimal cost over \(\epsilon \)-correct, \(\delta \)-secure protocols (with \(\epsilon =1/3\) when omitted).

In the non-local quantum computation setting there is no referee: Alice and Bob each send a single simultaneous quantum message to the other and then perform local operations. Concretely, to implement a target channel \(\mathcal{N}\) on a bipartite input, Alice and Bob apply local channels \(\mathcal{V}^L,\mathcal{V}^R\) to their inputs together with their halves of shared entanglement, exchange messages, and apply further local channels \(\mathcal{W}^L,\mathcal{W}^R\), so that the overall map equals \(\mathcal{N}\). The cost is the total communication and shared entanglement.

Let \(f : \{ 0,1\} ^n \times \{ 0,1\} ^n \to \{ 0,1\} \) and \(\epsilon \in [0,1]\). A two-way classical communication protocol involves Alice (input \(x\)) and Bob (input \(y\)), who may share a random string \(r\). They exchange a sequence of messages (each computed from the local input, \(r\), and previously received messages), and Alice finally outputs a bit \(z\). The protocol is \(\epsilon \)-correct if \(\Pr [f(x,y)=z]\ge 1-\epsilon \) for all \((x,y)\) on which \(f\) is defined. The cost is the number of bits exchanged, maximized over inputs; the two-way complexity \(\mathsf{R}_\epsilon (f)\) is the minimum cost over \(\epsilon \)-correct protocols.