Fugu-MT 論文翻訳(概要): A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs

論文の概要: A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs

arxiv url: http://arxiv.org/abs/2010.02324v2
Date: Tue, 11 May 2021 15:59:41 GMT
ステータス: 処理完了
システム内更新日: 2023-04-29 22:18:30.933277
Title: A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
Title（参考訳）: 一般グラフ上の最大マッチングのためのクエリ効率量子アルゴリズム
Authors: Shelby Kimmel and R. Teal Witter
Abstract要約: 最大マッチングのための量子アルゴリズムを設計する。特に、$n$ノードと$m$エッジを持つグラフの場合、我々のアルゴリズムは行列モデルで$O(n7/4)クエリを生成する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We design quantum algorithms for maximum matching. Working in the query model, in both adjacency matrix and adjacency list settings, we improve on the best known algorithms for general graphs, matching previously obtained results for bipartite graphs. In particular, for a graph with $n$ nodes and $m$ edges, our algorithm makes $O(n^{7/4})$ queries in the matrix model and $O(n^{3/4}(m+n)^{1/2})$ queries in the list model. Our approach combines Gabow's classical maximum matching algorithm [Gabow, Fundamenta Informaticae, '17] with the guessing tree method of Beigi and Taghavi [Beigi and Taghavi, Quantum, '20].
Abstract（参考訳）: 最大マッチングのための量子アルゴリズムを設計する。クエリモデルでは、隣接行列と隣接リストの設定の両方において、一般的なグラフの最もよく知られたアルゴリズムを改善し、前述した2部グラフの結果と一致します。特に、$n$ノードと$m$エッジを持つグラフに対して、我々のアルゴリズムは行列モデルの$O(n^{7/4})$クエリとリストモデルの$O(n^{3/4}(m+n)^{1/2})$クエリを作成する。提案手法はガボウの古典的最大マッチングアルゴリズム(Gabow, Fundamenta Informaticae, '17)とビギとタハビの推測木法(Beigi and Taghavi, Quantum, '20]を組み合わせる。

関連論文リスト

Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文参考訳（メタデータ） (2023-10-23T18:26:00Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文参考訳（メタデータ） (2022-01-25T00:10:03Z)
The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
論文参考訳（メタデータ） (2021-10-27T06:35:59Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文参考訳（メタデータ） (2021-05-18T06:51:11Z)
Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文参考訳（メタデータ） (2021-02-13T17:25:41Z)
Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文参考訳（メタデータ） (2021-01-28T02:39:27Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文参考訳（メタデータ） (2020-11-26T18:22:21Z)
Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。 ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
論文参考訳（メタデータ） (2020-11-17T13:12:43Z)
Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文参考訳（メタデータ） (2020-11-12T16:29:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。