量子は細粒度の複雑さを満たす:ストリング問題のための準線形時間量子アルゴリズム【JST・京大機械翻訳】

Gall Francois Le; Seddighin Saeed

プレプリント

J-GLOBAL ID：202202205849399280 整理番号：22P0203223

量子は細粒度の複雑さを満たす:ストリング問題のための準線形時間量子アルゴリズム【JST・京大機械翻訳】

Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2020年10月22日プレプリントサーバーでの情報更新日： 2022年05月23日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

最も長い共通サブストリング(LCS),最長パリンドロームサブストリング(LPS),およびUlm距離(UL)は,ほぼ線形時間で古典的に解くことができる3つの基本的ストリング問題である。本研究では,量子下限と共にこれらの問題に対するサブ線形時間量子アルゴリズムを提案した。著者らの結果は,LCSとLPSの古典的解がほとんど同一(サフィックス木)であるが,それらの量子計算複雑性が異なるという非常に驚くべき事実に光を当てた。LPSに対する正確なO(√n)時間アルゴリズムを与える一方で,LCSは0/1ストリングに対してさえ少なくとも時間Ω(n ̄2/3)を必要とすることを証明した。【JST・京大機械翻訳】

, , , , ,
, , , 【Automatic Indexing@JST】

計算理論 , フィルタ一般 , 記号処理 , 数値計算 , システム・制御理論一般

, , , , ,

前のページに戻る