論文の概要: Quantum Algorithm for Lexicographically Minimal String Rotation
- arxiv url: http://arxiv.org/abs/2012.09376v3
- Date: Mon, 13 Nov 2023 13:38:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 19:49:32.879522
- 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)$量子クエリアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 5.905222176603487
- 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 to its $\Omega\left(\sqrt{n/\log n}\right)$
lower bound. Furthermore, we show that our quantum algorithm outperforms any
(classical) randomized algorithms in both worst and average cases. As an
application, it is used in benzenoid identification and disjoint-cycle automata
minimization.
- Abstract（参考訳）: lexicographically minimal string rotation (lmsr) は、グラフ、多角形、オートマトン、化学構造の等式チェックにおいて広く用いられる、文字列の全ての回転のうち最小のものを見つける問題である。
本稿では,LMSRのための$O(n^{3/4})$量子クエリアルゴリズムを提案する。
特に、アルゴリズムは平均ケースクエリの複雑性$o(\sqrt n \log n)$ を持ち、これは多対数係数に対して漸近的に最適であることが示され、$\omega\left(\sqrt{n/\log n}\right)$ の下限である。
さらに,我々の量子アルゴリズムは,最悪の場合と平均の場合の両方において,任意の(古典的)ランダム化アルゴリズムを上回ることを示した。
応用例として、ベンゼノイド識別および解離サイクルオートマトン最小化に用いられる。
関連論文リスト
- Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。
我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
論文 参考訳（メタデータ） (2025-02-13T12:04:39Z) - 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) - 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) - A Note on Quantum Divide and Conquer for Minimal String Rotation [3.1157817010763136]
語彙的に最小限の弦の回転は、弦処理の基本的な問題である。
この問題を解決するために、準最適量子アルゴリズムが提案されている。
量子クエリの複雑性は$sqrtn cdot 2O(sqrtlog n)$であることを示す。
論文 参考訳（メタデータ） (2022-10-17T14:51:49Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳（メタデータ） (2020-05-28T22:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。