論文の概要: Quantum Bayesian Optimization

• arxiv url: http://arxiv.org/abs/2310.05373v1
• Date: Mon, 9 Oct 2023 03:10:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-12 08:01:29.547847
• Title: Quantum Bayesian Optimization
• Title（参考訳）: 量子ベイズ最適化
• Authors: Zhongxiang Dai, Gregory Kang Ruey Lau, Arun Verma, Yao Shu, Bryan Kian Hsiang Low, Patrick Jaillet
• Abstract要約: 本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
• 参考スコア（独自算出の注目度）: 64.58749619145908
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernelized bandits, also known as Bayesian optimization (BO), has been a prevalent method for optimizing complicated black-box reward functions. Various BO algorithms have been theoretically shown to enjoy upper bounds on their cumulative regret which are sub-linear in the number T of iterations, and a regret lower bound of Omega(sqrt(T)) has been derived which represents the unavoidable regrets for any classical BO algorithm. Recent works on quantum bandits have shown that with the aid of quantum computing, it is possible to achieve tighter regret upper bounds better than their corresponding classical lower bounds. However, these works are restricted to either multi-armed or linear bandits, and are hence not able to solve sophisticated real-world problems with non-linear reward functions. To this end, we introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. To the best of our knowledge, our Q-GP-UCB is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Moreover, thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm from the previous work. We use simulations, as well as an experiment using a real quantum computer, to verify that the theoretical quantum speedup achieved by our Q-GP-UCB is also potentially relevant in practice.
• Abstract（参考訳）: カーネル化された帯域幅(英: Kernelized bandits)は、複雑なブラックボックス報酬関数を最適化する一般的な方法である。 様々なBOアルゴリズムは、反復数 T のサブ線形である累積後悔の上限を満足することが理論的に示されており、古典的なBOアルゴリズムでは避けられない後悔を表す Omega(sqrt(T)) の左下限が導出されている。 量子帯域に関する最近の研究は、量子コンピューティングの助けを借りて、対応する古典的下界よりも強い後悔の上限を達成することができることを示した。 しかし、これらの作品はマルチアームまたはリニアバンディットに制限されており、従って非線形報酬関数による洗練された実世界の問題を解決することはできない。 この目的のために、量子ガウスプロセスアップパー信頼境界(Q-GP-UCB)アルゴリズムを導入する。 我々の知る限りでは、我々のq-gp-ucbは、古典的設定におけるomega(sqrt(t))の後悔の下限よりもかなり小さいo(polylog t)の後悔上限を達成することができる最初のboアルゴリズムである。 さらに, 線形カーネルを用いたQ-GP-UCBは, 従来の量子線形 UCB アルゴリズムに比べ, 新たな信頼性楕円体解析により, より少ない残差を達成できた。 シミュレーションや実量子コンピュータを用いた実験を用いて、Q-GP-UCBが達成した理論的量子スピードアップが、実際においても有意であることを示す。

関連論文リスト

• An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
  証明可能な指数的量子スピードアップは、線形系を解くためのセミナルHHL量子アルゴリズム以来、中心的な研究目標となっている。 量子と量子に着想を得た古典的アルゴリズム間で、このような証明可能な指数的分離を初めて提示する。
  論文  参考訳（メタデータ） (2024-11-04T13:49:26Z)
• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。 本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。 本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
  論文  参考訳（メタデータ） (2024-07-29T17:13:01Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。 深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
  論文  参考訳（メタデータ） (2023-09-22T18:00:03Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  ガウス過程上信頼境界 (GP-UCB) アルゴリズムは, ほぼ最適の後悔率を有することを示す。 私たちの改善は、基盤となるカーネルの滑らかさに比例してカーネルリッジ推定を正規化するという、重要な技術的貢献に依存しています。
  論文  参考訳（メタデータ） (2023-07-14T13:56:11Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• Limitations of variational quantum algorithms: a quantum optimal transport approach [11.202435939275675]
  我々は、ノイズとノイズレスの両体制において、標準NISQ提案の極めて厳密な境界を得る。 境界は、QAOAのような両方の回路モデルアルゴリズムと、量子アニールのような連続時間アルゴリズムの性能を制限する。
  論文  参考訳（メタデータ） (2022-04-07T13:58:44Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。