論文の概要: Quantum Algorithm for Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2007.15046v4
- Date: Fri, 1 Apr 2022 10:33:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 21:02:51.781997
- Title: Quantum Algorithm for Online Convex Optimization
- Title（参考訳）: オンライン凸最適化のための量子アルゴリズム
- Authors: Jianhao He, Feidiao Yang, Jialin Zhang, Lvzhou Li
- Abstract要約: ゼロ階オンライン凸最適化問題に対して量子的優位性を求める。
本稿では,この問題に対する量子アルゴリズムを提案し,量子的優位性の可能性を示す。
- 参考スコア（独自算出の注目度）: 4.702729080310267
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We explore whether quantum advantages can be found for the zeroth-order
online convex optimization problem, which is also known as bandit convex
optimization with multi-point feedback. In this setting, given access to
zeroth-order oracles (that is, the loss function is accessed as a black box
that returns the function value for any queried input), a player attempts to
minimize a sequence of adversarially generated convex loss functions. This
procedure can be described as a $T$ round iterative game between the player and
the adversary. In this paper, we present quantum algorithms for the problem and
show for the first time that potential quantum advantages are possible for
problems of online convex optimization. Specifically, our contributions are as
follows. (i) When the player is allowed to query zeroth-order oracles $O(1)$
times in each round as feedback, we give a quantum algorithm that achieves
$O(\sqrt{T})$ regret without additional dependence of the dimension $n$, which
outperforms the already known optimal classical algorithm only achieving
$O(\sqrt{nT})$ regret. Note that the regret of our quantum algorithm has
achieved the lower bound of classical first-order methods. (ii) We show that
for strongly convex loss functions, the quantum algorithm can achieve $O(\log
T)$ regret with $O(1)$ queries as well, which means that the quantum algorithm
can achieve the same regret bound as the classical algorithms in the full
information setting.
- Abstract（参考訳）: マルチポイントフィードバックを用いたバンド凸最適化(Bandit convex Optimization)としても知られる,ゼロ階オンライン凸最適化問題に対して,量子的優位性を求める。
この設定では、ゼロ階のオラクルへのアクセス(すなわち、損失関数は、問い合わせされた入力の関数値を返すブラックボックスとしてアクセスされる)が与えられた場合、プレイヤーは、逆向きに生成された凸損失関数のシーケンスを最小化しようとする。
この手順は、プレイヤーと相手の間のラウンドT$繰り返しゲームとして記述することができる。
本稿では,この問題に対する量子アルゴリズムを提案するとともに,オンライン凸最適化の問題に対する潜在的な量子的優位性を初めて示す。
特に、私たちの貢献は次のとおりです。
(i) プレイヤーが各ラウンドの0階オークルにフィードバックとして$O(1)$倍の値を求めることを許されたとき、次元$n$のさらなる依存を伴わずに$O(\sqrt{T})$後悔を達成できる量子アルゴリズムを与え、すでに知られている古典的アルゴリズムでは$O(\sqrt{nT})$後悔を達成できるのみである。
量子アルゴリズムの後悔は古典的な一階法の低い境界を達成したことに注意。
(II) 強い凸損失関数の場合, 量子アルゴリズムは$O(\log T)$ regret を$O(1)$ query で達成でき, つまり, 量子アルゴリズムは全情報設定において, 古典的アルゴリズムと同等の残差を達成できることを示す。
関連論文リスト
- Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
本稿では,量子オンライン準ニュートン法を提案する。
提案手法は, 量子推定不正確な勾配によりヘシアンを近似する。
このような後悔は、最適古典アルゴリズムを$T2/3$の係数で改善する。
論文 参考訳（メタデータ） (2024-10-25T16:58:44Z) - 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。
我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。
我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文 参考訳（メタデータ） (2023-04-27T14:02:54Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - The Quantum Approximate Optimization Algorithm performance with low
entanglement and high circuit depth [0.0]
変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。
最適化問題の解法における絡み合いの役割について検討する。
ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
論文 参考訳（メタデータ） (2022-07-07T16:21:36Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。