論文の概要: A quantum algorithm for learning a graph of bounded degree
- arxiv url: http://arxiv.org/abs/2402.18714v1
- Date: Wed, 28 Feb 2024 21:23:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-01 16:55:48.189728
- Title: A quantum algorithm for learning a graph of bounded degree
- Title（参考訳）: 有界次数のグラフを学習するための量子アルゴリズム
- Authors: Asaf Ferber, Liam Hardiman
- Abstract要約: 本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.8130068086063336
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We are presented with a graph, $G$, on $n$ vertices with $m$ edges whose edge
set is unknown. Our goal is to learn the edges of $G$ with as few queries to an
oracle as possible. When we submit a set $S$ of vertices to the oracle, it
tells us whether or not $S$ induces at least one edge in $G$. This so-called
OR-query model has been well studied, with Angluin and Chen giving an upper
bound on the number of queries needed of $O(m \log n)$ for a general graph $G$
with $m$ edges.
When we allow ourselves to make *quantum* queries (we may query subsets in
superposition), then we can achieve speedups over the best possible classical
algorithms. In the case where $G$ has maximum degree $d$ and is
$O(1)$-colorable, Montanaro and Shao presented an algorithm that learns the
edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an
upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a
Hamiltonian cycle, which is far away from the lower bound of $\Omega(\sqrt{m})$
queries given by Ambainis and Montanaro.
We improve on the work of Montanaro and Shao in the case where $G$ has
bounded degree. In particular, we present a randomized algorithm that, with
high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum
queries, matching the theoretical lower bound up to logarithmic factors.
- Abstract（参考訳）: 我々は、エッジセットが不明な$m$エッジを持つ$n$頂点上のグラフ、$G$を提示する。
私たちの目標は、oracleへのクエリを可能な限り少なくして、$g$のエッジを学ぶことです。
オラクルに$s$の頂点を提出すると、$s$が$g$で少なくとも1つのエッジを誘導するかどうかがわかる。
このいわゆるOR-クエリモデルはよく研究されており、Angluin と Chen は、$O(m \log n)$ の一般グラフ $G$ と$m$ edges のクエリ数に上限を与える。
もし私たちが *quantum* クエリを許容するなら(重ね合わせでサブセットをクエリできる)、最良の古典的なアルゴリズムよりも速いスピードアップを達成できます。
G$が最大$d$で$O(1)$-colorableである場合、モンタナロとシャオは$G$のエッジを最大$\tilde{O}(d^2m^{3/4})$量子クエリで学習するアルゴリズムを提示した。
これは、$G$がマッチングまたはハミルトンサイクルであるときに、$\tilde{O}(m^{3/4})$量子クエリの上限を与えるが、これは、アンバイニスとモンタナロによって与えられる$\Omega(\sqrt{m})$クエリの下位境界から遠く離れている。
我々は、$g$ が有界度を持つ場合、モンタナロとシャオの仕事を改善する。
特に、確率の高い確率で$\tilde{O}(\sqrt{m})$量子クエリでサイクルとマッチングを学習し、理論的な下界を対数的因子にマッチングするランダム化アルゴリズムを提案する。
関連論文リスト
- Learning Low Degree Hypergraphs [12.515216618616206]
エッジ検出クエリによるハイパーグラフ学習の問題について検討する。
本稿では,エッジサイズが指数関数的に大きくなるクエリの複雑さに悩まされることなく,学習可能なハイパーグラフの族を特定することを目的とする。
論文 参考訳（メタデータ） (2022-02-21T04:38:24Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Simple vertex coloring algorithms [2.8808678188754637]
1 + epsilon)Delta$-coloring に対して簡単なアルゴリズムを与える。
これは$tildeO(epsilon-1n4/3)$クエリを生成する量子クエリアルゴリズムに適応することができる。
論文 参考訳（メタデータ） (2021-02-14T07:27:10Z) - Quantum complexity of minimum cut [0.2538209532048867]
隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。
我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
論文 参考訳（メタデータ） (2020-11-19T13:51:49Z) - 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 algorithms for graph problems with cut queries [17.149741568581096]
量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。
また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
論文 参考訳（メタデータ） (2020-07-16T12:21:01Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。