Fugu-MT 論文翻訳(概要): Fixed-point Grover Adaptive Search for QUBO Problems

論文の概要: Fixed-point Grover Adaptive Search for QUBO Problems

arxiv url: http://arxiv.org/abs/2311.05592v2
Date: Mon, 27 Nov 2023 17:12:39 GMT
ステータス: 処理完了
システム内更新日: 2023-11-30 13:05:53.297599
Title: Fixed-point Grover Adaptive Search for QUBO Problems
Title（参考訳）: QUBO問題に対する固定点グロバー適応探索
Authors: \'Akos Nagy, Jaime Park, Cindy Zhang, Atithi Acharya, Alex Khan
Abstract要約: 二次非拘束二項最適化問題に対するGrover-type法の適用と検討を行う。 n 次元 QUBO 問題に対して、我々のオラクルは回路深さとゲート数$O left(n2right)$を持つ。また,QUBO問題に対する固定点グロバー適応探索法を開発した。
参考スコア（独自算出の注目度）: 0.17499351967216342
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We apply and study a Grover-type method for Quadratic Unconstrained Binary Optimization (QUBO) problems. First, we construct a marker oracle for such problems. For an $n$-dimensional QUBO problem, these oracles have circuit depth and gate count of $O \left( n^2 \right)$. We also develop a novel Fixed-point Grover Adaptive Search for QUBO Problems, using our oracle design and a hybrid Fixed-point Grover Search of Li et al. [9]. This method has better performance guarantees than the Grover Adaptive Search of Gilliam et al. [5].
Abstract（参考訳）: 二次連立最適化(qubo)問題に対してグローバー型手法を適用し,検討した。まず、このような問題に対するマーカーオラクルを構築する。 n 次元 QUBO 問題に対して、これらのオラクルは回路深さとゲート数$O \left(n^2 \right)$を持つ。我々はまた、オラクルの設計とli et alのハイブリッド固定点グローバー探索を用いて、qubo問題に対する新しい固定点グローバー適応探索を開発した。 [9]. この方法はGrover Adaptive Search of Gilliamなどよりも優れた性能を保証する。 [5].

関連論文リスト

Novel oracle constructions for quantum random access memory [0.6445605125467572]
量子ランダムアクセスメモリのための新しい設計を提案する。我々は、プロパティの始式であるMathcalO_f left| x rightrangle_n left| 0 rightrangle_d = left| x rightrangle_n left| f(x) rightrangle_d で、オラクルを$mathcalO_f$で構築する。
論文参考訳（メタデータ） (2024-05-30T16:30:16Z)
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems [0.0]
精度で実現可能な問題を解くために、決定論的アルゴリズムは$d1+delta$ bitsのメモリを使用するか、少なくとも$1/(d0.01delta epsilon2frac1-delta1+1.01 delta-o(1))$ Oracleクエリをしなければならない。また、ランダム化アルゴリズムは$d1+delta$メモリを使用するか、少なくとも$$$$deltainに対して$1/(d2delta epsilon2(1-4delta)-o(1))$クエリを生成する。
論文参考訳（メタデータ） (2024-04-10T04:15:50Z)
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
Finding Second-Order Stationary Point for Nonconvex-Strongly-Concave Minimax Problem [16.689304539024036]
本稿では,ミニマックス問題の2階定常点を求める非同相的挙動について考察する。高次元問題に対して、降下とチェビシェフ展開による勾配の立方体部分確率を解く2階オラクルのコスト対費用について提案する。
論文参考訳（メタデータ） (2021-10-10T14:54:23Z)
Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets [27.913569257545554]
2つの一般的な近似仮定(textitadditive と textitmultiplicative gap error)は、我々の問題には有効ではない。 DMO(textitapproximate dual Oracle)が提案され、ギャップではなく内部積を近似する。実験結果から,これらの改良された境界でさえ悲観的であり,グラフ構造を持つ実世界の画像に顕著な改善が認められたことが示唆された。
論文参考訳（メタデータ） (2021-06-29T19:39:43Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)
Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文参考訳（メタデータ） (2020-02-17T10:53:50Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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