pith. sign in

arxiv: 2606.12557 · v1 · pith:RXMZ43JUnew · submitted 2026-06-10 · 🪐 quant-ph

New bounds on private simultaneous quantum message passing

Uma Girish , Alex May , Natalie Parham , Henry Yuen This is my paper

Pith reviewed 2026-06-27 09:25 UTC · model grok-4.3

classification 🪐 quant-ph
keywords private simultaneous messagesquantum communicationnon-local quantum computationentanglement lower boundsFourier analysiscircuit complexitymultiparty computationcommunication complexity
0
0 comments X

The pith

Nečiporuk's measure lower bounds entanglement for k-player quantum PSM with perfect correctness, while circuit size upper bounds the communication cost.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes new lower and upper bounds on quantum private simultaneous message passing. Lower bounds use Nečiporuk's measure to limit entanglement in perfect-correctness k-party protocols, producing quadratic bounds for explicit functions, and use the rank of the communication matrix to bound 2-party protocols that preserve privacy. Upper bounds show that quantum PSM cost scales with circuit size, depth, and number of players, while classical PSM cost is bounded by the square of the Fourier 1-norm of the function. These results generalize T-depth techniques from non-local quantum computation to multiple parties and connect PSM to Boolean function complexity measures.

Core claim

Nečiporuk's measure lower bounds the entanglement required for k-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. The rank of the communication matrix of f(x1,x2) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. Letting s be the size of a quantum circuit computing f, df its depth, k the number of players, n the input length per player, and ε a correctness parameter, PSM_k^*(f) ≤ (kn + s) · log^{O(df)}(s/ε). Also, PSM(f) ≤ O(∥f̂∥_1²).

What carries the argument

Nečiporuk's measure for entanglement lower bounds in perfect k-party quantum PSM, together with generalization of T-depth techniques from non-local quantum computation to k parties with restricted Clifford light cones for the circuit-size upper bound.

If this is right

  • Quadratic lower bounds hold for explicit functions in k-player quantum PSM with perfect correctness.
  • The communication-matrix rank yields the first lower bounds on quantum PSM that use the privacy condition.
  • PSM complexity is at most linear in circuit size times a logarithmic factor in depth.
  • Classical PSM complexity is bounded above by the square of the Fourier 1-norm of f.
  • The matrix-rank bound implies a new lower bound for classical PSM with imperfect correctness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bounds may limit the quantum advantage possible in secure multiparty computation for functions with large Nečiporuk measure.
  • The upper-bound construction suggests that depth-bounded quantum circuits can be turned into low-communication PSM protocols by controlling light cones in Clifford layers.
  • Tightness could be tested by comparing the new bounds against known PSM costs for functions such as equality or disjointness.

Load-bearing premise

The T-depth based techniques for non-local quantum computation can be generalized from 2 to k parties while restricting Clifford layers to small light cones.

What would settle it

An explicit function f where the minimal shared entanglement for perfect-correctness k-player quantum PSM is strictly smaller than the Nečiporuk measure of f.

Figures

Figures reproduced from arXiv: 2606.12557 by Alex May, Henry Yuen, Natalie Parham, Uma Girish.

Figure 1
Figure 1. Figure 1: A private simultaneous message protocol (PSM). We show the case with two players for simplicity, but [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: a) A PSQM∗ protocol. The n players have been divided into two subsets, S and S¯. The input to the S¯ players is set to α. The last n − 1 bits of each of the players in S is set to β, while the first bit inputs are free, and the players can choose any string y to take as input. Correctness of the PSQM∗ protocol gives that the referee can compute fS|(α,β) (y) from the message systems MS, MS¯. b) In the proof… view at source ↗
Figure 3
Figure 3. Figure 3: XOR gadget for computing ⊕ifi in the garden-hose model. It can be checked directly that if water enters on the top left, it exits on the left if fi = 0 and on the right if fi = 1. Meanwhile if water enters from the top right, it exits from the bottom right if fi = 0 and from the bottom left if fi = 1. By wiring such gadgets together for each fi then, we can compute ⊕ifi . input qubit comes back out of the … view at source ↗
Figure 4
Figure 4. Figure 4: a) k-party garden-hose protocol for a function f. The water enters in the top left pipe, is redirected through a sequence of pipes represented abstractly as the white rectangle, then exits through one of two pipes, indicating the value of f(x, y). The open input and both open outputs are held by Alice, while the remaining parties are involved in the intermediate steps. b) Protocol for applying a (S † ) f(x… view at source ↗
read the original abstract

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then each send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Ne\v{c}iporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $\epsilon$ a correctness parameter, we obtain $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/\epsilon)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper establishes new upper and lower bounds for quantum private simultaneous message passing (PSM). Lower bounds include: Nečiporuk's measure bounding entanglement in k-player quantum PSM with perfect correctness (yielding quadratic bounds for explicit functions), and the rank of the communication matrix of f(x1,x2) bounding 2-player quantum PSM with perfect privacy but imperfect correctness (implying a new classical PSM lower bound). Upper bounds are: PSM_k^*(f) ≤ (kn + s) · log^{O(d_f)}(s/ε) via a generalization of T-depth NLQC techniques to k parties with small-light-cone Clifford layers, and PSM(f) ≤ O(∥f̂∥_1²) from the Fourier 1-norm.

