論文の概要: Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model

• arxiv url: http://arxiv.org/abs/2212.02768v1
• Date: Tue, 6 Dec 2022 05:39:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-09 17:50:26.916929
• Title: Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model
• Title（参考訳）: 量子局所モデルにおける環の3色化のための非自明な下界
• Authors: Fran\c{c}ois Le Gall and Ansis Rosmanis
• Abstract要約: 本研究では,一対一の通信のみを行うリングをカラー化するための分散アルゴリズムについて検討する。 適切な$$3のカラー化を出力する量子シングルラウンドワンウェイ分散アルゴリズムの確率は、指数関数的に$n$である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size. It is know that, classically, the round complexity of 3-coloring an $n$-node ring is $\Theta(\log^*\!n)$. In the case where communication is quantum, only trivial bounds were known: at least some communication must take place. We study distributed algorithms for coloring the ring that perform only a single round of one-way communication. Classically, such limited communication is already known to reduce the number of required colors from $\Theta(n)$, when there is no communication, to $\Theta(\log n)$. In this work, we show that the probability of any quantum single-round one-way distributed algorithm to output a proper $3$-coloring is exponentially small in $n$.
• Abstract（参考訳）: 分散コンピューティングのLOCALモデルを考えると、各ノードは1ラウンドの通信で各ノードに任意の大きさのメッセージを送ることができる。 古典的には、$n$-ノード環を3色する丸い複雑さは$\theta(\log^*\! n) である。 通信が量子である場合、単純な境界のみが知られており、少なくともいくつかの通信を行う必要がある。 単方向通信のラウンドのみを実行するリングの色付けのための分散アルゴリズムについて検討した。 古典的には、このような限定的な通信は必要な色数を$\theta(n)$ から$\theta(\log n)$ に減らすことが既に知られている。 本研究では,任意の量子一周一方向分散アルゴリズムが適切な3ドルカラー化を出力する確率は指数関数的にn$で小さいことを示す。

関連論文リスト

• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。 これらの問題は、分散量子の優位性を認めないことを示している。
  論文  参考訳（メタデータ） (2023-07-18T17:17:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• 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)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Communication memento: Memoryless communication complexity [5.88864611435337]
  我々は、メモリレス通信モデルにおいて、計算関数の通信複雑性を$F:0,1ntimes 0,1n rightarrow 0,1$で調べる。
  論文  参考訳（メタデータ） (2020-05-08T14:33:25Z)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  一般減衰器$Phi_lambda, sigma$はボゾン量子チャネルであり、入力と固定された環境状態を組み合わせることで作用する。 任意の$lambda>0$に対して、適切な単一モード状態 $sigma(lambda)$が存在することを示す。 我々の結果は、チャネルの入力でエネルギー制約を固定しても成り立ち、任意に低い透過率の極限でも一定の速度で量子通信が可能であることを示唆している。
  論文  参考訳（メタデータ） (2020-03-19T16:50:11Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。 $mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。 我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
  論文  参考訳（メタデータ） (2020-01-09T02:48:43Z)
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
  直径の計算は分散計算における最も中心的な問題の1つである。 正確な直径計算のための$tilde O(sqrtnD)$-round量子分散アルゴリズムを示し、$D$は直径を表す。 これは、CONGESTモデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
  論文  参考訳（メタデータ） (2018-04-09T11:24:24Z)

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

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