論文の概要: A parallel and distributed fixed-point quantum search algorithm for solving SAT problems
- arxiv url: http://arxiv.org/abs/2604.09980v1
- Date: Sat, 11 Apr 2026 01:28:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:15.776159
- Title: A parallel and distributed fixed-point quantum search algorithm for solving SAT problems
- Title（参考訳）: SAT問題解決のための並列および分散不動点量子探索アルゴリズム
- Authors: He Wang, Jinyang Yao,
- Abstract要約: SAT問題の解決には$mathcalO(sqrt2n)$クエリが必要です。
SAT問題を解くために並列固定点探索アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.341973606434514
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Boolean satisfiability (SAT) problem is of fundamental importance in computer science and many application domains. For Grover's algorithm, solving the SAT problem requires $\mathcal{O}(\sqrt{2^n})$ queries--where n denotes the number of logic variables in the problem. However, Grover's algorithm suffers from the Souffle problem: specifically, when the number of solutions is unknown, terminating the algorithm too early or too late leads to a significant reduction in the probability of obtaining a solution. In this paper, we propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem. By exploiting entanglement, each clause in the conjunctive normal form (CNF) formula can be processed independently, leading to a significant reduction in circuit depth. We also discuss how to perform the algorithm in distributed manner. These make the PFPS algorithm particularly suitable for the noisy intermediate-scale quantum (NISQ) era.
- Abstract（参考訳）: ブール満足度(SAT)問題は、コンピュータ科学と多くのアプリケーション領域において基本的な重要性である。
グロバーのアルゴリズムでは、SAT問題を解くには$\mathcal{O}(\sqrt{2^n})$クエリーが必要である。
しかし、グロバーのアルゴリズムはソッフル問題に悩まされており、特に解の数が不明な場合には、アルゴリズムが早すぎるか遅すぎるかで解を得る確率が大幅に低下する。
本稿では,SAT問題を解くために並列固定点探索アルゴリズムを提案する。
絡み合いを利用して、共役正規形(CNF)式の各節を独立に処理でき、回路深さが大幅に減少する。
また,アルゴリズムを分散的に実行する方法についても論じる。
これらにより、PFPSアルゴリズムは特にノイズのある中間スケール量子(NISQ)時代に適している。
関連論文リスト
- 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) - Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems [1.4513830934124627]
2組の演算子を用いた2段階量子探索(TSQS)アルゴリズムを提案する。
最初のステップでは、すべての実現可能な解は、同じ重ね合わせ状態に増幅される。
2番目のステップでは、この重ね合わせ状態から最適解状態が増幅される。
論文 参考訳（メタデータ） (2024-05-12T01:44: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) - Quantum optimization algorithm based on multistep quantum computation [0.0]
本稿では,多段階量子計算に基づく関数の最小値を求める量子アルゴリズムを提案する。
このアルゴリズムでは、問題の探索空間の次元を指数関数的に段階的に減らすことができる。
連続的なテスト関数のアルゴリズムを検証した。
論文 参考訳（メタデータ） (2023-06-30T01:58:23Z) - Solving Subset Sum Problems using Quantum Inspired Optimization
Algorithms with Applications in Auditing and Financial Data Analysis [2.0981723008692392]
Hopfield Networksの勾配勾配勾配が、人工データと実データの両方の解を確実に見つける方法を示す。
本稿では,このアルゴリズムを断熱量子コンピュータに応用する方法を概説する。
論文 参考訳（メタデータ） (2022-10-28T12:22:15Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳（メタデータ） (2020-11-17T17:27:33Z) - Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。
各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
論文 参考訳（メタデータ） (2020-09-11T17:31:39Z) - Second-order Conditional Gradient Sliding [70.88478428882871]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。