論文の概要: A note on quantum lower bounds for local search via congestion and expansion

• arxiv url: http://arxiv.org/abs/2412.13345v1
• Date: Tue, 17 Dec 2024 21:42:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-19 16:45:48.819696
• Title: A note on quantum lower bounds for local search via congestion and expansion
• Title（参考訳）: 混雑・膨張による局所探索のための量子下界に関する一考察
• Authors: Simina Brânzei, Nicholas J. Recker,
• Abstract要約: G$上の局所探索の量子クエリの複雑さは$Omegabigl( fracnfrac34sqrtg bigr)$であることを示す。 古典的な設定とは対照的に、そのようなグラフに対して、下界と最もよく知られた上界の$Obigl(nfrac13 bigr)$の間の量子ケースにギャップが残っている。
• 参考スコア（独自算出の注目度）: 4.68073705539907
• License:
• Abstract: We consider the quantum query complexity of local search as a function of graph geometry. Given a graph $G = (V,E)$ with $n$ vertices and black box access to a function $f : V \to \mathbb{R}$, the goal is find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few oracle queries as possible. We show that the quantum query complexity of local search on $G$ is $\Omega\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$, where $g$ is the vertex congestion of the graph. For a $\beta$-expander with maximum degree $\Delta$, this implies a lower bound of $ \Omega\bigl(\frac{\sqrt{\beta} \; n^{\frac{1}{4}}}{\sqrt{\Delta} \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Br\^anzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of $\Omega\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$. This improves upon the best prior quantum lower bound of $\Omega\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of $O\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs.
• Abstract（参考訳）: 局所探索の量子クエリ複雑性をグラフ幾何学の関数として考える。 グラフ $G = (V,E)$ with $n$ vertices and black box access to a function $f : V \to \mathbb{R}$ が与えられたとき、その目標は、局所最小値であるvertex $v$を見つけることである。 (v) \leq f (u)$ for all $(u,v) \in E$, using as few oracle query as as possible。 G$上の局所探索の量子クエリの複雑さは$\Omega\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$である。 最大次数が $\Delta$ の$\beta$-expander の場合、これは $ \Omega\bigl(\frac{\sqrt{\beta} \; n^{\frac{1}{4}}}{\sqrt{\Delta} \; \log{n}} \bigr)$ の下界を意味する。 Br\^anzei, Choo, and Recker (2024) による構築に強重み付き逆法を適用してこれらの境界を求める。 座標系として、等級拡大器上では、$\Omega\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$ の下界を導出する。 これは、Santha and Szegedy (2004) による $\Omega\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ の最高の先行量子下界を改善する。 古典的な設定とは対照的に、そのようなグラフに対して、下界と最もよく知られた上界の$O\bigl(n^{\frac{1}{3}} \bigr)$の間の量子ケースにギャップが残っている。

関連論文リスト

• Quantum Algorithms and Lower Bounds for Finite-Sum Optimization [22.076317220348145]
  我々は、複雑性 $tildeObig(n+sqrtd+sqrtell/mubig)$ の量子アルゴリズムを与え、古典的なタイト境界 $tildeThetabig(n+sqrtnell/mubig)$ を改善する。 また、$d$が十分大きいとき、量子下界$tildeOmega(n+n3/4(ell/mu)1/4)$を証明します。
  論文  参考訳（メタデータ） (2024-06-05T07:13:52Z)
• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。 特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-28T21:23:40Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
  論文  参考訳（メタデータ） (2020-10-23T19:21:28Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
  2つの問題の量子クエリ複雑性について検討する。 グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。 平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
  論文  参考訳（メタデータ） (2020-07-06T09:51:41Z)
• 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)

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

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