論文の概要: A Quantum-Inspired Classical Solver for Boolean k-Satisfiability
Problems
- arxiv url: http://arxiv.org/abs/2109.10291v1
- Date: Tue, 21 Sep 2021 16:10:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-14 03:12:28.671116
- Title: A Quantum-Inspired Classical Solver for Boolean k-Satisfiability
Problems
- Title（参考訳）: ブールk-満足度問題に対する量子インスピレーション古典解法
- Authors: S. Andrew Lanham and Brian R. La Cour
- Abstract要約: 本稿では,k-satisfiability(k-SAT)問題に対するアルゴリズム的アプローチについて述べる。
次に、AmplifySATの強みと限界を特定するために、古典的なデジタルまたはアナログコンピューティング環境でこの設定を有意義に活用することについて議論する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we detail a classical algorithmic approach to the
k-satisfiability (k-SAT) problem that is inspired by the quantum amplitude
amplification algorithm. This work falls under the emerging field of
quantum-inspired classical algorithms. To propose our modification, we adopt an
existing problem model for k-SAT known as Universal SAT (UniSAT), which casts
the Boolean satisfiability problem as a non-convex global optimization over a
real-valued space. The quantum-inspired modification to UniSAT is to apply a
conditioning operation to the objective function that has the effect of
"amplifying" the function value at points corresponding to optimal solutions.
We describe the algorithm for achieving this amplification, termed
"AmplifySAT," which follows a familiar two-step process of applying an
oracle-like operation followed by a reflection about the average. We then
discuss opportunities for meaningfully leveraging this processing in a
classical digital or analog computing setting, attempting to identify the
strengths and limitations of AmplifySAT in the context of existing non-convex
optimization strategies like simulated annealing and gradient descent.
- Abstract（参考訳）: 本稿では,量子振幅増幅アルゴリズムに触発されたk-sat問題に対する古典的なアルゴリズムアプローチについて述べる。
この研究は量子インスパイアされた古典的アルゴリズムの新興分野に属する。
提案手法では,実数値空間上での非凸大域最適化としてブール適合性問題を示す,Universal SAT (UniSAT) と呼ばれるk-SATの既存の問題モデルを採用する。
UniSATに対する量子インスパイアされた修正は、最適解に対応する点における関数値の「増幅」効果を持つ目的関数に条件付け演算を適用することである。
我々は、この増幅を達成するためのアルゴリズムを"amplifysat"と呼び、オラクルのような操作を適用して、平均について振り返る2段階のプロセスに従っている。
そこで我々は,従来の非凸最適化手法であるシミュレートアニーリングや勾配降下の文脈において,AmplifySATの強みと限界を識別し,この処理を古典的デジタルまたはアナログコンピューティング環境で有意義に活用する機会について論じる。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields [0.0]
IST-SAT(Iterative Symphonic Tunneling for Satisfiability Problem)と呼ばれる新しい反復量子アルゴリズムを導入する。
IST-SATは高周波振動横場を用いた量子スピンガラス最適化問題を解く。
論文 参考訳（メタデータ） (2024-08-13T02:09:30Z) - Compressed sensing enhanced by quantum approximate optimization algorithm [0.0]
本稿では,量子サブルーチンを用いた大規模圧縮センシング問題に対処する枠組みを提案する。
本研究は, 量子コンピュータを圧縮センシング分野に適用する有望な方法を探るものである。
論文 参考訳（メタデータ） (2024-03-26T05:26:51Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - Challenges of variational quantum optimization with measurement shot noise [0.0]
問題の大きさが大きくなるにつれて、量子資源のスケーリングが一定の成功確率に達するか検討する。
この結果から,ハイブリッド量子古典アルゴリズムは古典外ループの破壊力を回避する必要がある可能性が示唆された。
論文 参考訳（メタデータ） (2023-07-31T18:01:15Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - 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) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。