論文の概要: Quantum Speedups for Bayesian Network Structure Learning
- arxiv url: http://arxiv.org/abs/2305.19673v1
- Date: Wed, 31 May 2023 09:15:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 17:39:49.038257
- Title: Quantum Speedups for Bayesian Network Structure Learning
- Title（参考訳）: ベイズネットワーク構造学習のための量子スピードアップ
- Authors: Juha Harviainen (1), Kseniya Rychkova (2), Mikko Koivisto (1) ((1)
University of Helsinki, (2) IQM)
- Abstract要約: ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Bayesian network structure learning (BNSL) problem asks for a directed
acyclic graph that maximizes a given score function. For networks with $n$
nodes, the fastest known algorithms run in time $O(2^n n^2)$ in the worst case,
with no improvement in the asymptotic bound for two decades. Inspired by recent
advances in quantum computing, we ask whether BNSL admits a polynomial quantum
speedup, that is, whether the problem can be solved by a quantum algorithm in
time $O(c^n)$ for some constant $c$ less than $2$. We answer the question in
the affirmative by giving two algorithms achieving $c \leq 1.817$ and $c \leq
1.982$ assuming the number of potential parent sets is, respectively,
subexponential and $O(1.453^n)$. Both algorithms assume the availability of a
quantum random access memory.
- Abstract（参考訳）: ベイズネットワーク構造学習(BNSL)問題は、与えられたスコア関数を最大化する有向非巡回グラフを求める。
n$ノードを持つネットワークでは、最も速い既知のアルゴリズムは最悪の場合に$o(2^n n^2)$で動作し、漸近的なバウンドは20年間改善されなかった。
量子コンピューティングの最近の進歩に触発されて、bnslが多項式の量子スピードアップを認めているかどうか、つまり、ある定数のc$が2ドル未満の定数に対してo(c^n)$の量子アルゴリズムで問題を解くことができるかどうかを問う。
c \leq 1.817$ と $c \leq 1.982$ の2つのアルゴリズムに対して、潜在親集合の数がそれぞれsubexponential と $o(1.453^n)$と仮定して解く。
どちらのアルゴリズムも、量子ランダムアクセスメモリの可用性を前提としている。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。
Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。
評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
論文 参考訳（メタデータ） (2024-04-30T23:55:03Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-16T13:57:01Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。