論文の概要: Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum
CONGEST Model
- arxiv url: http://arxiv.org/abs/2206.02766v1
- Date: Mon, 6 Jun 2022 17:42:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 09:22:26.474927
- Title: Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum
CONGEST Model
- Title(参考訳): 量子ConGESTモデルにおける偏心性と全ペア短経路の複雑さ
- Authors: ChengSheng Wang, Xudong Wu and Penghui Yao
- Abstract要約: 本稿では、量子CONGESTモデルにおけるヘテロジスタンスパラメータについて検討し、偏心性およびAPSPのほぼ線形な下界を確立する。
その結果、これらの2つの問題に対して量子スピードアップが存在しないことが示唆された。
- 参考スコア(独自算出の注目度): 5.279257531335345
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computing the distance parameters of a network, including the diameter,
radius, eccentricities and the all-pairs shortest paths (APSP) is a central
problem in distributed computing. This paper investigates he dtistance
parameters in the quantum CONGEST models and establishes almost linear lower
bounds on eccentricities and APSP, which match the classical upper bounds. Our
results imply that there is not quantum speedup for these two problems. In
contrast with the diameter and radius, exchanging quantum messages is able to
save the communication when the networks have low diameters [Le Gall and
Magniez, PODC 2018]. We obtain the lower bounds via a reduction from the
two-way quantum communication complexity of the set intersection [Razborov,
Izvestiya Mathematics 2003].
- Abstract(参考訳): 直径、半径、偏心、全パイア短路(apsp)を含むネットワークの距離パラメータを計算することは、分散コンピューティングにおける中心的な問題である。
本稿では,量子CONGESTモデルにおけるヘテロジスタンスパラメータを調査し,古典的な上界と一致する偏心性およびAPSPのほぼ線形下界を確立する。
私たちの結果は、この2つの問題に量子スピードアップはないことを示している。
直径と半径とは対照的に、量子メッセージの交換は、ネットワークの直径が小さいときに通信を節約できる(Le Gall and Magniez, PODC 2018]。
我々は、集合交叉の双方向量子通信複雑性(Razborov, Izvestiya Mathematics 2003)からの還元により下界を得る。
関連論文リスト
- Efficient Quantum Circuits based on the Quantum Natural Gradient [0.0]
任意の絡み合った量子状態の効率的な準備は、量子計算に不可欠である。
対称保存型量子近似最適化(SCom-QAOA)回路を提案する。
提案手法は、変分量子アルゴリズムで利用できる初期状態の集合を拡大し、量子シミュレータにおける非平衡現象の研究範囲を広げる。
論文 参考訳(メタデータ) (2023-10-16T16:08:57Z) - Instantaneous nonlocal quantum computation and circuit depth reduction [7.148511452018054]
2パーティの量子計算は、2部構成の入力と出力を持つ計算プロセスであり、初期共有の絡み合いが存在する。
まず,ガーデニング・ホース・ガジェットとして知られる,単純化されたサブプロデューサは,絡み合いのコストを著しく低減できないことを示す。
第2部では、クリフォードゲートとTゲートの層からなる任意のユニタリ回路が、元の回路のT深さに比例した深さの測定値を持つ回路を用いて実装可能であることを示す。
論文 参考訳(メタデータ) (2023-06-15T17:57:50Z) - Quantum Broadcast Channel Simulation via Multipartite Convex Splitting [25.103483428654375]
量子放送チャネルシミュレーションの通信コストは、効率よく計算可能なシングルレター式によって特徴づけられる。
マルチパート量子状態分割のための新しいワンショット達成性結果を示す。
論文 参考訳(メタデータ) (2023-04-24T12:48:17Z) - High-fidelity parallel entangling gates on a neutral atom quantum
computer [41.74498230885008]
最大60個の原子に99.5%の忠実度を持つ2量子エンタングリングゲートの実現を報告した。
これらの進歩は、量子アルゴリズム、誤り訂正回路、デジタルシミュレーションの大規模実装の基礎となった。
論文 参考訳(メタデータ) (2023-04-11T18:00:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳(メタデータ) (2022-11-01T07:52:47Z) - Adiabatic quantum computing with parameterized quantum circuits [0.0]
断熱量子コンピューティング(Adiabatic quantum computing)は、量子コンピューティングの普遍的なモデルである。
本稿では,短期機器の限界を緩和する新しい手法を提案する。
提案アルゴリズムと変分量子固有解器を2つの古典最適化問題で比較する。
論文 参考訳(メタデータ) (2022-06-09T09:31:57Z) - Cavity-enhanced quantum network nodes [0.0]
将来の量子ネットワークは、量子チャネルで接続された量子プロセッサによって構成される。
光共振器が量子ネットワークノードをどのように促進するかを説明する。
論文 参考訳(メタデータ) (2022-05-30T18:50:35Z) - Shortcuts to Quantum Approximate Optimization Algorithm [2.150418646956503]
我々は「QAOAへのショートカット」(S-QAOA)と呼ばれる新しいアンサッツを提案する。
S-QAOAは、2体相互作用を多く含み、パラメータ自由を解放することで、ターゲットハミルトン状態へのショートカットを提供する。
MaxCut問題とSherrington-Kirkpatrick(SK)モデルを考えると、YY相互作用が最高の性能を示す。
論文 参考訳(メタデータ) (2021-12-21T02:24:19Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。
我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。
提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
論文 参考訳(メタデータ) (2021-08-06T19:38:03Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳(メタデータ) (2021-06-11T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。