論文の概要: Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- arxiv url: http://arxiv.org/abs/2007.03402v2
- Date: Thu, 9 Jul 2020 10:37:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 03:53:04.767609
- Title: Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- Title（参考訳）: 2d-gridとdyck言語の量子下界と上界
- Authors: Andris Ambainis, Kaspars Balodis, J\=anis Iraids, Kamil Khadiev,
Vladislavs K\c{l}evickis, Kri\v{s}j\=anis Pr\=usis, Yixin Shen, Juris
Smotrovs, Jevg\=enijs Vihrovs
- Abstract要約: 2つの問題の量子クエリ複雑性について検討する。
グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。
平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
- 参考スコア（独自算出の注目度）: 1.0118253437732931
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the quantum query complexity of two problems.
First, we consider the problem of determining if a sequence of parentheses is
a properly balanced one (a Dyck word), with a depth of at most $k$. We call
this the $Dyck_{k,n}$ problem. We prove a lower bound of $\Omega(c^k
\sqrt{n})$, showing that the complexity of this problem increases exponentially
in $k$. Here $n$ is the length of the word. When $k$ is a constant, this is
interesting as a representative example of star-free languages for which a
surprising $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently
constructed by Aaronson et al. Their proof does not give rise to a general
algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We
give an algorithm with $O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries
for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$
for $k=o\left(\frac{\log(n)}{\log\log n}\right)$.
Second, we consider connectivity problems on grid graphs in 2 dimensions, if
some of the edges of the grid may be missing. By embedding the "balanced
parentheses" problem into the grid, we show a lower bound of
$\Omega(n^{1.5-\epsilon})$ for the directed 2D grid and
$\Omega(n^{2-\epsilon})$ for the undirected 2D grid. The directed problem is
interesting as a black-box model for a class of classical dynamic programming
strategies including the one that is usually used for the well-known edit
distance problem. We also show a generalization of this result to more than 2
dimensions.
- Abstract（参考訳）: 2つの問題の量子クエリ複雑性について検討する。
まず、括弧列が適切にバランスのとれたもの(ダイク語)であり、深さが少なくとも$k$であるかどうかを決定する問題を考える。
これを$Dyck_{k,n}$ problemと呼ぶ。
我々は$\Omega(c^k \sqrt{n})$の低い境界を証明し、この問題の複雑さが指数関数的に$k$で増加することを示す。
ここで$n$は単語の長さです。
k$ が定数である場合、これはスターフリー言語の典型的な例として興味深いが、これはarronsonらによって最近構築された驚くべき $\tilde{o}(\sqrt{n})$ クエリ量子アルゴリズムである。
それらの証明は一般的なアルゴリズムを生み出しない。
k$ が定数でないとき、$Dyck_{k,n}$ は文脈自由ではない。
我々は、$O\left(\sqrt{n}(\log{n})^{0.5k}\right)$Dyck_{k,n}$ for all $k$というアルゴリズムを与える。
これは三項上界$n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$よりもよい。
第二に、グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。
平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$\Omega(n^{1.5-\epsilon})$、無向2Dグリッドに対して$\Omega(n^{2-\epsilon})$の低い境界を示す。
有向問題は、よく知られた編集距離問題に通常使用されるものを含む古典的動的プログラミング戦略のクラスのためのブラックボックスモデルとして興味深い。
また、この結果の2次元以上への一般化も示している。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。
最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。
2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文 参考訳（メタデータ） (2024-08-19T21:30:02Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - 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) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。