論文の概要: Hybrid divide-and-conquer approach for tree search algorithms
- arxiv url: http://arxiv.org/abs/2007.07040v4
- Date: Mon, 20 Mar 2023 11:56:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 08:39:01.949740
- Title: Hybrid divide-and-conquer approach for tree search algorithms
- Title（参考訳）: 木々探索アルゴリズムのハイブリッド分割・解法
- Authors: Mathys Rennela, Sebastiaan Brand, Alfons Laarman, Vedran Dunjko
- Abstract要約: 本稿では,木探索アルゴリズムの文脈におけるハイブリッド分割・コンカレント手法について検討する。
DPLLのアルゴリズムの高速化条件について述べる。
本稿では,大規模問題に対する高速化におけるハイブリッド手法の限界について概説する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the challenges of quantum computers in the near- and mid- term is the
limited number of qubits we can use for computations. Finding methods that
achieve useful quantum improvements under size limitations is thus a key
question in the field. In this vein, it was recently shown that a hybrid
classical-quantum method can help provide polynomial speed-ups to classical
divide-and-conquer algorithms, even when only given access to a quantum
computer much smaller than the problem itself. In this work, we study the
hybrid divide-and-conquer method in the context of tree search algorithms, and
extend it by including quantum backtracking, which allows better results than
previous Grover-based methods. Further, we provide general criteria for
polynomial speed-ups in the tree search context, and provide a number of
examples where polynomial speed ups, using arbitrarily smaller quantum
computers, can be obtained. We provide conditions for speedups for the well
known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ
algorithm (the core of the fastest exact Boolean satisfiability solver) for
well-behaved classes of formulas. We also provide a simple example where
speed-ups can be obtained in an algorithm-independent fashion, under certain
well-studied complexity-theoretical assumptions. Finally, we briefly discuss
the fundamental limitations of hybrid methods in providing speed-ups for larger
problems.
- Abstract（参考訳）: 短期的および中期的な量子コンピュータの課題の1つは、計算に使用できる量子ビット数が限られていることである。
サイズ制限の下で有用な量子改善を実現する方法を見つけることは、この分野において重要な問題である。
この例では、量子コンピュータへのアクセスが問題自体よりもはるかに小さい場合であっても、ハイブリッド古典量子法が古典的分割量子アルゴリズムの多項式スピードアップに役立てることが示されている。
本研究では,木木探索アルゴリズムの文脈におけるハイブリッド分割・コンカレント法について検討し,従来のGrover法よりも優れた結果を得られる量子バックトラッキングを含めて拡張する。
さらに,木探索の文脈における多項式スピードアップの一般的な基準を提供し,任意に小さい量子コンピュータを用いて多項式スピードアップが得られる例をいくつか提供する。
我々は,よく知られたdpllアルゴリズムの高速化条件を提供し,ppszアルゴリズム(最も高速で正確なブール充足可能な解法)のしきい値フリーな高速化を導出する。
また, アルゴリズム非依存の手法で, 一定の複雑性・理論的仮定の下で, 速度アップを得られる簡単な例を示す。
最後に,大規模問題に対する高速化におけるハイブリッド手法の基本的限界について概説する。
関連論文リスト
- Optimization by Decoded Quantum Interferometry [43.55132675053983]
本稿では,古典的復号化問題に対する古典的最適化問題を減じるための量子アルゴリズムを提案する。
DQIは、既知の量子時間古典アルゴリズムよりも近似比が良いことを示す。
論文 参考訳（メタデータ） (2024-08-15T17:47:42Z) - 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) - Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。
本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。
本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
論文 参考訳（メタデータ） (2024-07-29T17:13:01Z) - Runtime-coherence trade-offs for hybrid SAT-solvers [1.087459729391301]
総ランタイムとコヒーレンスタイムの間には,単純なトレードオフ関係が存在する,と我々は主張する。
最適トレードオフを伴うハイブリッドアルゴリズムの実装において,さらなる柔軟性を示唆する数値シミュレーションを提案する。
論文 参考訳（メタデータ） (2024-04-23T17:11:39Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Hybrid Quantum-Classical Search Algorithms [0.0]
古典計算は,探索問題自体が解けない限り,量子計算を補助できないことを示す。
我々はこの結果を、不安定な成功確率を持つアルゴリズムに一般化する。
論文 参考訳（メタデータ） (2022-02-23T11:43:17Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Multi-layer quantum search and inclusion of NP into BQP [6.362434591714693]
本稿では,Groverのアルゴリズムを指数的に高速化する多層量子探索法を提案する。
その結果、量子回路の高速化はユビキタスであり、Groverの探索は実証されたよりもはるかに強力であることがわかった。
論文 参考訳（メタデータ） (2020-04-23T17:44:51Z) - Quantifying Computational Advantage of Grover's Algorithm with the Trace
Speed [0.0]
本稿では,Groverの探索アルゴリズムにおけるトレース速度と量子スピードアップの密接な関係について報告する。
ノイズのないアルゴリズムでは、量子スピードアップと擬似純粋状態の偏極の1対1対応を見出す。
論文 参考訳（メタデータ） (2020-01-13T19:01:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。