Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations

Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations

arXiv:2610.23090v1 [quant-ph] 16 Oct 2026

Harumichi Nishimura Graduate School of Informatics, Nagoya University

Abstract Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on n-bit inputs, which determines whether the players’ n-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633 . . .)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3 log2 3. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k ≥ 3, we construct a perfectly correct and perfectly private one-shot protocol for k-bit AND using one qudit of dimension at most k per player, and hence at most k log2 k qubits in total.

Contents 1 Introduction 1.1 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 5 7

2 Preliminaries 2.1 Classical private simultaneous messages . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Private simultaneous quantum messages . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Two linear-algebra lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 9

3 Entanglement-Assisted Advantage for Equality on Strings 3.1 Combinatorial embeddings by multicolored sum-free families . . . . . . . . . . . . . . 3.2 A binary physical two-user Bell primitive . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Odd-party four-coordinate secure sum . . . . . . . . . . . . . . . . . . . . . . . . . .

10 10 12 13

1

3.4 3.5 3.6

From blockwise secure sums to private generalized equality . . . . . . . . . . . . . . 15 Our upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Shared-randomness-only comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Three-Bit Boolean Functions 4.1 GHZ labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Majority and equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 An analytic family of 80 functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Computational exploration of a restricted GHZ–Pauli model . . . . . . . . . . . . . .

18 18 18 23 25

5 Unique-Preimage Impossibility 27 5.1 Rank lower bound and purification forced by correctness . . . . . . . . . . . . . . . . 28 5.2 Rank upper bound by privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6 One-Qudit Protocols for Multiparty AND 6.1 Generalized GHZ labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Our protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Correctness and privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 32 34 37

7 Conclusion

38

A Shared-Randomness Compression for the Three-Party Qutrit Protocol A.1 The 48-value construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Perfect privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39 40 41 41

2

1

Introduction

Private simultaneous messages (PSM) [7, 16] form a minimal model of secure multiparty computation. Several spatially separated players receive private inputs and send one message each to a referee, without interaction among the players. The referee must recover the prescribed function value while learning nothing beyond that value. In the quantum version, called private simultaneous quantum messages (PSQM), the transmitted messages may be quantum states, and the players may share prior entanglement in addition to classical randomness. Kawachi and Nishimura [14] introduced the PSQM model and demonstrated that quantum communication and prior entanglement can reduce communication under perfect correctness and perfect privacy. Their results include a factor-two separation between PSQM and PSM for a total function extending two-party equality and an exponential separation for a partial function. More recently, Girish, May, Orshansky, and Waddell [8] obtained an exponential separation for a partial function in the robust setting which allows correctness and privacy errors. These results demonstrate that genuinely quantum resources can provide substantial advantages across both perfect and approximate privacy regimes. The behavior of familiar concrete functions, however, remains much less understood. This issue already appears in the classical PSM model. General upper and lower bounds have been developed [7, 3, 2], but a substantial gap between them remains. Various concrete functions have also been studied [7, 16], yet matching upper and lower bounds, and hence the optimal communication complexity, are known in only a few cases. Shinagawa and Nuida [21] advanced this line of research by deriving explicit lower bounds for concrete functions such as AND, majority, and equality. In particular, they determined the optimal classical PSM communication complexity for three-input majority and equality, while the precise complexity of three-input AND remained unresolved. This suggests that even among very small Boolean functions, private communication complexity may depend on structural features that are not captured by ordinary circuit complexity or by the apparent simplicity of their algebraic representations. This paper initiates a parallel investigation of perfectly correct and perfectly private PSQM protocols. Our goal is not merely to exhibit another specially designed separation, but to understand which types of concrete functions admit an advantage from prior entanglement and which structural features can obstruct efficient private quantum protocols. Our results reveal a striking contrast among Boolean functions. Entanglement provides communication savings for certain equality- and majority-type functions, whereas functions with a unique preimage, such as AND, encounter a strong obstruction when each player applies a local unitary encoding to one qubit and transmits that qubit to the referee. This contrast suggests that the complexity of a function in PSQM is not determined merely by its algebraic or computational simplicity. Rather, the sets of accepting and rejecting inputs and the effect of local input changes on the shared state play a central role. Table 1.1 summarizes the communication bounds established or used in this paper. Standalone values denote optimal communication costs, whereas inequalities and intervals denote upper or lower bounds. The classical and quantum communication costs are measured in bits and qubits, respectively. Our results are described in more detail below.

1.1

Our contributions

We develop this viewpoint through four complementary results.

3

Function

Classical PSM

EQk,n

≥ kn bits

MAJ3

6 bits [21]

Entanglement-assisted PSQM ≤

√ k n + Ok ( n) qubits 2h2 (1/k) 3 qubits

EQ3

3 log2 3 bits [21]

3 qubits

AND3

[6, 3 log2 5] bits [7, 21]

≤ 3 log2 3 qubits

ANDk (k ≥ 3)

≤ k log2 ℓk bits [7]

≤ k log2 pk ≤ k log2 k qubits

Table 1.1: Classical and entanglement-assisted quantum communication bounds for the functions studied in this paper. Here, ℓk is the smallest prime greater than k, while pk is the smallest prime satisfying k ≤ 2(pk − 1). The interval in the AND3 row gives the currently known classical lower and upper bounds. Entanglement-assisted advantage for multiparty equality. Our first result establishes an entanglement-assisted advantage for a standard predicate, rather than for a function designed specifically to produce a separation. For the multiparty equality function on n-bit strings, EQk,n (x1 , . . . , xk ) = 1[x1 = · · · = xk ], where 1[P ] equals 1 if the predicate P is true and 0 otherwise, we obtain an asymptotic separation between entanglement-assisted PSQM and PSQM without prior entanglement. Using multicolored sum-free families, we reduce the equality function to the generalized-equality problem studied in [14]. For three parties, the asymptotically tight tri-colored sum-free construction of Kleinberg, Sawin, and Speyer [15], completed by Pebody [18], yields a local embedding into Fd2 √ n with d = h2 (1/3) + O( n), where h2 is the binary entropy function. More generally, for fixed k, we use the corresponding construction of Lovász and Sauermann [19]. For odd k, the protocol in [14] incurs a dummy-user penalty. Inspired by the odd-party securesum construction of Lu, Yao, and Jafar [20], we develop a one-shot four-coordinate secure-sum layer that removes this penalty. Let QPSQM,∗ (f ) denote the minimum communication cost of a perfectly correct and perfectly private entanglement-assisted PSQM protocol for f . The resulting bound is √ k n + Ok ( n). 2h2 (1/k) √ For k = 3, this becomes QPSQM,∗ (EQ3,n ) ≤ (1.633 . . .)n + O( n). In contrast, every perfectly correct PSQM protocol without prior entanglement, even with arbitrary shared classical randomness, requires at least kn communicated qubits. Hence the construction gives a strict asymptotic separation for every fixed 3 ≤ k ≤ 9. QPSQM,∗ (EQk,n ) ≤

Three-bit majority and the local-Pauli landscape. We next study three-party perfectly correct and perfectly private PSQM protocols for three-bit functions in which each party has a onebit input. Starting from the optimal classical six-bit PSM protocol for the three-bit majority MAJ3 due to Shinagawa and Nuida [21], we obtain a three-qubit protocol for MAJ3 using one shared GHZ state, local Pauli encodings, and one transmitted qubit per player. We then compress the shared randomness to two bits while preserving the same two output-dependent density operators. A local parity twist converts this protocol into one for the three-bit equality EQ3 . These protocols yield quantum communication advantages since the optimal classical communication costs of MAJ3 and EQ3 are 6 and 3 log2 3 bits, respectively [21]. 4

We further construct protocols for a family of exactly 80 three-bit Boolean functions. Writing the algebraic normal form as f (x, y, z) = c ⊕ ax ⊕ by ⊕ dz ⊕ αxy ⊕ βxz ⊕ γyz ⊕ δxyz, we construct protocols whenever δ = 0 and (α, β, γ) ∈ {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)}. These conditions describe exactly 80 Boolean functions. A structural barrier for AND and unique preimage. Although the three-bit AND function AND3 may appear simpler than MAJ3 , the two functions behave very differently in our PSQM setting. Let f : {0, 1}k → {0, 1} be a function for which one of the two output values has exactly one preimage. We prove that no perfectly correct and perfectly private PSQM protocol exists in the one-qubit local-unitary model : the players share an arbitrary k-qubit mixed state and arbitrary classical randomness, apply arbitrary local U (2) encodings, and transmit one qubit each. The proof combines a structural property of one-qubit unitaries with rank bounds. After complementing the output if necessary, suppose that the unique input has output 1. Perfect correctness gives vanishing overlaps between its received state and the states obtained by nonempty sets of input flips. For single-coordinate flips, the one-qubit structural lemma (Lemma 2.4) forces the corresponding relative unitaries to be Hermitian involutions up to global phase. The full family of input-flip conditions then produces 2k − 1 mutually orthogonal pure-state components corresponding to output 0 in supp(ϱ0 ), where ϱ0 denotes the output-dependent state received by the referee whenever the function value is 0. Hence rank(ϱ0 ) ≥ 2k − 1. The resulting one-qubit structure, together with perfect privacy, confines this support to a three-dimensional local-action subspace, giving rank(ϱ0 ) ≤ 3. These bounds are incompatible for k ≥ 3. The theorem applies to all Boolean point functions, including the k-bit AND function ANDk , and their complements. The contrast between MAJ3 and AND3 therefore illustrates two different roles of entanglement in PSQM: a single GHZ state yields an efficient protocol for majority, whereas no shared three-qubit state suffices for AND in the one-qubit local-unitary model. One-qudit protocols for multiparty AND. The one-qubit obstruction is not an impossibility for PSQM itself: it can be overcome by increasing the local message dimension. We construct a one-shot PSQM protocol for ANDk using a single generalized GHZ state. A zero-sum-free construction ensures that the all-one input is distinguished from every other input, and a finite-field randomization hides which rejecting input was given. For every prime p satisfying k ≤ 2(p − 1), the protocol uses one p-dimensional qudit per player and has communication cost k log2 p. Since such a prime can always be chosen with p ≤ k by Bertrand’s postulate, we obtain QPSQM,∗ (ANDk ) ≤ k log2 k. For k = 3, the construction gives a one-qutrit protocol with communication 3 log2 3. Together with the classical lower bound of 6 bits in [21], this yields a strict quantum communication advantage for three-bit AND.

1.2

Related work

Classical private simultaneous messages for concrete functions. Shinagawa and Nuida [21] derived explicit upper and lower bounds for several concrete functions. Their protocols 5

and lower bounds, including the optimal bounds for MAJ3 and EQ3 , provide the principal classical comparison for our three-bit protocols. For two-input AND, the protocol of Feige, Kilian, and Naor [7] and the matching lower bound of Data, Prabhakaran, and Prabhakaran [6] establish the optimal classical communication cost of 2 log2 3 bits. Quantum versions of private simultaneous messages. Several quantum variants of the private simultaneous-message model have been studied. In PSQM, the model considered in this paper, the players receive classical inputs and may transmit quantum messages. In quantum private simultaneous messages (QPSM), each player may instead receive a quantum input register and transmit a quantum message to the referee. In [14], the authors introduced PSQM and established separations between entanglementassisted and shared-randomness-only protocols. Christensen and Popovski [5] constructed privateproduct protocols over prime fields using shared entanglement. Over the binary field, their protocol computes two-input AND using a shared Bell pair and one transmitted qubit from each player. Together with the classical bound above, this yields an entanglement-assisted communication advantage for AND2 . Our impossibility theorem contrasts this positive two-party result with the one-qubit local-unitary obstruction for AND3 . Allerstorfer, Buhrman, May, Speelman, and Verduyn Lunel [1] related PSQM to nonlocal quantum computation by deriving PSQM protocols from coherent function evaluation, a special case of position verification. Girish, May, Parham, and Yuen [9] showed that simultaneous quantummessage protocols with a low-T -depth referee can be transformed into entanglement-assisted PSM protocols with classical messages and approximate privacy. In subsequent work [10], they established general upper and lower bounds for PSM and PSQM, including correlation-cost lower bounds based on Nečiporuk’s measure and communication-matrix rank, and upper bounds based on Clifford + T -gates decomposition and Fourier 1-norm. These works provide general constructions, resource bounds, and connections with other computation models and complexity measures. Our results are complementary in focusing on perfect correctness, perfect privacy, and the communication complexity of concrete functions. Kawachi and Nishikubo [13] introduced private quantum signal processing and obtained PSM protocols with a one-qubit quantum evaluator for symmetric Boolean functions and functions admitting efficient one-qubit programs. These protocols send classical gate descriptions and therefore operate in a different resource regime from ours. Quantum decomposable randomized encodings and QPSM. In the classical setting, decomposable randomized encodings correspond to PSM protocols under an appropriate partition of the input. Brakerski and Yuen [4] developed a quantum analogue by introducing quantum randomized encodings and constructing a quantum decomposable randomized encoding (QDRE) for general quantum circuits. Gur, Huang, and Tang [11] subsequently established a corresponding equivalence between QDRE and QPSM for the qubit-by-qubit case: QDREs for k-qubit inputs decomposed into individual input qubits are equivalent to k-party QPSM protocols with one-qubit local inputs, with preservation of quantum encoding size and quantum communication. This correspondence does not directly cover our model. Their QPSM setting has quantum inputs and charges only quantum communication, whereas in our PSQM setting both classical and quantum message components contribute to the total communication cost.

