論文の概要: Directed st-connectivity with few paths is in quantum logspace

• arxiv url: http://arxiv.org/abs/2408.12473v1
• Date: Thu, 22 Aug 2024 15:11:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-23 13:22:23.164660
• Title: Directed st-connectivity with few paths is in quantum logspace
• Title（参考訳）: ほとんど経路を持たない直進st接続性は量子対数空間にある
• Authors: Roman Edenhofer, Simon Apers,
• Abstract要約: 有向グラフ上の$st$-pathをカウントするために、$mathsfBQSPACE(O(log))$-procedureを示す。 比較すると、このケースでよく知られた古典的上界は$st$-connectivityを$mathsfDSPACE(O(log2 n/ log nlog))$と判断するだけである。
• 参考スコア（独自算出の注目度）: 0.9208007322096533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a $\mathsf{BQSPACE}(O(\log n))$-procedure to count $st$-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in $s$ and polynomially many paths ending in $t$. For comparison, the best known classical upper bound in this case just to decide $st$-connectivity is $\mathsf{DSPACE}(O(\log^2 n/ \log \log n))$. The result establishes a new relationship between $\mathsf{BQL}$ and unambiguity and fewness subclasses of $\mathsf{NL}$. Further, some preprocessing in our approach also allows us to verify whether there are at most polynomially many paths between any two nodes in $\mathsf{BQSPACE}(O(\log n))$. This yields the first natural candidate for a language problem separating $\mathsf{BQL}$ from $\mathsf{L}$ and $\mathsf{BPL}$. Until now, all candidates separating these classes were promise problems.
• Abstract（参考訳）: 我々は、有向グラフ上の$st$-pathをカウントするために$\mathsf{BQSPACE}(O(\log n))$-procedureを提示する。 比較すると、$st$-接続性を決定するのに最もよく知られている古典上界は$\mathsf{DSPACE}(O(\log^2 n/ \log \log n))$である。 その結果、$\mathsf{BQL}$と$\mathsf{NL}$の曖昧さと小ささのサブクラスとの間の新しい関係が確立される。 さらに、このアプローチのいくつかの前処理により、$\mathsf{BQSPACE}(O(\log n))$の任意の2つのノードの間に、少なくとも多項式的に多くの経路が存在するかどうかを検証できる。 これは、$\mathsf{BQL}$と$\mathsf{L}$と$\mathsf{BPL}$を分離する言語問題に対する最初の自然な候補となる。 これまで、これらのクラスを分ける候補者は全員、約束の問題だった。

関連論文リスト

• 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)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Almost Optimal Proper Learning and Testing Polynomials [0.11421942894219898]
  我々のアルゴリズムは$q_U=left(fracsepsilonright)fraclog betabeta+O(frac1beta)+ tilde Oleft(logfrac1epsilonright)log n,$ 以前のアルゴリズムは、少なくとも$s$で2次、$/epsilon$で1/epsilon$で線形である。
  論文  参考訳（メタデータ） (2022-02-07T14:15:20Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• On polynomially many queries to NP or QMA oracles [0.0]
  本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。 まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。 次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
  論文  参考訳（メタデータ） (2021-11-03T15:29:01Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• 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)
• $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)

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

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