論文の概要: Quantum Algorithm for Lexicographically Minimal String Rotation
- arxiv url: http://arxiv.org/abs/2012.09376v2
- Date: Fri, 25 Dec 2020 12:45:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 08:44:59.729981
- Title: Quantum Algorithm for Lexicographically Minimal String Rotation
- Title（参考訳）: 語彙的最小文字列回転の量子アルゴリズム
- Authors: Qisheng Wang and Mingsheng Ying
- Abstract要約: 語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。
LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 3.015392924074054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Lexicographically minimal string rotation (LMSR) is a problem to find the
minimal one among all rotations of a string in the lexicographical order, which
is widely used in equality checking of graphs, polygons, automata and chemical
structures.
In this paper, we propose an $O(n^{3/4})$ quantum query algorithm for LMSR.
In particular, the algorithm has average-case query complexity $O(\sqrt n \log
n)$, which is shown to be asymptotically optimal up to a polylogarithmic
factor, compared with its $\Omega\left(\sqrt{n/\log n}\right)$ lower bound.
Furthermore, we claim that our quantum algorithm outperforms any (classical)
randomized algorithms in both worst-case and average-case query complexities by
showing that every (classical) randomized algorithm for LMSR has worst-case
query complexity $\Omega(n)$ and average-case query complexity $\Omega(n/\log
n)$.
Our quantum algorithm for LMSR is developed in a framework of nested quantum
algorithms, based on two new results: (i) an $O(\sqrt{n})$ (optimal) quantum
minimum finding on bounded-error quantum oracles; and (ii) its $O\left(\sqrt{n
\log(1/\varepsilon)}\right)$ (optimal) error reduction. As a byproduct, we
obtain some better upper bounds of independent interest: (i) $O(\sqrt{N})$
(optimal) for constant-depth MIN-MAX trees on $N$ variables; and (ii)
$O(\sqrt{n \log m})$ for pattern matching which removes
$\operatorname{polylog}(n)$ factors.
- Abstract（参考訳）: lexicographically minimal string rotation (lmsr) は、グラフ、多角形、オートマトン、化学構造の等式チェックにおいて広く用いられる、文字列の全ての回転のうち最小のものを見つける問題である。
本稿では,LMSRのための$O(n^{3/4})$量子クエリアルゴリズムを提案する。
特に、アルゴリズムは平均照会の複雑さ$o(\sqrt n \log n)$ を持ち、これは多対数係数に対して漸近的に最適であることが示され、$\omega\left(\sqrt{n/\log n}\right)$ の下限と比較される。
さらに、我々の量子アルゴリズムは、LMSRの全ての(古典的な)ランダム化アルゴリズムが最悪のクエリ複雑性$\Omega(n)$および平均的なクエリ複雑性$\Omega(n/\log n)$を持つことを示すことによって、最悪のケースおよび平均ケースのクエリ複雑さにおいて、任意の(古典的な)ランダム化アルゴリズムよりも優れていると主張している。
LMSRの量子アルゴリズムはネスト量子アルゴリズムの枠組みで開発され,2つの新しい結果を得た。
(i) 有界エラー量子オラクル上の$o(\sqrt{n})$ (最適) 量子最小探索
(ii)その$o\left(\sqrt{n \log(1/\varepsilon)}\right)$ (optimal) エラー低減。
副産物として、我々は独立した利益のより優れた上限を得る。
(i)$o(\sqrt{n})$ (optimal) $n$変数の有限長木に対する。
(ii) $o(\sqrt{n \log m})$ パターンマッチングは$\operatorname{polylog}(n)$ factor を削除する。
関連論文リスト
- 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - 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) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳（メタデータ） (2020-05-28T22:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。