論文の概要: Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields
- arxiv url: http://arxiv.org/abs/2408.06571v1
- Date: Tue, 13 Aug 2024 02:09:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 18:56:02.658415
- Title: Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields
- Title（参考訳）: 急速振動する横磁場をもつスピンガラス問題の反復量子最適化
- Authors: Brandon Barton, Jacob Sagal, Sean Feeney, George Grattan, Pratik Patnaik, Vadim Oganesyan, Lincoln D Carr, Eliot Kapit,
- Abstract要約: IST-SAT(Iterative Symphonic Tunneling for Satisfiability Problem)と呼ばれる新しい反復量子アルゴリズムを導入する。
IST-SATは高周波振動横場を用いた量子スピンガラス最適化問題を解く。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we introduce a new iterative quantum algorithm, called Iterative Symphonic Tunneling for Satisfiability problems (IST-SAT), which solves quantum spin glass optimization problems using high-frequency oscillating transverse fields. IST-SAT operates as a sequence of iterations, in which bitstrings returned from one iteration are used to set spin-dependent phases in oscillating transverse fields in the next iteration. Over several iterations, the novel mechanism of the algorithm steers the system toward the problem ground state. We benchmark IST-SAT on sets of hard MAX-3-XORSAT problem instances with exact state vector simulation, and report polynomial speedups over trotterized adiabatic quantum computation (TAQC) and the best known semi-greedy classical algorithm. When IST-SAT is seeded with a sufficiently good initial approximation, the algorithm converges to exact solution(s) in a polynomial number of iterations. Our numerical results identify a critial Hamming radius(CHR), or quality of initial approximation, where the time-to-solution crosses from exponential to polynomial scaling in problem size. By combining IST-SAT with future classical or quantum approximation algorithms, larger gains may be achieved. The mechanism we present in this work thus presents a new path toward achieving quantum advantage in optimization.
- Abstract（参考訳）: 本研究では,高周波振動逆場を用いた量子スピンガラス最適化問題を解くため,IST-SATと呼ばれる新しい反復型量子アルゴリズムを提案する。
IST-SATは、一イテレーションから返されるビットストリングを用いて、次のイテレーションで横フィールドを振動させる際のスピン依存位相を設定する一連のイテレーションとして動作する。
数回にわたり、アルゴリズムの新たなメカニズムが問題基底状態に向けてシステムを操る。
我々は, IST-SAT を MAX-3-XORSAT 問題インスタンスの厳密な状態ベクトルシミュレーションを用いてベンチマークし, トロッタ型アディバティック量子計算 (TAQC) による多項式の高速化を報告する。
IST-SAT が十分に良い初期近似でシードされるとき、アルゴリズムは多項式数の反復において正確な解(s)に収束する。
数値計算により,時間と解法が指数関数から多項式のスケーリングにまたがる初期近似の精度を,限界ハミング半径(CHR)と同定した。
IST-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) - Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。
本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。
我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
論文 参考訳（メタデータ） (2024-07-24T12:06:37Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - Indirect Quantum Approximate Optimization Algorithms: application to the
TSP [1.1786249372283566]
量子交互作用素 Ansatz はベクトルの集合を記述するハミルトニアンを効率的にモデル化するためにユニタリ作用素の一般パラメータ化された族を考える。
このアルゴリズムは,(1)量子マシン上で実行される量子パラメトリゼーション回路が弦ベクトルの集合をモデル化し,(2)古典機械で実行される古典的メタ最適化ループ,(3)各弦ベクトル計算の平均コストを推定する。
論文 参考訳（メタデータ） (2023-11-06T17:39:14Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
本稿では,3次元非拘束二項最適化(QUBO)問題と準拘束非拘束離散最適化(QUDO)問題を一方の相互作用で解くアルゴリズムを提案する。
提案手法は, 仮想時間進化を適用し, 最大振幅を得るために一連の部分的トレースを行う量子状態のシミュレーションに基づく。
論文 参考訳（メタデータ） (2023-09-19T10:45:15Z) - 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) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - A Quantum-Inspired Classical Solver for Boolean k-Satisfiability
Problems [0.0]
本稿では,k-satisfiability(k-SAT)問題に対するアルゴリズム的アプローチについて述べる。
次に、AmplifySATの強みと限界を特定するために、古典的なデジタルまたはアナログコンピューティング環境でこの設定を有意義に活用することについて議論する。
論文 参考訳（メタデータ） (2021-09-21T16:10:52Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。