WorksComputer Science
Quantum Algorithm with Quadratic Speedup for 2D Pattern Matching
Abstract
We consider the problem of 2 dimensional pattern matching under Quantum Query model. Here, we are given a rectangular text and a pattern . We take and as the sizes of text and the pattern respectively (we assume ). Based upon the Quantum Advantage given by Grover's search (and subsequent Dürr-Høyer search), we create a solution which takes query complexity to answer if the pattern exists in . Our solution uses deterministic sampling as a primary component. As noted by earlier work in the literature, deterministic sampling is inadequate and witness tables are essential components for 2D matching. In our settings, we assume that the witness table of the pattern is precomputed classically and is available as an oracle to the quantum algorithm. Our main novel component is how to compute and employ a geometric structure called ``skyline" without losing the quantum advantage.
Introduction
Two-dimensional pattern matching is one of the most fundamental and intriguing problem areas in string processing [1]. The multidimensional nature of periodicity poses unique structural challenges for exact matching, index construction, and space-efficient text compression across various computing models. In this work, we study 2D pattern matching within the quantum query model. We show that one can achieve a near-quadratic quantum speedup for searching a rectangular pattern inside a rectangular text , where , , , and .
The substantial increase in attention and funding for quantum computing over the last decade has sparked a renewed push towards developing efficient quantum algorithms. Within string matching, a diverse array of quantum results has recently emerged [30, 32, 35, 34, 29, 31, 33]. Much like classical models of computation—such as PRAM, External Memory, and Cache-Oblivious models—the quantum query model introduces unique structural constraints. These constraints restrict the direct application of traditional algorithmic tools without forfeiting quantum advantage, necessitating the invention of novel techniques tailored specifically to quantum computational paradigms.
At its core, our approach builds upon the foundational framework for one-dimensional quantum pattern matching introduced by Ramesh and Vinay [5] and Wang and Ying [30], which in turn adapted the classical deterministic sampling paradigm proposed by Vishkin [6] for fast parallel (PRAM) algorithms. However, relying solely on deterministic sampling presents significant structural hurdles in the case of 2D matching. Subsequent classical algorithms resorted to using witness tables. See [18, 19, 20, 21, 22, 25, 26] for this line of work. Due to this restriction, our quantum algorithm assumes access to a precomputed witness table that explicitly identifies character positions where two shifted pattern candidates differ.
The fundamental distinction between 1D and 2D pattern matching lies in shift geometry: while 1D overlaps are strictly collinear, 2D candidate shifts can occur along arbitrary 2D vectors. Consequently, 2D periodicity branches into 1D-linearly periodic and 2D-lattice periodic regimes. A naive approach would reduce 2D matching to multiple 1D instances by analyzing the deterministic sample and periodicity of individual rows; however, such a reduction yields a suboptimal quantum query complexity of . Our target is to achieve the near-optimal subquadratic query bound of .
Central to our solution is the idea of skyline and how to creatively use Grover’s/Dürr-Høyer Search [2, 3]to create the skyline in 2D geometry. We introduce a recursive, area-based divide-and-conquer partitioning scheme to construct this skyline efficiently in Qauntum Model.
We want to note that, although classical precomputation of the witness table requires time—resulting in a hybrid quantum (or qRAM-based) algorithm with an overall operational time complexity of —we note that in many realistic problem settings, .
Our approach is to first use deterministic sampling, and then find out where the samples match in the text block of size , for a fixed constant . Depending on periodicity, we attempt to get these matches down to factor, and then we can afford sequential witness duels, to reduce these candidate matches further. Lastly, we deploy skyline based verification to achieve the final answer of whether the pattern matches in the block. Combining this with the outer search across blocks, we get complexity.
Map. The remainder of this paper is organized as follows. Section 2 defines the problem and establishes preliminaries. Sections 3 and 4 detail the deterministic sampling scheme, discuss the structural intricacies introduced by 2D periodicity, and demonstrate how witness duels reduce the candidate set to the desired structure and density. Section 5 introduces the skyline framework and presents its construction algorithm. Section 6 describes the final verification phase that pinpoint actual pattern occurrences from the pruned candidate set. Finally, Section 7 concludes with a formal quantum query and time complexity analysis.
Preliminaries
For pattern matching, we consider a rectangular pattern embedded in a rectangular text . Let denote the size of the pattern (i.e. its number of characters) and the size of the text. Let be a constant to be fixed later.
A shift , denoted , of the pattern is the placement of with its top-left corner at :
A column at position , with and , is the list of all shifts that are “pierced” by that position. Formally,
If and , then column pierces every shift under consideration. Such a column is called a middle column. The middle region of a pattern is
The inner middle region is defined analogously, with the factor of quadrupled on each side:
is held constant at a value at least 10. This ensures the dimensions of the inner middle region are at least .
Deterministic Sampling
Deterministic Sampling for an Aperiodic Pattern
We first construct a deterministic sample across the shifts with and .
Deterministic sampling proceeds iteratively. At every point during the procedure we maintain a set of surviving shifts, initialized as
As columns are appended to the deterministic sample, any shift that fails to match every column currently in the sample is removed from .
At each iteration, use Dürr–Høyer search to pick any two distinct surviving shifts . (Any procedure that returns two distinct surviving shifts suffices; for instance, one can impose any total order on and take the Dürr–Høyer minimum and maximum.) If no two distinct shifts remain — i.e. — deterministic sampling is complete.
Otherwise, use Grover’s search to find a middle column at which and disagree. If no middle column is found, then since some column must exist where and disagree due to the pattern being aperiodic, the period breaker algorithm can be utilized. Append this column to the deterministic sample, labeled with either of the two conflicting characters, chosen uniformly at random. Each such step removes at least one of or from , and with probability at least removes at least half of the remaining shifts, so the expected iteration count and deterministic sample size is logarithmic.
Deterministic Sampling for a Pattern with One Period (1-D Periodic)
Let the pattern’s period be .
As before, we construct a deterministic sample across the shifts with and , maintaining a set of surviving shifts initialized as
Again, any shift that fails to match a column added to the deterministic sample is removed from .
At each iteration, use Dürr–Høyer search to find a surviving shift (for instance the one with lowest -coordinate, tiebroken by highest ). Then use Grover’s search to find another surviving shift such that is not an integer multiple of the period ; that is, there is no integer with . If no such exists, deterministic sampling is complete. Otherwise, use Grover’s search to find a middle column at which and disagree; if none exist, since there must exist some column where they differ as is the only period of the pattern, the period breaker algorithm can be utilized. Append this column with one of the two characters from or chosen uniformly at random. As in the aperiodic case, each such step removes with probability at least at least half of the remaining shifts, so the expected iteration count and deterministic sample size is logarithmic.
Deterministic Sampling for a Pattern With Two (or more) Distinct Periods
In this case, we can assume and to be 2 distinct periods of the pattern, found from the witness table.
Lemma 3.1. The middle region of the pattern is lattice periodic with respect to and .
Proof. (proof). Take two arbitrary indices and in the middle region, and let . Note that the line connecting and must lie completely within the middle region. Create a list of indices of the form , starting with and ending with . For each element , if , then make the next element ; otherwise, make it . Every element must be at most or away from the central line, and therefore lies in the pattern. Since every element of the list is separated from the last by a period, all store the same character, so .
Lemma 3.2. If there exists distinct linear combinations of and , and , such that either one has an or component of 0, or they lie in opposite quadrants, and both are bound by dimensions , then the entire pattern is lattice periodic with respect to and .
Proof. We assume throughout. We must show that for any and separated by and , that must equal . Note that since the middle region of the pattern is proven to be lattice periodic, it is sufficient to prove , where and for some integers such that lies within the middle region. This is because, by the same proof, can also be linked to an index in the middle region, so then by lattice periodicity, must equal .
Since and are linear combinations of and , it is sufficient to show that after some applications of and (or their negative versions), will be transformed to a point within the middle region. This is because after every application of these periods, the new index must store the same character in as the previous.
Case 1: or is horizontal or vertical.
Without loss of generality, let be horizontal, and since is distinct, it must have a non-zero component. Without loss of generality, let be in quadrant 4 or be vertical with negative component.
To map to a cell in the middle region, attempt to first ensure its coordinate is within . If , then repeatedly do the following: repeatedly add until , then subtract . If , then repeatedly do the following: repeatedly subtract until , then add . Once , can be put within and by repeatedly adding or subtracting .
Case 2: and lie in orthogonal quadrants, with neither being horizontal or vertical. Without loss of generality, let be in quadrant 4 (and in quadrant 2) and let be in quadrant 3 (and in quadrant 1).
Subcase 1: or .
Without loss of generality, let and . Then, repeatedly apply if and otherwise; since the components of and are bounded by , these operations cannot push out of the range . Since decreases with each operation, eventually will be within .
Subcase 2: isn’t between and is not between .
Without loss of generality, let and . Then, repeatedly subtracting will either push into the middle region, in which case we are done, or into the zone where Subcase 1 can be used.
Lemma 3.3. Given and , if they lie in the same or opposite quadrants, then a period lying in an orthogonal quadrant can be constructed whose dimensions are bounded by .
Proof. Let and be the periods, in the same quadrant, without loss of generality quadrant 1 (if they lie in opposite quadrants, first negate one of them). Potentially invert to ensure its direction component is opposite from ’s.
Repeatedly do the following with the current period , starting from 0, until lies in or : if ’s component matches ’s, add to it; otherwise, add .
’s component is bounded by the components of and . Since , over the process, ’s component will eventually exceed such a bound, putting in or .
Bound on ’s size: before the final application of or , ’s component was bounded by its component, which is bounded by ’s or ’s component. Then or is applied once. Hence is the sum of 3 vectors bounded by , so it is bounded by .
If this new period is a period of the entire pattern, then by lemma 3.2, the pattern is lattice periodic with respect to and . Otherwise, since the middle region of the pattern is periodic with respect to due to it being lattice periodic, and the whole pattern is not, the period breaker algorithm can be used.
Lemma 3.4. If the period-breaker algorithm terminates with multiple shifts remaining - which implies the existence of a horizontal or vertical period - then the pattern is lattice periodic with respect to that horizontal or vertical period together with some other period.
Proof. Since there is a horizontal period, and since the pattern is 2D periodic there must be some other distinct period, lemmas 3.1 and 3.2 can be applied to show the pattern is lattice periodic.
Deterministic Sampling for a Lattice Periodic Pattern
Let the current period vectors be and . At every iteration, we perform the following.
Find one surviving shift, , and let . Add to each column in the deterministic sample, taken modulo and so that they remain middle columns. This translates the surviving shift to .
Search for a surviving shift not on the lattice defined by , , and . If none exists, deterministic sampling is complete. If another exists, denote it .
If a column exists where and differ (if there exists one, there must be a middle column due to lattice periodicity), add it to the deterministic sample, randomly choosing a character from or . Otherwise, , which is not a linear combination of and , is a period of the pattern.
Note that linear combinations of and tile the plane in parallelograms, and so must lie in or on the edge of some such parallelogram. Let its corners be , , , and , where all corners are linear combinations of and .
Divide the parallelogram into 4 similar ones by dividing across the lines joining the midpoints of opposite sides. will lie in or on the edge of one; without loss of generality, let it be the parallelogram with as a vertex. Then, the triangles defined by the vectors and , as well as and , form disjoint regions within the parallelogram. If the former triangle is smaller in size, make and the new periods; otherwise, make them and .
Lemma 3.5. The parallelograms formed by the new period and the selected current period has area at most half that of the original parallelogram.
Proof. Without loss of generality, assume the new vectors chosen are and . Since the triangle defined by and is at most half of a quarter of the area of the parallelogram defined by and , the parallelogram defined by and is at most the area of the parallelogram defined by and . Hence the parallelogram defined by and has area at most half that of the parallelogram defined by and .
We then adopt this current period together with the new period as the new pair of period vectors. By Lemma 3.5, each iteration either the size of the parallelogram formed by and is halved or the total shifts (modulo and ) is halved, keeping the total iterations and the deterministic sample size .
Period-Breaker Algorithm
Note: If this stage is reached, any previously constructed deterministic sample should be disregarded.
This algorithm handles the following situation. Suppose there is where and , such that:
the middle region of the pattern is periodic with respect to . This can be implied from there being no middle column at which some 2 shifts and differ, where ; but
there is some pattern index with .
Define a pattern index to be:
good if ,
bad if ,
neutral if is out of range.
Lemma 3.6. If there is an rectangle in the pattern, , containing all good cells except exactly one row or one column containing at least 1 bad cell, a deterministic sample can be created leaving a horizontal or vertical line of at least one shifts.
Proof. (proof). Let the top left corner of the rectangle be at index , and let one bad index be at . Let and the index in shifted by be as in the period-breaker setting; in particular contains no neutral cells.
Consider the columns and . For any shift , these store the indices and . Note that these are an index in and the index shifted by , respectively.
Make the deterministic sample columns and with characters and . Since these are the characters stored by the shift , denoted , at least one shift survives this deterministic sample. Additionally, these characters are distinct, as is bad.
Without loss of generality, let bad indices only exist in the row of with indices . Then, for any shift with -coordinate not equal to , the index the first column is mapped to cannot have index , and therefore must be good. Hence it will store the same character in the 2 columns and be deleted. As such, at most the horizontal line of shifts with coordinate will survive.
From here, deterministic sampling can proceed analogously to the 1-D case.
Any index in the inner middle region — i.e. with and — is automatically good, due to the middle region being periodic with respect to . Since a bad index exists by hypothesis, at least one bad index lies outside the inner middle region. The remainder of the pattern (outside the inner middle region) partitions into four cardinal strips immediately adjacent to the inner middle region (above, below, left, right of it) and four corner regions (the four corners not in any cardinal direction from the inner middle region). We split into two cases based on where the bad indices lie.
Case 1: There exists a bad index inside one of the four cardinal strips.
Whether this condition holds can be tested with a Dürr–Høyer search over each strip. Without loss of generality, suppose a bad index lies in the top cardinal strip, i.e. satisfies together with (so it lies to the right of the inner middle region’s right edge, above the region). Use Dürr–Høyer search to find, among such indices, the bad index with smallest -coordinate; call it .
If , the rectangle with top left corner at satisfies the condition for the deterministic sample, as it only has bad indices in its top row; otherwise the rectangle with top right corner at can be used.
Case 2: No bad index lies in any cardinal strip (so every bad index lies in a corner region).
Without loss of generality, assume a bad index lies in the top-left corner region, i.e. satisfies and . Use Dürr–Høyer search to find, among such bad indices, the one with minimum -coordinate, tiebroken by maximum -coordinate, . This selection ensures that the region contains only good indices other than , and therefore can be used as the rectangle to create the deterministic sample.
Lemma 3.7 (Complexity of Deterministic Sampling). The deterministic sampling process runs in time.
Proof. Each form of deterministic sampling takes iterations, and each iteration utilizes a constant number of Grover’s or Dürr–Høyer queries. The period breaker algorithm also uses a constant number of Grover’s or Dürr–Høyer queries followed by iterations of a constant number of Grover’s or Dürr–Høyer queries. Hence, the total time complexity of deterministic sampling is .
Ricochet Property with the Deterministic Sample
The ricochet property states that once a deterministic sample matches at a given text position, the set of other positions in a surrounding neighborhood that can also match is tightly constrained. Which constraint applies depends on the periodicity type of . We treat the two cases separately.
Single Shift or Line of Shifts Surviving
Partition the initial surviving-shift region into four quadrants of (roughly) equal size. Without loss of generality, suppose the shift surviving deterministic sampling (or, in the 1-D periodic case, one of the arbitrary surviving shifts) lies in the bottom-right quadrant. Then in the region to the bottom-right of a deterministic-sample match, the pattern cannot match — except, in the 1-D periodic case, at translates of other surviving shifts by the period.
Lattice Periodic Deterministic Sample
Since a surviving shift sits at the center of the initial shift region, if the deterministic sample matches at a given position, then within a surrounding block of size , the pattern cannot match at any index that is not an integer linear combination of the periods away from the deterministic-sample match.
The Skyline
Consider a rectangle , where without loss of generality . Suppose we are given a binary function on with and , assigning each index a value in . Call indices mapped to 1 good and indices mapped to 0 bad.
The skyline aims to answer, for each row from 0 to , the maximum such that contains only good indices. Formally, the skyline is the sequence such that for all and all .
We solve this recursively. At every stage of the recursion we construct the skyline on a sub-rectangle parameterized by , with rows and columns. Initially , , , .
Let , the total number of cells relevant to the current portion of the skyline construction (within ), be the area. We would like to decompose the skyline into two pieces of (roughly) equal area. We do this by binary searching for the -coordinate of a “midpoint” — initialized at — that splits the skyline into two equal-area regions.
At each step of the binary search, for the trial -coordinate we use Grover’s algorithm (Dürr–Høyer) to find the bad index of least -coordinate, , within the region . If no such index exists, we set . The two resulting half-areas are and ; binary search equalizes them.
Once the correct -coordinate of the midpoint is found, a second binary search — this time on the -coordinate — refines the area balance exactly.
Lemma 5.1 (Area Bound). If both halves have exactly equal area, each must have at most of the area of the larger enclosing region.
Proof. Let the left region have dimensions and the right region have dimensions , where the enclosing region has dimensions and . It suffices to show
which is clearly true since and are positive and .
By the intermediate value theorem, some splitting point of this form must approximately exist. However, if one dimension of the region becomes too small, the split need not be close to half. To handle this edge case, if either dimension falls below some constant, we instead construct the skyline manually by locating the lowest violator in each row (or column) along the smaller dimension and tracking the jumps of the resulting skyline; this involves Grover searches over a region of size the (larger) remaining dimension, so the base case also costs , consistent with the recurrence below.
Lemma 5.2 (Skyline Construction Cost). Constructing the skyline for a block of area costs .
Proof. At a node of the recursion with region area , the two binary searches (for then ) each take steps, and each step is one Grover search over a region of size at most , costing . So the cost at a single node, excluding its recursive calls, is . By Lemma 5.1, the node recurses into 2 children each of area at most , giving
At recursion depth there are at most nodes, each of area at most , so the total cost at level is
The recursion bottoms out after at most levels, so summing across all levels,
The final stage of the algorithm yields a series of registers encoding “right” or “down” moves of specified magnitudes. This representation is then converted into per-column heights (one per column, indexed by ), so that the total information stored is at most .
Pattern Matching in the Text: Four-Corner Skyline Verification
Three of the subsequent pattern-matching subsections share a common verification step — running four skylines based from the four corners of adjacent blocks, computing four cardinal-direction extreme bad indices, screening a shared inner region, and then Grover-searching for a candidate shift that satisfies all the constraints. We present that shared machinery once here and reference it from each case.
Fix a block . Suppose we are given:
a notion of “good” and “bad” text cells supplied by a oracle (whose definition differs per case — see below), and
a residue condition that constrains which shifts are candidates (“in ,” “in the surviving class,” or “in the lattice coset through ” depending on the case).
Four-corner skylines. Construct skylines of good cells based from, respectively, the bottom-right corner of block , the bottom-left corner of block , the top-right corner of block , and the top-left corner of block . These four skylines are independent of each other and of the four cardinal extremes defined below.
Four cardinal-direction bad-index extremes. Independently from the four skylines, use Dürr–Høyer search over the four cardinal strips surrounding the current block to extract four bad-index extremes:
: the bad index of minimum -coordinate in the top strip ;
: the bad index of maximum -coordinate in the bottom strip ;
: the bad index of maximum -coordinate in the left strip ;
: the bad index of minimum -coordinate in the right strip .
(Here we have renamed the bottom-strip extreme to to avoid clashing with the period-breaker gap .)
Shared inner-region bad-cell screening. Use Grover’s search to test whether the shared region
contains any bad cell. Since this region is contained in every pattern instance whose top-left corner lies in the current block, the presence of a bad cell here rules out every candidate in the block; otherwise this region can be disregarded entirely.
Per-candidate verification oracle. For each pattern instance with top-left corner at satisfying the residue condition of the case, the full pattern instance consists only of good cells if and only if:
lies within the top-left-corner skyline,
lies within the top-right-corner skyline,
lies within the bottom-left-corner skyline,
lies within the bottom-right-corner skyline,
, and
.
This conjunction can be checked by an oracle.
Final Grover search. Use Grover’s search over candidate shifts, filtered by the residue condition of the case, returning any candidate for which the above conjunction holds. A pattern match in the block exists if and only if some candidate is returned.

