論文の概要: Quantum Algorithm for Dynamic Programming Approach for DAGs and
Applications
- arxiv url: http://arxiv.org/abs/2212.14433v1
- Date: Thu, 29 Dec 2022 19:07:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 02:35:09.431712
- Title: Quantum Algorithm for Dynamic Programming Approach for DAGs and
Applications
- Title(参考訳): DAGのための動的プログラミングのための量子アルゴリズムとその応用
- Authors: Kamil Khadiev and Liliya Safina
- Abstract要約: 有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。
OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we present a quantum algorithm for the dynamic programming
approach for problems on directed acyclic graphs (DAGs). The running time of
the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the
best known deterministic algorithm is $O(n+m)$, where $n$ is the number of
vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge;
$m$ is the number of edges. We show that we can solve problems that use OR,
AND, NAND, MAX, and MIN functions as the main transition steps. The approach is
useful for a couple of problems. One of them is computing a Boolean formula
that is represented by Zhegalkin polynomial, a Boolean circuit with shared
input and non-constant depth evaluation. Another two are the single source
longest paths search for weighted DAGs and the diameter search problem for
unweighted DAGs.
- Abstract(参考訳): 本稿では,有向非巡回グラフ(dags)上の問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。
アルゴリズムの実行時間は$O(\sqrt{\hat{n}m}\log \hat{n})$であり、最もよく知られている決定論的アルゴリズムの実行時間は$O(n+m)$である。
OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
このアプローチはいくつかの問題に役立ちます。
そのうちの1つは、共有入力と非定数深さ評価を持つブール回路であるzhegalkin多項式によって表されるブール公式を計算することである。
他の2つは、重み付きDAGを探索する単一ソース長経路と、重みなしDAGの直径探索問題である。
関連論文リスト
- Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。
最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。
2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文 参考訳(メタデータ) (2024-08-19T21:30:02Z) - 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) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳(メタデータ) (2024-02-09T19:01:48Z) - Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。
溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
論文 参考訳(メタデータ) (2023-07-24T02:50:34Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳(メタデータ) (2023-06-23T01:28:24Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳(メタデータ) (2023-06-08T14:48:48Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳(メタデータ) (2021-10-15T00:54:04Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳(メタデータ) (2020-12-02T15:32:52Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳(メタデータ) (2020-10-13T17:26:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。