PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Harumichi Nishimura

arXiv:2610.23090v1quant-phcs.CCcs.CR

TL;DR

The communication complexity of familiar concrete functions in perfectly correct and private PSQM remains less understood, and function structure may affect which protocols are possible. The paper develops entanglement-assisted constructions and structural bounds, finding both communication advantages and a one-qubit obstruction for unique-preimage functions.

  • Problem

    The communication complexity of familiar concrete functions in PSQM remains less understood, while classical PSM has matching bounds for only a few cases.

    Source: §1 · p. 3

  • Method

    The paper combines entanglement-assisted constructions for concrete functions with structural rank arguments for one-qubit local-unitary protocols.

    Source: §1.1 · pp. 4–5

  • Results

    Majority uses three communicated qubits versus the optimal classical cost of six bits, while unique-preimage functions are obstructed in the one-qubit local-unitary model and higher local dimension enables AND protocols.

    Source: §7 · p. 38

  • Takeaways & Limitations

    PSQM advantages and limitations depend jointly on function structure and the local message dimension available to the players.

    Source: §7 · pp. 38–39

    The equality construction relies on existential multicolored sum-free families; uniform efficiently computable local maps and improved lower-order terms remain open.

    Source: §7 · p. 39

Abstract

from arXiv · show

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\ldots)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\log_2 3$. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every $k\geq 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\log_2 k$ qubits in total.

1 Introduction

Prior work established quantum separations in PSQM, but the communication complexity of familiar concrete functions remained less understood. This paper studies where entanglement helps and where function structure obstructs perfectly correct and private protocols.

1 Introduction

  • The paper targets a gap in concrete-function complexity: even classical PSM had few cases with matching bounds, while the behavior of familiar functions in PSQM remained less understood.The introduction frames the study around perfect correctness and perfect privacy.Source: §1 · p. 3

1.1 Our contributions

  • For three-party equality, entanglement-assisted PSQM communicates at most (1.633...)n + O(√n) qubits, while protocols without prior entanglement require at least 3n qubits.The construction uses a one-shot secure-sum layer to remove the odd-party dummy-user penalty.Source: §1.1 · p. 4
  • For three-bit majority, one shared GHZ state and one transmitted qubit per player yield a three-qubit protocol, compared with the optimal classical cost of six bits.The same local-Pauli approach also yields a three-bit equality protocol and protocols for exactly 80 three-bit Boolean functions.Source: §1.1 · pp. 4–5
  • For functions with a unique accepting or rejecting input, no perfectly correct and private one-qubit local-unitary protocol exists for k ≥3, regardless of the shared k-qubit state or classical randomness.The proof combines a rank lower bound of 2k −1 with a privacy-based upper bound of 3.Source: §1.1 · p. 5
  • Increasing local message dimension overcomes the AND obstruction: one qutrit per player gives three-bit AND communication of 3 log2 3, below the classical lower bound of 6 bits.For every k ≥3, the construction gives a one-shot AND protocol using one qudit per player and at most k log2 k total qubits.Source: §1.1 · p. 5

1.2 Related work

  • The results complement earlier general bounds and quantum-model connections by focusing on concrete-function communication under perfect correctness and perfect privacy.The introduction situates its classical comparisons in work on explicit bounds for functions including majority, equality, and AND [21].Source: §1.2 · p. 6

2 Preliminaries

The preliminaries define classical and quantum simultaneous-message protocols through the referee’s view, then give two linear-algebra tools used in the paper. In PSQM, perfect privacy makes that view depend only on the function value.

2.1 Classical private simultaneous messages

  • In classical PSM, players send simultaneous messages using shared randomness hidden from the referee; correctness recovers the function, while privacy requires identical message distributions for inputs with the same output.A (4, 4, 4) protocol has three message alphabets of size four and costs six bits total.Source: §2.1 · p. 7

2.2 Private simultaneous quantum messages

  • In PSQM, players may share input-independent entanglement and randomness, apply local channels, and send quantum message registers; perfect privacy requires the referee’s averaged state to depend only on the function value.Perfect correctness together with perfect privacy gives output-dependent states with mutually orthogonal supports.Source: §2.2 · p. 8

2.3 Two linear-algebra lemmas

  • A one-qubit unitary with zero expectation against a qubit state is, up to global phase, a Hermitian involution.The preliminaries also use the support containment property for positive components of a positive-operator mixture.Source: §2.3 · pp. 9–10

3 Entanglement-Assisted Advantage for Equality on Strings

