論文の概要: 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)$と仮定して解く。
どちらのアルゴリズムも、量子ランダムアクセスメモリの可用性を前提としている。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳(メタデータ) (2023-05-09T20:53:27Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳(メタデータ) (2023-04-06T02:18:52Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - 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) - Quantum Subroutine Composition [1.1802674324027231]
量子アルゴリズムでは、サブルーチンは異なる入力の重ね合わせで呼ばれ、それが物事を複雑にする。
我々は、最近arXiv:2208.13492で導入された多次元量子ウォークの技術を用いてこれを証明した。
量子ウォークで量子サブルーチンを構成することができるのと同じ技術は、任意の量子アルゴリズムで構成することができる。
論文 参考訳(メタデータ) (2022-09-28T14:52:13Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。