論文の概要: Fixed-point Grover Adaptive Search for Binary Optimization Problems
- arxiv url: http://arxiv.org/abs/2311.05592v4
- Date: Thu, 16 May 2024 14:33:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-17 19:14:33.706918
- Title: Fixed-point Grover Adaptive Search for Binary Optimization Problems
- Title（参考訳）: 2元最適化問題に対する固定点グロバー適応探索
- Authors: Ákos Nagy, Jaime Park, Cindy Zhang, Atithi Acharya, Alex Khan,
- Abstract要約: 二次二項最適化問題に対するGrover-type法について検討する。
このような問題に対して、左[1, m right] の値 mathbbZ$ のチューナブルパラメータである $Lambda を用いてマーカーオラクルを構築する。
次に,新しいemphFixed-point Grover Adaptive Search for QUBO Problemsを紹介した。
- 参考スコア（独自算出の注目度）: 0.6524460254566903
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a Grover-type method for Quadratic Binary Optimization problems. In the unconstrained (QUBO) case, for an $n$-dimensional problem with $m$ nonzero terms, we construct a marker oracle for such problems with a tuneable parameter, $\Lambda \in \left[ 1, m \right] \cap \mathbb{Z}$. At $d \in \mathbb{Z}_+$ precision, the oracle uses $O \left( n + \Lambda d \right)$ qubits, has total depth $O \left( \tfrac{m}{\Lambda} \log_2 \left( n \right) + \log_2 \left( d \right) \right)$, and non-Clifford depth of $O \left( \tfrac{m}{\Lambda} \right)$. Moreover, each qubit required to be connected to at most $O \left( \log_2 \left( \Lambda + d \right) \right)$ other qubits. In the case of a maximal graph cuts, as $d = 2 \log_2 \left( n \right)$ always suffices, the depth of the marker oracle can be made as shallow as $O \left( \log_2 \left( n \right) \right)$. For all values of $\Lambda$, the non-Clifford gate count of these oracles is strictly lower (by a factor of $\sim 2$) than previous constructions. We then introduce a novel \emph{Fixed-point Grover Adaptive Search for QUBO Problems}, using our oracle design and a hybrid Fixed-point Grover Search of Li et al. This method has better performance guarantees than previous Grover Adaptive Search methods. Finally, we give a heuristic argument that, with high probability and in $O \left( \tfrac{\log_2 \left( n \right)}{\sqrt{\epsilon}} \right)$ time, this adaptive method finds a configuration that is among the best $\epsilon 2^n$ ones.
- Abstract（参考訳）: 二次二項最適化問題に対するGrover-type法について検討する。
制約のない (QUBO) の場合、$m$非ゼロ項を持つ$n$次元問題に対して、調整可能なパラメータを持つような問題に対して、$\Lambda \in \left[ 1, m \right] \cap \mathbb{Z}$ というマーカーオラクルを構築する。
d \in \mathbb{Z}_+$ 精度では、オラクルは$O \left(n + \Lambda d \right)$ qubitsを使用し、合計深さ$O \left( \tfrac{m}{\Lambda} \log_2 \left(n \right) + \log_2 \left(d \right) \right)$、非クリフォード深さ$O \left( \tfrac{m}{\Lambda} \right)$を持つ。
さらに、各キュービットは少なくとも$O \left( \log_2 \left( \Lambda + d \right) \right)$他のキュービットに接続する必要がある。
最大グラフ切断の場合、$d = 2 \log_2 \left(n \right)$ は常に十分であり、マーカーオラクルの深さは $O \left( \log_2 \left(n \right) \right)$ のように浅くすることができる。
$\Lambda$ のすべての値に対して、これらのオラクルの非クリフォードゲート数は、以前の構成よりも厳密に低い($\sim 2$ の係数で)。
次に,本手法は,従来のGrover Adaptive Search法よりも優れた性能保証を実現するため,本手法のオーラクル設計とハイブリッドなFixed-point Grover Search of Li et alを用いて,新しいGrover Adaptive Search for QUBO問題を提案する。
最後に、高い確率と$O \left( \tfrac{\log_2 \left(n \right)}{\sqrt{\epsilon}} \right)$timeにおいて、この適応的手法は最良の$\epsilon 2^n$の設定を見つける。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。