一般化退化文字列における量子パターンマッチング：技術的サマリー

本論文は、一般化退化文字列（Generalised Degenerate Strings, GD 文字列） 内での完全一致パターンマッチング問題を、量子計算モデルを用いて高速化する手法を提案しています。著者らは、古典的なアルゴリズムの戦略を量子並列性と振幅増幅（Grover 探索）に転換し、既存の最良の量子アルゴリズムを超える時間計算量を実現しました。

以下に、問題定義、手法、主要な貢献、結果、および意義について詳細にまとめます。

---

1. 問題定義

一般化退化文字列 (GD 文字列)

通常の文字列が「文字の列」であるのに対し、GD 文字列は「文字列の集合の列」です。

• 定義: $T = T[1]T[2]\cdots T[n]$ は、各セグメント $T[i]$ が固定長の文字列の集合（$T[i] \subseteq \Sigma^{k_i}$）で構成されます。
• 特徴: 同じセグメント内の文字列はすべて等しい長さを持ちますが、異なるセグメント間では長さが異なります。
• マッチング条件: パターン文字列 $P$ が GD 文字列 $T$ に出現するとは、以下のいずれかの条件を満たすことを意味します。
  1. $P$ が $T$ の任意のセグメント $T[i]$ に含まれる文字列 $S$ の部分文字列である。
  2. $P$ が複数のセグメントにまたがって構成される（例：$T[i]$ の末尾、$T[i+1]$ 全体、$T[i+2]$ の先頭など）。

目的 (Problem 1: SMGD)

• 入力: 文字列 $P$（長さ $m$）と GD 文字列 $T$（$n$ セグメント、総文字数 $N$）。
• 出力: $P$ が $T$ に少なくとも 1 回出現するかどうか（存在問題）。出現位置の報告は不要です。

古典的な背景

• 古典アルゴリズム（Ascone et al., WABI 2024）では、$O(mn + N)$ の時間で解決可能です。
• 既存のグラフマッチングへの量子アプローチ（レベル DAG への還元）を適用すると、エッジ数が $O(N^2)$ になるため、$O(N^2\sqrt{m})$ となり非効率的です。

---

2. 手法とアルゴリズムの概要

著者らは、古典的な並列アルゴリズムのロジックを量子計算の枠組みに再構築しました。

古典的並列アプローチの直観

パターン $P$ の長さ $m$ に対して、$m$ 個のスレッド（スレッド $t_1, \dots, t_m$）を並列に実行します。

• 各スレッド $t_h$ は、GD 文字列 $T$ に対して異なるオフセット（シフト量 $h$）からマッチングを試みます。
• 各スレッドは、$T$ のセグメントを左から右へ走査し、フォワードトライ（前方トライ）とバックワードトライ（後方トライ）を用いて、パターンの接頭辞・接尾辞がセグメント内で一致するかを確認します。
• $m$ 個のスレッドを並列に走らせることで、$T$ のすべての列（column）を網羅的にチェックします。

量子アルゴリズムの設計

この古典的な並列処理を、量子重ね合わせとネストされた Grover 探索に置き換えます。

3 段階のネストされた Grover 探索

アルゴリズムは、外側から内側へ向けて 3 つの Grover 探索（$G_1, G_2, G_3$）をネストして構成されます。

1. 外側探索 ($G_1$): シフト量の探索

   • 目的: $m$ 個の可能なシフト位置（スレッド ID $h \in [0, m-1]$）の中から、パターンが一致するものを見つける。
   • オラクル: 関数 $f_1(h)$。$P$ が $T$ の列 $h + r \cdot m$ から始まる一致を持つかどうかを判定します。
   • 実装: 内部で $G_2$ を呼び出し、$T$ の走査ロジックを実行します。

