⚛️ quantum physics

Quantum Pattern Matching in Generalised Degenerate Strings

This paper presents a quantum algorithm that accelerates the exact pattern matching problem in generalized degenerate strings from the classical $O(mn+N)$ time complexity to $\tilde{O}(\sqrt{mnN})$ .

Original authors: Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific sentence (let's call it the Target Phrase) hidden inside a very strange, chaotic library.

The Problem: The "Chaos Library"

In a normal library, books are just lines of text. But in this paper, we are dealing with a Generalized Degenerate (GD) String. Think of this library not as a single book, but as a sequence of mystery boxes.

Box 1 contains four different short stories: "ACG...", "TAA...", "CGT...", "GTA...".
Box 2 contains two different stories: "GATC..." and "CGGT...".
Box 3 contains three options: "AC", "GT", "CA".

To read the "library," you have to pick one story from Box 1, then one from Box 2, then one from Box 3, and so on. If you do this, you create a valid "path" through the library.

The Goal: Does your Target Phrase (e.g., "GTGTTAA") appear as a continuous part of any possible path you could create by picking stories from these boxes?

The Old Way: The Classical Detective

Before this paper, the best way to solve this was like a team of human detectives working in a very organized, but slow, way.

They would line up the boxes.
They would try to match the first letter of your phrase against the first box.
Then the second letter against the second box, and so on.
If they hit a dead end, they would backtrack and try a different combination.

This was fast enough for small libraries, but if the library was huge (millions of characters), the detectives would get tired. The time it took grew linearly with the size of the library.

The New Way: The Quantum Super-Search

The authors of this paper asked: "What if we could use a Quantum Computer to solve this?"

Quantum computers are weird. Instead of checking one thing at a time, they can check many things at once using a concept called superposition. Imagine a detective who can be in 100 different places at the exact same time, all looking for the clue.

Here is how their new algorithm works, using a simple analogy:

1. The "Parallel Threads" (The Quantum Team)

Imagine you have a team of m detectives (where m is the length of your Target Phrase).

Detective 1 starts looking for the phrase at the very beginning of the library.
Detective 2 starts looking one step later.
Detective 3 starts looking two steps later.
...and so on, until Detective m starts looking at the m-th step.

In a normal computer, you would have to run these detectives one after another. But in a Quantum Computer, you can put all these detectives into a superposition. This means you are essentially running all of them simultaneously in a single "quantum wave."

2. The "Nested Search" (The Russian Dolls)

To make this fast, the algorithm uses a technique called Grover's Search. Think of this as a magical magnifying glass that finds a needle in a haystack much faster than looking at every piece of hay.

The authors built a "Russian Doll" of searches:

The Outer Search (The Boss): This searches through all the possible starting positions (the different detectives) to see if anyone found the phrase.
The Middle Search (The Segment Checker): Once the Boss picks a starting position, it needs to check the current "Mystery Box." It searches through all the different stories inside that box to see if any of them match the next part of the phrase.
The Inner Search (The Letter Checker): Once a specific story is picked, it needs to check if the letters match perfectly. It searches through the letters of the story to find a mismatch.

By nesting these searches, the quantum computer doesn't just check one path; it checks the possibility of all paths simultaneously, amplifying the "correct" answer and canceling out the "wrong" ones.

Why is this a Big Deal?

Speed: The old method took time proportional to the size of the library ( $N$ $N$ ). The new quantum method takes time proportional to the square root of the library size ( $\sqrt{N}$ $N$ ).
- Analogy: If the library has 1,000,000 characters, the old way might take 1,000,000 steps. The new way takes only 1,000 steps. That is a massive speedup.
Efficiency: They managed to do this without needing to pre-process the data into a complex map (like a graph), which saves a lot of memory and setup time.

The Catch (The "Assumption")

The paper admits a small caveat: They initially assumed that the "stories" inside the mystery boxes were shorter than the Target Phrase.

Analogy: Imagine your Target Phrase is 10 words long, and the stories in the boxes are only 5 words long. This makes the math easy.
The Fix: If a story in a box is longer than your Target Phrase (e.g., a 20-word story), they added a quick "pre-check" step to handle those specific long stories first. This ensures the algorithm works for any library, no matter how weird the boxes are.

Summary

This paper introduces a Quantum Detective Team that can search through a chaotic, branching library of text options. Instead of checking every single path one by one, it uses the power of quantum mechanics to check all paths at once, finding your hidden phrase significantly faster than any classical computer could.

It's like going from walking through a maze to teleporting through it, checking every possible route instantly to find the exit.

1. Problem Definition

The paper addresses the String Matching in Generalised Degenerate Strings (SMGD) problem.

Input: A pattern string $P$ of length $m$ and a Generalised Degenerate (GD) string $T$ .
GD String Structure: A GD string is a sequence of $n$ segments, $T[1..n]$ . Each segment $T[i]$ is a non-empty set of strings $\{S_1, S_2, \dots\}$ where all strings in a specific segment have the same length $k_i$ . The total size of the GD string is $N = \sum_{i=1}^n \sum_{S \in T[i]} |S|$ .
Matching Criteria: A match occurs if $P$ appears as a substring within any single string in a segment, or if $P$ is formed by concatenating a suffix of a string in $T[i]$ , full strings in intermediate segments, and a prefix of a string in $T[j]$ .
Goal: Determine existence (True/False) of at least one occurrence of $P$ in $T$ .
Classical Baseline: The best known classical algorithm runs in $O(mn + N)$ time.

2. Methodology

The authors propose a quantum algorithm that leverages Grover's search and amplitude amplification to achieve a speedup over the classical approach. The methodology involves three nested layers of quantum search.

A. Core Strategy: Parallelism via Superposition

The algorithm is inspired by a classical parallel approach where $m$ "threads" simultaneously scan the GD string $T$ , each starting at a different offset (shift) relative to the pattern $P$ .

Classical Parallelism: In a classical setting, one would launch $m$ threads. Thread $h$ checks if a match starts at column $h + r \cdot m$ for integers $r$ .
Quantum Translation: Instead of $m$ physical threads, the quantum algorithm creates a superposition of $m$ states (representing the $m$ possible shifts). It uses a nested Grover search structure to verify matches across these shifts simultaneously.

B. Nested Grover Searches

The algorithm employs three levels of Grover's search ( $G_1, G_2, G_3$ ) to evaluate a Boolean oracle function $f_1(h)$ , which returns 1 if a match exists starting at shift $h$ .

Innermost Search ( $G_3$ ): Character Mismatch Detection
- Function: Checks if two strings of equal length are identical.
- Mechanism: Uses Grover's search to find a single character mismatch between the pattern substring and a string in the current segment.
- Complexity: $O(\sqrt{k_i})$ for a segment of width $k_i$ .
Middle Search ( $G_2$ ): Segment Matching
- Function: Checks if a specific substring of $P$ matches any string within a specific segment $T[i]$ .
- Mechanism: Iterates over all strings $S \in T[i]$ using Grover's search. The oracle for this search calls $G_3$ to verify equality.
- Complexity: $O(\sqrt{|T[i]| \cdot k_i})$ , where $|T[i]|$ is the number of strings in the segment.
Outermost Search ( $G_1$ ): Global Shift Verification
- Function: Determines if any of the $m$ shifts results in a full pattern match across the entire GD string.
- Mechanism: Iterates over the $m$ possible starting shifts ( $h \in [0, m-1]$ ). The oracle for this search simulates the scanning process of a single "thread" across all $n$ segments of $T$ .
- State Management: The algorithm maintains quantum registers to track:
  - Current position in the pattern ($ji,h$).
  - Whether an active prefix match exists ( $active_i$ ).
  - Whether a full match has been found ( $match_i$ ).
  - Extension, suffix, and prefix match flags for the current segment.

C. Handling Edge Cases

The authors initially assume segment widths $k_i < m$ to simplify the logic. In Section 6, they drop this assumption by adding a preprocessing step:

A separate quantum routine checks if $P$ exists as a substring within any single string of $T$ (handling cases where $k_i \ge m$ ).
This preprocessing runs in $\tilde{O}(\sqrt{mN})$ , which is subsumed by the main algorithm's complexity.
If no internal substring match is found, the main algorithm proceeds, skipping the "extension" check for segments wider than $m$ since those columns are already covered by the preprocessing.

3. Key Contributions

First Quantum Algorithm for GD Strings: This is the first work to propose a quantum solution for string matching in Generalised Degenerate Strings, a structure more complex than standard strings but less complex than general graphs.
Complexity Improvement: The paper achieves a running time of $\tilde{O}(\sqrt{mnN})$ , significantly improving upon the classical $O(mn + N)$ bound.
- The $\tilde{O}$ notation hides polylogarithmic factors.
- The speedup is derived from the quadratic speedup of Grover's search applied to the search space of shifts ( $m$ ) and the search space within segments.
Novel Oracle Construction: The paper details a sophisticated construction of nested oracles that simulate a parallel scanning process without requiring the $O(N^2)$ edge expansion that would occur if the GD string were naively converted to a graph (which would degrade the quantum performance to $O(N^2\sqrt{m})$ ).
Theoretical Lower Bound Discussion: The authors acknowledge the difficulty in proving matching quantum lower bounds for this problem, noting that current lower-bound strategies struggle even with the harder problem of string matching on general graphs.

4. Results and Complexity Analysis

Time Complexity: $\tilde{O}(\sqrt{mnN})$ $\tilde{O} (mn N)$ .
- Derived from $O(\sqrt{m})$ iterations of the outer Grover search ( $G_1$ ).
- Each iteration involves processing $n$ segments.
- Processing a segment $T[i]$ takes $\tilde{O}(\sqrt{|T[i]| \cdot k_i})$ via the nested searches.
- Summing over all segments and applying the Cauchy-Schwarz inequality yields the final bound.
Space Complexity: $O(\log m + n \log N)$ $O (lo g m + n lo g N)$ qubits.
- Requires $O(\log m)$ for thread IDs and $O(\log N)$ for data registers per iteration.
Success Probability: The algorithm succeeds with high probability (constant error probability $< 1/3$ ), which can be boosted to an arbitrarily low constant by repeating the algorithm a constant number of times.

5. Significance

Bridging the Gap: The work bridges the gap between string matching on simple strings and string matching on labeled graphs. It demonstrates that quantum speedups are achievable for intermediate structures like GD strings without resorting to inefficient graph reductions.
Biological Applications: GD strings are heavily used in bioinformatics to represent genetic variations (e.g., multiple sequence alignments with indels or SNPs). A faster quantum algorithm for pattern matching in these structures could significantly accelerate genomic analysis tasks.
Algorithmic Paradigm: The paper showcases a technique of "quantum parallelism" where a classical multi-threaded logic is mapped to a superposition state, utilizing nested amplitude amplification to avoid the overhead of preprocessing (like building tries) that classical algorithms might require.
Future Directions: It opens the door for quantum algorithms on other generalized string structures (e.g., elastic degenerate strings) and highlights the need for new techniques to establish quantum lower bounds for graph-based string problems.