New bounds on private simultaneous quantum message passing

• URL: http://arxiv.org/abs/2606.12557v1
• Date: Wed, 10 Jun 2026 18:07:16 GMT
• Title: New bounds on private simultaneous quantum message passing
• Abstract summary: In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_iin0,1n$ and then each send messages to a referee.<n>In the quantum setting, PSM has been related to non-local quantum computation (NLQC)
• Score: 0.6533091401094101
• License: http://creativecommons.org/licenses/by/4.0/
• 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č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 $ε$ a correctness parameter, we obtain $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)$. 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.

Related papers

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• A slightly improved upper bound for quantum statistical zero-knowledge [11.384500557173867]
  The complexity class Quantum Statistical Zero-Knowledge ($mathsfQSZK$) has the best known upper bound $mathsfQIP(2) cap textco-mathsfQIP(2)$.<n>We improve this to $mathsfQIP(2) cap textco-mathsfQIP(2)$ with a quantum linear-space honest prover.<n>Our main techniques are an algorithmic version of the Holevo-Helstrom measurement complexity and the Uhlmann transform, both implementable in quantum linear space
  arXiv  Detail & Related papers  (2025-12-12T14:33:20Z)
• Magic and communication complexity [0.6533091401094101]
  We establish novel connections between magic in quantum circuits and communication complexity.<n>We show that functions computable with low magic have low communication cost.
  arXiv  Detail & Related papers  (2025-10-08T17:14:25Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Rank lower bounds on non-local quantum computation [0.0]
  A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single round of communication and shared entanglement.<n>We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification.
  arXiv  Detail & Related papers  (2024-02-28T19:00:09Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  We develop a novel connection between discrepancy minimization and (quantum) communication complexity. We show that for every collection of symmetric $n times n$ $A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ there exist signs $x in pm 1n such that the maximum eigenvalue of $sum_i leq n x_i A_i$ is at most
  arXiv  Detail & Related papers  (2021-10-19T16:51:11Z)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  We study the advantages of quantum communication and prior entanglement of the private simultaneous quantum messages model. We show that the privacy condition inevitably increases the communication cost in the two-party PSQM model. We also show an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings.
  arXiv  Detail & Related papers  (2021-05-15T03:08:01Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.