論文の概要: Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability

• arxiv url: http://arxiv.org/abs/2202.00118v1
• Date: Mon, 31 Jan 2022 22:18:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-27 05:06:07.429969
• Title: Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Title（参考訳）: ハード2-SAT問題に対する量子アニール : 最小エネルギーギャップの分布とスケーリングと成功確率
• Authors: Vrinda Mehta, Fengping Jin, Hans De Raedt, and Kristel Michielsen
• Abstract要約: 量子アニールアルゴリズムのスケーリング複雑性を解析する。 最小エネルギーギャップの分布と成功確率について検討する。 また、D-Wave Systems Inc.の量子アニールを用いて、2-SAT問題の解法の性能について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiabilty (2-SAT) problems, consisting of upto 18-variables problems, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types : ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We found that although the scaling of the run-time is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Lastly, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.
• Abstract（参考訳）: 近年、量子アニーリングは様々な最適化問題を解決する有望な候補となっている。 最大18変数の問題からなるハードな2-サフィアビリティ(2-SAT)問題を用いて、量子アニールアルゴリズムのスケーリング複雑性を分析し、最小エネルギーギャップと成功確率の分布について検討する。 我々は、強磁性と反強磁性の2種類からなるトリガーハミルトニアンという用語を導入することで、標準量子アニール化ハミルトニアンの解析を拡張する。 これらのトリガーを用いて、選択された2-SAT問題の解法の成功確率への影響を研究する。 その結果、ランタイムのスケーリングは、標準および修正された量子アニーリングハミルトニアンに対して指数関数的であるが、トリガーハミルトニアンを追加する場合のスケーリング定数は、かなり小さくなることがわかった。 さらに、トリガーハミルトニアンとアニーリング時間の特定の選択は、シミュレーションアニーリングよりも優れたスケーリングをもたらす可能性がある。 最後に、D-Wave Systems Inc. の量子アニールを用いて、2-SAT問題の解法におけるそれらの性能を調べ、シミュレーション結果と比較する。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Hybrid Oscillator-Qubit Quantum Processors: Simulating Fermions, Bosons, and Gauge Fields [31.51988323782987]
  我々は,強い相関を持つフェルミオンとボソンの量子シミュレーションのためのハイブリッド発振器量子ビットプロセッサフレームワークを開発した。 この枠組みは、ベーカー・カンベル・ハウスドルフの公式に基づく近似法と同様に、粒子相互作用の正確な分解を与える。 我々の研究は超伝導ハードウェアの実装に焦点を当てているが、我々のフレームワークはトラップされたイオンや中性原子ハードウェアにも使用できる。
  論文  参考訳（メタデータ） (2024-09-05T17:58:20Z)
• Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver [1.0916270449935084]
  変分量子固有解法 (VQE) は、量子シミュレーションのためのハイブリッド量子古典的アルゴリズムである。 VQEの課題は、真の基底状態と基底状態エネルギーが未知のとき、アルゴリズムの出力解が真の基底状態にどの程度近いかを知ることである。 ハミルトン再構成の最近の発展は、ハミルトン固有解問題に対する変分解の質を評価するために計量を与えることができる。
  論文  参考訳（メタデータ） (2024-03-18T17:28:06Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  量子回路ボルンマシン(QCBM)と量子生成逆ネットワーク(QGAN)の学習可能性について検討する。 まず、QCBMの一般化能力を解析し、量子デバイスがターゲット分布に直接アクセスできる際の優位性を同定する。 次に、QGANの一般化誤差境界が、採用されるAnsatz、クォーディットの数、入力状態に依存することを示す。
  論文  参考訳（メタデータ） (2022-05-10T08:05:59Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。 シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
  論文  参考訳（メタデータ） (2022-03-04T19:00:45Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。 問題の難易度は解の縮退と局所ミニマの数によって制御される。 最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
  論文  参考訳（メタデータ） (2022-02-18T19:00:01Z)
• Quantum Circuits For Two-Dimensional Isometric Tensor Networks [0.0]
  我々は2次元テンソルネットワーク(isoTNS)の量子回路バージョンについて詳細に記述し、これをqisoTNSと呼ぶ。 2つの異なる2次元スピン1/2ハミルトニアン上でのQisoTNSの性能をベンチマークする。
  論文  参考訳（メタデータ） (2021-08-05T18:00:26Z)
• The quantum annealing gap and quench dynamics in the exact cover problem [0.0]
  アナリングはゆっくりと変化するパラメータを持つハミルトンの平衡位相を探索する。 クエンチはハミルトンの急激な変化であり、非平衡状態を生み出している。
  論文  参考訳（メタデータ） (2021-06-15T12:43:23Z)
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems [0.0]
  本研究では,Ising型ハミルトニアンに代表される2-サフタビリティ(2-SAT)問題と,2-SAT問題ハミルトニアンに余分なカップリングを加えて得られる非確率問題という2つの問題に対する量子アニールの性能について検討する。
  論文  参考訳（メタデータ） (2021-06-09T07:41:08Z)
• Variational Quantum Eigensolver for Frustrated Quantum Systems [0.0]
  変分量子固有解法(VQE)は、量子ハミルトニアンによって指定されたエネルギーランドスケープにおける大域最小値を決定するように設計されている。 本稿では、1次元のフェルミオン連鎖を記述するハバード様モデルに対するVQE手法の性能について考察する。 また、ハミルトニアンに対するバレンプラトー現象の研究を行い、この効果の重大性はフェルミオンの量子ビットへの符号化に依存することを示した。
  論文  参考訳（メタデータ） (2020-05-01T18:00:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。