Fugu-MT 論文翻訳(概要): Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language

論文の概要: Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language

arxiv url: http://arxiv.org/abs/2406.11270v1
Date: Mon, 17 Jun 2024 07:19:20 GMT
ステータス: 処理完了
システム内更新日: 2024-06-18 17:54:42.301981
Title: Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
Title（参考訳）: 2つのパリンドロム言語の連結のための量子特性試験アルゴリズム
Authors: Kamil Khadiev, Danil Serov,
Abstract要約: 本稿では,2つのパリンドロムを結合した文脈自由言語を認識するための量子特性試験アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we present a quantum property testing algorithm for recognizing a context-free language that is a concatenation of two palindromes $L_{REV}$. The query complexity of our algorithm is $O(\frac{1}{\varepsilon}n^{1/3}\log n)$, where $n$ is the length of an input. It is better than the classical complexity that is $\Theta^*(\sqrt{n})$. At the same time, in the general setting, the picture is different a little. Classical query complexity is $\Theta(n)$, and quantum query complexity is $\Theta^*(\sqrt{n})$. So, we obtain polynomial speed-up for both cases (general and property testing).
Abstract（参考訳）: 本稿では,2つのパリンドロム$L_{REV}$の結合である文脈自由言語を認識するための量子特性試験アルゴリズムを提案する。我々のアルゴリズムのクエリ複雑性は$O(\frac{1}{\varepsilon}n^{1/3}\log n)$であり、$n$は入力の長さである。古典的な複雑性よりは、$\Theta^*(\sqrt{n})$ の方がよい。同時に、一般的な設定では、その絵は少し違う。古典的なクエリ複雑性は$\Theta(n)$、量子クエリ複雑性は$\Theta^*(\sqrt{n})$である。そこで, 一般および特性試験のいずれにおいても, 多項式の高速化が得られる。

関連論文リスト

Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文参考訳（メタデータ） (2024-06-17T20:54:11Z)
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)
On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [0.0]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文参考訳（メタデータ） (2023-03-20T08:17:32Z)
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)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文参考訳（メタデータ） (2021-05-18T06:51:11Z)
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)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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