Significance. If the stated bounds and the NLQC generalization hold, the work supplies the first privacy-based lower bounds on quantum PSM and connects PSM complexity to standard Boolean-function measures (Nečiporuk, matrix rank, circuit size, Fourier norm). The upper-bound construction via circuit parameters and the classical Fourier-norm bound would be concrete, falsifiable contributions to the communication-complexity literature.

major comments (2)
  1. [Proof of the circuit-size upper bound (generalization of T-depth NLQC)] The claimed upper bound PSM_k^*(f) ≤ (kn + s) · log^{O(d_f)}(s/ε) rests on extending 2-party T-depth NLQC constructions to k ≥ 2 parties while enforcing small light cones on Clifford layers. The abstract asserts this generalization is performed, but any failure of the light-cone restriction to control entanglement or communication overhead for k > 2 would invalidate the stated polylog(d_f) factor and the overall multiplier; the proof of this step therefore requires explicit verification.
  2. [Lower-bound statements in the abstract] The lower-bound claims are expressed in terms of external complexity measures (Nečiporuk, matrix rank) rather than quantities internal to the PSM model; while this is not circular, the paper must show that the reductions preserve the privacy and correctness parameters exactly as stated.
minor comments (2)
  1. [Abstract] The abstract states the bounds but supplies no derivations, error analysis, or verification details; the full manuscript must include complete proofs and explicit parameter tracking for the ε-dependence.
  2. [Introduction / notation section] Notation for PSM_k^* versus PSM should be defined at first use and kept consistent throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for recognizing the significance of connecting PSM to standard complexity measures. We respond to the major comments below.

read point-by-point responses

  1. Referee: [Proof of the circuit-size upper bound (generalization of T-depth NLQC)] The claimed upper bound PSM_k^*(f) ≤ (kn + s) · log^{O(d_f)}(s/ε) rests on extending 2-party T-depth NLQC constructions to k ≥ 2 parties while enforcing small light cones on Clifford layers. The abstract asserts this generalization is performed, but any failure of the light-cone restriction to control entanglement or communication overhead for k > 2 would invalidate the stated polylog(d_f) factor and the overall multiplier; the proof of this step therefore requires explicit verification.

    Authors: The full manuscript (Section 4) contains the explicit generalization: we reduce the k-party case to a sequence of 2-party NLQC instances by partitioning the circuit into layers and using the small-light-cone restriction on Clifford gates to ensure that each party's effective support remains O(1) per layer, yielding only a logarithmic overhead in depth rather than exponential in k. The communication multiplier remains linear in k because the referee's messages are assembled from the localized outputs. To make verification immediate, we will add a short self-contained lemma stating the k-party light-cone bound and its communication cost. revision: yes

  2. Referee: [Lower-bound statements in the abstract] The lower-bound claims are expressed in terms of external complexity measures (Nečiporuk, matrix rank) rather than quantities internal to the PSM model; while this is not circular, the paper must show that the reductions preserve the privacy and correctness parameters exactly as stated.

    Authors: Sections 3 and 5 derive the reductions directly from the PSM definitions. For Nečiporuk, the entanglement lower bound is obtained by embedding the function's variable-disjoint subfunctions into a perfect-correctness PSM protocol and showing that any such protocol induces a valid Nečiporuk covering; privacy is not required for this direction. For the matrix-rank bound, the 2-player reduction maps any PSM protocol with perfect privacy and (1-ε)-correctness to a low-rank communication matrix for the function, preserving both parameters exactly. We will insert a one-sentence clarification in the abstract and introduction that the stated parameters are preserved by these embeddings. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation relies on external measures (Nečiporuk's measure for lower bounds on entanglement, communication matrix rank for 2-player privacy, circuit size s and depth d_f for the PSM_k^* upper bound, and Fourier 1-norm for classical PSM) that are standard and independent of the paper's own quantities. The stated generalization of T-depth NLQC techniques from 2 to k parties is described as an extension of existing methods without reducing the central claims to self-defined inputs or self-citation chains by construction. The paper is self-contained against these external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard quantum circuit axioms and prior complexity measures; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Properties of quantum circuits, entanglement, and non-local quantum computation hold as in prior literature.
    Invoked when generalizing T-depth techniques to k parties.
  • domain assumption Nečiporuk's measure and communication matrix rank behave as established complexity measures.
    Used directly to lower bound entanglement and PSM cost.

