論文の概要: Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits
- arxiv url: http://arxiv.org/abs/2209.12897v1
- Date: Mon, 26 Sep 2022 03:19:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 16:46:08.787980
- Title: Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits
- Title（参考訳）: 概凸関数最適化の量子スピードアップと対数的後悔確率凸バンドへの応用
- Authors: Tongyang Li, Ruizhe Zhang
- Abstract要約: 量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 8.682187438614296
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We initiate the study of quantum algorithms for optimizing approximately
convex functions. Given a convex set ${\cal K}\subseteq\mathbb{R}^{n}$ and a
function $F\colon\mathbb{R}^{n}\to\mathbb{R}$ such that there exists a convex
function $f\colon\mathcal{K}\to\mathbb{R}$ satisfying $\sup_{x\in{\cal
K}}|F(x)-f(x)|\leq \epsilon/n$, our quantum algorithm finds an $x^{*}\in{\cal
K}$ such that $F(x^{*})-\min_{x\in{\cal K}} F(x)\leq\epsilon$ using
$\tilde{O}(n^{3})$ quantum evaluation queries to $F$. This achieves a
polynomial quantum speedup compared to the best-known classical algorithms. As
an application, we give a quantum algorithm for zeroth-order stochastic convex
bandits with $\tilde{O}(n^{5}\log^{2} T)$ regret, an exponential speedup in $T$
compared to the classical $\Omega(\sqrt{T})$ lower bound. Technically, we
achieve quantum speedup in $n$ by exploiting a quantum framework of simulated
annealing and adopting a quantum version of the hit-and-run walk. Our speedup
in $T$ for zeroth-order stochastic convex bandits is due to a quadratic quantum
speedup in multiplicative error of mean estimation.
- Abstract（参考訳）: 概凸関数を最適化するための量子アルゴリズムの研究を開始する。
凸集合 ${\cal k}\subseteq\mathbb{r}^{n}$ と関数 $f\colon\mathbb{r}^{n}\to\mathbb{r}$ が与えられたとき、その凸関数 $f\colon\mathcal{k}\to\mathbb{r}$ が $\sup_{x\in{\cal k}}|f(x)-f(x)|\leq \epsilon/n$ を満たすような凸関数 $f(x^{*})-\min_{x\in{\cal k}} f(x)\leq\epsilon$ が $f(x^{*})-\tilde{o}(n^{3})$ で$f(x)-f(x)|\leq \epsilon/n$ を満たすように、量子アルゴリズムは $x^{*}\in{\cal k}$ を求める。
これは、よく知られた古典的アルゴリズムと比較して多項式量子スピードアップを達成する。
例として、ゼロ次確率凸バンドの量子アルゴリズムを$\tilde{o}(n^{5}\log^{2} t)$ regretで与え、従来の$\omega(\sqrt{t})$lowboundと比較して指数速度が$t$である。
技術的には、シミュレーションアニーリングの量子フレームワークを利用し、ヒットアンドランウォークの量子バージョンを採用することで、量子スピードアップをn$で達成する。
ゼロ階確率凸バンディットの$T$での高速化は、平均推定の乗算誤差の2次量子スピードアップに起因する。
関連論文リスト
- Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - The classical limit of Quantum Max-Cut [0.18416014644193066]
我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。
半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
論文 参考訳（メタデータ） (2024-01-23T18:53:34Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。