論文の概要: Quantum speed-ups for solving semidefinite relaxations of polynomial optimization
- arxiv url: http://arxiv.org/abs/2511.14389v1
- Date: Tue, 18 Nov 2025 11:48:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-19 16:23:53.08395
- Title: Quantum speed-ups for solving semidefinite relaxations of polynomial optimization
- Title（参考訳）: 多項式最適化の半定緩和を解くための量子スピードアップ
- Authors: Daniel Stilck França, Ngoc Hoang Anh Mai,
- Abstract要約: 最適化のためのラッサール階層値を近似するための量子アルゴリズムについて検討する。
我々は,行列乗法重みに基づく量子アルゴリズムを提案し,その精度を$_k$と近似する。
QRAMを使わずに必要なブロックエンコーディングの実装方法を示す。
- 参考スコア（独自算出の注目度）: 3.1798318618973362
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let $f,g_1,\ldots,g_m$ be real polynomials in $n$ variables and $f^\star$ the infimum of $f$ over the semialgebraic set $S(g)=\{x: g_i(x)\ge 0\}$. Let $λ_k$ be the value of the order-$k$ Lasserre relaxation. Assume either (i) $f^\star=λ_k$ and the optimum is attained in the $\ell_1$-ball of radius $1/2$, or (ii) $S(g)$ lies in the simplex $\{x\ge 0: \sum_j x_j\le 1/2\}$, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates $λ_k$ to accuracy $\varepsilon>0$ with runtime, for fixed $k$, \[ O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), \] where $s_g$ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as $O(n^{3k}\mathrm{poly}(1/\varepsilon))$ even in the unconstrained case. As an example, we obtain an $O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$ quantum algorithm for portfolio optimization, improving over the classical $O(n^{ω+1}\log(1/\varepsilon))$ bound with $ω\approx2.373$. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.
- Abstract（参考訳）: 多項式最適化のためのラッサール階層値を近似するための量子アルゴリズムについて検討する。
f,g_1,\ldots,g_m$ を$n$変数の実多項式とし、$f^\star$ を半代数集合 $S(g)=\{x:g_i(x)\ge 0\}$ 上の$f$ の無限小とする。
λ_k$ を順序-k$ラッサール緩和の値とする。
とも。
(i)$f^\star=λ_k$と最適値は半径1/2$の$\ell_1$-ballで達成される。
(ii)$S(g)$ は単純体 $\{x\ge 0: \sum_j x_j\le 1/2\}$ にあり、制約はこの単純体を定義する。
適切な係数の再スケーリングの後、固定された$k$, \[O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!
左(s_g\!
\left[n^k\varepsilon^{-4}+\!
\left(n^{k}+\!
1}^m n^{k-d_i}\right)^{1/2}\!
\varepsilon^{-5}\right]\right), \] ここで$s_g$は、制約に関連付けられた係数マッチング行列の間隔を束縛する。
古典行列乗法は、制約のない場合でさえ、$O(n^{3k}\mathrm{poly}(1/\varepsilon))$としてスケールする。
例えば、ポートフォリオ最適化のための$O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$量子アルゴリズムが得られ、古典的な$O(n^{ω+1}\log(1/\varepsilon))$ω\approx2.373$よりも改善される。
提案手法は,多項式最適化におけるSDPに対する Apeldoorn と Gilyén の解析を基礎として行う。
また、必要なブロックエンコーディングをQRAMなしで実装する方法も示す。
提案手法は,ラッサール緩和計算における問題次元の超2次高速化を実現する。
関連論文リスト
- Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳（メタデータ） (2025-08-09T08:28:06Z) - Fast Convex Optimization with Quantum Gradient Methods [2.5094874597551913]
雑音関数評価オラクルを用いた量子(サブ)次次推定に基づく量子アルゴリズムについて検討する。
滑らかな条件と非滑らかな条件の両方において、ゼロ階凸最適化のための最初の次元非依存的な問合せ複雑性を示す。
半定値プログラミングと固有値最適化の接続を利用して、量子ミラー降下法を用いて、半定値プログラム、線形プログラム、ゼロサムゲームを解決するための新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2025-03-21T17:58:12Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳（メタデータ） (2023-11-13T00:45:41Z) - Quantum speedup of leverage score sampling and its application [0.0]
本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。
応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-15T14:40:18Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。