pith-pipeline@v0.9.1-grok · 5947 in / 1359 out tokens · 24841 ms · 2026-06-27T09:25:51.141688+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Equivalence of non-local computation tasks beyond Clifford operations

    quant-ph 2026-06 unverdicted novelty 6.0

    Reductions link redirecting a quantum system to controlled measurements and Clifford-diagonal-Clifford unitaries, implying equivalent entanglement scaling for many position-verification protocols.

Reference graph

Works this paper leans on

30 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    A minimal model for secure computation

    Uri Feige, Joe Killian, and Moni Naor. A minimal model for secure computation. InProceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 554–563, 1994. 28

    1994

  2. [2]

    Private simultaneous messages protocols with applications

    Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. InProceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 174–183. IEEE, 1997

    1997

  3. [3]

    The communication complexity of private simultaneous messages, revisited.Journal of Cryptology, 33(3):917–953, 2020

    Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited.Journal of Cryptology, 33(3):917–953, 2020

    2020

  4. [4]

    Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the complexity of decomposable randomized encodings, or: How friendly can a garbling- friendly prf be? In11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pages 86–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020

    2020

  5. [5]

    A note on the complexity of private simultaneous messages with many parties

    Marshall Ball and Tim Randolph. A note on the complexity of private simultaneous messages with many parties. In3rd Conference on Information-Theoretic Cryp- tography (ITC 2022), pages 7–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022

    2022

  6. [6]

    Communication complexity of private simultaneous quantum messages protocols.arXiv preprint arXiv:2105.07120, 2021

    Akinori Kawachi and Harumichi Nishimura. Communication complexity of private simultaneous quantum messages protocols.arXiv preprint arXiv:2105.07120, 2021

    arXiv 2021

  7. [7]

    Relating non-local quantum computation to information theoretic cryptog- raphy.Quantum, 8:1387, 2024

    Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptog- raphy.Quantum, 8:1387, 2024

    2024

  8. [8]

    Comparing classical and quantum conditional disclosure of secrets.arXiv preprint arXiv:2505.02939, 2025

    Uma Girish, Alex May, Leo Orshansky, and Chris Waddell. Comparing classical and quantum conditional disclosure of secrets.arXiv preprint arXiv:2505.02939, 2025

    arXiv 2025

  9. [9]

    Magic and communication complexity.arXiv preprint arXiv:2510.07246, 2025

    Uma Girish, Alex May, Natalie Parham, and Henry Yuen. Magic and communication complexity.arXiv preprint arXiv:2510.07246, 2025

    arXiv 2025

  10. [10]

    Communication complexity lower bounds by polynomials

    Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. InProceedings 16th Annual IEEE Conference on Computational Complexity, pages 120–130. IEEE, 2001

    2001

  11. [11]

    Instantaneous non-local computation of low T-depth quantum circuits.arXiv preprint arXiv:1511.02839, 2015

    Florian Speelman. Instantaneous non-local computation of low T-depth quantum circuits.arXiv preprint arXiv:1511.02839, 2015

    Pith/arXiv arXiv 2015

  12. [12]

    Quantum circuit complexity

    A Chi-Chih Yao. Quantum circuit complexity. InProceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352–361. IEEE, 1993

    1993

  13. [13]

    Bounded-width polynomial-size branching programs recognize exactly those languages in NC

    David A Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC. InProceedings of the eighteenth annual ACM sym- posium on Theory of computing, pages 1–5, 1986

    1986

  14. [14]

    Cambridge University Press, 2014

    Ryan O’Donnell.Analysis of boolean functions. Cambridge University Press, 2014

    2014

  15. [15]

    On the power of circuits with gates of low l1 norms.Theoretical computer science, 188(1-2):117–128, 1997

    Vince Grolmusz. On the power of circuits with gates of low l1 norms.Theoretical computer science, 188(1-2):117–128, 1997

    1997

  16. [16]

    Continuity of quantum conditional information

    Robert Alicki and Mark Fannes. Continuity of quantum conditional information. Journal of Physics A: Mathematical and General, 37(5):L55–L57, 2004

    2004

  17. [17]

    Andreas Winter. Tight uniform continuity bounds for quantum entropies: condi- tional entropy, relative entropy distance and energy constraints.Communications in Mathematical Physics, 347(1):291–313, 2016

    2016

  18. [18]

    Rank lower bounds on non-local quantum computation.arXiv preprint arXiv:2402.18647, 2024

    Vahid R Asadi, Eric Culf, and Alex May. Rank lower bounds on non-local quantum computation.arXiv preprint arXiv:2402.18647, 2024

    arXiv 2024

  19. [19]

    Protect- ing data privacy in private information retrieval schemes.Journal of Computer and System Sciences, 60(3):592–629, 2000

    Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protect- ing data privacy in private information retrieval schemes.Journal of Computer and System Sciences, 60(3):592–629, 2000. ISSN 0022-0000. doi:https://doi.org/10.1006/jcss.1999.1689. URLhttps://www.sciencedirect. com/science/article/pii/S0022000099916896

    work page doi:10.1006/jcss.1999.1689 2000

  20. [20]

    Conditional disclosure of secrets with quantum resources.Quantum, 9:1885, 2025

    Vahid R Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources.Quantum, 9:1885, 2025. 29

    2025

  21. [21]

    Quantum computations: algorithms and error correction.Russian Mathematical Surveys, 52(6):1191–1249, 1997

    A Yu Kitaev. Quantum computations: algorithms and error correction.Russian Mathematical Surveys, 52(6):1191–1249, 1997

    1997

  22. [22]

    Cambridge university press, 2010

    Michael A Nielsen and Isaac L Chuang.Quantum computation and quantum infor- mation. Cambridge university press, 2010

    2010

  23. [23]

    Catalyticz-rotations in constantt-depth.arXiv preprint arXiv:2506.15147, 2025

    Isaac H Kim. Catalyticz-rotations in constantt-depth.arXiv preprint arXiv:2506.15147, 2025

    arXiv 2025

  24. [24]

    Any Clifford+T circuit can be controlled with constant T-depth overhead.arXiv preprint arXiv:2512.24982, 2025

    Isaac H Kim and Tuomas Laakkonen. Any Clifford+T circuit can be controlled with constant T-depth overhead.arXiv preprint arXiv:2512.24982, 2025

    arXiv 2025

  25. [25]

    Post on X (Twitter).https://x.com/CraigGidney/status/ 1936285631359197210

    Craig Gidney. Post on X (Twitter).https://x.com/CraigGidney/status/ 1936285631359197210. Accessed: 2026-02-12

    2026

  26. [26]

    Quan- tum circuits for general multiqubit gates.Physical review letters, 93(13):130502, 2004

    Mikko Möttönen, Juha J Vartiainen, Ville Bergholm, and Martti M Salomaa. Quan- tum circuits for general multiqubit gates.Physical review letters, 93(13):130502, 2004

    2004

  27. [27]

    Thegarden- hose model

    HarryBuhrman, SergeFehr, ChristianSchaffner, andFlorianSpeelman. Thegarden- hose model. InProceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 145–158, 2013

    2013

  28. [28]

    New bounds for the garden-hose model

    Hartmut Klauck and Supartha Podder. New bounds for the garden-hose model. arXiv preprint arXiv:1412.4904, 2014

    Pith/arXiv arXiv 2014

  29. [29]

    Private vs

    Ilan Newman. Private vs. common random bits in communication complexity.In- formation processing letters, 39(2):67–71, 1991

    1991

  30. [30]

    Placing conditional disclosure of secrets in the communication complexity universe.Journal of Cryptology, 34(2): 11, 2021

    Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe.Journal of Cryptology, 34(2): 11, 2021. 30

    2021