論文の概要: Quantum Algorithm for Online Exp-concave Optimization
- arxiv url: http://arxiv.org/abs/2410.19688v1
- Date: Fri, 25 Oct 2024 16:58:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-28 13:36:19.296892
- Title: Quantum Algorithm for Online Exp-concave Optimization
- Title（参考訳）: オンラインExp-concave最適化のための量子アルゴリズム
- Authors: Jianhao He, Chengchang Liu, Xutong Liu, Lvzhou Li, John C. S. Lui,
- Abstract要約: 本稿では,量子オンライン準ニュートン法を提案する。
提案手法は, 量子推定不正確な勾配によりヘシアンを近似する。
このような後悔は、最適古典アルゴリズムを$T2/3$の係数で改善する。
- 参考スコア（独自算出の注目度）: 30.962392035110135
- License:
- Abstract: We explore whether quantum advantages can be found for the zeroth-order feedback online exp-concave optimization problem, which is also known as bandit exp-concave optimization with multi-point feedback. We present quantum online quasi-Newton methods to tackle the problem and show that there exists quantum advantages for such problems. Our method approximates the Hessian by quantum estimated inexact gradient and can achieve $O(n\log T)$ regret with $O(1)$ queries at each round, where $n$ is the dimension of the decision set and $T$ is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of $T^{2/3}$.
- Abstract（参考訳）: マルチポイントフィードバックを用いたBandit exp-concave最適化としても知られる,ゼロ階フィードバックのオンラインexp-concave最適化問題に対して,量子的優位性を見出すことができるかを検討する。
本稿では,この問題に対処する量子オンライン準ニュートン法を提案し,そのような問題に対して量子的優位性が存在することを示す。
提案手法は, 量子推定不正確な勾配によりヘシアンを近似し, それぞれのラウンドで$O(1)$クエリで$O(n\log T)$ regretを達成し, 決定セットの次元は$n$, $T$は総決定ラウンドである。
このような後悔は、最適古典アルゴリズムを$T^{2/3}$の係数で改善する。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - 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) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Optimal Stochastic Non-smooth Non-convex Optimization through
Online-to-Non-convex Conversion [56.92236659731376]
本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。
決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
論文 参考訳（メタデータ） (2023-02-07T22:09:20Z) - 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) - Quantum Algorithm for Online Convex Optimization [4.702729080310267]
ゼロ階オンライン凸最適化問題に対して量子的優位性を求める。
本稿では,この問題に対する量子アルゴリズムを提案し,量子的優位性の可能性を示す。
論文 参考訳（メタデータ） (2020-07-29T18:34:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。