論文の概要: Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
- arxiv url: http://arxiv.org/abs/2603.20038v1
- Date: Fri, 20 Mar 2026 15:22:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-23 19:48:39.206034
- Title: Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
- Title（参考訳）: 製品状態量子$k$-SAT(PRODSAT-QSAT)に対する探索駆動クローズ学習
- Authors: Samuel González-Castillo, Joon Hyung Lee, Alfons Laarman,
- Abstract要約: ProDSAT-QSAT($k$): 与えられたランク1$k$ローカルプロジェクターを用いて、量子$k$-SATインスタンスが満足な積状態を持つかどうかを決定する。
この問題を定式化し、節学習規則の健全性を証明し、実用的なアルゴリズムと実装を記述する。
- 参考スコア（独自算出の注目度）: 0.8301212911450326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study PRODSAT-QSAT($k$): given rank-one $k$-local projectors, determine whether a quantum $k$-SAT instance admits a satisfying product state. We present a CDCL-style refutation framework that searches a finite partition of each qubit's Bloch sphere while a sound theory solver checks region feasibility using a geometric overapproximation of the projection amplitudes for each constraint. When the theory solver proves that no state in a region can satisfy a constraint, it produces a sound conflict clause that blocks that region; accumulated blocking clauses can yield a global result of product-state unsatisfiability (UN-PRODSAT). We formalise the problem, prove the soundness of the clause-learning rule, and describe a practical algorithm and implementation.
- Abstract（参考訳）: ProDSAT-QSAT($k$): 与えられたランク1$k$ローカルプロジェクターを用いて、量子$k$-SATインスタンスが満足な積状態を持つかどうかを決定する。
本稿では,各キュービットのブロッホ球の有限分割を探索するCDCLスタイルの難読化フレームワークを提案する。
理論解法が領域の状態が制約を満たすことができないことを証明した場合、その領域をブロックする健全な競合節を生成し、蓄積されたブロック節は積状態不満足(UN-PRODSAT)のグローバルな結果をもたらす。
この問題を定式化し、節学習規則の健全性を証明し、実用的なアルゴリズムと実装を記述する。
関連論文リスト
- Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Bisimulation Learning [55.859538562698496]
我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。
提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
論文 参考訳（メタデータ） (2024-05-24T17:11:27Z) - The PRODSAT phase of random quantum satisfiability [7.5465062534540515]
k$-QSAT問題は、有名な$k$-SAT制約満足度問題の量子アナログである。
ゼロエネルギーの積状態が高い確率で存在することは、基礎因子グラフが節被覆二量体構成を持つ場合に限る。
論文 参考訳（メタデータ） (2024-04-29T06:10:45Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳（メタデータ） (2023-12-16T12:44:36Z) - Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT [55.78588835407174]
振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。
Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。
振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
論文 参考訳（メタデータ） (2023-03-02T11:52:39Z) - Testing quantum satisfiability [0.0]
量子k-SATはランダムな時間で解けることを示す。
まず、量子 k-SAT の充足可能なインスタンスに対して、一定数の量子ビット上のほとんどの部分プロブレムは積状態によって満足できることを示す。
次に、積状態によって満足できない量子 k-SAT のインスタンスの場合、ほとんどのサブプロブレムは積状態によって満足できないことを示す。
論文 参考訳（メタデータ） (2023-01-25T17:02:46Z) - Estimating the hardness of SAT encodings for Logical Equivalence
Checking of Boolean circuits [58.83758257568434]
LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。
そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
論文 参考訳（メタデータ） (2022-10-04T09:19:13Z) - On Continuous Local BDD-Based Search for Hybrid SAT Solving [40.252804008544985]
CLSに必要な勾配を効率的に計算するための新しいアルゴリズムを提案する。
多くのベンチマークインスタンスに適用することにより、多用途CLSソルバであるGradSATの機能と限界について検討する。
実験結果から,GradSATは既存のSATおよびMaxSATソルバのポートフォリオに追加され,ブール適合性および最適化問題の解決に有用であることが示唆された。
論文 参考訳（メタデータ） (2020-12-14T22:36:20Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。