論文の概要: 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)からの還元により下界を得る。
関連論文リスト
- Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。
私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。
基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
論文 参考訳（メタデータ） (2024-05-22T18:11:42Z) - Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
量子回路(PQC)は、その主応用の範囲外ではまだ完全には理解されていない。
我々は、量子ビット接続性に関する制約の下で、PQCにおけるランダム状態の生成を分析する。
生成した状態の分布の均一性の増加と絡み合いの発生との間には,どれだけ急激な関係があるかを示す。
論文 参考訳（メタデータ） (2024-05-03T17:32:55Z) - 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) - 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) - 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) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。