Fugu-MT 論文翻訳(概要): Quantum speedups for dynamic programming on $n$-dimensional lattice graphs

論文の概要: Quantum speedups for dynamic programming on $n$-dimensional lattice graphs

arxiv url: http://arxiv.org/abs/2104.14384v2
Date: Fri, 7 May 2021 16:13:43 GMT
ステータス: 処理完了
システム内更新日: 2023-04-02 02:11:15.108772
Title: Quantum speedups for dynamic programming on $n$-dimensional lattice graphs
Title（参考訳）: n$-次元格子グラフ上での動的プログラミングのための量子スピードアップ
Authors: Adam Glos, Martins Kokainis, Ryuhei Mori, Jevg\=enijs Vihrovs
Abstract要約: 複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
参考スコア（独自算出の注目度）: 0.11470070927586015
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the $n$-dimensional lattice graph $Q(D,n)$ with vertices in $\{0,1,\ldots,D\}^n$. We study the complexity of the following problem: given a subgraph $G$ of $Q(D,n)$ via query access to the edges, determine whether there is a path from $0^n$ to $D^n$. While the classical query complexity is $\widetilde{\Theta}((D+1)^n)$, we show a quantum algorithm with complexity $\widetilde O(T_D^n)$, where $T_D < D+1$. The first few values of $T_D$ are $T_1 \approx 1.817$, $T_2 \approx 2.660$, $T_3 \approx 3.529$, $T_4 \approx 4.421$, $T_5 \approx 5.332$. We also prove that $T_D \geq \frac{D+1}{\mathrm e}$, thus for general $D$, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for $D=1$ by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity $\text{poly}(n)^{\log n} T_D^n$, and apply it to the Set Multicover problem. In this problem, $m$ subsets of $[n]$ are given, and the task is to find the smallest number of these subsets that cover each element of $[n]$ at least $D$ times. While the time complexity of the best known classical algorithm is $O(m(D+1)^n)$, the time complexity of our quantum algorithm is $\text{poly}(m,n)^{\log n} T_D^n$.
Abstract（参考訳）: ambainis et al. (2019) によるboolean hypercube 上の動的プログラミングの量子スピードアップに動機づけられ、どのグラフが同様の量子アドバンテージを持つかを調査した。本稿では, ブールハイパーキューブグラフ, $n$次元格子グラフ $Q(D,n)$ の一般化を, $\{0,1,\ldots,D\}^n$ の頂点で検討する。グラフ$G$ of $Q(D,n)$がエッジへのクエリアクセスを介して与えられると、$0^n$から$D^n$への経路が存在するかどうかが決定される。古典的なクエリ複雑性は$\widetilde{\Theta}((D+1)^n)$であるが、複雑性を持つ量子アルゴリズムは$\widetilde O(T_D^n)$である。 T_D$の最初の値は$T_1 \approx 1.817$, $T_2 \approx 2.660$, $T_3 \approx 3.529$, $T_4 \approx 4.421$, $T_5 \approx 5.332$である。また、$t_d \geq \frac{d+1}{\mathrm e}$を証明し、一般の$d$に対して、このアルゴリズムは、例えば、格子の大きさの速度アップ多項式を提供しない。提示された量子アルゴリズムは、アンバニスらによって既知の量子アルゴリズムの自然な一般化であるが、複雑さの分析はかなり複雑である。正確な解析には、解析的組合せ論において一般的なツールであるsaddle-point法を用いるが、この分野では広く使われていない。次に、時間複雑性$\text{poly}(n)^{\log n} t_d^n$を持つこのアルゴリズムの実装を示し、集合のマルチカバー問題に適用する。この問題では、$[n]$の$m$サブセットが与えられ、そのタスクは、$[n]$のそれぞれの要素をカバーする最小のサブセットを見つけることである。最もよく知られた古典的アルゴリズムの時間複雑性は$o(m(d+1)^n)$であるが、量子アルゴリズムの時間複雑性は$\text{poly}(m,n)^{\log n} t_d^n$である。

関連論文リスト

Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文参考訳（メタデータ） (2023-03-20T08:17:32Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文参考訳（メタデータ） (2023-02-20T19:11:44Z)
Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文参考訳（メタデータ） (2020-11-22T01:22:37Z)
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)
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)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文参考訳（メタデータ） (2020-02-12T03:40:52Z)
Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
論文参考訳（メタデータ） (2019-12-31T14:52:36Z)

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

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