This section develops entanglement-assisted protocols for equality on strings by embedding inputs into generalized equality and combining secure-sum primitives with randomized scaling. It compares their communication upper bound with the lower bound of at least kn qubits for perfectly correct protocols without prior entanglement, noting that the entanglement-assisted coefficient is smaller for 3 ≤ k ≤ 9.

3.1 Combinatorial embeddings by multicolored sum-free families

  • For fixed k ≥ 3, a combinatorial embedding maps n-bit inputs to vectors whose sum is zero exactly when all inputs are equal.The local embedding is the basis for reducing string equality to generalized equality.Source: §3.1 · p. 11

3.3 Odd-party four-coordinate secure sum

  • The two-user Bell primitive encodes two binary sums in two transmitted qubits; for odd k, paired triangle instances yield four secure sums using 2k qubits with no dummy party.The odd-party protocol is perfectly correct and perfectly private.Source: §3.2 · p. 12, §3.3 · p. 13

3.4 From blockwise secure sums to private generalized equality

  • Uniformly random nonzero scaling makes all nonzero generalized-equality aggregates induce one received state, while zero aggregates induce another, giving perfect privacy.The scaling preserves whether the aggregate is zero, so correctness is retained.Source: §3.4 · p. 16

3.5 Our upper bound

  • (1.633...)n + O(√n) qubits suffice for three-party string equality, and the upper bound has no asymptotic parity distinction across k.The general bound is QPSQM,∗(EQk,n) ≤ k/(2h2(1/k)) n + Ok(√n).Source: §3.5 · pp. 16–17

3.6 Shared-randomness-only comparison

  • Every perfectly correct PSQM protocol for EQk,n using shared classical randomness but no prior entanglement communicates at least kn qubits.Source: §3.6 · p. 17
  • At least kn qubits are required without prior entanglement for k-player equality on n-bit strings.For each player, the 2^n local message states for distinct inputs must have pairwise orthogonal nonzero supports, requiring at least n qubits per player.Source: §3.6 · p. 17
  • For 3 ≤ k ≤ 9, the entanglement-assisted upper-bound coefficient k·2h_2(1/k) is smaller than the shared-randomness-only lower-bound coefficient k.Source: §3.6 · p. 18

4 Three-Bit Boolean Functions

This section develops three-qubit GHZ–Pauli protocols for majority and equality and extends the approach to an analytic family of three-bit Boolean functions. It gives explicit constructions for 80 of 256 functions found feasible by the restricted search, while failures for the others remain numerical observations rather than impossibility results.

4.1 GHZ labels

  • Local Pauli encodings map the shared GHZ state to labels (u, v, w) with u = a1 ⊕ a2, v = a1 ⊕ a3, and w = b1 ⊕ b2 ⊕ b3.The two relative bit-flip parities and the parity of the three Z exponents determine the label.Source: §4.1 · p. 18

4.2 Majority and equality

  • One shared GHZ state, two shared random bits, and one transmitted qubit per player give a perfectly correct and private protocol for three-bit majority, using three qubits versus the classical six-bit cost.Disjoint GHZ-label sets encode the two outputs, while the resulting state distribution depends only on the majority value.Source: §4.2 · pp. 18, 20, 22
  • Applying local Z operations and reversing the referee’s output converts the majority protocol into a perfectly correct and private three-bit equality protocol with the same resources, yielding quantum advantage over classical cost 3 log2 3.The construction uses Zx, Zy, and Zz on the players’ encoders.Source: §4.2 · p. 23

4.3 An analytic family of 80 functions

  • Exactly 80 three-bit functions admit perfectly correct and private protocols in the stated GHZ–Pauli model, with finite shared randomness and one transmitted qubit per player.The construction covers 16 affine functions, 48 with one quadratic term, and 16 with all three quadratic terms, using affine encodings, the xy ⊕ z base protocol, majority, and input or output transformations.Source: §4.3 · pp. 23–25

4.4 Computational exploration of a restricted GHZ–Pauli model

  • The computation enumerated 256 Boolean truth tables, 256 decoder supports, and 4096 deterministic encoding types, then solved the resulting feasibility problems using floating-point linear programming.Source: §4.4 · pp. 26–27
  • 80 of 256 three-bit Boolean functions were feasible in the restricted search, and Theorem 4.5 gives explicit analytic constructions for all 80.Source: §4.4 · p. 27
  • The solver reported no feasible solution for functions including EXACT1, EXACT2, and 48 affine extensions, but these are numerical outcomes confined to the restricted model.The search does not establish impossibility for arbitrary local U(2) or CPTP encodings, other shared states, or larger messages.Source: §4.4 · pp. 26–27
  • The exploration suggests that two-edge quadratic forms such as xy ⊕ xz may be the remaining case for analytic classification of the restricted model and offers candidates for future impossibility arguments.Source: §4.4 · p. 27