6

1.3

Organization

Section 2 defines the PSQM model and gives the required linear-algebraic preliminaries. Section 3 proves the entanglement-assisted upper bounds for EQk,n . Section 4 gives the PSQM protocols for MAJ3 and EQ3 , the analytic construction of 80 Boolean functions, and the finite linear-programming experiment. Section 5 proves the unique-preimage impossibility theorem in the one-qubit local-unitary model. Section 6 develops the PSQM protocol for multiparty AND while Appendix A gives a three-party-specific shared-randomness compression. Section 7 discusses the resulting picture for concrete functions and open problems.

2

Preliminaries

2.1

Classical private simultaneous messages

We first recall a classical private simultaneous-message (PSM) protocol. Let k ≥ 2, let X = X1 × · · · × Xk , and let f : X −→ Y be a function with finite input and output alphabets. We call the inputs x with f (x) = 1 and f (x) = 0 the accepting inputs and the rejecting inputs, respectively. In a PSM protocol, player Pi receives its local input xi ∈ Xi , and the players share an inputindependent classical random variable r whose distribution p has finite support R,1 and r ∈ R is hidden from the referee. Player Pi sends mi (xi ; r) ∈ Mi to the referee, and the referee applies a decoding function D : M1 × · · · × Mk −→ Y to obtain the output. The players send their messages simultaneously and do not communicate with one another during the protocol. Perfect correctness requires
D m1 (x1 ; r), . . . , mk (xk ; r) = f (x1 , . . . , xk ) for every input x = (x1 , . . . , xk ) and every r ∈ R. For each input x, let Dx denote the distribution of the joint message tuple
m1 (x1 ; r), . . . , mk (xk ; r) , where the probability is over the shared randomness. Perfect privacy requires f (x) = f (x′ ) =⇒ Dx = Dx′ . Thus the referee’s complete view reveals no information about the input beyond the value of f . Q  Pk k The communication cost is log |M | = log |M | . A protocol with messagei i 2 2 i=1 i=1 alphabet sizes |M1 | = d1 , . . . , |Mk | = dk is called a (d1 , . . . , dk )-PSM protocol. For example, a (4, 4, 4) PSM protocol has three players, each of whom sends one of four possible messages. Its total communication cost is log2 4 + log2 4 + log2 4 = 6 bits.

2.2

Private simultaneous quantum messages

We assume familiarity with the basics of quantum information and quantum computation and standard notations such as Pauli matrices [17]. L(A) denotes the set of all linear operators on a linear space A, and D(B) denotes the set of mixed states over a quantum register B. 1

We restrict the shared randomness to distributions with finite support. This entails no loss of generality in the finite-input, finite-dimensional setting considered here.

7

The private simultaneous quantum message (PSQM) model replaces the classical message alphabets by quantum message registers and additionally allows the players to share prior entanglement. We now give the precise PSQM model used throughout this paper. This is an equivalent reformulation of the original PSQM model in [14], stated directly in terms of the joint message state received by the referee. Whereas the original formulation expresses correctness through the referee’s output probability and privacy through the existence of a simulator, we equivalently formulate these conditions below as properties of the averaged joint message state. Let k ≥ 2, let X = X1 ×· · ·×Xk , and let f : X −→ Y be a function with finite input and output alphabets. An input to the protocol is a tuple x = (x1 , . . . , xk ) ∈ X, where player Pi receives only its local input xi ∈ Xi . A k-party PSQM protocol for f consists of the following objects. 1. An input-independent shared random variable r whose distribution p has finite support R. 2. An input-independent multipartite state σA1 ···Ak ∈ D(A1 ⊗ · · · ⊗ Ak ), shared among the players and independent of r. Player Pi holds register Ai . The referee holds no part of these setup resources before the communication. 3. For every player Pi , local input xi ∈ Xi , and r ∈ R, a quantum channel Eixi ,r : L(Ai ) −→ L(Mi ). Player Pi applies Eixi ,r to register Ai and sends the resulting message register Mi to the referee. 4. A decoding measurement, represented by a POVM {Dy : y ∈ Y }, on the joint message register M := M1 ⊗ · · · ⊗ Mk . The players send their messages simultaneously and do not communicate with one another during the protocol. For a global input x = (x1 , . . . , xk ) and a fixed value r of shared randomness, define
ρx,r := E1x1 ,r ⊗ · · · ⊗ Ekxk ,r (σ). Since the shared randomness is hidden from the referee, the referee actually receives X ρx := p(r)ρx,r . r∈R

Thus, throughout this paper, x denotes the global input tuple, whereas ρx denotes the joint state of all message registers received by the referee on input x, after averaging over all input-independent shared randomness. The protocol is perfectly correct if, for every x ∈ X,
Tr Df (x) ρx = 1. The protocol is perfectly private if there exist density operators {ϱy ∈ D(M) : y ∈ Y } such that ρx = ϱf (x) for every x ∈ X. Equivalently, f (x) = f (x′ )

=⇒

ρx = ρx′ .

This is the simulation-based privacy condition for a classical-output function: a simulator given only y = f (x) can reproduce the referee’s global view by preparing ϱy . If the protocol is both perfectly correct and perfectly private, then the output-dependent states have mutually orthogonal supports: supp(ϱy ) ⊥ supp(ϱy′ ) 8

(y ̸= y ′ ).

The communication cost of the protocol is k X

log2 dim Mi = log2 dim M.

(2.1)

i=1

No additional free classical transcript is allowed. If a message contains a classical string, that string is represented by an orthogonal register and its dimension is included in (2.1). A protocol is shared-randomness-only if the shared state is a product state, σA1 ···Ak = σA1 ⊗ · · · ⊗ σAk . Since the input-independent local states σA1 , . . . , σAk can be absorbed into the local encoding channels, this is equivalent to the usual model in which the players share only the classical random variable. An entanglement-assisted protocol may use an arbitrary multipartite mixed state σA1 ···Ak , independent of the shared random variable. The shared state and the shared randomness are inputindependent and are not charged as communication. We nevertheless specify these resources explicitly when stating concrete protocols. We write QPSQM (f ) for the minimum communication cost of a perfectly correct and perfectly private shared-randomness-only protocol for f , and QPSQM,∗ (f ) for the corresponding minimum cost of an entanglement-assisted protocol. Remark 2.1 (Relation to the original PSQM model). The definition above is equivalent to the PSQM model in [14]. We describe a fixed shared state and independent shared randomness simultaneously, since the latter can equivalently be represented by correlated orthogonal registers in the shared state. Our main difference is presentational: we formulate correctness and privacy directly in terms of the averaged joint message state ρx . Remark 2.2 (Relation to decomposable randomized encodings). For classical inputs and a classical output, a PSQM protocol in our model may be viewed as an information-theoretic quantum decomposable randomized encoding with respect to the fixed input partition X = X1 × · · · × Xk , whose setup consists of a fixed multipartite state together with independent shared classical randomness. The collection of message registers generated by the local encoders forms the decomposable encoding, the referee’s measurement is the decoder, and the output-dependent states in the privacy condition give the simulator. Conversely, a quantum decomposable randomized encoding with this input partition and with a setup consisting of independent shared classical randomness and a fixed shared quantum state gives a PSQM protocol in our model. Under this correspondence, the total encoding size equals the PSQM communication cost.

2.3

Two linear-algebra lemmas

P Lemma 2.3 (support of a positive mixture). If A = j cj Aj with cj > 0 and Aj ≥ 0, then supp(Aj ) ⊆ supp(A) for every j. Hence, if A and B have orthogonal supports, every positive component of A has support orthogonal to every positive component of B. P Proof. If |z⟩ ∈ ker A, then 0 = j cj ⟨z|Aj |z⟩. Since every term is nonnegative, Aj |z⟩ = 0 for every j. Thus ker A ⊆ ker Aj , equivalently supp(Aj ) ⊆ supp(A).

9

Lemma 2.4 (zero-expectation qubit-unitary structure). Let τ be a one-qubit density operator and V ∈ U (2). If Tr(τ V ) = 0, then up to a global phase, V is a Hermitian involution: V † = V and V 2 = I. Proof. Let σ := (X, Y, Z) denote the vector of Pauli matrices. For v = (vx , vy , vz ) ∈ R3 , write v · σ := vx X + vy Y + vz Z. Using the Bloch representation of a qubit state and the standard parametrization of a 2 × 2 unitary, write 1 V = eiα (cos θ I + i sin θ n · σ) , τ = (I + t · σ) , 2 where t ∈ R3 , ∥t∥ ≤ 1, n ∈ R3 , ∥n∥ = 1. Let V ′ = e−iα V . The direct calculation using standard relations on Pauli matrices (such as Equation (2.78) in [17]) gives Tr(τ V ′ ) = cos θ + i sin θ t · n. The hypothesis Tr(τ V ) = 0 implies Tr(τ V ′ ) = 0 and, by taking the real part, that cos θ = 0. Hence sin θ = ±1. Let V ′′ = −i sin θV ′ = n · σ. Then V ′′ is Hermitian and satisfies (n · σ)2 = I. V ′′ is equal to V up to a global phase.

3

Entanglement-Assisted Advantage for Equality on Strings

We begin in Section 3.1 with the combinatorial reduction from EQk,n to generalized equality, and recall the previously known protocol, to derive some non-trivial upper bound for EQk,n . Sections 3.2 and 3.3 develop the Bell-based secure-sum primitives needed to remove the odd-party dummy-user penalty. Section 3.4 applies these primitives blockwise, and uses random nonzero scaling to obtain a PSQM protocol for generalized equality. Section 3.5 combines this protocol with the combinatorial reduction to derive the upper bound for EQk,n claimed in Section 1.

3.1

Combinatorial embeddings by multicolored sum-free families

For a positive integer L, write [L] = {1, . . . , L}. Let h2 denote the binary entropy function: h2 (p) = −p log2 p − (1 − p) log2 (1 − p). Definition 3.1. A k-colored sum-free family of size L in an abelian group G is a collection {(a1,v , . . . , ak,v ) : v ∈ [L]} ⊆ Gk such that a1,v1 + · · · + ak,vk = 0

⇐⇒

v1 = · · · = vk .

For an abelian group G, let sfsk (G) denote the maximum size of a k-colored sum-free family in G, where G is regarded as an additive group. For k = 3, the corresponding asymptotically tight construction was obtained by Kleinberg, Sawin, and Speyer [15], together with Pebody’s proof of the required conjecture [18]. Lovász and

10

Sauermann [19] proved a general lower bound for k-colored sum-free families in Zdm . Applying their Theorem 1.3 to the binary group Zd2 = Fd2 gives √ d−Ok ( d)

sfsk (Fd2 ) ≥ Γ2,k

,

where Γ2,k = min (1 + γ)γ −1/k . 0<γ<1

Indeed, logarithmic differentiation gives
(k − 1)γ − 1 d log (1 + γ)γ −1/k = . dγ kγ(1 + γ) Hence the objective decreases before γ = 1/(k−1) and increases thereafter, and its unique minimum is attained at γ = 1/(k − 1). It follows that Γ2,k =

k = 2h2 (1/k) . (k − 1)(k−1)/k

Therefore,

√

sfsk (Fd2 ) ≥ 2h2 (1/k)d−Ok ( d) .

(3.1)

Lemma 3.2 (fixed-k local embedding). Fix k ≥ 3. For all sufficiently large n, there are an integer d=

√ n + Ok ( n) h2 (1/k)

and local maps Aj : {0, 1}n −→ Fd2 , such that

k X

Aj (xj ) = 0

⇐⇒

j ∈ [k],

x1 = · · · = xk .

j=1

√ n Proof. By (3.1), we may choose d = h2 (1/k) + Ok ( n) such that sfsk (Fd2 ) ≥ 2n . Choose a k-colored sum-free family of size 2n , and index its members by x ∈ {0, 1}n : {(a1,x , . . . , ak,x ) : x ∈ {0, 1}n } ⊆ (Fd2 )k . For each j ∈ [k], define Aj (x) := aj,x . Then k X

Aj (xj ) = 0

⇐⇒

x1 = · · · = xk ,

j=1

by the defining property of the sum-free family. The sum-free theorem uses only the additive group. In particular, Zd2 = (Fd2 , +). Field multiplication is introduced only after the embedding, through a chosen additive isomorphism with F2d . No multiplicative closure of the sum-free family is assumed or required.

11

