論文の概要: Karush-Kuhn-Tucker conditions for non-commutative optimization problems
- arxiv url: http://arxiv.org/abs/2311.18707v2
- Date: Thu, 15 Feb 2024 18:57:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-16 23:35:31.475137
- Title: Karush-Kuhn-Tucker conditions for non-commutative optimization problems
- Title（参考訳）: 非可換最適化問題に対するKarush-Kuhn-Tucker条件
- Authors: Mateus Ara\'ujo, Igor Klep, Andrew J. P. Garner, Tam\'as V\'ertesi and
Miguel Navascu\'es
- Abstract要約: 問題変数、状態および演算子最適条件の小さなバリエーションを通して導出する。
状態最適条件は、すべてのアルキメデス(つまり有界)NPO問題によって満たされる。
作用素最適条件は、KKT(Karush-Kuhn-Tucker)条件の非可換類似である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of optimizing the state average of a polynomial of
non-commuting variables, over all states and operators satisfying a number of
polynomial constraints, and over all Hilbert spaces where such states and
operators are defined. Such non-commutative polynomial optimization (NPO)
problems are routinely solved through hierarchies of semidefinite programming
(SDP) relaxations. By phrasing the general NPO problem in Lagrangian form, we
heuristically derive, via small variations on the problem variables, state and
operator optimality conditions, both of which can be enforced by adding new
positive semidefinite constraints to the SDP hierarchies. State optimality
conditions are satisfied by all Archimedean (that is, bounded) NPO problems,
and allow enforcing a new type of constraints: namely, restricting the
optimization over states to the set of common ground states of an arbitrary
number of operators. Operator optimality conditions are the non-commutative
analogs of the Karush-Kuhn-Tucker (KKT) conditions, which are known to hold in
many classical optimization problems. In this regard, we prove that a weak form
of non-commutative operator optimality holds for all Archimedean NPO problems;
stronger versions require the problem constraints to satisfy some qualification
criterion, just like in the classical case. We test the power of the new
optimality conditions by computing local properties of ground states of
many-body spin systems and the maximum quantum violation of Bell inequalities.
- Abstract（参考訳）: 我々は、非可換変数の多項式の状態平均、多くの多項式制約を満たすすべての状態と作用素、およびそのような状態と作用素が定義されるすべてのヒルベルト空間の状態平均を最適化する問題を考える。
このような非可換多項式最適化(NPO)問題は、半定値プログラミング(SDP)緩和の階層によって日常的に解決される。
一般 NPO 問題をラグランジュ形式で表現することにより、問題変数、状態および演算子最適条件の小さな変分を通じてヒューリスティックに導出し、どちらも SDP 階層に新しい正の半定値制約を加えることで強制することができる。
状態最適条件は、すべてのアルキメデス(すなわち有界)の NPO 問題によって満たされ、新しいタイプの制約、すなわち、任意の数の作用素の共通基底状態の集合に状態に対する最適化を制限することができる。
作用素最適条件 (OperatorOptimity conditions) は、カルーシュ=クーン=タッカー条件 (KKT) の非可換アナログであり、多くの古典的な最適化問題において成立することが知られている。
この点において、非可換作用素最適性の弱い形式が全てのアルキメデス NPO 問題に対して成立することを証明する。
我々は,多体スピン系の基底状態の局所的性質とベル不等式最大量子違反を計算し,新しい最適条件のパワーを検証した。
関連論文リスト
- One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
NP完全制約最適化問題を解くための統一量子古典的枠組みを提案する。
QCPのパラメータ化アンサッツクラスは、生成したサブコーン内の最適値を常にキャプチャすることを示す。
論文 参考訳（メタデータ） (2024-11-01T08:00:30Z) - 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) - Non-commutative optimization problems with differential constraints [0.0]
作用素変数のサブセットが通常の微分方程式の系を満たすような NPO 問題の変種について検討する。
これにより、元の微分問題に取り組むために、SDPの完全な階層を定義することができる。
この手法を用いて、半デバイス非依存の方法で量子時系列を外挿する。
論文 参考訳（メタデータ） (2024-08-05T15:46:57Z) - QSlack: A slack-variable approach for variational quantum semi-definite
programming [5.0579795245991495]
量子コンピュータは、最もよく知られた古典的アルゴリズムのスピードアップを提供することができる。
半定値および線形プログラムを含む最適化問題の解法を示す。
これらの問題に対する予備問題と双対問題の両方の実装が、基礎的真理に近づいていることが示される。
論文 参考訳（メタデータ） (2023-12-06T19:00:01Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality
Conditions, Algorithm and Convergence [4.886985244621422]
我々は $ell_p$ ノルムの次数と $ell_p$ 球の正規錐の次数を計算する。
逐次最適性条件は反復的に重み付けされたアルゴリズムに対して容易に満足できることを示す。
論文 参考訳（メタデータ） (2021-10-27T02:17:42Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Parity Quantum Optimization: Compiler [0.4194295877935867]
任意の$k$-body相互作用とサイド条件からなる最適化問題を解くことを目的としたパリティ量子最適化を導入する。
この方法は、ハイパーグラフの一般化閉サイクルを用いた任意の$k$-body項による問題グラフの分解を導入する。
論文 参考訳（メタデータ） (2021-05-13T12:35:57Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。