Figure 1. 4 Skylines and extended regions for block
Pattern Matching if no Other Shifts Remain in the Ricochet Zone of a Surviving Shift
Divide the text into blocks of size .
For each block , use the skyline algorithm to find a skyline of the region relative to the top-left corner that contains no deterministic-sample matches. Then, by the ricochet property, the only potential pattern-match positions are among the at most deterministic-sample matches lying just outside corners of the skyline.
We then maintain a list of candidate match positions, sorted by increasing -coordinate, initially empty. For each deterministic-sample-match position encountered along the skyline, proceed as follows:
If is empty, add to it and continue to the next match along the skyline.
Otherwise, let the last element of be . Use the witness table to either find an index in the text at which pattern instances based at and at would disagree, or determine that no such index exists.
If no such exists (either in or in the witness table), add to and continue to the next match along the skyline.
If the pattern instance at matches the text at , remove from and restart from step 1. Otherwise, continue to the next match along the skyline.
By construction, only positions in can match the pattern, and no two pattern instances based at positions in disagree at any text index.
Build, in time, a query structure that given - and -coordinate ranges returns an index into falling in that range; queries cost .
Define a oracle labeling each text index as good or bad: good indices match the pattern instance being considered; bad indices either do not match or are irrelevant to any instance under consideration.
The oracle acts on a text index as follows. First, query for an element with and ; this ensures the pattern instance based at covers . If no such exists, label bad. Otherwise, label good if and bad otherwise.
Apply the four-corner skyline verification from § 6 with this good/bad oracle and the residue condition “” to detect any pattern match in the block.
Pattern Matching if the Pattern is 1-D Periodic and Another Shift Survives in the Ricochet Zone
Let the pattern’s period be . Without loss of generality, assume .
For each block , use the skyline algorithm to find a skyline of relative to the top-left corner that contains no deterministic-sample matches.
Call two text indices members of the same class if they differ by an integer multiple of . Since the pattern is only 1-D periodic, no two indices from distinct classes could support pattern instances whose overlapping region is free of conflicts.
Two cases arise, depending on . In each we identify a single class that could contain all possible pattern matches.
Finding the Surviving Class if
Each class that could contain a pattern match must include a deterministic-sample match on the skyline together with the shifts lying at integer multiples of below it. There are at most such classes. All indices within one such class share an -coordinate.
We reduce these classes down to one surviving class via repeated pairwise duels. In each duel, between class 1 (with -coordinate ) and class 2 (with -coordinate ), assume WLOG . Let be the index in class 1 of lowest -coordinate, and the index in class 2 of highest -coordinate. Since — by the skyline’s structure — the -coordinate of exceeds the -coordinate of every index in class 1, the overlap region of the pattern instances at and sits entirely within every pattern instance based at an index in class 1 or class 2, with one potential exception: , the index of class 2 with lowest -coordinate, if .
Using the witness table, find an index at which the pattern instances at and disagree. If matches the text at this disagreement index, then no index in class 1 can match the pattern, and class 2 wins the duel. Otherwise, matches at the disagreement; the only candidate in class 2 that might still match is . Then duel against the index in class 1 of highest -coordinate: since the overlap region of these two pattern instances lies inside every pattern instance in class 1, if matches at the disagreement index, class 2 wins; otherwise class 1 wins.
Finding the Surviving Class if
For every -coordinate present in the block, consider the deterministic-sample match on the skyline with the greatest -coordinate not exceeding (if no such match exists, every index in the block with -coordinate lies outside the skyline and cannot match the pattern). Every index in the block with -coordinate is either in the ricochet zone of , or outside the skyline and hence not a pattern-match candidate.
Hence, the only index with -coordinate that could match the pattern is the at-most-one index that is an integer multiple of away from , i.e. , and only when is an integer.
Since there is only one possible surviving index per -coordinate, at most surviving indices remain overall.
Maintain a list of candidate indices, sorted by increasing -coordinate, initially empty. At all times contains only indices whose pattern instances pairwise have no index of disagreement, so can contain indices from at most one class.
For each surviving index , in order of increasing , repeatedly do:
If is empty or already contains elements from ’s class, add to .
Otherwise, duel against the last element of by consulting the witness table’s disagreement index. If matches the text at the disagreement index, remove the last element of and repeat; otherwise skip .
In the end, contains indices from at most one class — the surviving class.
Pattern Matching Once the Surviving Class Is Known
Let be any index in the surviving class.
Define a oracle labeling text cells as good or bad: good indices match the pattern instances under consideration; bad indices either do not match or are irrelevant.
To implement the oracle for query index : find an integer (and in the sub-case, this takes the form of using the period relation once) such that lies inside , by using the intersection of the four inequalities , , , . If no such exists, is bad. Otherwise, is good iff .
Apply the four-corner skyline verification from Section 6 with this oracle and with residue condition “ belongs to the same class as ” to detect any pattern match in the block.
Pattern Matching for a Lattice-Periodic Pattern
Let the two periods be and .
Use Grover’s search to find some deterministic-sample match . By the ricochet property, the pattern either matches at an integer linear combination of and away from , or matches nowhere in the block.
Define a oracle labeling text cells as good or bad: good indices match the pattern instances under consideration; bad indices either do not match or are irrelevant.
To implement the oracle for query index : find integers such that lies inside , using the intersection of the four inequalities , , , . Then is good iff .
Apply the four-corner skyline verification from Section 6 with this oracle and with residue condition “ is an integer linear combination of and away from ” to detect any pattern match in the block.
Time Complexity
As shown earlier, the time complexity of deterministic sampling is .
Per block, the cost for creating the 4 block skylines is shown to be , and finding the nearest bad cells on the edges and checking if the shared region only contains good cells are all Grover’s or Dürr–Høyer algorithm queries. In the 1st case of pattern matching, per block, there is an cost of finding the initial skyline shifts, another to duel them to create , and a final cost to create a query structure for elements of amounting to a additional cost.
In the 2nd case of pattern matching, per block, there is an additional cost to finding the skyline shifts and a cost to find the surviving class.
In the 3rd case of pattern matching, there is an additional cost per block to find a deterministic sample match.
Hence, the total cost per block in any case is . Querying over the blocks with Grover’s search, the total complexity arrives to .
Theorem 7.1. Given a pattern and a text and a witness table as oracles, (where ) finding whether occurs in can be found by quantum query complexity.
AI disclosure: Generative AI has been used for proof reading, fixing language issues, checking logical issues, creating pseudocodes and figures and creating latex from drafts. All the ideas and solutions are authors’ own. AI generated parts were carefully reviewed for accuracy. Authors are fully responsibility for the content.
References
- [1]Amihood Amir, Gary Benson, and Martin Farach. An alphabet-independent optimal parallel algorithm for two-dimensional pattern matching. SIAM Journal on Computing, 23(2):313–323, 1994.
- [2]Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996.arxiv.org/abs/quant-ph/9607014
- [3]Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 212–219, 1996.arxiv.org/abs/quant-ph/9605043
- [5]H. Ramesh and V. Vinay. String matching in O(√n + √m) quantum queries. Journal of Discrete Algorithms, 1(1):103–110, 2003.DOI
- [6]Uzi Vishkin. Deterministic sampling—a tool for fast parallel string matching. SIAM Journal on Computing, 20(1):22–40, 1991.
- [18]A. Amir, G. Benson, and M. Farach. Alphabet independent two dimensional matching. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pages 59–68, 1992.DOI
- [19]A. Amir, G. Benson, and M. Farach. An alphabet independent approach to two-dimensional pattern matching. SIAM Journal on Computing, 23(2):313–323, 1994.DOI
- [20]Z. Galil and K. Park. Truly alphabet-independent two-dimensional pattern matching. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 247–256, 1992.DOI
- [21]M. Crochemore, L. Gasieniec, and W. Rytter. Two-dimensional pattern matching by sampling. Information Processing Letters, 46(4):159–162, 1993.
- [22]M. Crochemore, L. Gasieniec, R. Hariharan, S. Muthukrishnan, and W. Rytter. A constant time optimal parallel algorithm for two-dimensional pattern matching. SIAM Journal on Computing, 27(3):668–681, 1998.
- [25]A. Amir and G. Benson. Two-dimensional periodicity and its applications. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 440–452, 1992.
- [26]A. Amir and G. Benson. Two-dimensional periodicity in rectangular arrays. SIAM Journal on Computing, 27(1):90–106, 1998.DOI
- [29]A. Montanaro. Quantum pattern matching fast on average. Algorithmica, 77(1):16–39, 2017.
- [30]Q. Wang and M. Ying. Quantum algorithm for lexicographically minimal string rotation. arXiv preprint arXiv:2012.09376, 2020.DOI
- [31]S. Akmal and C. Jin. Near-optimal quantum algorithms for string problems. Algorithmica, 85(8):2260–2317, 2023.
- [32]C. Jin and J. Nogler. Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching. ACM Transactions on Algorithms, 20(4):1–36, 2024. Preliminary version in SODA 2023.
- [33]F. Le Gall and S. Seddighin. Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 97:1–97:23, 2022.DOI
- [34]D. Gibney and S. V. Thankachan. Compressibility-aware quantum algorithms on strings. arXiv preprint arXiv:2302.07235, 2023.arxiv.org/abs/2302.07235
- [35]D. Gibney, C. Jin, T. Kociumaka, and S. V. Thankachan. Near-optimal quantum algorithms for bounded edit distance and Lempel–Ziv factorization. In Proceedings of the 2024 ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 3302–3332, 2024.arxiv.org/abs/2311.01793