5 Unique-Preimage Impossibility

Theorem 5.1 rules out perfectly correct and perfectly private protocols for functions with a unique preimage in the one-qubit local-unitary model. Its proof combines a rank lower bound from correctness with a contradictory rank upper bound from privacy.

5 Unique-Preimage Impossibility

  • No perfectly correct and perfectly private protocol exists for a Boolean function with a unique preimage in the one-qubit local-unitary model, for k ≥ 3.The model permits an arbitrary shared k-qubit mixed state and arbitrary input-independent classical shared randomness.Source: §5 · p. 28
  • The theorem covers k-bit AND, OR, NAND, NOR, Boolean point functions, and their complements.Its scope is limited to qubit messages with local unitary encodings; it does not directly cover arbitrary CPTP encodings or functions with both output classes containing at least two inputs.Source: §5 · p. 28, §5.2 · p. 31

5.1 Rank lower bound and purification forced by correctness

  • Perfect correctness forces the shared state to be pure and produces orthogonal rejecting components, giving a rank lower bound.The argument uses the qubit-unitary structure for single-coordinate flips before considering the full family of input flips.Source: §5 · p. 28, §5.1 · p. 29

5.2 Rank upper bound by privacy

  • Perfect privacy yields a rank upper bound that contradicts the correctness-based lower bound for every k ≥ 3.The contradiction completes the impossibility proof.Source: §5 · p. 28, §5.2 · p. 31

6 One-Qudit Protocols for Multiparty AND

The section constructs perfectly correct and private one-qudit-per-player protocols for multiparty AND, then specializes the construction to three-bit AND. It shows that qutrits overcome the one-qubit obstruction and give a strict communication advantage for AND3.

6.1 Generalized GHZ labels

  • The GHZ labels form an orthonormal basis indexed by relative shifts and a phase label, and local Weyl operations determine these labels up to global phase.The shared common shift is removed; the remaining shifts are relative to player 1.Source: §6.1 · p. 32

6.2 Our protocol

  • The protocol encodes inputs as changes to a GHZ label and accepts exactly when the measured label belongs to the kernel Kt.Players share uniform M ∈GL(2, p) and τ ∈Kt, apply input-independent and input-dependent local operations, and transmit one qudit each.Source: §6.2 · p. 34

6.3 Correctness and privacy

  • For every random choice, the quotient label belongs to Kt exactly on the all-one input; averaging over shared randomness makes the referee’s state depend only on ANDk.The proof uses nonzero subset sums for correctness and uniform nonzero quotient labels for rejecting inputs’ privacy.Source: §6.3 · pp. 35–36

6.4 Consequences

  • For every k ≥3, a prime p with k ≤2(p −1) gives a perfectly correct and private ANDk protocol using one p-dimensional GHZ state and one transmitted p-dimensional qudit per player.The communication is k log2 p; some p ≤k always satisfies the condition, yielding at most k log2 k.Source: §6.4 · p. 37
  • For AND3, one shared three-qutrit GHZ state and one transmitted qutrit per player achieve perfect correctness and privacy at communication 3 log2 3.The six-bit classical lower bound makes this a strict communication advantage.Source: §6.4 · pp. 37–38
  • For AND3, one qutrit per player is the smallest local dimension in the symmetric one-system-per-player local-unitary setting, since one qubit per player is impossible.The direct construction uses 144 shared-randomness values; an optimized version reduces this to 48 without changing communication cost.Source: §6.4 · pp. 37–38

7 Conclusion

The conclusion contrasts quantum advantages for familiar functions with structural limits that depend on the function and local dimension. It also identifies open questions about AND3 protocols, finite-search results, and equality constructions.

