論文の概要: No distributed quantum advantage for approximate graph coloring
- arxiv url: http://arxiv.org/abs/2307.09444v2
- Date: Tue, 14 Nov 2023 16:37:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 18:38:22.007178
- Title: No distributed quantum advantage for approximate graph coloring
- Title（参考訳）: 近似グラフ彩色における分散量子優位性
- Authors: Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn,
Fran\c{c}ois Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou,
Gustav Schmid, Jukka Suomela
- Abstract要約: 分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。
これらの問題は、分散量子の優位性を認めないことを示している。
- 参考スコア（独自算出の注目度）: 2.733913397827945
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give an almost complete characterization of the hardness of $c$-coloring
$\chi$-chromatic graphs with distributed algorithms, for a wide range of models
of distributed computing. In particular, we show that these problems do not
admit any distributed quantum advantage. To do that: 1) We give a new
distributed algorithm that finds a $c$-coloring in $\chi$-chromatic graphs in
$\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ rounds, with $\alpha =
\bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$. 2) We prove that any distributed
algorithm for this problem requires $\Omega(n^{\frac{1}{\alpha}})$ rounds.
Our upper bound holds in the classical, deterministic LOCAL model, while the
near-matching lower bound holds in the non-signaling model. This model,
introduced by Arfaoui and Fraigniaud in 2014, captures all models of
distributed graph algorithms that obey physical causality; this includes not
only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL,
even with a pre-shared quantum state.
We also show that similar arguments can be used to prove that, e.g.,
3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even
for the non-signaling model, and in particular do not admit any quantum
advantage. Our lower-bound arguments are purely graph-theoretic at heart; no
background on quantum information theory is needed to establish the proofs.
- Abstract（参考訳）: 分散コンピューティングの幅広いモデルに対して、分散アルゴリズムを用いた$c$-coloring $\chi$-chromatic graphの難しさについて、ほぼ完全な特徴付けを行う。
特に、これらの問題は分散量子の優位性を認めないことを示す。
それを行うには:
1)$\tilde{\mathcal{o}}(n^{\frac{1}{\alpha}})$ rounds の$\chi$-chromatic graphs で$c$-coloringを見つける新しい分散アルゴリズムを与え、$\alpha = \bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$ を付与する。
2) この問題の分散アルゴリズムには$\Omega(n^{\frac{1}{\alpha}})$ roundsが必要であることを証明している。
我々の上界は古典的決定論的局所モデルであり、ほぼ一致する下界は非符号モデルである。
2014年にArfaouiとFraigniaudによって導入されたこのモデルは、物理的因果性に従う分散グラフアルゴリズムのすべてのモデルをキャプチャする。
また、同様の議論は、例えば、3色2次元グリッドや$c$-coloringツリーが、非符号モデルにおいても難しい問題であり、特に量子的な利点を認めないことを示すためにも利用できる。
我々の下界の議論は純粋にグラフ理論であり、証明を確立するには量子情報理論の背景は必要ない。
関連論文リスト
- Predicting quantum channels over general product distributions [19.09244195034539]
我々は、分布$D$からサンプリングされたほとんどの$rho$に対して、写像の始点* rho mapto mathrmTr(O E[rho]) endequation* を小さな誤差の範囲内で学習する。
自明な指数的下界が存在する場合の「古典的」ではないことを前提として、基本的に任意の積分布に対して正確な予測を行う新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-09-05T16:39:13Z) - Online Locality Meets Distributed Quantum Computing [2.3821076274208552]
分散コンピューティングの古典的なLOCALモデルの拡張について、3行の研究が最近行われた。
局所チェック可能なラベリング問題(LCL)に対するこれらのモデルの機能と制限に関する新しい結果が証明された。
我々の研究は、分散環境での利点の限界を示唆しており、より厳密な境界を示すための新たな障壁も示しています。
論文 参考訳（メタデータ） (2024-03-04T10:03:54Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Improved spectral gaps for random quantum circuits: large local
dimensions and all-to-all interactions [0.0]
我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。
2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
論文 参考訳（メタデータ） (2020-12-09T19:00:50Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。