論文の概要: Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
- arxiv url: http://arxiv.org/abs/1804.02917v3
- Date: Thu, 11 Jan 2024 18:32:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-13 04:35:50.144761
- Title: Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
- Title（参考訳）: 密集ネットワークにおける直径のサブリニア時間量子計算
- Authors: Fran\c{c}ois Le Gall and Fr\'ed\'eric Magniez
- Abstract要約: 直径の計算は分散計算における最も中心的な問題の1つである。
正確な直径計算のための$tilde O(sqrtnD)$-round量子分散アルゴリズムを示し、$D$は直径を表す。
これは、CONGESTモデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The computation of the diameter is one of the most central problems in
distributed computation. In the standard CONGEST model, in which two adjacent
nodes can exchange $O(\log n)$ bits per round (here $n$ denotes the number of
nodes of the network), it is known that exact computation of the diameter
requires $\tilde \Omega(n)$ rounds, even in networks with constant diameter. In
this paper we investigate quantum distributed algorithms for this problem in
the quantum CONGEST model, where two adjacent nodes can exchange $O(\log n)$
quantum bits per round. Our main result is a $\tilde O(\sqrt{nD})$-round
quantum distributed algorithm for exact diameter computation, where $D$ denotes
the diameter. This shows a separation between the computational power of
quantum and classical algorithms in the CONGEST model. We also show an
unconditional lower bound $\tilde \Omega(\sqrt{n})$ on the round complexity of
any quantum algorithm computing the diameter, and furthermore show a tight
lower bound $\tilde \Omega(\sqrt{nD})$ for any distributed quantum algorithm in
which each node can use only $\textrm{poly}(\log n)$ quantum bits of memory.
- Abstract（参考訳）: 直径の計算は分散計算における最も中心的な問題の1つである。
2つの隣接ノードが1ラウンド当たり$o(\log n)$bit(ここで$n$はネットワークのノード数を表す)を交換できる標準連続モデルでは、直径の正確な計算には、一定の直径のネットワークでさえ$\tilde \omega(n)$ roundが必要であることが知られている。
本稿では,2つの隣接ノードが1ラウンド当たり$o(\log n)$量子ビットを交換できる量子集束モデルにおいて,この問題に対する量子分散アルゴリズムを検討する。
我々の主な成果は、正確な直径計算のための$\tilde O(\sqrt{nD})$ラウンド量子分散アルゴリズムであり、$D$は直径を表す。
これは、凝縮モデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
さらに、各ノードが$\textrm{poly}(\log n)$量子ビットのメモリしか使用できない任意の分散量子アルゴリズムに対して、下限の$\tilde \omega(\sqrt{nd})$という条件のない下限の$\tilde \omega(\sqrt{n})$を示し、さらに下限の$\tilde \omega(\sqrt{nd})$を示す。
関連論文リスト
- Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
同一の$k$密度行列のパワーのトレースを推定することは、多くのアプリケーションにとって重要なサブルーチンである。
The Newton-Girard method, we developed a algorithm that only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates。
論文 参考訳（メタデータ） (2024-08-01T06:23:52Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - 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) - Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [6.236743421605786]
本稿では,量子CONGESTモデルにおけるグラフの重み付き直径と半径の計算の複雑さについて検討する。
我々は、$widetilde Oleft(minleftn9/10D3/10,nrightright)$という量子アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-06-06T17:43:27Z) - A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
量子クエリアルゴリズムを量子CONGESTで実装するための一般的なフレームワークを提供する。
分散Deutsch-Jozsa問題に対するプロトコルを一般化する。
また、サイクル検出と計算の問題を量子スピードアップする。
論文 参考訳（メタデータ） (2022-02-22T15:18:39Z) - On quantum algorithms for the Schr\"odinger equation in the
semi-classical regime [27.175719898694073]
半古典的状態におけるシュル・オーディンガーの方程式を考える。
このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
論文 参考訳（メタデータ） (2021-12-25T20:01:54Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳（メタデータ） (2021-08-13T09:47:11Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Low-depth Quantum State Preparation [3.540171881768714]
量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。
ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。
我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
論文 参考訳（メタデータ） (2021-02-15T13:11:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。