論文の概要: First-order optimality conditions for non-commutative optimization problems
- arxiv url: http://arxiv.org/abs/2311.18707v4
- Date: Fri, 22 Nov 2024 15:41:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-25 18:36:06.035886
- Title: First-order optimality conditions for non-commutative optimization problems
- Title（参考訳）: 非可換最適化問題に対する一階最適条件
- Authors: Mateus Araújo, Igor Klep, Andrew J. P. Garner, Tamás Vértesi, Miguel Navascués,
- Abstract要約: 非可換変数の導出状態平均を最適化する問題を考察する。
状態最適条件はすべてのNPO問題によって満たされる。
作用素最適条件はカルーシュ=クーン=タッカー条件の非可換類似である。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- 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 formulating the general NPO problem in Lagrangian terms, we heuristically derive first-order optimality conditions via small variations in the problem variables. Although the derivation is not rigorous, it gives rise to two types of optimality conditions - state and operator - which are rigorously analyzed in the paper. Both types of conditions can be enforced through additional positive semidefinite constraints in the SDP hierarchies. State optimality conditions are shown to be satisfied by all NPO problems. For NPO problems with optimal solutions (such as, e.g., Archimedean ones) they 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 operator optimality holds for all NPO problems; stronger versions require the problem constraints to satisfy some qualification criterion, just like in the classical case (e.g. Mangasarian-Fromovitz constraint qualification). 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 問題を定式化することにより、問題変数の小さなバリエーションを通して一階最適条件をヒューリスティックに導出する。
導出は厳密ではないが、この論文では厳密に解析された2種類の最適条件(状態と演算子)が生じる。
どちらの条件も、SDP階層における追加の正半定的制約によって強制することができる。
状態最適条件はすべてのNPO問題によって満たされる。
最適解(例えばアルキメデス問題など)を持つ 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。