Fugu-MT 論文翻訳(概要): Quantum Algorithm for Approximating Maximum Independent Sets

論文の概要: Quantum Algorithm for Approximating Maximum Independent Sets

arxiv url: http://arxiv.org/abs/2005.13089v2
Date: Fri, 26 Feb 2021 05:52:15 GMT
ステータス: 処理完了
システム内更新日: 2023-05-18 07:14:31.846065
Title: Quantum Algorithm for Approximating Maximum Independent Sets
Title（参考訳）: 最大独立集合近似のための量子アルゴリズム
Authors: Hongye Yu, Frank Wilczek, Biao Wu
Abstract要約: 量子非アベリア断熱混合に基づくグラフの最大独立集合を近似する量子アルゴリズムを提案する。スパースグラフや密度グラフの場合、平均的な量子アルゴリズムは$alpha(G)$と非常に近い大きさの独立した集合を見つけることができる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states, which generates quantum annealing in a secondary Hamiltonian. For both sparse and dense graphs, our quantum algorithm on average can find an independent set of size very close to $\alpha(G)$, which is the size of the maximum independent set of a given graph $G$. Numerical results indicate that an $O(n^2)$ time complexity quantum algorithm is sufficient for finding an independent set of size $(1-\epsilon)\alpha(G)$. The best classical approximation algorithm can produce in polynomial time an independent set of size about half of $\alpha(G)$.
Abstract（参考訳）: 本稿では,2次ハミルトニアンの量子アニーリングを生成する縮退基底状態のサブヒルベルト空間における非可換な量子混合に基づくグラフの最大独立集合を近似する量子アルゴリズムを提案する。疎グラフと密グラフの両方に対して、平均的な量子アルゴリズムは、与えられたグラフ$g$の最大独立集合の大きさである$\alpha(g)$に近い大きさの独立集合を見つけることができる。数値的な結果から、$O(n^2)$時間複雑性量子アルゴリズムは、1-\epsilon)\alpha(G)$の独立したサイズの集合を見つけるのに十分である。最高の古典近似アルゴリズムは多項式時間で$\alpha(G)$の約半分の大きさの独立な集合を生成できる。

関連論文リスト

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)
Quantum Hamiltonian Algorithms for Maximum Independent Sets [6.772902928686719]
PKアルゴリズムと呼ばれる別のアルゴリズムは、独立集合が創発的PXPモデルの非アーベルゲージ行列によって支配されるメディアグラフ上で拡散することを明らかにする。 2つのアルゴリズムは数学的に等価であるが、PKアルゴリズムはより効率的でリソース節約性能を示す。
論文参考訳（メタデータ） (2023-10-23T04:00:34Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。我々は距離の計算を高速化するために量子現象を利用する。我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文参考訳（メタデータ） (2022-12-13T16:04:16Z)
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。我々はモンテカルロ法と量子ウォークの量子アナログを利用する。また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文参考訳（メタデータ） (2022-10-12T19:10:43Z)
Quantum Approximate Counting for Markov Chains and Application to Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文参考訳（メタデータ） (2022-04-06T03:04:42Z)
Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文参考訳（メタデータ） (2020-10-13T17:26:09Z)
Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
論文参考訳（メタデータ） (2020-05-18T16:55:08Z)
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
論文参考訳（メタデータ） (2020-04-20T00:48:02Z)

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