Fugu-MT 論文翻訳(概要): Multidimensional Quantum Walks, with Application to $k$-Distinctness

論文の概要: Multidimensional Quantum Walks, with Application to $k$-Distinctness

arxiv url: http://arxiv.org/abs/2208.13492v3
Date: Tue, 27 Aug 2024 10:49:10 GMT
ステータス: 処理完了
システム内更新日: 2024-08-28 20:28:28.276362
Title: Multidimensional Quantum Walks, with Application to $k$-Distinctness
Title（参考訳）: 多次元量子ウォークと$k$-distinctnessへの応用
Authors: Stacey Jeffery, Sebastian Zur,
Abstract要約: 時間複雑性に対して$widetildeOleft(n3/4-1/4(2k-1)right)の新たな上限を与える。この新しい手法を用いて,$O(n)$クエリと$O(n2)$タイムで溶接木を解く方法を示す。
参考スコア（独自算出の注目度）: 0.5064404027153093
License: http://creativecommons.org/licenses/by/4.0/
Abstract: While the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper bound of $\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)$ on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in $O(n)$ queries and $O(n^2)$ time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.
Abstract（参考訳）: k$-distinctnessの量子クエリ複雑性は、任意の定数$k \geq 4$に対して$O\left(n^{3/4-1/4(2^k-1)}\right)$であることが知られているが、時間複雑性の前の最高の上限は$\widetilde{O}\left(n^{1-1/k}\right)$である。新しい上限である$\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)を時間複雑性に基づいて与え、クエリの複雑さを多変数因子に合わせる。この上限を達成するために、電気ネットワークフレームワークの拡張である量子ウォーク探索アルゴリズムを設計する新しい手法を提案する。また、この新しい手法を用いて、$O(n)$クエリと$O(n^2)$タイムで溶接木を解く方法を示し、新しい量子ウォークフレームワークが指数的なスピードアップを達成することを示す。

関連論文リスト

A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文参考訳（メタデータ） (2024-06-17T20:54:11Z)
Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
量子状態のエントロピーを推定することは、量子情報の基本的な問題である。我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
論文参考訳（メタデータ） (2024-01-18T12:50:20Z)
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文参考訳（メタデータ） (2023-11-03T09:09:23Z)
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 Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文参考訳（メタデータ） (2022-04-22T12:37:56Z)
Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文参考訳（メタデータ） (2022-02-23T04:19:57Z)
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)
Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。 Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-08-01T14:21:45Z)
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)

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