論文の概要: Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- arxiv url: http://arxiv.org/abs/2609.40116v2
- Date: Sun, 04 Oct 2026 11:56:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 04:43:28.477099
- Title: Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- Title（参考訳）: 通信複雑度における置換不変関数の量子アドバンテージ
- Abstract要約: 本研究では,対称性が双方向通信の複雑性において量子優位性にどのように影響するかを考察する。
すべての固定された $varepsilonin(0,1)$ に対して、量子通信複雑性を持つ二項置換不変部分函数が存在する。
- 参考スコア（独自算出の注目度）: 3.388546694531524
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneous coordinate permutations, we prove $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$ denotes public-coin randomized communication complexity, and $Q^{\ast}$ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed $\varepsilon\in(0,1)$, there are binary permutation-invariant partial functions with quantum communication complexity $O_\varepsilon(\log\log n)$ and randomized communication complexity $Ω_\varepsilon((\log n)^{1-\varepsilon})$. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed $\varepsilon\in(0,1)$, we exhibit permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum communication complexity $O_\varepsilon(\log n)$ and randomized communication complexity $Ω_\varepsilon(n^{1-\varepsilon})$. For graph-invariant partial functions on $v$-vertex graphs, we obtain $O_\varepsilon(\log v)$ quantum versus $Ω_\varepsilon(v^{2-\varepsilon})$ randomized communication complexity. All separation protocols require no prior entanglement.
- Abstract（参考訳）: 本研究では,対称性が双方向通信の複雑性において量子優位性にどのように影響するかを考察する。
任意の部分関数 $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneously coordinate permutations, yet $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$は公開結合ランダム化通信複雑性を示し、$Q^{\ast}$は共役型量子通信複雑性を示す。
この境界は集合の不整合に対して厳密であり、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$-シンボルアルファベット上の長さ-$n$文字列上の置換不変部分関数を示す。
v$-頂点グラフ上のグラフ不変部分函数に対して、$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。