For u1 , . . . , uk ∈ Fd2 , define the generalized equality function2 GEQk,d (u1 , . . . , uk ) = 1[u1 + · · · + uk = 0]. In [14], the authors gave perfectly correct and perfectly private entanglement-assisted protocols satisfying, for even d, ( kd/2, k even, PSQM,∗ Q (GEQk,d ) ≤ (3.2) (k + 1)d/2, k odd. Note that for odd k, the last party simulates an additional zero-input dummy party. Combining Lemma 3.2 with (3.2), and padding the embedded vectors by at most one zero coordinate, gives the parity-dependent bounds  √ k   n + Ok ( n), k even,  2h2 (1/k) QPSQM,∗ (EQk,n ) ≤ √ k+1    n + Ok ( n), k odd. 2h2 (1/k) In particular, for k = 3, QPSQM,∗ (EQ3,n ) ≤

√ √ 2 n + O( n) = (2.177 . . .)n + O( n). h2 (1/3)

We retain these bounds for comparison with the improved odd-party layer below.

3.2

A binary physical two-user Bell primitive

Let |Φ0,0 ⟩ =

|00⟩ + |11⟩ √ , 2

|Φa,b ⟩ = (X a Z b ⊗ I)|Φ0,0 ⟩,

a, b ∈ F2 .

These four Bell states form an orthonormal basis. Since (I ⊗ M )|Φ0,0 ⟩ = (M T ⊗ I)|Φ0,0 ⟩, suitable local Pauli operations map two users’ input pairs (a1 , a2 ) and (b1 , b2 ) to |Φa1 +b1 ,a2 +b2 ⟩ up to global phase. Concretely, the two users initially share |Φ0,0 ⟩ with each user holding one qubit, and apply X a1 Z a2 and X b1 Z b2 , respectively. Up to a global phase, the referee receives |Φa1 +b1 ,a2 +b2 ⟩ and obtains (a1 + b1 , a2 + b2 ) by the Bell-basis measurement. Thus two transmitted qubits carry two binary sums, and the joint state received by the referee depends only on those sums. In what follows, we call this protocol the two-user Bell primitive. 2

This name was used in [14] since it matches the equality function for the k = 2 case.

12

3.3

Odd-party four-coordinate secure sum

Lemma 3.3 (four-coordinate secure sum for odd k). Let k ≥ 3 be odd. Player i, for i = 1, . . . , k, holds four bits (1) (2) (3) (4) wi , wi , wi , wi ∈ F2 . There is a perfectly correct and perfectly private PSQM protocol for the four sums S

(ℓ)

=

k X

(ℓ)

wi

∈ F2 ,

ℓ = 1, 2, 3, 4.

i=1

The protocol uses exactly 2k transmitted qubits and no dummy party. Proof. We use players 1, 2, 3 to run two independent triangle instances. The first instance handles the coordinate pair (1, 2), and the second handles the coordinate pair (3, 4). Each triangle instance assigns one binary value to each of the three edges {1, 2},

{1, 3},

{2, 3}.

We will pack the two values assigned to the same edge into one application of the two-user Bell primitive from Section 3.2. We first describe one triangle instance. Suppose that players 1, 2, 3 hold input pairs (ui , vi ) ∈ F22 ,

i = 1, 2, 3.

Choose a uniform r ∈ F2 , and assign the edge values Y12 = v1 + (u2 + r), Y13 = (u1 + v1 ) + (u3 + r), Y23 = (u2 + v2 ) + (v3 + r) to the edges {1, 2}, {1, 3}, {2, 3}, respectively. Each edge value is the sum of one bit locally computable by each endpoint. For example, on edge {1, 2}, player 1 contributes v1 , while player 2 contributes u2 + r. Similarly, on edge {1, 3}, players 1 and 3 contribute u1 + v1 and u3 + r, respectively; on edge {2, 3}, players 2 and 3 contribute v2 + u2 and v3 + r, respectively. Since r is shared randomness, all these contributions are locally computable by the indicated endpoints. The referee can reconstruct Y12 + Y13 = u1 + u2 + u3 , Let Su :=

3 X

Y12 + Y23 = v1 + v2 + v3 .

ui ,

Sv :=

i=1

3 X

vi .

i=1

Setting t := Y12 , we have (Y12 , Y13 , Y23 ) = (t, Su + t, Sv + t). Since r is uniform, so is t. Thus, conditioned on (Su , Sv ), the joint distribution of the three edge values is uniform over {(t, Su + t, Sv + t) : t ∈ F2 } , 13

and hence depends only on (Su , Sv ). Apply this construction first with (1)

(2)

(3)

(4)

(ui , vi ) = wi , wi and independently with (e ui , vei ) = wi , wi

.

Denote the resulting edge values by [1]

Yab

[2]

and

 {a, b} ∈ {1, 2}, {1, 3}, {2, 3} .

Yab ,

For each edge {a, b}, its endpoints now have two pairs of local contributions, one pair for each triangle instance. They use these as their two-bit inputs to one application of the Bell primitive [1] [2]
in Section 3.2. The referee consequently recovers Yab , Yab by the Bell-basis measurement. Thus each edge uses one Bell pair, and the two triangle instances together use three Bell pairs and transmit six qubits. Now write k = 2m + 1 and partition the remaining players into the unordered pairs {4, 5}, {6, 7}, . . . , {k − 1, k}, with the collection understood to be empty when k = 3. Using the common classical randomness shared by all k players, choose independent uniform masks (ℓ)

zj ∈ F2 ,

j = 1, . . . , m − 1,

ℓ = 1, 2, 3, 4.

For pair j, denote its endpoints by aj and bj , and let the pair supply (ℓ)

(ℓ)

(ℓ)

Qj = wa(ℓ) + w bj + z j . j Each remaining pair shares two Bell pairs, one for coordinates (1, 2) and one for coordinates (3, 4), and therefore transmits four qubits. The first three users run the two triangle instances with shifted partial sums m−1 X (ℓ) (ℓ) (ℓ) (ℓ) (ℓ) T = w1 + w2 + w3 + zj . j=1

Pm−1

(ℓ)

(ℓ)

(ℓ)

For each coordinate ℓ, the shift j=1 zj is implemented locally by adding this shared offset to one selected input of the corresponding three-user triangle. The referee then reconstructs T

(ℓ)

+

m−1 X

(ℓ)

(ℓ)

Qj = w1 + w2 + w3 +

j=1

 X (ℓ) X  (ℓ) (ℓ) zj + wa(ℓ) + w + z j bj j j

=S

(ℓ)

j

. (ℓ)

We next verify privacy. For fixed inputs, the random variables Qj are independent uniform bits, (ℓ)

because the masks zj are independent and uniform. Conditioned on the four global sums, the shifted triangle targets are determined by T (ℓ) = S (ℓ) +

m−1 X j=1

14

(ℓ)

Qj .

For the triangle instance associated with coordinates (ℓ1 , ℓ2 ), conditioned on T (ℓ1 ) , T (ℓ2 ) , its three edge values are uniform over n  o t, T (ℓ1 ) + t, T (ℓ2 ) + t : t ∈ F2 . It follows that the joint distribution of all edge values depends only on the four global sums   S (1) , S (2) , S (3) , S (4) . Each Bell block is, up to global phase, a pure orthogonal Bell state completely determined by its two edge values. Therefore the averaged joint state received by the referee also depends only on the four global sums. Finally, the first three players transmit six qubits, and each of the remaining k−3 k−3 2 = m−1 pairs transmits four qubits. Hence the total communication is 6+4 2 = 2k qubits. The triangle, pairing, and mask-cancellation pattern are based on the odd-k secure-sum idea of Lu, Yao, and Jafar [20]. Lemma 3.3 expands their normalized additive-channel accounting into physical Bell-state primitives and makes explicit the finite four-coordinate block used in our one-shot generalized-equality protocol.3

3.4

From blockwise secure sums to private generalized equality

The preceding subsection gives a four-coordinate secure-sum block for odd k, while the protocol of [14] gives the required two-coordinate secure-sum block for even k. After padding and partitioning the embedded vectors into blocks of the appropriate size, these primitives produce a received state Pk that depends only on the full aggregate s = i=1 yi . Correctness for generalized equality requires distinguishing s = 0 from s ̸= 0, but perfect privacy additionally requires all nonzero aggregates to induce the same received state. We enforce this by multiplying all embedded inputs by the same uniformly random nonzero element of an extension field. Let d′ be the padded coordinate length: a multiple of two for even k, and a multipleP of four ′ ′ for odd k. Embed each original input yi ∈ Fd2 as yei = (yi , 0d −d ) ∈ Fd2 . Its aggregate se = ki=1 yei P vanishes if and only if the original aggregate s = ki=1 yi vanishes. For notational simplicity, we subsequently write yi and s for the padded vectors yei and se, respectively. For every aggregate ′ s ∈ Fd2 , let Ωs denote the global density operator received from the secure-sum layer when the aggregate vector is s. This notation is well defined: if two tuples (y1 , . . . , yk ) and (y1′ , . . . , yk′ ) satisfy k k X X yi = yi′ = s, i=1

i=1

then the aggregate-privacy property of the secure-sum layer (namely, the Sum2 protocol of [14] for even k and Lemma 3.3 for odd k) implies that the two tuples produce exactly the same received ′ density operator Ωs . Fix an F2 -linear isomorphism ι : Fd2 −→ (F2d′ , +). The players choose a shared uniform λ ∈ F× and locally replace each input vector yi by 2d′ −1 ι (λ ι(yi )). This is an F2 -linear operation, and therefore the new aggregate is sλ = ι−1 (λ ι(s)). After averaging over λ, the received global density operator is X 1 Ωs = d′ Ωι−1 (λι(s)) . (3.3) 2 −1 × λ∈F d′ 2

3

“one-shot” means that one joint input tuple produces one function value. The block coding is internal to that tuple and is not amortization over independent instances.

15

Consequently,   Ω0 ,  1 Ωs =  ′ d  2 − 1

s = 0, X

Ωt ,

s ̸= 0.

(3.4)

′

t∈Fd2 \{0}

Indeed, if s ̸= 0, multiplication by ι(s) permutes F× . Equation (3.4) proves perfect Boolean 2d′ privacy at the level of the received global density operator: all zero aggregates give one fixed state, and all nonzero aggregates give a second fixed state. Theorem 3.4 (one-shot generalized equality). For every d ≥ 1, ( k⌈d/2⌉, k even, PSQM,∗ Q (GEQk,d ) ≤ 2k⌈d/4⌉, k odd. In particular, if 2 | d for even k, or 4 | d for odd k, then QPSQM,∗ (GEQk,d ) ≤ kd/2. These are one-shot bounds for one length-d instance. Proof. For even k, group coordinates into pairs and apply the Sum2 protocol of [14] to each pair. For odd k, group coordinates into blocks of four and apply Lemma 3.3 to each block, padding by at most three zero coordinates. This gives the aggregate-dependent family (Ωs )s . The players then apply the random input transformation by λ defined above and produce the family (Ωs )s defined in (3.3). Correctness follows from the correctness of the secure-sum layer and the fact that sλ = 0 if and only if s = 0. Perfect privacy follows from (3.4). The coordinate grouping occurs inside one vector-valued input. It does not invoke multiple copies of generalized equality and hence gives an ordinary one-shot communication bound.

3.5

Our upper bound

We now combine the local embedding with the generalized-equality protocol to obtain the claimed upper bound for EQk,n . Theorem 3.5. For every fixed k ≥ 3, QPSQM,∗ (EQk,n ) ≤

√ k n + Ok ( n). 2h2 (1/k)

There is no asymptotic parity distinction. Proof. Apply Lemma 3.2, and then apply Theorem 3.4 to the resulting length-d generalized-equality instance. For even k, the communication cost is   d kd = + Ok (1), k 2 2 whereas for odd k, it is   d kd 2k = + Ok (1). 4 2 16

√ √ n k Since d = h2 (1/k) + Ok ( n), both cases give 2h2 (1/k) n + Ok ( n). Correctness follows from exact preservation of the zero-sum condition. For perfect privacy, apply the random input transformation defined above. Equations (3.3) and (3.4) show that the joint state received by the referee depends only on whether the embedded aggregate is zero, which is equivalent to all original inputs being equal. Corollary 3.6. QPSQM,∗ (EQ3,n ) ≤

3.6

√ √ 3 n + O( n) = (1.633 . . .)n + O( n). 2h2 (1/3)

Shared-randomness-only comparison

The following lower bound follows readily from perfect correctness, but we include the proof for completeness. Proposition 3.7. Every perfectly correct PSQM protocol for EQk,n that uses shared classical randomness but no prior entanglement communicates at least kn qubits. Proof. Fix a player j and distinct inputs x, x′ ∈ {0, 1}n , and set every input other than that of player j equal to x. The all-x input (x, x, . . . , x) has output 1, whereas replacing player j’s input by x′ gives output 0. Since every conditional success probability is at most one, an average success probability of one implies perfect correctness for every r ∈ R. Moreover, for every such r, the message state conditioned on r is a positive component of the corresponding averaged message state. Since the support of every positive component is contained in the support of the averaged state, the conditional message states corresponding to the two different outputs have orthogonal supports. Fix r ∈ R. Since the protocol uses no prior entanglement, the initial shared state has the product form k O σA1 ···Ak = σi . i=1

For each player i, define ρi (x; r) := Eix,r (σi ). The two global message states conditioned on r are then k O

ρi (x; r)

and

ρj (x′ ; r) ⊗

i=1

O

ρi (x; r),

i̸=j

respectively. Their Hilbert–Schmidt overlap therefore factors as
Y
Tr ρj (x; r)ρj (x′ ; r) Tr ρi (x; r)2 = 0. i̸=j

Every factor in the product over i ̸= j is strictly positive, because each ρi (x; r) is a density operator. Hence
Tr ρj (x; r)ρj (x′ ; r) = 0. Since the two operators are positive semidefinite, their supports are orthogonal. The same argument applies to every pair of distinct x, x′ ∈ {0, 1}n . Thus, for the fixed r, the 2n local message states of player j have pairwise orthogonal nonzero supports. Therefore, player j must communicate at least n qubits. Since j was arbitrary, summing over all k players gives a total communication cost of at least kn qubits. 17

k The coefficient in the entanglement-assisted upper bound of Theorem 3.5, 2h2 (1/k) , is smaller than k for 3 ≤ k ≤ 9. Thus the entanglement-assisted upper bound is strictly smaller than the shared-randomness-only lower bound kn throughout this range.

4

Three-Bit Boolean Functions

In this section, we investigate PSQM protocols for three-bit Boolean functions using one shared GHZ state and one transmitted qubit per player. We first give explicit protocols for majority and equality, and then extend these constructions to an analytic family of 80 functions in the randomized local-Pauli model. Finally, we compare this analytic family with an exhaustive linear-programming search within the same restricted model. Throughout this section, Pauli operators are identified up to global phase, and we use the representatives {I, X, Z, XZ}. In particular, Y = iXZ is represented by XZ.

4.1

GHZ labels

For the three-bit constructions, let |G+ ⟩ =

|000⟩ + |111⟩ √ 2

and define an orthonormal basis by |Φu,v,w ⟩ = (I ⊗ X u ⊗ X v Z w )|G+ ⟩,

u, v, w ∈ F2 .

Throughout this section, whenever we refer to the three-qubit GHZ basis, we mean the basis defined above. We call (u, v, w) the GHZ label of |Φu,v,w ⟩. Lemma 4.1 (Pauli-to-GHZ-label rule). If player 1, player 2, and player 3 apply X a1 Z b1 , X a2 Z b2 , and X a3 Z b3 , respectively, the resulting state is, up to global phase, |Φu,v,w ⟩ with u = a1 ⊕ a2 ,

v = a1 ⊕ a3 ,

w = b1 ⊕ b2 ⊕ b3 .

Proof. The stabilizer identity (X ⊗ X ⊗ X)|G+ ⟩ = |G+ ⟩ reduces the bit-flip information to two relative parities. A Pauli-Z operation on any one qubit toggles the relative phase between |000⟩ and |111⟩, and thus only the parity of the three Z exponents remains.

4.2

Majority and equality

We first derive the three-qubit protocol for the majority function MAJ3 (x, y, z) := 1[x + y + z ≥ 2] from the optimal classical PSM protocol of Shinagawa and Nuida [21]. This derivation explains both the choice of local Pauli encodings and the two four-dimensional subspaces associated with the two output values. We then compress the shared randomness to four values while preserving the same two output-dependent density operators. The classical (4, 4, 4) protocol. We first recall the classical (4, 4, 4) PSM protocol of Shinagawa and Nuida [21], where each of the three players sends a message from a four-element alphabet, and hence the total communication cost is 6 bits. 18

The players share independent uniform random variables b ∈ {0, 1} and c1 , c2 ∈ Z4 , and set c3 = −c1 − c2 (mod 4). For b = 0, the players send mi = xi + ci

i ∈ {1, 2, 3}.

(mod 4),

For b = 1, they send m1 = 1 − x1 + c1 ,

m2 = −x2 + c2 ,

m3 = −x3 + c3

(mod 4).

The referee computes m = m1 + m2 + m3

(mod 4)

and outputs 0 if m ∈ {0, 1}, and 1 if m ∈ {2, 3}. For b = 0, the sum is m = x1 + x2 + x3

(mod 4),

whereas for b = 1, m = 1 − (x1 + x2 + x3 )

(mod 4).

Consequently, if x1 + x2 + x3 ∈ {0, 1}, then m is uniform on {0, 1}, while if x1 + x2 + x3 ∈ {2, 3}, then m is uniform on {2, 3}. For each fixed value of m, the uniform choices of c1 and c2 , with c3 = −c1 − c2 , make the joint message tuple uniform over all triples in Z34 whose coordinate sum is m. Since b makes m uniform over {0, 1} or over {2, 3} according to the majority value, the global message distribution depends only on that value. Hence the protocol is perfectly correct and perfectly private, with message alphabet Z4 for each player. A Pauli lift of the classical protocol. We now convert the classical protocol into a quantum protocol by replacing each classical message value with a fixed local Pauli operation. The shared randomness and the local message functions of the classical protocol remain unchanged. For each m ∈ Z4 , define Um := X a(m) Z d(m) , where (a(0), d(0)) = (0, 0),

(a(1), d(1)) = (1, 1),

(a(2), d(2)) = (0, 1),

(a(3), d(3)) = (1, 0).

(4.1)

Thus, up to global phase, U0 = I,

U1 = XZ,

U2 = Z,

U3 = X.

√ Suppose that the three players share one copy of |G+ ⟩ = |000⟩+|111⟩ . For a global input x = 2 3 2 (x1 , x2 , x3 ) ∈ {0, 1} and shared randomness r = (b, c1 , c2 ) ∈ {0, 1} × Z4 , set c3 = −c1 − c2 (mod 4), and let mi (xi ; r) ∈ Z4 denote the message sent by player i in the classical protocol above. The corresponding conditional quantum message state is
|ψx;r ⟩ := Um1 (x1 ;r) ⊗ Um2 (x2 ;r) ⊗ Um3 (x3 ;r) |G+ ⟩.

The GHZ label of this state is a deterministic function of the classical joint message tuple. More precisely, define Λ : Z34 −→ F32 by Λ(m1 , m2 , m3 ) := (a(m1 ) ⊕ a(m2 ), a(m1 ) ⊕ a(m3 ), d(m1 ) ⊕ d(m2 ) ⊕ d(m3 )) . 19

By Lemma 4.1, the state |ψx;r ⟩ is, up to global phase, the GHZ-basis state indexed by
Λ m1 (x1 ; r), m2 (x2 ; r), m3 (x3 ; r) . We next relate this GHZ label to the quantity decoded by the classical referee. Write pi , qi ∈ F2 .

mi = 2qi + pi , Under the correspondence (4.1) above,

d(mi ) = pi ⊕ qi .

a(mi ) = pi , Hence, if

(u, v, w) = Λ(m1 , m2 , m3 ), then u = p 1 ⊕ p2 ,

v = p1 ⊕ p 3 .

Now write m1 + m2 + m3 = 2q + p

(mod 4),

p, q ∈ F2 .

Binary addition, including the carry from the three low-order bits, gives p = p1 ⊕ p2 ⊕ p3 and q = q1 ⊕ q2 ⊕ q3 ⊕ p1 p2 ⊕ p1 p3 ⊕ p2 p3 . Using p2 = p1 ⊕ u and p3 = p1 ⊕ v, we obtain w = (p1 ⊕ q1 ) ⊕ (p2 ⊕ q2 ) ⊕ (p3 ⊕ q3 ) = q ⊕ p1 ⊕ p2 ⊕ p3 ⊕ p1 p2 ⊕ p1 p3 ⊕ p2 p3 = q ⊕ u ⊕ v ⊕ uv. Therefore, ( u ⊕ v ⊕ uv, w= 1 ⊕ u ⊕ v ⊕ uv,

m1 + m2 + m3 ∈ {0, 1} m1 + m2 + m3 ∈ {2, 3}

(mod 4), (mod 4).

The classical referee outputs 0 in the first case and 1 in the second. Thus the GHZ labels corresponding to the two output values lie in S0 := {(u, v, u ⊕ v ⊕ uv) : u, v ∈ F2 } = {000, 011, 101, 111} and S1 := {(u, v, 1 ⊕ u ⊕ v ⊕ uv) : u, v ∈ F2 } = {001, 010, 100, 110}, respectively. Since S0 ∩ S1 = ∅, a GHZ-basis measurement followed by membership testing in S1 recovers the majority value with certainty. Hence the quantum protocol is perfectly correct. Perfect privacy follows directly from the classical protocol. The distribution of the classical joint message tuple (m1 , m2 , m3 ) depends on the input only through its majority value. Since the GHZ label is its deterministic image under Λ, the induced GHZ-label distribution, and hence the joint quantum state received by the referee, also depends only on the majority value. We have proved the following theorem. 20

Theorem 4.2 (Pauli lift of the classical majority protocol). The classical (4, 4, 4)-PSM protocol for MAJ3 in [21] can be converted into a perfectly correct and perfectly private PSQM protocol by replacing each classical message m ∈ Z4 with the local Pauli operation Um defined above. The converted protocol uses one shared three-qubit GHZ state, five shared random bits, and one transmitted qubit per player. We next determine the two output-dependent density operators ϱ0 and ϱ1 , the joint state received by the referee when the output is 0 and 1, respectively. For each fixed value of m1 +m2 +m3 (mod 4), each pair (u, v) ∈ F22 has exactly four preimages among the classical transcripts. Indeed, for fixed m = 2q + p and fixed (u, v), the equations above determine p1 , p2 , p3 uniquely, while the high-order bits q1 , q2 , q3 satisfy one affine constraint and therefore admit exactly four choices. Moreover, for each majority value, the classical protocol makes the corresponding two possible values of m1 + m2 + m3 equally likely. Hence every GHZ label in S0 or S1 , as appropriate, occurs with probability 1/4. Therefore, 1 X ϱ0 = |Φλ ⟩⟨Φλ |, (4.2) 4 λ∈S0

whereas ϱ1 =

1 X |Φλ ⟩⟨Φλ |. 4

(4.3)

λ∈S1

It is worth emphasizing that the correspondence 0, 1, 2, 3 7−→ I, XZ, Z, X is not a group homomorphism from Z4 to the one-qubit Pauli group modulo phase. The construction therefore does not coherently implement addition in Z4 . Rather, it maps the classical transcript distribution to a coarser GHZ-label distribution. Perfect privacy is preserved under this deterministic postprocessing, while the compatibility between the classical masking and the GHZ stabilizer structure maps the two majority values to the disjoint GHZ-label sets S0 and S1 . Observable formulation. The two output states also admit a compact operator description. Define M := X ⊗ X ⊗ X + X ⊗ Y ⊗ Y + Y ⊗ X ⊗ Y + Y ⊗ Y ⊗ X. The eigenvalues of M are +2 and −2, each with multiplicity four, and ϱ0 −ϱ1 = − 18 M . Equivalently,     1 M 1 M ϱ0 = I− , ϱ1 = I+ . 8 2 8 2 Hence the referee may decode the majority value by measuring the sign of the observable M . The −2 eigenspace corresponds to output 0, and the +2 eigenspace corresponds to output 1. Shared-randomness compression. In the direct quantization, the intermediate classical messages m1 , m2 , m3 , and hence the local Pauli operations, are determined by (b, c1 , c2 ) ∈ {0, 1} × Z24 . The shared-randomness support therefore has size 32. We now show that the same two outputdependent states can be realized using only four equally likely local-Pauli encoding types, without the Z4 -valued masks. The four encoding types admit the following direct construction. Choose (s, t) ∈ F22 uniformly at random and set u = x ⊕ y ⊕ s, v = x ⊕ z ⊕ t.

21

For every fixed input, the pair (u, v) is then uniform on F22 . To ensure that the resulting GHZ label belongs to SMAJ3 (x,y,z) , we should set w = MAJ3 (x, y, z) ⊕ u ⊕ v ⊕ uv. Using MAJ3 = xy ⊕ xz ⊕ yz, this simplifies to w = (1 ⊕ s ⊕ t)x ⊕ (1 ⊕ t)y ⊕ (1 ⊕ s)z ⊕ s ⊕ t ⊕ st, which is affine in the three inputs for every fixed (s, t). To implement these affine GHZ-label maps, choose the local Pauli exponents for players 1, 2, 3, respectively, as a1 = x, b1 = (1 ⊕ s ⊕ t)x, a2 = y ⊕ s, b2 = (1 ⊕ t)y, a3 = z ⊕ t,

b3 = (1 ⊕ s)z ⊕ s ⊕ t ⊕ st,

so that the corresponding local Pauli operations for players 1, 2, 3 are, respectively, x (1⊕s⊕t)x As,t , x := X Z

Bys,t := X y⊕s Z (1⊕t)y , Czs,t := X z⊕t Z (1⊕s)z⊕s⊕t⊕st . Then Lemma 4.1 gives u = a1 ⊕ a2 = x ⊕ y ⊕ s,

v = a1 ⊕ a3 = x ⊕ z ⊕ t,

and w = b1 ⊕ b2 ⊕ b3 = MAJ3 (x, y, z) ⊕ u ⊕ v ⊕ uv, as desired. Evaluating these expressions for the four choices of (s, t) ∈ F22 gives the following array, in which the superscripts s, t are omitted from the column headings. (s, t) A0 A1 (0, 0) I XZ (0, 1) I X (1, 0) I X (1, 1) I XZ

B0 B1 I XZ I X X Z X I

C0 C1 I XZ XZ I Z XZ XZ Z

By Lemma 4.1, these encodings generate the GHZ labels shown in Table 4.1. Every row corresponding to output 0 is a permutation of S0 , whereas every row corresponding to output 1 is a permutation of S1 . Consequently, the protocol with four equally likely encoding types produces exactly the same two density operators ϱ0 and ϱ1 as the direct quantization with shared-randomness support of size 32. We have proved the following theorem. Theorem 4.3 (Compressed three-bit majority protocol). There is a perfectly correct and perfectly private PSQM protocol for MAJ3 using one shared three-qubit GHZ state, two shared random bits, local Pauli encodings, and one transmitted qubit per player. Its output-dependent states are the states ϱ0 and ϱ1 in (4.2) and (4.3).

22

xyz 000 001 010 100 011 101 110 111

(s, t) = (0, 0) (0, 0, 0) (0, 1, 1) (1, 0, 1) (1, 1, 1) (1, 1, 0) (1, 0, 0) (0, 1, 0) (0, 0, 1)

(s, t) = (0, 1) (0, 1, 1) (0, 0, 0) (1, 1, 1) (1, 0, 1) (1, 0, 0) (1, 1, 0) (0, 0, 1) (0, 1, 0)

(s, t) = (1, 0) (1, 0, 1) (1, 1, 1) (0, 0, 0) (0, 1, 1) (0, 1, 0) (0, 0, 1) (1, 1, 0) (1, 0, 0)

(s, t) = (1, 1) (1, 1, 1) (1, 0, 1) (0, 1, 1) (0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (1, 1, 0)

MAJ3 (x, y, z) 0 0 0 0 1 1 1 1

Table 4.1: GHZ labels generated by the compressed majority protocol The protocol using four equally likely encoding types should therefore be viewed as a sharedrandomness-compressed realization of the direct Pauli quantization of the classical (4, 4, 4) protocol. The classical protocol transmits the complete Z4 -valued message tuple, whereas the quantum protocol maps this tuple to a coarser GHZ-label distribution that retains only the information needed to determine the function value. Equality by a parity twist. Their truth tables satisfy

Let PAR3 (x, y, z) = x ⊕ y ⊕ z and EQ3 (x, y, z) = 1[x = y = z]. EQ3 = 1 ⊕ MAJ3 ⊕ PAR3 .

Moreover, (Z x ⊗ Z y ⊗ Z z )|Φu,v,w ⟩ = |Φu,v,w⊕x⊕y⊕z ⟩ up to global phase. Thus the third GHZ-label component is flipped exactly when PAR3 (x, y, z) = 1. Since flipping this component exchanges S0 and S1 , we obtain the following consequence. Corollary 4.4 (Three-bit equality). Composing the encoders in Theorem 4.3 with the local operations Z x , Z y , Z z , and reversing the referee’s output, gives a perfectly correct and perfectly private protocol for EQ3 with the same resources. In [21], the authors showed that the classical PSM complexity of EQ3 is 3 log2 3. Thus the above corollary shows quantum communication advantage for EQ3 .

4.3

An analytic family of 80 functions

Every three-bit Boolean function has a unique algebraic normal form f = c ⊕ ax ⊕ by ⊕ dz ⊕ αxy ⊕ βxz ⊕ γyz ⊕ δxyz. Theorem 4.5 (80-function construction). Suppose δ=0

and

(α, β, γ) ∈ {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)}.

Then f admits a perfectly correct and perfectly private protocol with one shared three-qubit GHZ state, finite shared randomness, local Pauli encodings, and one transmitted qubit per player. These conditions describe exactly 5 · 24 = 80 distinct functions.

23

Proof. Under permutations of the players, it suffices to consider the three quadratic coefficient vectors (0, 0, 0), (1, 0, 0), (1, 1, 1). These correspond, respectively, to an affine function, a function with one quadratic term such as xy, and a function containing all three quadratic terms xy ⊕ xz ⊕ yz = MAJ3 . We treat these three cases using affine phase encodings, the xy ⊕ z base protocol, and the majority protocol, respectively. The base protocol also yields a protocol for xy by having the third player ignore its input and always use its z = 0 encoder. Player permutations cover the single-term cases xz and yz. We also use input complementation, which swaps a player’s two encoders, and output complementation, which reverses the referee’s declaration. All 16 affine functions are immediate: for case (0, 0, 0); ℓ = c ⊕ ax ⊕ by ⊕ dz, the players apply Z ax , Z by , Z dz and the referee reads the GHZ phase, reversing the result if c = 1. Next, we consider case (1, 0, 0). For the base function xy ⊕ z, let the shared randomness be uniform on F22 . The corresponding local-Pauli encodings are given in the following array. (s, t) A0 A1 (0, 0) I XZ (0, 1) I X (1, 0) I X (1, 1) I XZ

B0 B1 I XZ I X X Z X I

C0 C1 I Z XZ X Z I XZ X

(1, 0) (1, 0, 1) (1, 0, 0) (0, 0, 0) (0, 0, 1) (0, 1, 1) (0, 1, 0) (1, 1, 0) (1, 1, 1)

(1, 1) xy ⊕ z (1, 1, 1) 0 (1, 1, 0) 1 (0, 1, 1) 0 (0, 1, 0) 1 (0, 0, 0) 0 (0, 0, 1) 1 (1, 0, 0) 1 (1, 0, 1) 0

The GHZ-label table is as follows. xyz 000 001 010 011 100 101 110 111

(0, 0) (0, 0, 0) (0, 0, 1) (1, 0, 1) (1, 0, 0) (1, 1, 1) (1, 1, 0) (0, 1, 0) (0, 1, 1)

(0, 1) (0, 1, 1) (0, 1, 0) (1, 1, 1) (1, 1, 0) (1, 0, 1) (1, 0, 0) (0, 0, 1) (0, 0, 0)

Every input xy⊕z = 0 produces the uniform distribution on S0 , whereas every input with xy⊕z = 1 produces the uniform distribution on S1 . This protocol also gives a protocol for xy: player 3 ignores its input and always applies the encoder C0 .4 Equivalently, we restrict the xy ⊕ z protocol to z = 0. The resulting protocol produces the uniform distribution on S0 when xy = 0 and the uniform distribution on S1 when xy = 1. Now fix f = xy ⊕ ax ⊕ by ⊕ dz ⊕ c. 4

Although xy can be computed by applying an existing two-party protocol for AND2 to the first two inputs and ignoring the third input, we require here a realization within the fixed three-party GHZ–Pauli model.

24

If d = 0, use (x ⊕ b)(y ⊕ a) = xy ⊕ ax ⊕ by ⊕ ab and obtain f from the xy protocol by input and output complementations. If d = 1, use (x ⊕ b)(y ⊕ a) ⊕ z = xy ⊕ ax ⊕ by ⊕ z ⊕ ab and the xy ⊕ z protocol. Permuting players covers xz and yz. This yields 3 · 16 = 48 functions. Finally, we consider case (1, 1, 1); MAJ3 = xy ⊕ xz ⊕ yz. For the majority protocol, composing the local encoders with Z ax , Z by , and Z dz , respectively, exchanges the two output-dependent states whenever ax ⊕ by ⊕ dz = 1. Output complementation then supplies the constant term c. This gives 16 functions whose quadratic part is xy ⊕ xz ⊕ yz. Together with the 16 affine functions and the 48 functions whose quadratic part consists of exactly one of xy, xz, yz, this proves Theorem 4.5. Remark 4.6. The arrays of MAJ3 and xy ⊕ z differ only in the C1 column. More precisely, the xy ⊕ z array is obtained from the majority array by composing C1 with X,

X,

XZ,

XZ

for (s, t) = (0, 0), (0, 1), (1, 0), (1, 1), respectively. To see why this works, define D(u, v, w) := w ⊕ u ⊕ v ⊕ uv, so that D(u, v, w) = b exactly when (u, v, w) ∈ Sb . Composing the third player’s operation with X changes D by 1 ⊕ u, while composing it with XZ changes D by u. In the majority array, ( x ⊕ y, (s, t) = (0, 0), (0, 1), u= 1 ⊕ x ⊕ y, (s, t) = (1, 0), (1, 1). Hence all four corrections change the decoded bit by 1 ⊕ x ⊕ y when z = 1, and by zero when z = 0. Since MAJ3 (x, y, z) ⊕ (xy ⊕ z) = z(1 ⊕ x ⊕ y), the corrected array computes xy ⊕ z.

4.4

Computational exploration of a restricted GHZ–Pauli model

The analytic constructions above were motivated in part by a finite computational exploration. This exploration is restricted to the model described below, and its negative outcomes are reported only as numerical observations. Restricted model.

We restrict attention to protocols satisfying all of the following conditions.

√ 1. The shared quantum resource is the fixed GHZ state |G+ ⟩ = |000⟩+|111⟩ . 2

2. The players may use an arbitrary input-independent classical random variable r ∈ R, hidden from the referee. No a priori bound is imposed on its finite support size.

25

3. For every r ∈ R, every player i ∈ {1, 2, 3}, and every input bit b ∈ {0, 1}, the local encoding operation is given by a Pauli operator in {I, X, Z, XZ}, up to global phase. 4. Each player sends its share of the GHZ state to the referee. 5. The referee may perform an arbitrary measurement. Thus the search is complete only within the one-GHZ randomized local-Pauli model. It does not cover arbitrary local unitary encodings or, more generally, arbitrary local CPTP encodings, including encodings that couple the message qubits to auxiliary systems. Nor does it cover shared states other than the fixed GHZ state, multiple shared entangled states, or more than one transmitted qubit per player. Every deterministic shared-randomness value is specified by t = (A0 , A1 ; B0 , B1 ; C0 , C1 ) ∈ {I, X, Z, XZ}6 . Hence there are exactly 46 = 4096 deterministic encoding types. By the GHZ-label rule, a type t induces a function Lt : {0, 1}3 −→ F32 , where Lt (u) is the GHZ label of the state received on input u. Different shared-randomness values may induce the same deterministic encoding type. Combining their probabilities, any protocol in the restricted class is described by a probability distribution (pt )t over the 4096 types. For an input u ∈ {0, 1}3 , define the induced GHZ-label distribution by X Du (λ) := pt 1[Lt (u) = λ], λ ∈ F32 . (4.4) t

The global message state is ρu =

X

Du (λ)|Φλ ⟩⟨Φλ |.

λ∈F32

In particular, all averaged message states in this restricted model are diagonal in the same GHZ basis. Fix a Boolean function f : {0, 1}3 −→ {0, 1} and a subset S ⊆ F32 interpreted as the set of GHZ labels decoded as one. We retain only those deterministic types that satisfy Lt (u) ∈ S

⇐⇒

f (u) = 1

for every u ∈ {0, 1}3 .

(4.5)

Let Tf,S be the set of retained types. For this fixed pair (f, S), we solve the following linear feasibility problem in the variables pt , t ∈ Tf,S : pt ≥ 0 (t ∈ Tf,S ), X pt = 1,

(4.6) (4.7)

t∈Tf,S

X

pt 1[Lt (u) = λ] − 1[Lt (v) = λ] = 0,

(4.8)

t∈Tf,S

for every u, v satisfying f (u) = f (v) and every λ ∈ F32 . Equation (4.8) is exactly the perfect-privacy requirement Du = Dv whenever f (u) = f (v). Equation (4.5) ensures perfect correctness for every deterministic type receiving positive probability.

26

It is sufficient to enumerate all 28 = 256 subsets S ⊆ F32 . Indeed, all received states in the restricted model are diagonal in the GHZ basis. If the two output-dependent states have orthogonal supports, then their GHZ-label supports are disjoint and can be separated by some subset S ⊆ F32 . Consequently, an arbitrary perfectly correct referee measurement can be replaced, in this restricted model, by a GHZ-basis measurement followed by membership testing in S. The computation enumerated all 28 = 256 Boolean truth tables, all 256 decoder supports, and all 4096 deterministic encoding types. The constraint matrices of the resulting feasibility problems have entries in {−1, 0, 1} since each privacy constraint is the difference of two indicator sums. These problems were solved in floating-point arithmetic using the HiGHS linear-programming solver through scipy.optimize.linprog [12, 22]. For every reported feasible instance, the returned probability distribution was independently checked by recomputing all eight distributions in (4.4) and verifying f (u) = f (v) =⇒ Du = Dv . We also checked normalization, nonnegativity, and disjointness of the GHZ label supports corresponding to the two function values. Remark 4.7 (Computational outcome and its interpretation). The computation found feasible solutions for 80 of the 256 three-bit Boolean functions. Classified by the number of inputs on which f takes the value 1, the counts were as follows. |f −1 (1)| 0 2 4 6 8 number found feasible 1 16 46 16 1 The positive cases are no longer dependent on the computation: Theorem 4.5 gives explicit analytic constructions for all 80 functions. For the other functions, the floating-point solver reported no feasible solution in the restricted model. This group includes EXACT1 , EXACT2 , where EXACTt (x, y, z) := 1[x + y + z = t] and the sum is taken over the integers, as well as the 48 affine extensions of the two-edge quadratic forms with coefficient vectors (1, 1, 0), (1, 0, 1), (0, 1, 1). We record these negative outcomes only as numerical observations, not as rigorous impossibility results. In particular, they imply no impossibility statement for arbitrary local U (2) encodings, general CPTP encodings, other shared states, or larger quantum messages. The purpose of the computation is therefore exploratory. It identifies the algebraic pattern captured by Theorem 4.5, suggests that a two-edge quadratic form such as xy ⊕ xz is the essential remaining case for an analytic classification of the restricted model, and provides candidate functions for future impossibility arguments.

5

Unique-Preimage Impossibility

In this section, we restrict the general model of Section 2.2 as follows. Each player holds exactly one qubit of the fixed shared k-qubit state σ, the message register Mi is that same qubit, and, conditioned on the shared random value r ∈ R and the input bit xi , the local encoding channel is conjugation by a unitary Ui (xi , r) ∈ U (2). Thus ρx,r =

k O

! Ui (xi , r) σ

i=1

k O i=1

27

!† Ui (xi , r)

.

We refer to this restriction as the one-qubit local-unitary model. Let k ≥ 3 and let f : {0, 1}k → {0, 1}. The players share an arbitrary mixed state σ ∈ D((C2 )⊗k ) and arbitrary input-independent classical shared randomness with finite support R. For every player i, input bit b, and r ∈ R, the local encoder is an arbitrary unitary Ui (b, r) ∈ U (2). All k qubits are sent to the referee. We now state the main impossibility theorem. Theorem 5.1 (local-unitary unique-preimage impossibility). If min{|f −1 (0)|, |f −1 (1)|} = 1, then no protocol in the one-qubit local-unitary model has both perfect privacy and perfect correctness. Theorem 5.1 applies to k-bit AND, OR, NAND, NOR, every Boolean point function x 7→ 1[x = a], and their complements. The proof is divided into two steps. Section 5.1 derives a rank lower bound from perfect correctness and Lemma 2.4 (zero-expectation qubit-unitary structure). Section 5.2 uses perfect privacy to obtain a contradictory rank upper bound. After complementing the output, assume that f (a) = 1 for a unique a ∈ {0, 1}k . For S ⊆ [k], let a(S) be obtained by flipping exactly the positions in S. Then a(∅) = a and every nonempty S yields output zero. Let ϱb be the global state received by the referee when b is output in the assumed protocol with perfect correctness and perfect privacy.

5.1

Rank lower bound and purification forced by correctness

Take a spectral decomposition σ=

X

λc |ψc ⟩⟨ψc |,

λc > 0.

c

Fix a spectral component c and r ∈ R. Define Wr =

k O

Ui (ai , r),

(r)

Vi

= Ui (ai , r)† Ui (1 − ai , r),

i=1

where ai is the i-th bit of a. The pure component for input a(S) is ! O (r) Wr Vi |ψc ⟩. i∈S

Lemma 2.3 and perfect correctness imply ! ⟨ψc |

O

(r) Vi

|ψc ⟩ = 0

(∅ ̸= S ⊆ [k]).

(5.1)

i∈S

Let τi,c := Tr[k]\{i} (|ψc ⟩⟨ψc |) be the reduced density operator of the i-th qubit of |ψc ⟩⟨ψc |. Taking S = {i} in (5.1) gives     (r) (r) 0 = ⟨ψc | Vi ⊗ I[k]\{i} |ψc ⟩ = Tr τi,c Vi . 28

(r)

Applying Lemma 2.4, we may rephase Vi , which changes every subset-flip vector only by a global phase, so that (r) (r) (r) (Vi )† = Vi , (Vi )2 = I. For nonempty S, put ! O

|ϕS ⟩ =

(r)

Vi

|ψc ⟩.

i∈S

If S ̸= T , then  ⟨ϕS | ϕT ⟩ = ⟨ψc | 

 O

(r) Vi  |ψc ⟩ = 0

i∈S△T

by (5.1). Since Wr is unitary, the vectors Wr |ϕS ⟩,

∅ ̸= S ⊆ [k],

are also mutually orthonormal. Each of them is a pure-state component of the received state for the rejecting input a(S) , and hence belongs to supp(ϱ0 ) by Lemma 2.3. Therefore, rank(ϱ0 ) ≥ 2k − 1.

(5.2)

The total space has dimension 2k , and thus orthogonality of the output supports forces rank(ϱ1 ) = 1.

(5.3)

But ϱ1 =

X

pr λc Wr |ψc ⟩⟨ψc |Wr† .

r,c

Every positive component must lie in the same one-dimensional support. Every vector Wr |ψc ⟩ belongs to the common one-dimensional support of ϱ1 . On the other hand, for every fixed r, the unitary Wr preserves the orthogonality of the spectral vectors: ⟨ψc |Wr† Wr |ψc′ ⟩ = ⟨ψc |ψc′ ⟩ = 0

(c ̸= c′ ).

Hence σ can have only one positive-eigenvalue spectral component. Therefore rank(σ) = 1, and the input-independent shared state is of the form σ = |ψ⟩⟨ψ| for a fixed k-qubit unit vector |ψ⟩, independent of r.

5.2

Rank upper bound by privacy

Equation (5.3) implies that all vectors Wr |ψ⟩,

r ∈ R,

29

lie on the same ray. Hence there exist a unit vector |η⟩ and phases eiθr , r ∈ R, such that Wr |ψ⟩ = eiθr |η⟩ for every r ∈ R. Choose any r0 ∈ R. Apply the fixed product unitary Wr†0 to every received state as a common change of coordinates, and redefine Wr′ := Wr†0 Wr . Since Wr0 |ψ⟩ and |η⟩ lie on the same ray, this common coordinate change gives ′

Wr′ |ψ⟩ = eiθr |ψ⟩ ′

for every r ∈ R, after absorbing an r-independent phase into the phases eiθr . After dropping the primes, we may therefore assume that Wr |ψ⟩ = eiθr |ψ⟩

(5.4)

for every r ∈ R. Let τi = Tr[k]\{i} |ψ⟩⟨ψ| be the reduced density operator of the i-th qubit of |ψ⟩⟨ψ|. Define Li = {M ∈ L(C2 ) : Tr(τi M ) = 0}. The functional fi : M 7→ Tr(τi M ) is nonzero because Tr(τi I) = 1. This means the dimension of the image of fi is 1. Since L(C2 ) has complex dimension four and Li = ker fi , dim Li = 3. Define Ai = {(Mi ⊗ I[k]\{i} )|ψ⟩ : M ∈ Li }, where Mi ⊗ I[k]\{i} denotes the operator that acts as M on the i-th qubit and as identity on every other qubit. Since Ai is the image of the linear map M 7→ (Mi ⊗ I[k]\{i} )|ψ⟩, dim Ai ≤ dim Li ≤ 3. Taking the partial trace of (5.4) over all qubits except the ith one gives Ui (ai , r)τi Ui (ai , r)† = τi . Therefore conjugation by Ui (ai , r) preserves Li . Consequently, Wr Ai = Ai . For the input a({i}) obtained by flipping only coordinate i, Equation (5.1) with S = {i} gives (r)

⊗ I)|ψ⟩ = Tr(τi Vi ).

(r)

⊗ I |ψ⟩ ∈ Ai

0 = ⟨ψ|(Vi (r)

Hence Vi

(r)

∈ Li . Since Vi

and Wr Ai = Ai , we have (r)

W r Vi

⊗ I |ψ⟩ ∈ Ai 30

for every r ∈ R. Thus every pure-state component of ρa({i}) (the global state received by the referee when the input is a({i}) ) lies in Ai . Consequently, supp (ρa({i}) ) ⊆ Ai . Since a({i}) has f (a({i}) ) = 0, perfect privacy gives supp(ϱ0 ) = supp(ρa({i}) ) ⊆ Ai , and thus rank(ϱ0 ) ≤ 3.

(5.5)

Combining (5.2) and (5.5) gives 2k − 1 ≤ rank(ϱ0 ) ≤ 3, a contradiction for every k ≥ 3. This proves Theorem 5.1. Theorem 5.1 allows any shared k-qubit mixed state and any amount of classical shared randomness. It also permits each player to possess an arbitrary untouched auxiliary system: if the input-dependent operation is restricted to Ui (xi , r) on a designated message qubit and the auxiliary system is neither acted upon nor sent, tracing out all auxiliaries reduces the setting to an arbitrary mixed state on the k message qubits. However, the theorem is specific to qubits and local unitary encodings. It does not directly cover local operations that couple the message qubit to an auxiliary system, arbitrary CPTP encodings, protocols in which each player transmits more than one qubit, or functions for which both f −1 (0) and f −1 (1) contain at least two inputs.

6

One-Qudit Protocols for Multiparty AND

The impossibility theorem of the preceding section is specific to one transmitted qubit per player. In this section, we show that the obstruction can be overcome by increasing the local message dimension. We first give a general quotient-label construction for ANDk . For every prime p satisfying k ≤ 2(p−1), the construction uses one p-dimensional qudit per player. We then specialize the protocol to k = p = 3, obtaining a one-qutrit protocol for three-bit AND with communication 3 log2 3. Combined with the 6-bit classical lower bound of Shinagawa and Nuida [21], this gives a strict quantum communication advantage. The direct three-party specialization uses 144 values of shared randomness. A three-party-specific optimization reduces the shared-randomness support to 48 values without changing the communication cost. The optimized construction is given in Appendix A. Throughout this section, all vector and matrix operations are over Fp , where all vectors in F2p are regarded as column vectors.

6.1

Generalized GHZ labels

We use the standard p-dimensional Weyl operators (see, e.g., [23]). Let k ≥ 3, and let p be a prime satisfying k ≤ 2(p − 1). Let ω = e2πi/p , and define the p-dimensional Weyl operators by X a |j⟩ = |j + a⟩,

Z b |j⟩ = ω bj |j⟩,

31

a, b, j ∈ Fp .

The players share the k-partite p-dimensional GHZ state 1 X ⊗k |Gp,k ⟩ = √ |j⟩ . p j∈Fp

For u2 , . . . , uk , w ∈ Fp , define |Φu2 ,...,uk ,w ⟩ = (I ⊗ X u2 ⊗ · · · ⊗ X uk−1 ⊗ X uk Z w ) |Gp,k ⟩. These pk states form an orthonormal basis, which we call the generalized GHZ basis. We call (u2 , . . . , uk , w) the GHZ label of |Φu2 ,...,uk ,w ⟩. Lemma 6.1 (Multiparty Weyl-to-GHZ-label rule). Suppose that player i applies X ai Z bi ,

ai , bi ∈ Fp .

The resulting state is, up to global phase, |Φu2 ,...,uk ,w ⟩, where ui = ai − a1

(2 ≤ i ≤ k),

w=

k X

bi .

i=1

Proof. For every c ∈ Fp ,

(X c )⊗k |Gp,k ⟩ = |Gp,k ⟩.

Hence the common shift a1 can be removed, leaving P the relative shifts ai − a1 , 2 ≤ i ≤ k. The phase operators contribute the total phase exponent i bi . Commuting X- and Z-operators may introduce a power of ω, but this is only a global phase.

6.2

Our protocol

In this subsection, we describe our PSQM protocol. We first choose nonzero weights t2 , . . . , tk ∈ F× p such that T :=

k X

ti ̸= 0.

(6.1)

i=2

Lemma 6.2 (Existence of suitable weights). There exist t2 , . . . , tk ∈ F× p satisfying (6.1). Proof. The condition k ≤ 2(p − 1) and k ≥ 3 implies p ≥ 3. First set t2 = · · · = tk = 1. If k − 1 ̸= 0 in Fp , these weights give T = k − 1 ̸= 0. Suppose instead that k − 1 = 0 in Fp . Set t2 = 2 and t3 = · · · = tk = 1. All these weights are nonzero because p ≥ 3, and T = 2 + (k − 2) = k = 1 in Fp . Thus T ̸= 0. Fix once and for all publicly known weights t2 , . . . , tk ∈ F× p satisfying (6.1). These weights are deterministic parameters of the protocol and are not part of the shared randomness. Define πt : Fkp −→ F2p by ! k X πt (u2 , . . . , uk , w) = ti ui , w . i=2

32

Since t2 ̸= 0, the map πt is surjective. Its kernel Kt := ker πt has dimension k − 2, and hence |Kt | = pk−2 . For a GHZ label λ = (u2 , . . . , uk , w) ∈ Fkp , we call πt (λ) ∈ F2p its quotient label. We next construct vectors governing the local input changes. Lemma 6.3 (Zero-sum-free sequence). Under the condition k ≤ 2(p − 1), there exist vectors P (0) (0) (0) s1 , . . . , sk ∈ F2p such that i∈S si ̸= 0 for every nonempty S ⊆ [k]. Proof. Let e1 = (1, 0)T and e2 = (0, 1)T be the standard basis of F2p . Form the sequence e ,...,e ,e ,...,e . |1 {z }1 |2 {z }2 p−1

p−1

Its length is 2(p − 1), and thus the condition k ≤ 2(p − 1) allows us to retain the first k terms and denote them by (0) (0) s1 , . . . , sk . For a nonempty subset S ⊆ [k], write X (0) si = c1 e1 + c2 e2 , i∈S

where 0 ≤ c1 , c2 ≤ p−1. Since S is nonempty, c1 +c2 > 0, so at least one of c1 , c2 lies in {1, . . . , p−1} and is nonzero modulo p. Therefore the sum is nonzero in F2p . Let GL(2, p) denote the group of invertible 2×2 matrices over Fp . The players share independent uniform random variables M ∈ GL(2, p) and τ ∈ Kt . They define (0)

si = M si

= (ξi , βi )T

(i ∈ [k]).

(6.2)

Writing τ = (τ2 , . . . , τk , 0), the kernel condition is k X

ti τi = 0.

i=2

Define h := −

k X

si = (h1 , h2 )T .

i=1

Choose the GHZ-label representative
k g(h) = t−1 2 h1 , 0, . . . , 0, h2 ∈ Fp . 33

(6.3)

Then πt (g(h)) = h. To generate the input-independent GHZ label g(h) + τ , player 1 applies Z h2 , player 2 applies −1 X t2 h1 +τ2 , and player i ≥ 3 applies X τi . For the input-dependent part, player 1, on input x1 ∈ {0, 1}, applies X −x1 T

−1 ξ 1

Z x1 β1 ,

(6.4)

X xi ti ξi Z xi βi .

(6.5)

and player i ≥ 2, on input xi ∈ {0, 1}, applies −1

These operations are composed with the input-independent operations above. The order of the Weyl factors affects only a global phase. Let LM,τ (x) ∈ Fkp ,

x = (x1 , . . . , xk ) ∈ {0, 1}k ,

denote the resulting GHZ label. Protocol summary. The public parameters are the prime p, the zero-sum-free sequence (0) (0) s1 , . . . , sk , the weights t2 , . . . , tk , the quotient map πt , and its kernel Kt . For each execution, the players share independent uniform M ∈ GL(2, p) and τ ∈ Kt . They first compute si and h in (6.2) and (6.3). They then apply the local operations that generate the input-independent GHZ label g(h) + τ , compose them with the input-dependent operations in (6.4) and (6.5), and transmit one p-dimensional qudit each. The referee measures in the generalized GHZ basis and outputs 1 if and only if the observed GHZ label belongs to Kt .

6.3

Correctness and privacy

Lemma 6.4 (Quotient label formula). For every x ∈ {0, 1}k , X πt (LM,τ (x)) = − si .

(6.6)

i:xi =0

Proof. The input-independent GHZ label has the quotient label πt (g(h) + τ ) = πt (g(h)) + πt (τ ) = h = −

k X

si .

i=1

For player i ≥ 2, increasing xi from 0 to 1 changes the ui -component of the GHZ label by t−1 i ξi and its last component w by βi . Hence the quotient label changes by
ti (t−1 i ξi ), βi = (ξi , βi ) = si . For player 1, increasing x1 from 0 to 1 changes the first player’s X-exponent a1 by −T −1 ξ1 . By Lemma 6.1, the ui -component of the GHZ label is ui = ai − a1 , 34

2 ≤ i ≤ k.

Since the exponents ai for i ≥ 2 remain unchanged, every ui -component changes by T −1 ξ1 . Therefore the first component of the quotient label changes by k X

ti T −1 ξ1 = T T −1 ξ1 = ξ1 .

i=2

The last component w of the GHZ label changes by β1 . Therefore, when x1 changes from 0 to 1, the quotient label changes by (ξ1 , β1 ) = s1 . Thus changing xi from 0 to 1 changes the quotient label by si for every i ∈ [k]. Since the input-independent GHZ label has quotient label −

k X

si ,

i=1

we obtain

k k X X
πt LM,τ (x) = − si + xi si i=1

i=1

X

=−

si .

i:xi =0

Proposition 6.5 (Perfect correctness). For every M ∈ GL(2, p) and τ ∈ Kt , LM,τ (x) ∈ Kt

x = 1k .

⇐⇒

Proof. If x = 1k , (6.6) gives πt (LM,τ (1k )) = 0. Hence LM,τ (1k ) ∈ Kt . Now suppose that x ̸= 1k , and define the zero-position set of x: Sx := {i ∈ [k] : xi = 0}. Then Sx is nonempty, and

! X

si = M

i∈Sx

X

(0)

si

.

i∈Sx

The inner sum is nonzero by Lemma 6.3. Since M is invertible, X si ̸= 0. i∈Sx

Equation (6.6) therefore gives πt (LM,τ (x)) ̸= 0, and hence LM,τ (x) ∈ / Kt . Lemma 6.6 (Uniform P nonzero quotient labels). Fix a nonempty subset S ⊆ [k]. If M is uniform on GL(2, p), then i∈S si is uniform on F2p \ {0}. 35

Proof. Set X (0) si .

vS :=

i∈S

Lemma 6.3 gives vS ̸= 0, and X

si = M vS .

i∈S

The group GL(2, p) acts transitively on F2p \ {0}. More explicitly, for any nonzero y, z, choose A ∈ GL(2, p) with Ay = z. Then M 7→ AM is a bijection between the matrices satisfying M vS = y and those satisfying M vS = z. Thus every nonzero vector has the same number of preimages, and M vS is uniform on the nonzero vectors. Proposition 6.7 (Perfect privacy). After averaging over the shared randomness M and τ , the state received by the referee depends only on the value of ANDk . Proof. For each y ∈ F2p , choose a GHZ label λy ∈ Fkp satisfying πt (λy ) = y. The set of GHZ labels with the quotient label y is the coset Cy := λy + Kt = πt−1 (y). Every such coset has cardinality |Cy | = |Kt | = pk−2 . Fix M and an input x. The GHZ label depends additively on τ . Since τ is uniform on Kt , conditioned on the quotient label y = πt (LM,τ (x)), the GHZ label is uniform on Cy . For the accepting input x = 1k , the quotient label is 0, and thus, the averaged received state is ϱ1 =

1 pk−2

X

|Φλ ⟩⟨Φλ |.

λ∈Kt

Now fix a rejecting input x ̸= 1k . Its zero-position set Sx is nonempty, and X πt (LM,τ (x)) = − si . i∈Sx

By Lemma 6.6, this quotient label is uniform on F2p \ {0}, independently of Sx . Conditioned on each nonzero quotient label, the kernel shift makes the GHZ label uniform on the corresponding coset. Hence every rejecting input induces ϱ0 =

X X X 1 1 |Φ ⟩⟨Φ | = |Φλ ⟩⟨Φλ |. λ λ (p2 − 1)pk−2 pk − pk−2 2 λ∈K / t

y∈Fp λ∈Cy y̸=0

This state is independent of the rejecting input.

36

6.4

Consequences

We can now state the resulting PSQM upper bound for ANDk . Theorem 6.8 (One-qudit protocols for multiparty AND). Let k ≥ 3, and let p be a prime satisfying k ≤ 2(p − 1). Then there is a perfectly correct and perfectly private entanglement-assisted PSQM protocol for ANDk in which the players share one k-partite p-dimensional GHZ state and every player transmits one p-dimensional qudit. Consequently, QPSQM,∗ (ANDk ) ≤ k log2 p. Proof. The protocol is defined in Section 6.2. Perfect correctness follows from Proposition 6.5, and perfect privacy follows from Proposition 6.7. Since each player transmits one p-dimensional register, the communication cost is k log2 p. Corollary 6.9. For every k ≥ 3, there exists a prime p ≤ k such that k ≤ 2(p − 1). Consequently, QPSQM,∗ (ANDk ) ≤ k log2 p ≤ k log2 k.   Proof. Let n = k2 . Since k ≥ 3, we have n > 1. By Bertrand’s postulate, there is a prime p   satisfying n < p < 2n. Since p and n are integers, p − 1 ≥ n = k2 , and hence k ≤ 2(p − 1). If k is even, then 2n = k, so p < k. If k is odd, then 2n = k + 1, so p < k + 1, and hence p ≤ k. The result follows from Theorem 6.8. The classical construction for ANDk in [7] chooses a prime ℓ > k and uses message alphabet size ℓ for every player, giving communication k log2 ℓ, which remains the best general-k classical upper bound for AND known to us. Corollary 6.9 gives a one-shot quantum protocol with local dimension p ≤ k, and therefore k log2 p < k log2 ℓ. Thus our quantum construction improves on the achievable communication cost in [7] for every k ≥ 3. This compares achievable upper bounds and does not by itself establish a separation from the optimal classical PSM complexity unless a sufficiently strong classical lower bound is known. The three-party qutrit protocol case.

Taking k = 3 in Corollary 6.9 gives the following special

Corollary 6.10 (One-qutrit protocol for three-bit AND). There is a perfectly correct and perfectly private entanglement-assisted PSQM protocol for AND3 using one shared three-qutrit GHZ state and one transmitted qutrit per player. Consequently, QPSQM,∗ (AND3 ) ≤ 3 log2 3. The direct specialization uses independent uniform shared randomness M ∈ GL(2, 3) and τ ∈ Kt . Since | GL(2, 3)| = (32 − 1)(32 − 3) = 48 and |Kt | = 3, this protocol has 144 values of shared randomness. For three players, however, the independent kernel randomizer can be removed. Appendix A gives another perfectly correct and perfectly private protocol with the same communication cost whose shared randomness is a single uniform M ∈ GL(2, 3). Thus the optimized implementation uses only 48 shared-randomness values. Shinagawa and Nuida [21] showed that the message-alphabet sizes of any classical PSM protocol for AND3 , up to permutation and componentwise enlargement, must dominate one of (3, 6, 6), (4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6) and (5, 5, 5). The smallest product 37

among these tuples is 4 · 4 · 4 = 64. Hence every classical PSM protocol for AND3 communicates at least log2 64 = 6 bits. In contrast, Corollary 6.10 gives an entanglement-assisted PSQM protocol communicating 3 log2 3 = log2 27 < 6 qubits. Corollary 6.10 complements Theorem 5.1. Theorem 5.1 rules out a protocol for AND3 in the one-qubit local-unitary model, even with an arbitrary shared three-qubit state and arbitrary shared randomness. Corollary 6.10 shows that one qutrit per player is sufficient. Thus, within the symmetric one-system-per-player local-unitary setting, local dimension three is the smallest possible local dimension for AND3 . Lu, Yao, and Jafar [20] constructed a non-one-shot protocol for ANDk by applying the protocol in [7] separately to each AND instance and jointly computing the resulting masked sums using a capacity-achieving secure k-sum protocol. Each AND instance is reduced to a secure sum over Fp , where k < p < 2k. The resulting amortized cost is k2 log2 p qubits per computation. For k = 3, this is 23 log2 5. This value is an asymptotic per-instance cost obtained by jointly encoding multiple product instances. In contrast, Corollary 6.10 is a one-shot construction for a single instance of AND3 .

7

Conclusion

The communication complexity of natural functions remains much less understood in PSQM than quantum separations for specially designed functions. Our results show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. Prior entanglement reduces communication for multiparty equality and three-bit majority. In particular, majority requires only three communicated qubits, compared with the optimal classical cost of six bits. Together with the protocols for three-bit equality and a wider family of Boolean functions, these results show that quantum advantage in PSQM is not confined to artificial promise problems. The contrast with AND shows that the structure of the function is equally important. Functions with a unique accepting or rejecting input are incompatible with perfect correctness and perfect privacy in the one-qubit local-unitary model, regardless of the shared k-qubit state and shared randomness. This is a general structural obstruction, not a failure of a particular GHZ construction. Increasing the local dimension overcomes the obstruction. Our quotient-label construction gives one-shot protocols for multiparty AND using one qudit per player with dimension at most the number of players. For three-bit AND, one qutrit per player is sufficient, whereas one qubit per player is impossible in the local-unitary model. Thus the benefit of entanglement in PSQM is governed jointly by the structure of the function and the local dimension available to the players. Several questions remain open. First, the unique-preimage theorem is specific to unitary operations on a designated message qubit. Arbitrary local CPTP encodings, input-dependent interactions with auxiliary systems, and protocols in which each player transmits more than one qubit may evade the three-dimensional localaction bound. It remains open whether the one-shot quantum communication cost of AND3 can be reduced below 3 log2 3 using asymmetric message dimensions, arbitrary local CPTP encodings, or input-dependent interactions with auxiliary systems. Equivalently, it is unknown whether the qutrit protocol is optimal among all entanglement-assisted PSQM protocols. The exact classical and quantum communication complexities of AND3 also remain open, although the known bounds already give a strict separation.

38

Second, the finite GHZ–Pauli experiment leaves 176 functions without feasible numerical solutions. The most structured unresolved cases include EXACT1 , EXACT2 , and the affine extensions of two-edge quadratic forms such as xy ⊕ xz. A rigorous infeasibility proof or a direct analytic converse would turn the numerical census into a complete theorem for the restricted model. Third, the construction for EQk,n relies on existential multicolored sum-free families and on a reduction through generalized equality. It remains open to obtain uniform and efficiently computable local maps, improve the lower-order terms, or construct direct protocols that bypass the zero-sum layer. It would also be natural to ask which other standard multiparty predicates admit comparable entanglement-assisted reductions. More generally, our results suggest a program for PSQM centered on concrete functions. Equality and majority demonstrate that prior entanglement can reduce the communication cost of familiar total functions. The contrast between majority and AND shows that changing the structure of the accepting and rejecting inputs can create a strong obstruction. A fuller understanding of quantum advantage in secure simultaneous communication will therefore require both constructive mechanisms, such as combinatorial embeddings and entangled secure sums, and structural tools that explain when privacy is incompatible with local quantum encodings. AI disclosure. Microsoft Copilot and Chat GPT were used to assist with iterative discussion, manuscript editing, and the generation and execution of code for the exploratory linearprogramming and finite-search experiments. The author independently verified the final analytic constructions and takes full responsibility for the contents of the paper. Acknowledgements. This work is supported by JSPS KAKENHI 24H00071, 24K22293, 26H02504, MEXT Q-LEAP JPMXS0120319794, and JST CREST JPMJCR24I4.

A

Shared-Randomness Compression for the Three-Party Qutrit Protocol

The direct specialization of the quotient-label construction to k = p = 3 uses independent uniform random variables M ∈ GL(2, 3) and τ ∈ Kt , and therefore has 48 · 3 = 144 values. In this appendix, we give a three-party-specific optimization that removes the independent kernel randomizer and reduces the shared-randomness support to 48 values. The optimized construction preserves the communication cost 3 log2 3, but produces different output-dependent density operators from those of the direct specialization. Instead of using an independent random shift in the kernel, it correlates the choice of a GHZ label with the uniformly random matrix M , subject to the prescribed quotient label. The resulting mixtures over GHZbasis states are nonuniform. Nevertheless, every rejecting input produces the same density operator, while the accepting input produces another density operator with orthogonal support. Thus perfect privacy and perfect correctness are preserved. Throughout this appendix, all vector and matrix operations are over F3 . We specialize the notation of Section 6.1 by writing 1 X |G3 ⟩ := |G3,3 ⟩ = √ |j, j, j⟩ 3 j∈F 3

39

and |Φu,v,w ⟩ := |Φu2 =u,u3 =v,w ⟩ = (I ⊗ X u ⊗ X v Z w ) |G3 ⟩. By Lemma 6.1, local Weyl exponents (a1 , b1 ), (a2 , b2 ), and (a3 , b3 ) produce the GHZ label (a2 − a1 , a3 − a1 , b1 + b2 + b3 ).

(A.1)

The quotient map specializes to π(u, v, w) = (u + v, w), with kernel ker π = {(0, 0, 0), (1, 2, 0), (2, 1, 0)}. The referee decodes a GHZ label in ker π as output 1, and every other GHZ label as output 0.

A.1

The 48-value construction

Let (0)

(0)

(0)

s1 = s2 = (0, 1)T ,

s3 = (1, 2)T

(A.2)

in F23 . Every nonempty subset sum of these three vectors is nonzero. Explicitly, (0)

(0)

s1 = (0, 1)T , (0)

(0)

(0)

s2 = (0, 1)T , (0)

(0)

s3 = (1, 2)T , (0)

(0)

s1 + s2 = (0, 2)T , s1 + s3 = (1, 0)T , s2 + s3 = (1, 0)T ,

(A.3)

(0) (0) (0) s1 + s2 + s3 = (1, 1)T .

The players share a uniformly random matrix   a b ∈ GL(2, 3). M= c d Since | GL(2, 3)| = 48, the shared-randomness support has size 48. Set (0)

si = M si

(i = 1, 2, 3).

Thus s1 = s2 = (b, d),

s3 = (a + 2b, c + 2d).

Players 1, 2, 3 hold the local input bits x, y, z, respectively, and apply the following Weyl operators: Ax = X bx Z dx , By = X a+by Z dy ,

(A.4)

Cz = X a+2b+(a+2b)z Z 2c+2d+(c+2d)z . The order of the X- and Z-factors affects only a global phase. The input-dependent parts of these operators are exactly the specialization of (6.4) and (6.5) to k = p = 3 and t2 = t3 = 1. The input-independent factors select an M -dependent GHZ-label representative of the required quotient label. Equivalently, they replace the independent uniform kernel shift of the general construction by a deterministic kernel shift correlated with M . Let
LM (x, y, z) = uM (x, y, z), vM (x, y, z), wM (x, y, z) ∈ F33 denote the resulting GHZ label. By (A.1), uM (x, y, z) = a + b(y − x), vM (x, y, z) = a + 2b + (a + 2b)z − bx, wM (x, y, z) = 2c + 2d + d(x + y) + (c + 2d)z. 40

(A.5)

A.2

Correctness

The quotient label admits a particularly simple description. Lemma A.1 (Quotient label formula). For every M ∈ GL(2, 3) and (x, y, z) ∈ {0, 1}3 , π(LM (x, y, z)) = −(1 − x)s1 − (1 − y)s2 − (1 − z)s3 .

(A.6)

Proof. The input-dependent factors are the k = p = 3, t2 = t3 = 1 specialization of the general construction, and thus Lemma 6.4 applies to them. The input-independent GHZ label gM = (a, a + 2b, 2c + 2d) satisfies π(gM ) = −(a + b, c + d) = −(s1 + s2 + s3 ). The claimed formula follows. Proposition A.2 (Perfect correctness). For every M ∈ GL(2, 3), LM (x, y, z) ∈ ker π

⇐⇒

x = y = z = 1.

Proof. For input 111, (A.6) gives π(LM (1, 1, 1)) = 0, and hence LM (1, 1, 1) ∈ ker π. Now suppose that (x, y, z) ̸= (1, 1, 1), and define the nonempty set T = {i ∈ {1, 2, 3} : xi = 0}, where x1 = x, x2 = y, and x3 = z. Then π(LM (x, y, z)) = −

X

si = −M

i∈T

X (0) si . i∈T

The corresponding subset sum of the vectors in (A.2) is nonzero by (A.3). Since M is invertible, its image is also nonzero. Therefore π(LM (x, y, z)) ̸= 0, so LM (x, y, z) ∈ / ker π. Thus a GHZ-basis measurement followed by membership testing in ker π computes AND3 with perfect correctness.

A.3

Perfect privacy

By Lemma A.1 and the p = 3 case of Lemma 6.6, every rejecting input produces the uniform distribution on F23 \ {0} at the level of the quotient label. Unlike the general construction, however, the present protocol does not use an independent uniform shift in ker π. Uniformity of the quotient label therefore does not by itself imply privacy of the received state. We must additionally verify that all rejecting inputs induce the same GHZ-label distribution. Define R3 := {(1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2)}, 41

and N := {(0, 0, 1), (0, 0, 2)}. Set
R2 := F33 \ ker π ∪ R3 ∪ N . Then |R2 | = 18 and |R3 | = 4. Lemma A.3 (GHZ-label distributions). Let M be uniform on GL(2, 3). For every rejecting input (x, y, z) ̸= (1, 1, 1), the GHZ label LM (x, y, z) has the same distribution, given by   2/48, λ ∈ R2 , Pr[LM (x, y, z) = λ] = 3/48, λ ∈ R3 , (A.7)   0, λ ∈ ker π ∪ N. For the accepting input,   12/48,    18/48, Pr[LM (1, 1, 1) = λ] = 18/48,    0,

λ = (0, 0, 0), λ = (1, 2, 0), λ = (2, 1, 0), λ∈ / ker π.

(A.8)

Proof. Write   a b . M= c d Substituting the eight possible inputs into (A.5) reduces the assertion to counting the quadruples (a, b, c, d) ∈ F43 satisfying ad − bc ̸= 0. For input 111, (A.5) simplifies to LM (1, 1, 1) = (a, 2a, 0). There are 12 invertible matrices with a = 0, and 18 each with a = 1 and a = 2. This gives (A.8). For each of the other seven inputs, one substitutes the corresponding values into (A.5) and counts the solutions of ad − bc ̸= 0, which gives (A.7). We illustrate the rejecting-input count for 000. In this case, (A.5) gives LM (0, 0, 0) = (a, a + 2b, 2c + 2d). Fix a GHZ label λ = (u, v, w). The identity LM (0, 0, 0) = λ is equivalent to a = u,

b = 2(v − u),

c = 2w − d,

where d ∈ F3 is free. Substitution into the determinant gives det M = 2(u + v)d + (u − v)w. If u + v ̸= 0, this is a nonconstant affine function of d, so it vanishes for exactly one of the three values of d. Hence the GHZ label has exactly two preimages in GL(2, 3). If u + v = 0, then det M = (u − v)w. 42

This constant is nonzero exactly when u ̸= 0 and w ̸= 0, which gives the four GHZ labels in R3 . Otherwise either w = 0, giving a GHZ label in ker π, or u = v = 0, giving a GHZ label in N . In both cases, det M vanishes for every value of the free parameter d. For each of the other six rejecting inputs, substituting the corresponding values into (A.5) gives the same multiplicity pattern. More precisely, after solving the three GHZ-label equations, one free parameter remains. For GHZ labels in R2 , the determinant is a nonconstant affine function of this parameter and therefore vanishes once; for GHZ labels in R3 , it is a nonzero constant; and for GHZ labels in ker π ∪ N , it vanishes identically. Hence the multiplicities are 2, 3, and 0, respectively, for every rejecting input. Define the two density operators   X X 1  ϱ0 := |Φλ ⟩⟨Φλ | |Φλ ⟩⟨Φλ | + 3 2 48 λ∈R3

λ∈R2

and ϱ1 :=

1 (12|Φ0,0,0 ⟩⟨Φ0,0,0 | + 18|Φ1,2,0 ⟩⟨Φ1,2,0 | + 18|Φ2,1,0 ⟩⟨Φ2,1,0 |) . 48

Lemma A.3 gives ( ϱ0 , (x, y, z) ̸= (1, 1, 1), ρ(x,y,z) = ϱ1 , (x, y, z) = (1, 1, 1),

(A.9)

where ρ(x,y,z) is the state received by the referee when the input is (x, y, z). Thus the joint state received by the referee depends only on the value of AND3 . We have proved the following theorem. Theorem A.4 (48-value three-party qutrit protocol). There is a perfectly correct and perfectly private entanglement-assisted PSQM protocol for AND3 in which the players share one three-qutrit GHZ state and a uniformly random matrix M ∈ GL(2, 3), and each player transmits one qutrit. The communication cost is 3 log2 3, and the shared-randomness support has size 48. Proof. Perfect correctness follows from Proposition A.2. Perfect privacy follows from (A.9). Each player transmits one three-dimensional quantum register, so the total communication cost is 3 log2 3.

References [1] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel, “Relating Non-Local Quantum Computation to Information-Theoretic Cryptography,” Quantum, vol. 8, Article no. 1387, 2024. DOI: 10.22331/q-2024-06-27-1387. [2] Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz, “The communication complexity of private simultaneous messages, revisited,” Journal of Cryptography, vol. 33, no. 3, pp. 916–953, 2020. DOI: 10.1007/s00145-019-09334-y. [3] Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz, “On the Cryptographic Complexity of the Worst Functions,” in Proceedings of the 11th Theory of Cryptography Conference, pages 317–342. Springer, 2014. DOI: 10.1007/978-3-642-54242-8 14. 43

[4] Zvika Brakerski and Henry Yuen, “Quantum garbled circuits,” in Proceedings of the 54th Annual ACM Symposium on Theory of Computing, pages 804–817, 2022. DOI: 10.1145/3519935.3520073. [5] René Bødker Christensen and Petar Popovski, “Private Product Computation Using Quantum Entanglement,” IEEE Transactions on Quantum Engineering, vol. 4, Art. no. 2100609, 2023. DOI: 10.1109/TQE.2023.3320052. [6] Deepesh Data, Vinod M. Prabhakaran, and Manoj M. Prabhakaran, “Communication and randomness lower bounds for secure computation,” IEEE Transactions on Information Theory, vol. 62, no. 7, pp. 3901–3929, 2016. DOI: 10.1109/TIT.2016.2554541. [7] Uri Feige, Joe Kilian, and Moni Naor, “A minimal model for secure computation,” in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994, pp. 554–563. DOI: 10.1145/195058.195408. [8] Uma Girish, Alex May, Leo Orshansky, and Chris Waddell, “Comparing classical and quantum conditional disclosure of secrets,” Quantum, vol. 10, Article no. 2049, 2026. DOI: 10.22331/q2026-04-01-2049. [9] Uma Girish, Alex May, Natalie Parham, and Henry Yuen, “Magic and Communication Complexity,” in Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 845–856, 2026. DOI: 10.1145/3798129.3800799 [10] Uma Girish, Alex May, Natalie Parham, and Henry Yuen, “New Bounds on Private Simultaneous Quantum Message Passing,” arXiv:2606.12557, 2026. [11] Tom Gur, Miryam Mi-Ying Huang, and Er-Cheng Tang, “Quantum Encodings, Private Messages, and Communication Complexity,” arXiv:2609.17690, 2026. [12] Q. Huangfu and J. A. J. Hall, “Parallelizing the Dual Revised Simplex Method,” Mathematical Programming Computation, vol. 10, no. 1, pp. 119–142, 2018. DOI: 10.1007/s12532-017-0130-5. [13] Akinori Kawachi and Yuto Nishikubo, “Private Quantum Signal Processing,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E108-A, no. 9, pp. 1105–1113, 2025. DOI: 10.1587/transfun.2024DMP0017. [14] Akinori Kawachi and Harumichi Nishimura, “Communication Complexity of Private Simultaneous Quantum Messages Protocols,” 2nd Conference on Information-Theoretic Cryptography (ITC 2021), LIPIcs 199, Article 20, 2021. DOI: 10.4230/LIPIcs.ITC.2021.20. [15] Robert Kleinberg, Will Sawin, and David E. Speyer, “The Growth Rate of Tri-Colored SumFree Sets,” Discrete Analysis, 2018:12, 2018. DOI: 10.19086/da.3734. [16] Yuval Ishai and Eyal Kushilevitz, “Private Simultaneous Messages Protocols with Applications,” in Proceedings of the 5th Israel Symposium on the Theory of Computing and Systems, 1997, pp. 174–183. DOI: 10.1109/ISTCS.1997.595170. [17] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000. [18] Luke Pebody, “Proof of a Conjecture of Kleinberg–Sawin–Speyer,” Discrete Analysis, 2018:13, 2018. DOI: 10.19086/da.3733. 44

[19] László M. Lovász and Lisa Sauermann, “A Lower Bound for the k-Multicolored Sum-Free Problem in Znm ,” Proceedings of the London Mathematical Society, 119(1):55–103, 2019. DOI: 10.1112/plms.12223. [20] Yuxiang Lu, Yuhang Yao, and Syed A. Jafar, “On the Capacity of Secure K-User Product Computation over a Quantum MAC,” IEEE Communications Letters, 27(10):2598–2602, 2023, DOI: 10.1109/LCOMM.2023.3311368. Updated version: arXiv:2305.20073v3, September 2025. [21] Kazumasa Shinagawa and Koji Nuida, “Explicit Lower Bounds for Communication Complexity of PSM for Concrete Functions,” in Progress in Cryptology–INDOCRYPT 2023, Lecture Notes in Computer Science, Springer, 2023, pp. 45–61. DOI: 10.1007/978-3-031-56235-8 3. [22] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E.A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors, “SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python,” Nature Methods, vol. 17, pp. 261–272, 2020. DOI: 10.1038/s41592-0190686-2. [23] John Watrous, The Theory of Quantum Information, Cambridge University Press, 2018.

45

Related documents

• Quantum Grounded Symbols - Unified Framework#20904
• Quantum Grounded Symbols - Unified Framework#14501
• Privacy-preserving quantum federated learning via gradient hiding#177307
• Finite-time quantum equilibration from local correlations#1327941
• Federated Unlearning of Quantum Data via Classical Shadows#1344900