論文の概要: A Quantum Time-Space Tradeoff for Directed $st$-Connectivity
- arxiv url: http://arxiv.org/abs/2510.08403v1
- Date: Thu, 09 Oct 2025 16:22:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:15.195956
- Title: A Quantum Time-Space Tradeoff for Directed $st$-Connectivity
- Title（参考訳）: 直接$st$-Connectivityのための量子時間空間トレードオフ
- Authors: Stacey Jeffery, Galina Pass,
- Abstract要約: 任意の$Sgeq log2(n)$に対して、空間$S$と時間$Tleq 2frac12log(n)log(n/S)+o(log2(n))$を用いてDSTCONの量子アルゴリズムが存在することを示す。
- 参考スコア（独自算出の注目度）: 0.08594140167290097
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Directed $st$-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices $s$ and $t$ in an input directed graph. This problem appears in many algorithmic applications, and is also a fundamental problem in complexity theory, due to its ${\sf NL}$-completeness. We show that for any $S\geq \log^2(n)$, there is a quantum algorithm for DSTCON using space $S$ and time $T\leq 2^{\frac{1}{2}\log(n)\log(n/S)+o(\log^2(n))}$, which is an (up to quadratic) improvement over the best classical algorithm for any $S=o(\sqrt{n})$. Of the $S$ total space used by our algorithm, only $O(\log^2(n))$ is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.
- Abstract（参考訳）: Directed $st$-connectivity (DSTCON) は、入力された有向グラフ内の有向グラフのペア$s$と$t$の間に有向パスが存在するかどうかを決定する問題である。
この問題は、多くのアルゴリズムの応用に現れ、さらに${\sf NL}$-completeness という複雑さ理論の根本的問題でもある。
任意の$S\geq \log^2(n)$に対して、空間$S$と時間$T\leq 2^{\frac{1}{2}\log(n)\log(n/S)+o(\log^2(n))}$を用いてDSTCONの量子アルゴリズムが存在する。
我々のアルゴリズムで使われる$S$トータル空間のうち、O(\log^2(n))$だけが量子空間であり、残りは古典的である。
これは事実上、古典空間を量子時間で交換できることを意味する。
関連論文リスト
- Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms [4.832760917132771]
我々は量子力学プログラミングフレームワークを導入し、古典的動的プログラミングアルゴリズムの大きな体系である量子領域に直接拡張することを可能にする。
対応する量子力学プログラミングアルゴリズムは、計算スピードアップを達成しながら、従来のものと同じ空間の複雑さを保っている。
論文 参考訳（メタデータ） (2025-07-01T14:55:18Z) - Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。
最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。
2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文 参考訳（メタデータ） (2024-08-19T21:30:02Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。