7 Conclusion

  • Prior entanglement reduces communication for multiparty equality and three-bit majority; majority uses three qubits versus the optimal classical cost of six bits.The conclusion also notes protocols for three-bit equality and a wider family of Boolean functions.Source: §7 · p. 38
  • Functions with a unique accepting or rejecting input are incompatible with perfect correctness and privacy in the one-qubit local-unitary model, regardless of shared state and randomness.For AND, increasing local dimension overcomes the obstruction; one qutrit per player suffices for AND3, and the general construction uses dimension at most the player count.Source: §7 · p. 38
  • The exact classical and quantum communication complexities of AND3 remain open, including whether its qutrit protocol is optimal among entanglement-assisted protocols.The impossibility result is limited to unitary operations on a designated message qubit; CPTP encodings, auxiliary-system interactions, or multiple transmitted qubits may evade its bound.Source: §7 · p. 38
  • The equality construction relies on existential multicolored sum-free families and a reduction through generalized equality; uniform efficient local maps and improved lower-order terms remain open.The paper also leaves 176 functions without feasible numerical solutions in its finite GHZ–Pauli experiment.Source: §7 · p. 39
  • The paper frames further PSQM work as combining constructive mechanisms with structural tools for understanding when privacy conflicts with local quantum encodings.Its examples include combinatorial embeddings and entangled secure sums.Source: §7 · p. 39

A Shared-Randomness Compression for the Three-Party Qutrit Protocol

The appendix compresses shared randomness in the three-party qutrit protocol while preserving its communication cost, correctness, and privacy.

A Shared-Randomness Compression for the Three-Party Qutrit Protocol

  • The direct three-party specialization uses 144 shared-randomness values, while the optimized construction uses 48.The optimization removes the independent kernel randomizer and correlates GHZ-label choice with the uniformly random matrix M.Source: A Shared-Randomness Compression for… · p. 39
  • The optimized construction preserves communication cost 3 log2 3 but produces different output-dependent density operators from the direct specialization.Its GHZ-basis mixtures are nonuniform, yet all rejecting inputs yield the same state and the accepting state has orthogonal support.Source: A Shared-Randomness Compression for… · p. 39
  • The referee decodes a GHZ label in ker π as output 1 and every other label as output 0.Source: A Shared-Randomness Compression for… · p. 40

A.1 The 48-value construction

The construction replaces the independent kernel shift with a deterministic shift correlated with a uniformly random matrix, while retaining the quotient-label decoding scheme.

A.1 The 48-value construction

  • The three input-change vectors have no nonempty subset summing to zero, supporting separation of the all-one input from rejecting inputs.Source: §A.1 · p. 40
  • The players share a uniformly random matrix M ∈GL(2, 3), giving 48 shared-randomness values.The input-independent factors choose an M-dependent GHZ-label representative of the required quotient label.Source: §A.1 · p. 40
  • For the three-party protocol, players apply input-dependent Weyl operators to encode their respective bits x, y, and z.The input-dependent operators specialize the general construction to k = p = 3 and t2 = t3 = 1.Source: §A.1 · p. 40

A.2 Correctness

The correctness proof separates the all-ones input from every other input by testing whether its GHZ label lies in ker π. A GHZ-basis measurement followed by this membership test computes AND3 with perfect correctness.

A.2 Correctness

  • The passage gives an if-and-only-if criterion for label membership in ker π: LM(x, y, z) lies there exactly when all three coordinates satisfy x = y = z = 1.Source: §A.2 · p. 41
  • For every other input, a nonempty subset sum is nonzero and remains nonzero under invertible M, placing its label outside ker π.The proof uses the nonempty set of input coordinates that differ from 1.Source: §A.2 · p. 41
  • A GHZ-basis measurement followed by membership testing in ker π computes AND3 with perfect correctness.Source: §A.2 · p. 41

A.3 Perfect privacy

Perfect privacy is established by showing that the referee’s received state depends only on AND3. The proof checks identical GHZ-label distributions across rejecting inputs, since quotient-label uniformity alone is insufficient here.

A.3 Perfect privacy

  • Uniformity of quotient labels alone does not imply privacy here because the protocol has no independent uniform shift in ker π.The proof therefore additionally verifies that all rejecting inputs induce the same GHZ-label distribution.Source: §A.3 · p. 41
  • Every rejecting input has the same GHZ-label distribution: 2/48 per label in R2, 3/48 in R3, and 0 in ker π ∪ N.The corresponding multiplicities are 2, 3, and 0 for labels in those three sets.Source: §A.3 · pp. 42–43
  • The referee’s received state depends only on the value of AND3.Source: §A.3 · p. 43
  • One shared three-qutrit GHZ state and one transmitted qutrit per player give a perfectly correct and private AND3 protocol costing 3 log2 3.The protocol uses a uniformly random matrix M ∈ GL(2, 3) with shared-randomness support of size 48.Source: §A.3 · p. 43
Loading 2610.23090v1…