論文の概要: Magic and communication complexity

• arxiv url: http://arxiv.org/abs/2510.07246v1
• Date: Wed, 08 Oct 2025 17:14:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.65662
• Title: Magic and communication complexity
• Title（参考訳）: マジックとコミュニケーションの複雑さ
• Authors: Uma Girish, Alex May, Natalie Parham, Henry Yuen,
• Abstract要約: 量子回路におけるマジックと通信複雑性の間の新しい接続を確立する。 低魔法で計算可能な関数は通信コストが低いことを示す。
• 参考スコア（独自算出の注目度）: 0.6533091401094101
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communication cost. Our first result shows that the $\mathsf{D}\|$ (deterministic simultaneous message passing) cost of a Boolean function $f$ is at most the number of single-qubit magic gates in a quantum circuit computing $f$ with any quantum advice state. If we allow mid-circuit measurements and adaptive circuits, we obtain an upper bound on the two-way communication complexity of $f$ in terms of the magic + measurement cost of the circuit for $f$. As an application, we obtain magic-count lower bounds of $\Omega(n)$ for the $n$-qubit generalized Toffoli gate as well as the $n$-qubit quantum multiplexer. Our second result gives a general method to transform $\mathsf{Q}\|^*$ protocols (simultaneous quantum messages with shared entanglement) into $\mathsf{R}\|^*$ protocols (simultaneous classical messages with shared entanglement) which incurs only a polynomial blowup in the communication and entanglement complexity, provided the referee's action in the $\mathsf{Q}\|^*$ protocol is implementable in constant $T$-depth. The resulting $\mathsf{R}\|^*$ protocols satisfy strong privacy constraints and are $\mathsf{PSM}^*$ protocols (private simultaneous message passing with shared entanglement), where the referee learns almost nothing about the inputs other than the function value. As an application, we demonstrate $n$-bit partial Boolean functions whose $\mathsf{R}\|^*$ complexity is $\mathrm{polylog}(n)$ and whose $\mathsf{R}$ (interactive randomized) complexity is $n^{\Omega(1)}$, establishing the first exponential separations between $\mathsf{R}\|^*$ and $\mathsf{R}$ for Boolean functions.
• Abstract（参考訳）: 量子回路におけるマジックと通信複雑性の間の新しい接続を確立する。 特に,低魔法で計算可能な関数は通信コストが低いことを示す。 我々の最初の結果は、ブール関数$f$の$\mathsf{D}\|$(決定論的同時メッセージパッシング)コストは、量子回路計算の$f$における1量子ビットマジックゲートの最大数であることを示している。 中間回路の測定と適応回路を許すと、回路のマジック+測定コストで$f$の双方向通信複雑性の上限を$f$とする。 応用として、$n$-qubit 一般化トフォリゲートと$n$-qubit 量子多重化器に対して、マジックカウント下界$\Omega(n)$を得る。 2つ目の結果は、$\mathsf{Q}\|^*$プロトコル(共有絡み付き同時量子メッセージ)を$\mathsf{R}\|^*$プロトコル(共有絡み付き同時量子メッセージ)に変換する一般的な方法であり、$\mathsf{Q}\|^*$プロトコルは定数$T$-depthで実装可能である。 結果として生じる$\mathsf{R}\|^*$プロトコルは、強いプライバシー制約を満たし、$\mathsf{PSM}^*$プロトコル(共有絡み付き同時メッセージパッシング)である。 アプリケーションとしては、$\mathsf{R}\|^*$複雑さが$\mathrm{polylog}(n)$で、$\mathsf{R}$(対話的ランダム化)複雑性が$n^{\Omega(1)}$で、$\mathsf{R}\|^*$と$\mathsf{R}$の間の最初の指数的分離を確立する。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。 私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
  論文  参考訳（メタデータ） (2023-11-22T20:27:05Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)
• A direct product theorem for quantum communication complexity with applications to device-independent cryptography [6.891238879512672]
  我々は、$l$プレーヤの入力集合にまたがる分布である$p$に対して、任意の絡み合い支援量子通信プロトコルの成功確率は、$n$で指数関数的に低下することを示した。 また、デバイスが情報を漏らさないという仮定なしに、デバイス非依存(DI)量子暗号が可能であることも示している。
  論文  参考訳（メタデータ） (2021-06-08T12:52:10Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• 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)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

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

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