Fugu-MT 論文翻訳(概要): Quantum algorithm for Dyck Language with Multiple Types of Brackets

論文の概要: Quantum algorithm for Dyck Language with Multiple Types of Brackets

arxiv url: http://arxiv.org/abs/2106.09374v1
Date: Thu, 17 Jun 2021 10:48:19 GMT
ステータス: 処理完了
システム内更新日: 2023-03-26 10:47:01.109162
Title: Quantum algorithm for Dyck Language with Multiple Types of Brackets
Title（参考訳）: 複数のブラケットを持つdyck言語の量子アルゴリズム
Authors: Kamil Khadiev and Dmitry Kravchenko
Abstract要約: 量子クエリ複雑性$O(sqrtn(log n)0.5k)$,$n$は入力の長さ、$k$はブラケットの最大ネスト深さである。ある定数$c$に対して$O(sqrtnck)$であるこの問題に対する下限を示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity $O(\sqrt{n}(\log n)^{0.5k})$, where $n$ is the length of input and $k$ is the maximal nesting depth of brackets. Additionally, we show the lower bound for this problem which is $O(\sqrt{n}c^{k})$ for some constant $c$. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ form the algorithm solving the original Dyck language. At the same time, quantum algorithms for solving both kinds of the Dyck language are of similar nature and requirements.
Abstract（参考訳）: 複数のブラケットに対して一般化されたDyck言語の認識問題を考察する。量子クエリ複雑性$O(\sqrt{n}(\log n)^{0.5k})$,$n$は入力の長さ、$k$はブラケットの最大ネスト深さである。さらに、ある定数$c$に対して$O(\sqrt{n}c^{k})$であるこの問題に対する下界を示す。興味深いことに、複数の種類の括弧に対してDyck言語を解く古典的なアルゴリズムは、元のDyck言語を解くアルゴリズムを形成する。同時に、両方の種類のdyck言語を解くための量子アルゴリズムは、同様の性質と要件を持つ。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language [0.0]
本稿では,2つのパリンドロムを結合した文脈自由言語を認識するための量子特性試験アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-17T07:19:20Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文参考訳（メタデータ） (2023-10-23T18:26:00Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
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)
Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm [2.1485350418225244]
本稿では,特殊な輸送問題 (OT) について検討し,それを正確に解くための改良されたハンガリーのアルゴリズムを提案する。 m$と$n$の原子を持つ辺り間のOT問題に対して、提案アルゴリズムの計算複雑性は$O(m2n)$である。
論文参考訳（メタデータ） (2022-10-29T16:28:46Z)
An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
論文参考訳（メタデータ） (2022-10-20T19:35:50Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文参考訳（メタデータ） (2021-05-18T06:51:11Z)

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