論文の概要: Linear programming with unitary-equivariant constraints
- arxiv url: http://arxiv.org/abs/2207.05713v2
- Date: Tue, 4 Apr 2023 12:28:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 19:04:06.988339
- Title: Linear programming with unitary-equivariant constraints
- Title（参考訳）: ユニタリ同値制約付き線形計画法
- Authors: Dmitry Grinko, Maris Ozols
- Abstract要約: ユニタリ同値(英: Unitary equivariance)は、物理学や数学において多くの文脈で発生する自然な対称性である。
追加の対称性の仮定の下では、この問題は、$d$でスケールしない時間で解決できる線形プログラムに還元されることを示す。
また,本手法を一般ユニタリ同変半定プログラムに拡張する可能性についても概説する。
- 参考スコア（独自算出の注目度）: 2.0305676256390934
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Unitary equivariance is a natural symmetry that occurs in many contexts in
physics and mathematics. Optimization problems with such symmetry can often be
formulated as semidefinite programs for a $d^{p+q}$-dimensional matrix variable
that commutes with $U^{\otimes p} \otimes \bar{U}^{\otimes q}$, for all $U \in
\mathrm{U}(d)$. Solving such problems naively can be prohibitively expensive
even if $p+q$ is small but the local dimension $d$ is large. We show that,
under additional symmetry assumptions, this problem reduces to a linear program
that can be solved in time that does not scale in $d$, and we provide a general
framework to execute this reduction under different types of symmetries. The
key ingredient of our method is a compact parametrization of the solution space
by linear combinations of walled Brauer algebra diagrams. This parametrization
requires the idempotents of a Gelfand-Tsetlin basis, which we obtain by
adapting a general method arXiv:1606.08900 inspired by the Okounkov-Vershik
approach. To illustrate potential applications, we use several examples from
quantum information: deciding the principal eigenvalue of a quantum state,
quantum majority vote, asymmetric cloning and transformation of a black-box
unitary. We also outline a possible route for extending our method to general
unitary-equivariant semidefinite programs.
- Abstract（参考訳）: ユニタリ同値性(unitary equivariance)は、物理学や数学の多くの文脈で起こる自然な対称性である。
このような対称性を持つ最適化問題は、u^{\otimes p} \otimes \bar{u}^{\otimes q}$, for all $u \in \mathrm{u}(d)$ で可換な$d^{p+q}$-次元行列変数の半定値プログラムとして定式化することができる。
このような問題を解決するには、もし$p+q$ が小さいが、局所次元 $d$ が大きければ、必然的に高価である。
追加の対称性仮定の下では、この問題は$d$でスケールしない時間に解くことができる線形プログラムに還元され、異なる種類の対称性の下でこの還元を実行するための一般的なフレームワークを提供する。
本手法の重要な成分は,壁付きブラウアー代数図の線形結合による解空間のコンパクトパラメトリゼーションである。
このパラメトリゼーションはゲルファント・タセリン基底の等等式を必要とし、オクンコフ・ヴェルシクのアプローチにインスパイアされた一般的な方法 arXiv:1606.08900 を適用することによって得られる。
潜在的な応用を説明するために、量子状態の主固有値の決定、量子多数決、非対称クローニング、ブラックボックスユニタリの変換など、量子情報からのいくつかの例を用いる。
また,本手法を一般ユニタリ同変半定プログラムに拡張する可能性についても概説する。
関連論文リスト
- Geometry of degenerate quantum states, configurations of $m$-planes and invariants on complex Grassmannians [55.2480439325792]
退化状態の幾何学を非アーベル接続(英語版)$A$に還元する方法を示す。
部分空間のそれぞれに付随する独立不変量を見つける。
それらのいくつかはベリー・パンチャラトナム位相を一般化し、1次元部分空間の類似点を持たないものもある。
論文 参考訳（メタデータ） (2024-04-04T06:39:28Z) - Solving the $KP$ problem with the Global Cartan Decomposition [0.5524804393257919]
本稿では,Frakp$ で $-iH(t) を制御したターゲット $-iX in [frakp,frakp] サブセット frakk$ の時間最適ユニタリを生成する新しい手法を提案する。
dTheta$の仮定は、変動的手法を用いて解析的に解ける時間最適ユニタリ制御問題と等価であることを示す。
論文 参考訳（メタデータ） (2024-04-02T23:03:16Z) - Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
MLで使用されるほとんどの数学的歪みは、本質的に自然界において積分的である。
本稿では,これらの歪みを改善するための基礎的理論とツールを公表し,機械学習の要件に対処する。
我々は、最近MLで注目を集めた問題、すなわち、ハイパーボリック埋め込みを「チープ」で正確なエンコーディングで適用する方法を示す。
論文 参考訳（メタデータ） (2024-02-06T17:21:06Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Multiplicative updates for symmetric-cone factorizations [0.0]
コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。
SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
論文 参考訳（メタデータ） (2021-08-02T09:23:39Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。