論文の概要: Fixed-point Grover Adaptive Search for Quadratic Binary Optimization Problems

• arxiv url: http://arxiv.org/abs/2311.05592v5
• Date: Sat, 19 Oct 2024 13:19:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:12:00.274071
• Title: Fixed-point Grover Adaptive Search for Quadratic Binary Optimization Problems
• Title（参考訳）: 二次最適化問題に対する固定点グロバー適応探索
• Authors: Ákos Nagy, Jaime Park, Cindy Zhang, Atithi Acharya, Alex Khan,
• Abstract要約: 擬似非拘束バイナリ最適化(QUBO)問題に対するGrover型手法について検討する。 このような問題に対して、左[1, m right] の値 mathbbZ$ のチューナブルパラメータである $Lambda を用いてマーカーオラクルを構築する。 Lambda$のすべての値に対して、これらのオラクルの非クリフォードゲート数は厳格に低い。 この結果のいくつかは新規であり、固定点探索に基づく任意の手法に有用である。
• 参考スコア（独自算出の注目度）: 0.6524460254566903
• License:
• Abstract: We study a Grover-type method for Quadratic Unconstrained Binary Optimization (QUBO) problems. For an $n$-dimensional QUBO 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 (n + \Lambda d)$ qubits, has total depth of $O \left( \tfrac{m}{\Lambda} \log_2 (n) + \log_2 (d) \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 (\Lambda + d) \right)$ other qubits. In the case of a maximum graph cuts, as $d = 2 \left\lceil \log_2 (n) \right\rceil$ always suffices, the depth of the marker oracle can be made as shallow as $O (\log_2 (n))$. For all values of $\Lambda$, the non-Clifford gate count of these oracles is strictly lower (at least by a factor of $\sim 2$) than previous constructions. Furthermore, we introduce a novel \textit{Fixed-point Grover Adaptive Search for QUBO Problems}, using our oracle design and a hybrid Fixed-point Grover Search, motivated by the works of Boyer et al. and Li et al. This method has better performance guarantees than previous Grover Adaptive Search methods. Some of our results are novel and useful for any method based on Fixed-point Grover Search. Finally, we give a heuristic argument that, with high probability and in $O \left( \tfrac{\log_2 (n)}{\sqrt{\epsilon}} \right)$ time, this adaptive method finds a configuration that is among the best $\epsilon 2^n$ ones.
• Abstract（参考訳）: 擬似非拘束バイナリ最適化(QUBO)問題に対するGrover型手法について検討する。 非零項$m$の$n$次元QUBO問題に対して、調整可能なパラメータを持つような問題に対して、$\Lambda \in \left[ 1, m \right] \cap \mathbb{Z}$ というマーカーオラクルを構築する。 d \in \mathbb{Z}_+$精度では、オラクルは$O (n + \Lambda d)$ qubitsを使用し、総深さは$O \left( \tfrac{m}{\Lambda} \log_2 (n) + \log_2 (d) \right)$、非クリフォード深さは$O \left( \tfrac{m}{\Lambda} \right)$である。 さらに、各キュービットは少なくとも$O \left( \log_2 (\Lambda + d) \right)$他のキュービットに接続する必要がある。 最大グラフカットの場合、$d = 2 \left\lceil \log_2 (n) \right\rceil$ は常に十分であり、マーカーオラクルの深さは$O (\log_2 (n))$ と浅くなる。 $\Lambda$ のすべての値に対して、これらのオラクルの非クリフォードゲート数は、以前の構成よりも厳密に低い(少なくとも$\sim 2$ の係数で)。 さらに,本手法は,従来のGrover Adaptive Search法よりも優れた性能保証を実現するため,本手法を応用した新規な「textit{Fixed-point Grover Adaptive Search for QUBO Problems」を提案する。 この結果のいくつかは新規であり、固定点グロバーサーチに基づく任意の手法に有用である。 最後に、高い確率と$O \left( \tfrac{\log_2 (n)}{\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)

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

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