論文の概要: 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})$を示す。
関連論文リスト
- 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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [6.236743421605786]
本稿では,量子CONGESTモデルにおけるグラフの重み付き直径と半径の計算の複雑さについて検討する。
我々は、$widetilde Oleft(minleftn9/10D3/10,nrightright)$という量子アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-06-06T17:43:27Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳(メタデータ) (2022-04-06T03:04:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。