論文の概要: Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking
- arxiv url: http://arxiv.org/abs/2604.18218v1
- Date: Mon, 20 Apr 2026 13:03:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-28 17:21:40.167041
- Title: Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking
- Title（参考訳）: Quantangle-SAT: エンタングルと等価チェックに基づく量子SATソルバ
- Authors: Shang-Wei Lin, Ji-Qing Yan, Yean-Ru Chen, Zhe Hou, David Sanán,
- Abstract要約: 本稿では,絡み合いと等価性チェックに基づく新しい量子SATソルバを提案する。
提案手法は,解数に関する事前知識を前提とせず,量子カウントよりも計算効率が高い。
- 参考スコア（独自算出の注目度）: 2.0164889460156417
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.
- Abstract（参考訳）: SAT (Satifiability) は計算機科学の中心的な問題であり、SAT解決アルゴリズムの進歩は多くの分野において大きな影響を与えている。
近年の研究では、Groverのアルゴリズムに基づく量子SATソルバが提案されている。
しかし、グロバーに基づくアプローチは重要な制限に直面している。それらは典型的には、対象ブール公式の満足な割り当ての数に関する事前の知識を必要とする。
この情報は、ほとんどの実用的な設定では利用できない。
量子カウントは、この量を推定するために用いられるが、グロバーサーチよりも数桁高い計算オーバーヘッドを引き起こす。
本稿では,絡み合いと等価性チェックに基づく新しい量子SATソルバを提案する。
提案手法は,解数に関する事前知識を前提とせず,量子カウントよりも計算効率が高い。
最悪のケースタイムの複雑性は必然的に指数関数的であるが、我々のアプローチの期待される時間複雑性はランダムブール関数上の定数時間 O(1) のみであることが証明される。
実験結果も我々の理論的な主張を支持している。
関連論文リスト
- A parallel and distributed fixed-point quantum search algorithm for solving SAT problems [6.341973606434514]
SAT問題の解決には$mathcalO(sqrt2n)$クエリが必要です。
SAT問題を解くために並列固定点探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-04-11T01:28:20Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - A Parallel and Distributed Quantum SAT Solver Based on Entanglement and
Quantum Teleportation [1.5201992393140886]
並列量子SATソルバは,線形時間 O(m) から定数時間 O(1) までの繰り返しの時間複雑性を,余分な絡み合った量子ビットを用いて低減する。
我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。
論文 参考訳（メタデータ） (2023-08-07T06:52:06Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。
この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文 参考訳（メタデータ） (2023-06-07T12:19:22Z) - Opening the Black Box Inside Grover's Algorithm [0.0]
グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
論文 参考訳（メタデータ） (2023-03-20T17:56:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。