論文の概要: SAT, Gadgets, Max2XOR, and Quantum Annealers
- arxiv url: http://arxiv.org/abs/2403.00182v1
- Date: Thu, 29 Feb 2024 23:18:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-05 18:46:08.327480
- Title: SAT, Gadgets, Max2XOR, and Quantum Annealers
- Title（参考訳）: SAT、ガジェット、Max2XOR、量子アニール
- Authors: Carlos Ans\'otegui and Jordi Levy
- Abstract要約: SATをMax2XORに還元するガジェットをいくつか提示する。
SATインスタンスを量子アニールの初期構成に変換する方法を示す。
- 参考スコア（独自算出の注目度）: 2.0450716801079443
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum Annealers are basically quantum computers that with high probability
can optimize certain quadratic functions on Boolean variables in constant time.
These functions are basically the Hamiltonian of Ising models that reach the
ground energy state, with a high probability, after an annealing process. They
have been proposed as a way to solve SAT.
These Hamiltonians can be seen as Max2XOR problems, i.e. as the problem of
finding an assignment that maximizes the number of XOR clauses of at most 2
variables that are satisfied. In this paper, we present several gadgets to
reduce SAT to Max2XOR. We show how they can be used to translate SAT instances
to initial configurations of a quantum annealer.
- Abstract（参考訳）: 量子アナラー(Quantum Annealers)は、基本的には確率の高い量子コンピュータであり、ブール変数上の特定の二次関数を一定時間で最適化することができる。
これらの関数は基本的に、アニール過程の後、高い確率で基底エネルギー状態に達するイジング模型のハミルトニアンである。
SATを解く方法として提案されている。
これらのハミルトニアンはマックス2XOR問題、すなわち、満たされる少なくとも2つの変数のXOR節数を最大化する代入を見つける問題と見なすことができる。
本稿では,SAT を Max2XOR に還元するガジェットをいくつか提示する。
SATインスタンスを量子アニールの初期構成に変換する方法を示す。
関連論文リスト
- 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) - 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) - Quantum Computing and the Riemann Hypothesis [0.0]
量子コンピューティングは、古典的なアルゴリズムに対する潜在的なスピードアップを提供する量子アルゴリズムによる、有望な新しいコンピューティング領域である。
超対称性量子力学における状態として関数を得る方法を示す。
論文 参考訳（メタデータ） (2023-03-07T04:28:54Z) - Quantum annealing for hard 2-SAT problems : Distribution and scaling of
minimum energy gap and success probability [0.0]
量子アニールアルゴリズムのスケーリング複雑性を解析する。
最小エネルギーギャップの分布と成功確率について検討する。
また、D-Wave Systems Inc.の量子アニールを用いて、2-SAT問題の解法の性能について検討する。
論文 参考訳（メタデータ） (2022-01-31T22:18:35Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。
そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文 参考訳（メタデータ） (2021-07-15T04:47:35Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Quantum algorithm of a set of quantum 2-sat problem [0.0]
本稿では,量子2-満足度(Q2SAT)問題に対する量子断熱アルゴリズムを提案する。
Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
論文 参考訳（メタデータ） (2020-09-05T21:01:27Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。