2. 中間探索 ($G_2$): セグメント内での一致探索

   • 目的: 特定のセグメント $T[i]$ 内で、パターンの部分文字列と一致する文字列を見つける。
   • オラクル: 関数 $f_2(s, A)$。セグメント $T[i]$ の $s$ 番目の文字列が、指定されたパターン部分 $A$ と一致するか判定します。
   • 実装: 内部で $G_3$ を呼び出し、文字列同士の比較を行います。

3. 内側探索 ($G_3$): 文字列同士の比較

   • 目的: 2 つの文字列 $A$ と $B$ が等しいか判定（不一致の検出）。
   • オラクル: 関数 $f_3(c, A, B)$。$A$ と $B$ の $c$ 番目の文字が異なるか判定します。
   • 特徴: 1 つでも不一致があれば「不一致」と判定し、一致するまで探索します。QRAM を用いて文字列にアクセスします。

状態管理と更新

• 量子レジスタ（ID, prefix, active, match など）を用いて、各「量子スレッド」の状態（現在のパターン位置、アクティブなプレフィックスの有無、完全一致の有無）を管理します。
• 各セグメント $T[i]$ の処理において、$G_2$ と $G_3$ を用いて「拡張（ext）」「接尾辞一致（sm）」「接頭辞一致（pm）」を計算し、次のセグメントへの状態遷移を量子重ね合わせのまま更新します。

---

3. 主要な貢献と結果

時間計算量の改善

• 古典的最良: $O(mn + N)$
• 提案アルゴリズム: $\tilde{O}(\sqrt{mnN})$
  • ここで $\tilde{O}$ は対数因子を隠します。
  • この改善は、$m$（パターン長）、$n$（セグメント数）、$N$（総文字数）の平方根加速を組み合わせることで達成されました。
  • 証明にはコーシー・シュワルツの不等式が用いられ、$\sum \sqrt{|T[i]| \cdot k_i}$ の項が $\sqrt{mnN}$ で抑えられることが示されています。

仮定の緩和

• 初期のアルゴリズムでは、各セグメントの長さ $k_i < m$ であることを仮定していましたが、セクション 6 でこれを緩和しています。
• $k_i \ge m$ の場合、事前処理として「$P$ が単一の文字列 $S \in T[i]$ の部分文字列として存在するか」を $\tilde{O}(\sqrt{mN})$ でチェックする量子アルゴリズムを追加し、メインアルゴリズムの正しさを保証しています。

空間計算量

• 必要な量子ビット数は $O(\log m + n \log N)$ です。

---

4. 意義と考察

理論的意義

1. 構造化データへの量子適用: これまで主に単純な文字列や特殊なグラフ（レベル DAG）に限定されていた量子パターンマッチングの応用範囲を、より一般的な「一般化退化文字列」へと拡大しました。
2. ビット並列性の量子化: 従来の量子アルゴリズム（例：Equi et al. [9]）がビット並列的な古典アルゴリズムのシミュレーションに依存していたのに対し、本論文は GD 文字列特有の構造（シフトによるカバレッジ）を直接量子化し、より効率的な加速を実現しました。
3. 下界の難しさ: 本問題に対する量子下界（lower bound）の証明は困難であり、現在の技術ではグラフ内での文字列マッチング問題の量子下界さえ確立されていないことが指摘されています。

実用的意義

• バイオインフォマティクス: 退化文字列は DNA シーケンシング（特にバリアントやミスマッチを許容する領域）やタンパク質配列の解析で頻繁に現れます。GD 文字列モデルは、これらの不確実性を自然に表現できます。
• 大規模データ処理: 総文字数 $N$ が巨大なデータセットにおいて、$\sqrt{N}$ の加速は実用的な意味を持つ可能性があります。

結論

本論文は、一般化退化文字列におけるパターンマッチング問題に対して、古典アルゴリズムの並列性を量子重ね合わせと振幅増幅に転換することで、$\tilde{O}(\sqrt{mnN})$ という画期的な高速化を実現しました。これは、構造化された複雑なテキストデータに対する量子アルゴリズム設計の新たな指針を示すものです。