論文の概要: Simple Quantum Algorithm for Approximate $k$-Mismatch Problem

• arxiv url: http://arxiv.org/abs/2510.02399v1
• Date: Wed, 01 Oct 2025 12:09:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.082059
• Title: Simple Quantum Algorithm for Approximate $k$-Mismatch Problem
• Title（参考訳）: 近似$k$-Mismatch問題に対する簡単な量子アルゴリズム
• Authors: Ruhan Habib,
• Abstract要約: パターンと長さがそれぞれ$n$と$m$のテキストが与えられた$k$-mismatch問題では、テキストがパターンから少なくとも$k$のハミング距離を持つサブストリングを持っているかどうかを確認する必要がある。 パラメータ $epsilon in (0, 1]$ が与えられたとき、近似的に問題を解く単純な量子アルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the $k$-mismatch problem, given a pattern and a text of length $n$ and $m$ respectively, we have to find if the text has a sub-string with a Hamming distance of at most $k$ from the pattern. This has been studied in the classical setting since 1982 and recently in the quantum computational setting by Jin and Nogler and Kociumaka, Nogler, and Wellnitz. We provide a simple quantum algorithm that solves the problem in an approximate manner, given a parameter $\epsilon \in (0, 1]$. It returns an occurrence as a match only if it is a $\left(1+\epsilon\right)k$-mismatch. If it does not return any occurrence, then there is no $k$-mismatch. This algorithm has a time (size) complexity of $\tilde{O}\left( \epsilon^{-1} \sqrt{\frac{mn}{k}} \right)$.
• Abstract（参考訳）: パターンと長さがそれぞれ$n$と$m$のテキストが与えられた$k$-mismatch問題では、テキストがパターンから少なくとも$k$のハミング距離を持つサブストリングを持っているかどうかを確認する必要がある。 1982年から古典的な環境で研究され、最近ではJinとNogler、Kociumaka、Nogler、Wellnitzによって量子計算環境で研究されている。 パラメータ $\epsilon \in (0, 1]$ が与えられたとき、近似的に問題を解く単純な量子アルゴリズムを提供する。 これは、$\left(1+\epsilon\right)k$-mismatchの場合のみ、マッチとして発生を返します。 もし何か発生を返さなければ、$k$-mismatchは存在しない。 このアルゴリズムの時間(サイズ)は$\tilde{O}\left( \epsilon^{-1} \sqrt {\frac{mn}{k}} \right)$である。

関連論文リスト

• Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
  パターンマッチングにおけるハミング距離と、編集によるパターンマッチングにおける編集距離の2つを考える。 時間的複雑性は$tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatchesと$hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Editsである。
  論文  参考訳（メタデータ） (2024-10-09T12:05:26Z)
• On the Communication Complexity of Approximate Pattern Matching [2.4167127333650202]
  上界が$O(n/m cdot k log2 m)$ bitsであることを証明する。 また、$O(n/m cdot k log2 m)$ bits は、$k$-error 発生毎に$P$ in $T$ のエンコードを可能にする。
  論文  参考訳（メタデータ） (2024-03-27T17:57:16Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。 この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
  論文  参考訳（メタデータ） (2020-05-28T22:44:01Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)
• Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
  Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。 ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。 本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
  論文  参考訳（メタデータ） (2019-12-31T14:52:36Z)

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

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