論文の概要: A quantum analogue of convex optimization
- arxiv url: http://arxiv.org/abs/2510.02151v1
- Date: Thu, 02 Oct 2025 16:03:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-03 16:59:21.197275
- Title: A quantum analogue of convex optimization
- Title（参考訳）: 凸最適化の量子アナログ
- Authors: Eunou Lee,
- Abstract要約: 制約のない凸最適化の量子アナログを導入する。
我々は、凸ポテンシャルを持つシュリンガー作用素 $h = -Delta + V の最小固有値を計算する。
我々は低エネルギー空間に集中できる新しい技術を用いて分析する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schr\"odinger operator $h = -\Delta + V $ with convex potential $V:\mathbb R^n \rightarrow \mathbb R_{\ge 0}$ such that $V(x)\rightarrow\infty $ as $\|x\|\rightarrow\infty$. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of $h$ up to error $\epsilon$ in polynomial time in $n$, $1/\epsilon$, and parameters that depend on $V$. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an $n$-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an $n$-dimensional region that is defined by $m$ linear constraints in polynomial time in $n$, $m$, $1/\epsilon$ and the radius $R$ of a ball encompassing the region.
- Abstract（参考訳）: 凸最適化は最適化の理論と実践の背後にある動力源である。
制約のない凸最適化の量子アナログ: シュル・オジンガー作用素 $h = -\Delta + V $ with convex potential $V:\mathbb R^n \rightarrow \mathbb R_{\ge 0}$ {\displaystyle $V(x)\rightarrow\infty $ as $\|x\|\rightarrow\infty$} の最小固有値を計算する。
この問題に対して、基本ギャップアルゴリズム (FGA) と呼ばれる効率的な量子アルゴリズムを提案し、このアルゴリズムは最小固有値$h$から誤差$\epsilon$まで多項式時間で$n$、$/\epsilon$、および$V$に依存するパラメータを計算する。
基底状態の断熱的進化はキーサブルーチンとして利用され、低エネルギー空間に集中できる新しい技術を用いて解析する。
我々は、FGAを用いて、$n$次元凸ドラムの最低周波数を求める最初の多項式時間アルゴリズム、または、その領域を含む球の半径$R$と$n$, $m$, $1/\epsilon$の多項式時間における線形制約で定義される$n$次元領域上のディリクレ・ラプラシアンの最小固有値を求める。
関連論文リスト
- Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。
行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-11T12:43:58Z) - 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) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - An Improved Classical Singular Value Transformation for Quantum Machine Learning [2.3326951882644553]
量子機械学習(QML)における量子スピードアップについて,量子特異値変換(QSVT)フレームワークを解析して検討する。
我々の重要な洞察は、行列安定性を計算するための反復的手法であるClenshaw繰り返しと、QSVTを古典的にシミュレートするスケッチ技術を組み合わせることである。
論文 参考訳（メタデータ） (2023-03-02T18:53:03Z) - 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) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Greedy Adversarial Equilibrium: An Efficient Alternative to
Nonconvex-Nonconcave Min-Max Optimization [28.431572772564518]
リプシッツの$varepsilon$-greedy逆数モデルは任意の出発点から$max_z f(x, z)$に収束することを示す。
また、リプシッツの$nabla_y f(x,y)$が$d$, $1/varepsilon$であり、$nabla2_y f(x,y)$上の境界は$nabla2_yであることを示す。
論文 参考訳（メタデータ） (2020-06-22T16:03:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。