論文の概要: Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem
- arxiv url: http://arxiv.org/abs/2311.10941v1
- Date: Sat, 18 Nov 2023 02:36:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 13:19:33.070098
- Title: Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem
- Title（参考訳）: ハミルトンサイクル問題に対する古典的・確率的・量子アルゴリズムの比較
- Authors: Giuseppe Corrente, Carlo Vincenzo Stanzione and Vittoria Stanzione
- Abstract要約: ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。
本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Hamiltonian cycle problem (HCP), which is an NP-complete problem,
consists of having a graph G with n nodes and m edges and finding the path that
connects each node exactly once. In this paper we compare some algorithms to
solve a Hamiltonian cycle problem, using different models of computations and
especially the probabilistic and quantum ones. Starting from the classical
probabilistic approach of random walks, we take a step to the quantum direction
by involving an ad hoc designed Quantum Turing Machine (QTM), which can be a
useful conceptual project tool for quantum algorithms. Introducing several
constraints to the graphs, our analysis leads to not-exponential speedup
improvements to the best-known algorithms. In particular, the results are based
on bounded degree graphs (graphs with nodes having a maximum number of edges)
and graphs with the right limited number of nodes and edges to allow them to
outperform the other algorithms.
- Abstract（参考訳）: NP完全問題であるハミルトンサイクル問題(HCP)は、n個のノードとm個のエッジを持つグラフGを持ち、各ノードを正確に1度に接続する経路を見つける。
本稿では,計算の異なるモデル,特に確率的および量子的問題を用いて,ハミルトニアンサイクル問題を解くアルゴリズムを比較する。
ランダムウォークの古典的確率論的アプローチから始めて、量子アルゴリズムの有用な概念的プロジェクトツールであるアドホック設計の量子チューリングマシン(Quantum Turing Machine, QTM)を取り入れることで、量子方向への一歩を踏み出す。
グラフにいくつかの制約を導入することで、我々の分析は、よく知られたアルゴリズムの指数関数的高速化に繋がる。
特に、結果は有界次数グラフ(エッジ数が最大となるノードを持つグラフ)と、他のアルゴリズムを上回るようなノードとエッジの数が制限されたグラフに基づいている。
関連論文リスト
- 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) - Quantum Algorithm for Testing Graph Completeness [0.0]
グラフ完全性をテストすることは、コンピュータ科学とネットワーク理論において重要な問題である。
Szegedy量子ウォークと量子位相推定(QPE)を用いた効率的なアルゴリズムを提案する。
このアプローチは、ネットワーク構造解析、古典的なルーティングアルゴリズムの評価、ペア比較に基づくシステム評価に有用である。
論文 参考訳（メタデータ） (2024-07-29T14:56:25Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - Quantum Speedup for Graph Sparsification, Cut Approximation and
Laplacian Solving [1.0660480034605238]
スペクトルスペーシフィケーション」は、ノード数でエッジの数をほぼ直線に減らす。
スペクトルスカラー化のための量子スピードアップとその多くの応用について述べる。
我々のアルゴリズムはラプラシア系を解くための量子スピードアップを意味する。
論文 参考訳（メタデータ） (2019-11-17T17:29:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。