論文の概要: Runtime-coherence trade-offs for hybrid SAT-solvers

• arxiv url: http://arxiv.org/abs/2404.15235v1
• Date: Tue, 23 Apr 2024 17:11:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-24 12:53:16.034692
• Title: Runtime-coherence trade-offs for hybrid SAT-solvers
• Title（参考訳）: ハイブリッドSAT-ソルバのランタイムコヒーレンストレードオフ
• Authors: Vahideh Eshaghian, Sören Wilkening, Johan Åberg, David Gross,
• Abstract要約: 総ランタイムとコヒーレンスタイムの間には,単純なトレードオフ関係が存在する,と我々は主張する。 最適トレードオフを伴うハイブリッドアルゴリズムの実装において,さらなる柔軟性を示唆する数値シミュレーションを提案する。
• 参考スコア（独自算出の注目度）: 1.087459729391301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many search-based quantum algorithms that achieve a theoretical speedup are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts.This raises the question of how to divide computational tasks into a collection of parallelizable sub-problems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the k-SAT problem. Our analysis is based on Sch\"oning's algorithm, which solves instances of k-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for "natural" partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.
• Abstract（参考訳）: 計算タスクを並列化可能なサブプロブレムの集合に分割する方法の疑問が提起され、それぞれがコヒーレンス時間に制限された量子コンピュータで解ける。 ここでは、k-SAT問題に対するハイブリッドアルゴリズムを用いてこの問題にアプローチする。 我々の解析はSch\"oning's algorithm(英語版)に基づいており、これは潜在的な割り当ての空間をランダムにウォークすることでk-SATのインスタンスを解く。 この設定では、全体ランタイムとコヒーレンスタイムの間には単純なトレードオフ関係があり、そのような分割ベースのハイブリッドスキームは超えられない、と論じる。 分割の具体的な選択については、特定の実行時コヒーレンス時間関係を明示的に決定し、理想的なトレードオフの飽和を示す。 最後に、最適トレードオフを持つハイブリッドアルゴリズムの実装において、さらなる柔軟性を示唆する数値シミュレーションを提案する。

関連論文リスト

• Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
  量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。 本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。 我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
  論文  参考訳（メタデータ） (2024-08-11T10:28:49Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。 この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。 D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
  論文  参考訳（メタデータ） (2024-07-09T11:44:58Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
  古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。 本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。 これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
  論文  参考訳（メタデータ） (2022-03-09T19:00:00Z)
• Parallelizing Contextual Linear Bandits [82.65675585004448]
  並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。 また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
  論文  参考訳（メタデータ） (2021-05-21T22:22:02Z)
• Hybrid divide-and-conquer approach for tree search algorithms [0.0]
  本稿では,木探索アルゴリズムの文脈におけるハイブリッド分割・コンカレント手法について検討する。 DPLLのアルゴリズムの高速化条件について述べる。 本稿では,大規模問題に対する高速化におけるハイブリッド手法の限界について概説する。
  論文  参考訳（メタデータ） (2020-07-14T13:57:12Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。