論文の概要: Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- arxiv url: http://arxiv.org/abs/2609.40116v1
- Date: Wed, 30 Sep 2026 16:42:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:28.097867
- Title: Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- Title（参考訳）: 通信複雑度における置換不変関数の量子アドバンテージ
- Abstract要約: Rmathrmpub(f)=O_q(Qast(f)2log n)$。
また、対数係数までのパラメータによって量子通信の複雑さを特徴づける。
- 参考スコア（独自算出の注目度）: 3.388546694531524
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study how symmetry constrains quantum advantage in two-party communication complexity. For partial functions over any fixed alphabet of size $q$ that are invariant under simultaneous coordinate permutations, we prove that public-coin randomized and entanglement-assisted quantum communication complexities satisfy $R^{\mathrm{pub}}(f)=O_q(Q^{\ast}(f)^2\log n)$, where $n$ is the input length. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. These results extend the binary-alphabet result of Guan et al. and improve its logarithmic overhead. Input-length dependence is necessary: for every fixed $\varepsilon\in(0,1)$, binary permutation-invariant partial functions can have quantum complexity $O_\varepsilon(\log\log n)$ and randomized complexity $Ω_\varepsilon((\log n)^{1-\varepsilon})$. Growing alphabets and graph symmetries permit exponential separations. For every fixed $\varepsilon\in(0,1)$, we construct permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum complexity $O_\varepsilon(\log n)$ and randomized complexity $Ω_\varepsilon(n^{1-\varepsilon})$. We also construct graph-invariant partial functions on $v$-vertex graphs with quantum complexity $O_\varepsilon(\log v)$ and randomized complexity $Ω_\varepsilon(v^{2-\varepsilon})$. All separation protocols use neither prior entanglement nor shared randomness.
- Abstract（参考訳）: 本研究では,2次元通信の複雑性において,対称性が量子優位性にどのように制約するかを考察する。
座標の同時置換の下で不変となる$q$の任意の固定アルファベット上の部分関数に対して、n$ が入力長であるような$R^{\mathrm{pub}}(f)=O_q(Q^{\ast}(f)^2\log n)$を満たす公開コインランダム化およびエンタングルメント支援量子通信複雑性が成立することを証明する。
また、対数係数までの組合せパラメータによって量子通信の複雑さを特徴づける。
これらの結果は、Guan et al のバイナリ-アルファベット結果を拡張し、対数的オーバーヘッドを改善する。
すべての固定された $\varepsilon\in(0,1)$ に対して、二項置換不変部分函数は量子複雑性を持つことができる $O_\varepsilon(\log\log n)$ およびランダム化複雑性を持つ $Ω_\varepsilon((\log n)^{1-\varepsilon})$ である。
成長するアルファベットとグラフ対称性は指数的な分離を可能にする。
固定されたすべての$\varepsilon\in(0,1)$に対して、量子複雑性$O_\varepsilon(\log n)$とランダム化複雑性$Ω_\varepsilon(n^{1-\varepsilon})$で、長さ-$n$文字列上の置換不変部分関数を構成する。
また、量子複雑性 $O_\varepsilon(\log v)$ とランダム化複雑性 $Ω_\varepsilon(v^{2-\varepsilon})$ のグラフ不変部分函数も構成する。
全ての分離プロトコルは、事前の絡み合いや共有ランダム性を使用しない。
関連論文リスト
- Optimal learning of covariant quantum states and channels [0.0]
我々は、既知の対称性を持つ量子状態やチャネルに対する集合トモグラフィープロトコルを提供する。
我々は, 最適な純状態推定のために, 林測度を近似する効率的な量子回路を構築した。
論文 参考訳（メタデータ） (2026-09-30T08:30:12Z) - Learning Sparse Quantum States [0.8122270502556375]
我々は、$n$-qubit $k$-sparse純量子状態を学ぶための最初の近似アルゴリズムを与える。
我々は、$tildeO(k/varepsilon)$状態のコピーと$tildeO(kn/varepsilon)$時間を使って、高い確率で少なくとも1-varepsilon$を得る。
例えば、ほぼ最適な$tildeO(kr/varepsilon)$サンプル複雑性を持つアルゴリズムも得られ、$k$-sparse rank-$rを学習する。
論文 参考訳（メタデータ） (2026-09-10T21:28:21Z) - On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。
格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。
$d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
論文 参考訳（メタデータ） (2026-04-27T10:23:24Z) - Unitary designs in nearly optimal depth [40.28216388589026]
回路深さ$O(log k log log n k / varepsilon)$。
深さは既知のすべての結果に対して指数関数的に改善され、すべてのパラメータは$n$, $k$, $varepsilon$である。
また,多数のクエリをランダムなユニタリーに格納する量子実験において,エラーをバウンディングするための新しい分析フレームワークを開発した。
論文 参考訳（メタデータ） (2025-07-08T17:48:33Z) - Quantum Complexity of Permutations [0.0]
論理ゲートとして$sigma, tau, tau-1$を用いて, 置換の量子複雑性について検討した。
我々は、$S_n$ のほとんどすべての置換が、$nrightarrow infty$ のときの2次量子複雑性を下限とすることを示した。
論文 参考訳（メタデータ） (2022-07-21T23:18:54Z) - 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) - Partially Concatenated Calderbank-Shor-Steane Codes Achieving the
Quantum Gilbert-Varshamov Bound Asymptotically [36.685393265844986]
我々は,量子-Omega-Varshamovを有界に達成する量子誤り訂正符号の新たなファミリを構築する。
$mathscrQ$は$O(N)$とdeep $O(sqrtN)$の回路で非常に効率的に符号化できる。
$mathscrQ$は$O(sqrtN)$timeで並列に復号することもできる。
論文 参考訳（メタデータ） (2021-07-12T03:27:30Z) - 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) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳（メタデータ） (2020-06-21T06:57:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。