論文の概要: Performance Gains in Quantum SAT Solvers Using ESOP Encoding
- arxiv url: http://arxiv.org/abs/2605.16202v1
- Date: Fri, 15 May 2026 17:17:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-18 21:22:26.387415
- Title: Performance Gains in Quantum SAT Solvers Using ESOP Encoding
- Title（参考訳）: ESOP符号化を用いた量子SATソルバの性能向上
- Authors: Majd Assaad, Abhoy Kole, Rolf Drechsler,
- Abstract要約: 量子SATの解法に適した排他的生産量に基づくCNF表現について検討する。
我々は,e-CNF符号化を用いたグロバーベースSATソルバに対して,キュービット要求値とClifford+$T$ゲート数に基づいて,より強い上限を求める。
代表的なSATベンチマークの実験評価により,提案手法が量子資源の大幅な,一貫した削減をもたらすことが示された。
- 参考スコア（独自算出の注目度）: 1.3267048706241158
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Boolean Satisfiability (SAT) problem is a canonical NP-complete problem and a natural candidate for quantum acceleration via search-based algorithms. In Grover-based quantum SAT solvers, the dominant computational cost stems from the construction of a reversible oracle that evaluates the Boolean formula, rendering the choice of SAT encoding crucial for overall quantum resource efficiency. Although SAT instances are conventionally expressed in Conjunctive Normal Form (CNF), such encodings typically translate into quantum circuits with significant qubit overhead and high non-Clifford gate complexity. In this work, we investigate an Exclusive-Sum-of-Products (ESOP)-based CNF (e-CNF) representation tailored for quantum SAT solving and analyze its impact on oracle construction. We derive tighter upper bounds on qubit requirements and Clifford+$T$ gate counts for Grover-based SAT solvers when e-CNF encodings are employed in place of standard CNF. In addition, we propose a scalable transformation from Boolean formulas to e-CNF and present a systematic procedure for interpreting e-CNF representations as reversible quantum circuits suitable for oracle implementation. Experimental evaluation on representative SAT benchmarks demonstrates that the proposed e-CNF-based approach yields substantial and consistent reductions in quantum resources, including qubit count, T-gate complexity, and circuit depth, when compared to CNF-based oracle constructions. These results establish e-CNF as an effective quantum-aware SAT encoding that significantly improves the practicality of oracle-based quantum SAT solving.
- Abstract（参考訳）: Boolean Satisfiability (SAT) 問題は標準NP完全問題であり、探索に基づくアルゴリズムによる量子加速の自然な候補である。
グロバーをベースとした量子SATソルバでは、計算コストはブール式を評価する可逆的なオラクルの構築に起因している。
SATインスタンスは、通常、接続正規形式(CNF)で表されるが、そのような符号化は通常、量子回路に変換され、量子ビットオーバーヘッドが大きく、非クリフォードゲートの複雑さが高い。
本研究では, 量子SAT法に適したESOP(Exclusive-Sum-of-Products)ベースのCNF(e-CNF)表現について検討し, オーラクル構造への影響を分析する。
我々は,標準CNFの代わりにe-CNF符号化を用いる場合,GroverベースのSATソルバに対して,キュービット要求の上限とClifford+$T$ゲート数を求める。
さらに、ブール式からe-CNFへのスケーラブルな変換を提案し、オラクル実装に適した可逆量子回路としてe-CNF表現を解釈するための体系的な手順を提案する。
代表的なSATベンチマークを用いた実験により,提案手法は量子ビット数,Tゲート複雑性,回路深さなどの量子資源をCNFベースのオラクル構造と比較した場合,相当かつ一貫した減少をもたらすことが示された。
これらの結果から,e-CNFを有効量子認識SAT符号化として確立し,オラクルベースの量子SAT解決の実用性を大幅に向上させる。
関連論文リスト
- EQISA: Energy-efficient Quantum Instruction Set Architecture using Sparse Dictionary Learning [0.7856998585396422]
固定深さの離散ソロワ・キタエフ基底で量子回路を合成するエネルギー効率のよい量子命令セットアーキテクチャ(EQISA)を導入する。
このアプローチは、システムサイズで60%以上の量子命令ストリームの圧縮を示すベンチマーク量子回路で評価される。
論文 参考訳（メタデータ） (2026-03-21T04:42:10Z) - Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
多重入力多重出力(MIMO)は6G通信において重要であり、スペクトル効率と信頼性の向上を提供する。
本稿では、送信機と受信機の両方でbビット量子化位相シフト器の問題に対処するために、量子近似最適化アルゴリズム(QAOA)と交互最適化を適用することを検討する。
この量子化ビームフォーミング問題の構造はQAOAのようなハイブリッド古典的手法と自然に一致し、ビームフォーミングで使われる位相シフトは量子回路の回転ゲートに直接マッピングできる。
論文 参考訳（メタデータ） (2025-10-07T17:53:02Z) - RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
変分量子アルゴリズム(VQA)は、ノイズ中間スケール量子(NISQ)コンピュータを活用するための有望なアプローチである。
与えられたVQA問題を効率的に解く最適な量子回路を選択することは、非自明な作業である。
量子アーキテクチャ探索(QAS)アルゴリズムは、与えられた問題に合わせた量子回路の自動生成を可能にする。
論文 参考訳（メタデータ） (2025-06-04T08:30:35Z) - qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking [2.178037930899554]
我々はGroverのアルゴリズムを用いた回路の等価性チェックのための効率的な量子SATソルバを提案する。
共役正規形式等価節の排他的帰結に基づく生成は、量子回路解釈のゲートと深さを最小化し、より少ない量子ビットを要求する。
論文 参考訳（メタデータ） (2024-09-05T21:25:38Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Towards a SAT Encoding for Quantum Circuits: A Journey From Classical
Circuits to Clifford Circuits and Beyond [3.610459670994051]
任意の量子回路に適用可能な命題SAT符号化を提案する。
量子状態を表現することの本質的な複雑さのため、そのようなエンコーディングを構築することは一般には不可能である。
提案手法がClifford回路のクラスにどのように適用できるかを明確に示す。
論文 参考訳（メタデータ） (2022-03-01T19:00:02Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - A Quantum-Inspired Classical Solver for Boolean k-Satisfiability
Problems [0.0]
本稿では,k-satisfiability(k-SAT)問題に対するアルゴリズム的アプローチについて述べる。
次に、AmplifySATの強みと限界を特定するために、古典的なデジタルまたはアナログコンピューティング環境でこの設定を有意義に活用することについて議論する。
論文 参考訳（メタデータ） (2021-09-21T16:10:52Z) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
本稿では、QAS(Quantum Architecture Search)と呼ばれるリソースと実行時の効率的なスキームを提案する。
QASは、よりノイズの多い量子ゲートを追加することで得られる利点と副作用のバランスをとるために、自動的にほぼ最適アンサッツを求める。
数値シミュレータと実量子ハードウェアの両方に、IBMクラウドを介してQASを実装し、データ分類と量子化学タスクを実現する。
論文 参考訳（メタデータ） (2020-10-20T12:06:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。