論文の概要: New bounds on private simultaneous quantum message passing

• arxiv url: http://arxiv.org/abs/2606.12557v1
• Date: Wed, 10 Jun 2026 18:07:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-12 15:55:27.395917
• Title: New bounds on private simultaneous quantum message passing
• Title（参考訳）: プライベート同時量子メッセージパッシングの新しい境界
• Authors: Uma Girish, Alex May, Natalie Parham, Henry Yuen,
• Abstract要約: プライベート同時メッセージ(PSM)設定では、$k$プレーヤーは$x_iin0,1n$の入力を取得し、それぞれがレフェリーにメッセージを送信する。 量子環境では、PSMは非局所量子計算(NLQC)と関連している。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: プライベート同時メッセージ(PSM)設定では、$k$プレーヤーは$x_i\in\{0,1\}^n$の入力を取得し、その後、それぞれがレフェリーにメッセージを送り、$f(x_1,...,x_k)$を学ぶが、$(x_1,...,x_k)$に関する他の情報はない。 PSM設定はセキュアなマルチパーティ計算のための最小限のモデルとして導入され、ブール関数の複雑性と接続する。 量子環境では、PSMは非局所量子計算(NLQC)と関連している。 PSMの実装における通信コストと相関コストはいまだによく分かっていない。 ここでは、(量子)PSMモデルに新しい上界と下界を与える。 下限については、次のように示します。 1) ネチポルク測度は、完全正当性を持つ$k$プレーヤ量子PSMに必要な絡み合いを低くする。 これにより、明示函数の2次下界が導かれる。 2) 通信行列のランクは$f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness。 これは、以前は知られていなかった古典的な PSM 上の下界が不完全であることを意味する。 量子通信と共有絡み合いを許容する場合、これらはプライバシ条件を利用する量子PSM上の最初の下位境界である。 上界について、以下に示す。 1)$s$を量子回路コンピューティングのサイズとして$f$,$d_f$を回路深さとし、$k$をプレイヤー数、$n$を各プレイヤーが受信したビット数とし、$ε$を正当性パラメータとし、$\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)$とする。 2) フーリエ1ノルムの平方は$f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$である。 最初の上限を証明する際に、NLQCの既存の$T$-depthベースのテクニックを$$$から$k\geq 2$partyに一般化し、クリフォード層が小さな光円錐を持つように制限されている場合を考える。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• A slightly improved upper bound for quantum statistical zero-knowledge [11.384500557173867]
  複雑性クラスであるQuantum Statistical Zero-Knowledge(mathsfQSZK$)は、最もよく知られた上限である$mathsfQIP(2) cap textco-mathsfQIP(2)$を持つ。 我々はこれを$mathsfQIP(2) cap textco-mathsfQIP(2)$に改善する。 我々の主な手法は、量子線型空間で実装可能なホレボ・ヘルストロム測度複雑性とウルマン変換のアルゴリズム版である。
  論文  参考訳（メタデータ） (2025-12-12T14:33:20Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Rank lower bounds on non-local quantum computation [0.0]
  非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。 NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
  論文  参考訳（メタデータ） (2024-02-28T19:00:09Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  我々は,不一致の最小化と(量子)通信複雑性の新たな関連性を開発する。 対称$n times n$$A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ に対し、pm 1n において $sum_i leq n x_i A_i$ の最大固有値が最大となる符号 $x が存在することを示す。
  論文  参考訳（メタデータ） (2021-10-19T16:51:11Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。