論文の概要: On the Limits of Quantum Multiparty Simultaneous Communication
- arxiv url: http://arxiv.org/abs/2609.10289v1
- Date: Wed, 09 Sep 2026 15:07:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:09.073811
- Title: On the Limits of Quantum Multiparty Simultaneous Communication
- Title（参考訳）: 量子多人数同時通信の限界について
- Abstract要約: 我々はtextscIndex Coordination の自然な $k$-party 一般化を通じて,多元的指数分離を確立する。
量子重ね合わせは、公共のランダム性によって得られる調整を効率的にシミュレートできないことを示し、この分離を任意の$k$に拡張する。
- 参考スコア（独自算出の注目度）: 1.7205106391379026
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Simultaneous Message Passing (SMP) model provides a fundamental framework for comparing classical and quantum communication. For two players, Gavinsky et al. (STOC 2006) established a separation underlying the incomparability of shared randomness and quantum communication: \textsc{Index Coordination} needs $O(\log n)$ public-coin bits but $Ω(n^{1/3})$ bounded-error qubits. In this work, we establish a multiparty exponential separation through $\operatorname{IC}_{k,n}$, a natural $k$-party generalization of \textsc{Index Coordination}. Public-coin protocols solve it unambiguously with maximum message length $O(\log n)$ bits. In contrast, quantum SMP protocols without shared entanglement or public coins require maximum message length $Ω(n^{1-1/k})$ qubits in the unambiguous regime and $Ω(n^{(k-1)/(k+1)})$ qubits in the bounded-error regime. A classical private-coin protocol matches the unambiguous bound, so quantum communication provides no asymptotic advantage over private randomness in this regime. For fixed error parameters, all constants are independent of $k$, establishing the exponential separation for every integer-valued function $k=k(n)\ge2$, without restricting its growth. Both quantum lower bounds become $Ω(n)$ when $k\ge c\log n$ for any fixed $c>0$, matching the full-input protocol and yielding tight linear complexity in both regimes. Our results demonstrate that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$. To bound success probabilities for multiparty product states, we prove an exact factorization theorem for unambiguous quantum state identification, which may be of independent mathematical interest.
- Abstract（参考訳）: 同時メッセージパッシング(SMP)モデルは、古典的および量子的通信を比較するための基本的なフレームワークを提供する。
2人のプレイヤーに対して、Gavinsky et al (STOC 2006) は共有ランダム性と量子通信の非互換性に基づく分離を確立した: \textsc{Index Coordination} は$O(\log n)$ public-coin bits but $Ω(n^{1/3})$ bounded-error qubits を必要とする。
この研究では、$\operatorname{IC}_{k,n}$, a natural $k$-party generalization of \textsc{Index Coordination} を通じて、多元的指数分離を確立する。
公開コインプロトコルは、最大メッセージ長$O(\log n)$ bitsで明らかにそれを解決している。
対照的に、共有エンタングルメントや公開コインを持たない量子SMPプロトコルは、あいまいな状態の最大メッセージ長$Ω(n^{1-1/k})$ qubits、境界エラー状態の$Ω(n^{(k-1)/(k+1)}$ qubitsを必要とする。
古典的なプライベートコインプロトコルは、あいまいな境界と一致するため、量子通信は、この状態におけるプライベートランダム性よりも漸近的な優位性を提供しない。
固定誤差パラメータに対しては、全ての定数は$k$とは独立であり、その成長を制限することなく全ての整数値関数$k=k(n)\ge2$に対する指数的分離を確立する。
どちらの量子下界も$Ω(n)$となる:$k\ge c\log n$ for any fixed $c>0$, matching the full-input protocol and yield tight linear complexity in both regimes。
この結果は、量子重ね合わせが公共のランダム性によって得られる調整を効率的にシミュレートできないことを示し、この分離を任意の$k$に拡張する。
多党積状態の成功確率を有界化するために、不明瞭な量子状態同定のための正確な分解定理を証明し、これは独立した数学的関心を持つかもしれない。
関連論文リスト
- Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication [0.0]
fn$ のインスタンスあたりの最適な最悪の通信は [ Dparallel(f)=log|mathrmRow(f)|+log|mathrmCol(f)| に収束する。
また、同じしきい値が指数的強い逆を支配していることも証明する。
論文 参考訳（メタデータ） (2026-09-13T16:55:55Z) - Distributed Quantum Property Testing with Quantum Carrier Pigeons [2.764897610820182]
通信制約下での分散量子推論のためのフレームワークを提案する。
量子状態認証の基本的な問題に焦点をあてる。
分散状態認証のコピー複雑性は$(fracd22n_q 2n_c/22)$であることを示す。
論文 参考訳（メタデータ） (2026-09-08T15:09:45Z) - Quantum memory advantage for quantum process tomography [2.956729394666618]
ブラックボックスアクセスから未知の量子チャネルを学習するタスクである量子プロセストモグラフィは、量子情報の中心的な問題である。
量子メモリのないプロトコルが実験に適応しても、量子メモリはクエリ・複雑性に有利であることを示す。
この結果から,量子プロセストモグラフィーと量子メモリとの厳密な学習分離が確立された。
論文 参考訳（メタデータ） (2026-07-15T06:09:08Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Trade-offs between Entanglement and Communication [5.88864611435337]
我々は,$tildeTheta(k5 log3 n)$ qubits of tanglementの量子同時プロトコルが,$O(k)$ qubits of tanglementの2方向ランダム化プロトコルよりも指数関数的に優れていることを示す。
私たちの研究以前には、リレーショナルな分離のみが知られていました。
論文 参考訳（メタデータ） (2023-06-02T01:49:39Z) - Communication complexity of entanglement assisted multi-party
computation [11.820804392113294]
プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。
量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。
これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
論文 参考訳（メタデータ） (2023-05-08T03:10:08Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Communication Cost of Quantum Processes [49.281159740373326]
分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。
重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。
クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
論文 参考訳（メタデータ） (2020-02-17T08:51:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。