論文の概要: Classical and Quantum Distributed Algorithms for the Survivable Network Design Problem
- arxiv url: http://arxiv.org/abs/2404.10748v1
- Date: Tue, 16 Apr 2024 17:27:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 15:55:23.534870
- Title: Classical and Quantum Distributed Algorithms for the Survivable Network Design Problem
- Title（参考訳）: 生存可能なネットワーク設計問題に対する古典的および量子的分散アルゴリズム
- Authors: Phillip Kerger, David E. Bernal Neira, Zoe Gonzalez Izquierdo, Eleanor G. Rieffel,
- Abstract要約: 生存可能なネットワーク設計問題(SNDP)に対する分散古典的および量子的アプローチについて検討する。
SNDPの古典的あるいは量子的アルゴリズムは、我々が考慮している分散設定では定式化されていない。
結果は、考慮された問題のアプリケーションスケールのインスタンスに対して、古典的モデルと量子的モデルが分離されているかどうかという問題を提起する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate distributed classical and quantum approaches for the survivable network design problem (SNDP), sometimes called the generalized Steiner problem. These problems generalize many complex graph problems of interest, such as the traveling salesperson problem, the Steiner tree problem, and the k-connected network problem. To our knowledge, no classical or quantum algorithms for the SNDP have been formulated in the distributed settings we consider. We describe algorithms that are heuristics for the general problem but give concrete approximation bounds under specific parameterizations of the SNDP, which in particular hold for the three aforementioned problems that SNDP generalizes. We use a classical, centralized algorithmic framework first studied in (Goemans & Bertsimas 1993) and provide a distributed implementation thereof. Notably, we obtain asymptotic quantum speedups by leveraging quantum shortest path computations in this framework, generalizing recent work of (Kerger et al. 2023). These results raise the question of whether there is a separation between the classical and quantum models for application-scale instances of the problems considered.
- Abstract（参考訳）: 本研究では,Survivable Network Design problem (SNDP) に対する古典的および量子的分散アプローチを,一般化されたスタイナー問題(Generalized Steiner problem)と呼ぶことがある。
これらの問題は、旅行セールスパーソン問題、スタイナーツリー問題、k接続ネットワーク問題など、多くの複雑なグラフ問題を一般化する。
我々の知る限り、SNDPの古典的あるいは量子的アルゴリズムは、我々が考慮している分散設定で定式化されていない。
本稿では,一般問題に対するヒューリスティックなアルゴリズムについて述べるが,SNDPが一般化した3つの問題に特に当てはまる,SNDPの特定のパラメータ化の下で具体的な近似境界を与える。
我々は(Goemans & Bertsimas 1993)で最初に研究された古典的集中型アルゴリズムフレームワークを使用し、その分散実装を提供する。
特に,近年のKerger et al 2023の量子最短経路計算を応用して,漸近的な量子スピードアップを実現する。
これらの結果は、考慮された問題のアプリケーションスケールのインスタンスに対して、古典的モデルと量子的モデルの間に分離が存在するかどうかという問題を提起する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
我々は、Harrow, Hassidim and Lloyd (HHL) によって提案された方程式の線形系に対するよく知られたアルゴリズムを、直接解法ではなく予測子-相関子に適応させることにより適用する。
この戦略は、多くの古典的アルゴリズムでよく見られる計算コストの高いステップのインテリジェントな省略を可能にし、同時に量子状態の抽出に関連する悪名高い読み出し問題を緩和する。
このアプローチの汎用性は、滑らかな粒子流体力学、プラズマシミュレーション、反応性流れ構成など、様々な分野の応用を通して説明される。
論文 参考訳（メタデータ） (2024-06-28T15:31:10Z) - Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval [1.6421520075844793]
主な例として、積層複合材料の重量最適化がある。
量子計算の急速に発展する分野は、これらの複雑な問題に対処するための新しいアプローチを提供するかもしれない。
論文 参考訳（メタデータ） (2024-02-09T15:01:56Z) - Unsupervised Random Quantum Networks for PDEs [0.0]
PINNは、微分演算子と関連する境界条件を満たすように訓練されたディープニューラルネットワークの助けを借りて、PDEの解を近似する。
我々はこのアイデアを量子コンピューティング領域で再考し、パラメータ化されたランダム量子回路を試行的な解として用いた。
ランダムな量子ネットワークは、従来の量子ネットワークやランダムな古典的ネットワークよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-12-21T10:25:52Z) - On the quantum time complexity of divide and conquer [42.7410400783548]
量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。
これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
論文 参考訳（メタデータ） (2023-11-28T01:06:03Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Two convergent NPA-like hierarchies for the quantum bilocal scenario [2.048226951354646]
結合量子系の単一部分の局所的な測定から生じる相関を特徴づけることは、量子情報理論の主要な問題の一つである。
スカラー拡張に同値性を示す新しい階層を導入し、既知の一般化との関係を探求する。
論文 参考訳（メタデータ） (2022-10-17T13:04:41Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。