論文の概要: Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism

• arxiv url: http://arxiv.org/abs/2503.05596v1
• Date: Fri, 07 Mar 2025 17:24:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-10 12:19:49.885034
• Title: Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism
• Title（参考訳）: 古典的および量子的文字列マッチングのブリッジ:ビットパラレルの計算的再構成
• Authors: Simone Faro, Arianna Pavone, Caterina Viola,
• Abstract要約: 本稿では,ビット並列文字列マッチングアルゴリズムを量子フレームワークに変換する新しい経路を提案する。 ビット並列モデルに量子探索を埋め込むことにより、文字列マッチングの時間的複雑さを低減する。 また,Groverの探索による2次高速化を実現するため,性能の向上も図っている。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: String matching is a fundamental problem in computer science, with critical applications in text retrieval, bioinformatics, and data analysis. Among the numerous solutions that have emerged for this problem in recent decades, bit-parallelism has significantly enhanced their practical efficiency, leading to the development of several optimized approaches for both exact and approximate string matching. However, their potential in quantum computing remains largely unexplored. This paper presents a novel pathway that not only translates bit-parallel string matching algorithms into the quantum framework but also enhances their performance to achieve a quadratic speedup through Grover's search. By embedding quantum search within a bit-parallel model, we reduce the time complexity of string matching, establishing a structured pathway for transforming classical algorithms into quantum solutions with provable computational advantages. Beyond exact matching, this technique offers a foundation for tackling a wide range of non-standard string matching problems, opening new avenues for efficient text searching in the quantum era. To demonstrate the simplicity and adaptability of the technique presented in this paper, we apply this translation and adaptation process to two landmark bit-parallel algorithms: Shift-And for exact pattern matching and Shift-Add for approximate string matching with up to k errors.
• Abstract（参考訳）: 文字列マッチングはコンピュータ科学の基本的な問題であり、テキスト検索、バイオインフォマティクス、データ解析に重要な応用がある。 この問題に何十年にもわたって現れた多くのソリューションの中で、ビット並列性は実践的効率を大幅に向上させ、正確な文字列マッチングと近似文字列マッチングの両方に最適化されたアプローチの開発につながった。 しかし、量子コンピューティングにおけるその可能性はほとんど未解明のままである。 本稿では,ビット並列文字列マッチングアルゴリズムを量子フレームワークに変換するだけでなく,Groverの探索による2次高速化を実現するために,その性能を向上させる新しい経路を提案する。 ビット並列モデルに量子探索を埋め込むことにより、文字列マッチングの時間的複雑さを低減し、古典的アルゴリズムを証明可能な計算上の利点を持つ量子解に変換するための構造化経路を確立する。 この手法は、正確なマッチング以外にも、幅広い非標準文字列マッチング問題に対処するための基盤を提供し、量子時代の効率的なテキスト検索のための新しい道を開く。 提案手法の単純さと適応性を実証するために,この変換と適応処理を2つの目覚しいビット並列アルゴリズムに適用する: Shift-And for exact pattern matching and Shift-Add for almost string matching with up k error。

関連論文リスト

• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。 我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
  論文  参考訳（メタデータ） (2024-09-20T08:27:42Z)
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Data Loading [7.88657961743755]
  本稿では,ACLBM(Adaptive Circuit Learning of Born Machine)という新しいアルゴリズムを提案する。 我々のアルゴリズムは、ターゲット状態に存在する複雑な絡み合いを最もよく捉える2ビットの絡み合いゲートを選択的に統合するように調整されている。 実験結果は、振幅埋め込みによる実世界のデータの符号化における我々のアプローチの習熟度を裏付けるものである。
  論文  参考訳（メタデータ） (2023-11-29T16:47:31Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Grover search revisited; application to image pattern matching [0.8367938108534343]
  本稿では,Groverデータベース全体の探索やパターンマッチングを行う量子アルゴリズムを提案する。 鍵となる考え方は、最近提案された近似振幅符号化法を浅い量子回路で使用することである。
  論文  参考訳（メタデータ） (2021-08-24T17:30:41Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。