論文の概要: 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の量子最短経路計算を応用して,漸近的な量子スピードアップを実現する。
これらの結果は、考慮された問題のアプリケーションスケールのインスタンスに対して、古典的モデルと量子的モデルの間に分離が存在するかどうかという問題を提起する。
関連論文リスト
- 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) - The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for
Deep Quantum Machine Learning [52.77024349608834]
古典的なディープニューラルネットワークの量子アナログを構築することは、量子コンピューティングにおける根本的な課題である。
鍵となる問題は、古典的なディープラーニングの本質的な非線形性にどのように対処するかである。
我々は、深層機械学習のこれらの側面を複製できる量子機械学習の定式化であるQuantum Path Kernelを紹介する。
論文 参考訳(メタデータ) (2022-12-22T16:06:24Z) - 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) - BILP-Q: Quantum Coalition Structure Generation [0.0]
我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。
実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
論文 参考訳(メタデータ) (2022-04-28T22:19:50Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳(メタデータ) (2022-03-29T05:44:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。