betaFeedback

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 T[0..n1−1][0..n2−1]T[0..n_1-1][0..n_2-1] and a pattern P[0..m1−1][0..m2−1]P[0..m_1 -1][0..m_2-1]. We take N=n1n2N = n_1n_2 and M=m1m2M = m_1m_2 as the sizes of text and the pattern respectively (we assume M<NM < N). Based upon the Quantum Advantage given by Grover's search (and subsequent Dürr-Høyer search), we create a solution which takes O~(N)\tilde{O}(\sqrt{N}) query complexity to answer if the pattern PP exists in TT. 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 P[0…m1−1][0…m2−1]P[0 \ldots m_{1} - 1][0 \ldots m_{2} - 1] inside a rectangular text T[0…n1−1][0…n2−1]T[0 \ldots n_{1} - 1][0 \ldots n_{2} - 1], where m1≤n1m_{1} \le n_{1}, m2≤n2m_{2} \le n_{2}, M=m1m2M = m_{1}m_{2}, and N=n1n2N = n_{1}n_{2}.

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 O~(N3/4)\widetilde{O}(N^{3/4}). Our target is to achieve the near-optimal subquadratic query bound of O~(N)\widetilde{O}(\sqrt{N}).

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 O(M)O(M) time—resulting in a hybrid quantum (or qRAM-based) algorithm with an overall operational time complexity of O(M+N)O(M+\sqrt{N})—we note that in many realistic problem settings, M≤O(N)M \le O(\sqrt{N}).

Our approach is to first use deterministic sampling, and then find out where the samples match in the text block of size (m1+m1/(2k))×(m2+m2/(2k))(m_1+m_1/(2k)) \times(m_2+m_2/(2k)), for a fixed constant kk. Depending on periodicity, we attempt to get these matches down to M\sqrt{M} 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 O~(N)\widetilde{O}(\sqrt{N}) 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 O~(N)\widetilde{O}(\sqrt{N}) 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 P[0…m1−1][0…m2−1]P[0\ldots m_1-1][0\ldots m_2-1] embedded in a rectangular text T[0…n1−1][0…n2−1]T[0\ldots n_1-1][0\ldots n_2-1]. Let M=m1⋅m2M=m_1\cdot m_2 denote the size of the pattern (i.e. its number of characters) and N=n1⋅n2N=n_1\cdot n_2 the size of the text. Let kk be a constant to be fixed later.

A shift (a,b)(a,b), denoted P(a,b)P_{(a,b)}, of the pattern P[0…m1−1][0…m2−1]P[0\ldots m_1-1][0\ldots m_2-1] is the placement of PP with its top-left corner at (a,b)(a,b):

P(a,b)[i,j]=P[i−a][j−b],with index space P(a,b)[a…a+m1−1][b…b+m2−1].P_{(a,b)}[i,j] = P[i-a][j-b],\qquad\text{with index space } P_{(a,b)}[a\ldots a+m_1-1][b\ldots b+m_2-1].

A column at position (i,j)(i,j), with i<m1+m1/ki < m_1+m_1/k and j<m2+m2/kj < m_2+m_2/k, is the list of all shifts that are “pierced” by that position. Formally,

Si,j={((a,b);c):P[i−a][j−b]=c ∧ a≤i<a+m1 ∧ b≤j<b+m2}.S_{i,j}=\{((a,b);c):P[i-a][j-b]=c\ \land\ a\le i<a+m_1\ \land\ b\le j<b+m_2\}.

If m1/k≤i<m1m_1/k\le i<m_1 and m2/k≤j<m2m_2/k\le j<m_2, then column (i,j)(i,j) pierces every shift under consideration. Such a column is called a middle column. The middle region of a pattern P[0…m1][0…m2]P[0 \ldots m_1][0 \ldots m_2] is

Pmid=P[m1/k…m1−m1/k][m2/k…m2−m2/k].P^{\mathrm{mid}} = P[m_1/k \ldots m_1-m_1/k][m_2/k \ldots m_2-m_2/k].

The inner middle region is defined analogously, with the factor of mi/km_i/k quadrupled on each side:

Pinmid=P[4m1/k…m1−4m1/k][4m2/k…m2−4m2/k].P^{\mathrm{inmid}} = P[4m_1/k \ldots m_1-4m_1/k][4m_2/k \ldots m_2-4m_2/k].

kk is held constant at a value at least 10. This ensures the dimensions of the inner middle region are at least 2m1/k×2m2/k2m_1/k \times2m_2/k.

Deterministic Sampling

Deterministic Sampling for an Aperiodic Pattern

We first construct a deterministic sample across the shifts (a,b)(a,b) with 0≤a≤⌊m1/k⌋0 \leq a \leq\lfloor m_1/k \rfloor and 0≤b≤⌊m2/k⌋0 \leq b \leq\lfloor m_2/k \rfloor.

Deterministic sampling proceeds iteratively. At every point during the procedure we maintain a set SS of surviving shifts, initialized as

S={(a,b):0≤a≤⌊m1/k⌋∧0≤b≤⌊m2/k⌋}.S = \{(a,b): 0 \leq a \leq\lfloor m_1/k \rfloor\mathbin{\wedge} 0 \leq b \leq\lfloor m_2/k \rfloor\}.

As columns are appended to the deterministic sample, any shift that fails to match every column currently in the sample is removed from SS.

At each iteration, use Dürr–Høyer search to pick any two distinct surviving shifts s1,s2∈Ss_1,s_2 \in S. (Any procedure that returns two distinct surviving shifts suffices; for instance, one can impose any total order on SS and take the Dürr–Høyer minimum and maximum.) If no two distinct shifts remain — i.e. ∣S∣≤1|S| \leq1 — deterministic sampling is complete.

Otherwise, use Grover’s search to find a middle column at which s1s_1 and s2s_2 disagree. If no middle column is found, then since some column must exist where s1s_1 and s2s_2 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 s1s_1 or s2s_2 from SS, and with probability at least 1/21/2 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 v=(xv,yv)\mathbf{v}=(x_v,y_v).

As before, we construct a deterministic sample across the shifts (a,b)(a,b) with 0≤a≤⌊m1/k⌋0 \leq a \leq\lfloor m_1/k \rfloor and 0≤b≤⌊m2/k⌋0 \leq b \leq\lfloor m_2/k \rfloor, maintaining a set SS of surviving shifts initialized as

S={(a,b):0≤a≤⌊m1/k⌋∧0≤b≤⌊m2/k⌋}.S = \{(a,b): 0 \leq a \leq\lfloor m_1/k \rfloor\mathbin{\wedge} 0 \leq b \leq\lfloor m_2/k \rfloor\}.

Again, any shift that fails to match a column added to the deterministic sample is removed from SS.

At each iteration, use Dürr–Høyer search to find a surviving shift sl=(xl,yl)s_l=(x_l,y_l) (for instance the one with lowest xx-coordinate, tiebroken by highest yy). Then use Grover’s search to find another surviving shift so=(xo,yo)s_o=(x_o,y_o) such that so−sls_o-s_l is not an integer multiple of the period v\mathbf{v}; that is, there is no integer nn with so−sl=nvs_o-s_l=n\mathbf{v}. If no such sos_o exists, deterministic sampling is complete. Otherwise, use Grover’s search to find a middle column at which sls_l and sos_o disagree; if none exist, since there must exist some column where they differ as vv is the only period of the pattern, the period breaker algorithm can be utilized. Append this column with one of the two characters from sls_l or sos_o chosen uniformly at random. As in the aperiodic case, each such step removes with probability at least 1/21/2 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 v1v_1 and v2v_2 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 v1v_1 and v2v_2.

Proof. (proof). Take two arbitrary indices (a,b)(a,b) and (c,d)(c,d) in the middle region, and let (c−a,d−b)=αv1+βv2(c-a,d-b)=\alpha v_1+\beta v_2. Note that the line connecting (a,b)(a,b) and (c,d)(c,d) must lie completely within the middle region. Create a list of indices of the form (a,b)+c1v1+c2v2(a,b)+c_1v_1+c_2v_2, starting with (a,b)+0v1+0v2(a,b)+0v_1+0v_2 and ending with (a,b)+αv1+βv2=(c,d)(a,b)+\alpha v_1+\beta v_2=(c,d). For each element (a,b)+c1v1+c2v2(a,b)+c_1v_1+c_2v_2, if c1α<c2β\frac{c_1}{\alpha}<\frac{c_2}{\beta}, then make the next element (a,b)+(c1+1)v1+c2v2(a,b)+(c_1+1)v_1+c_2v_2; otherwise, make it (a,b)+c1v1+(c2+1)v2(a,b)+c_1v_1+(c_2+1)v_2. Every element must be at most v1v_1 or v2v_2 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 P[a][b]=P[c][d]P[a][b]=P[c][d].

Lemma 3.2. If there exists distinct linear combinations of v1v_1 and v2v_2, v3v_3 and v4v_4, such that either one has an xx or yy component of 0, or they lie in opposite quadrants, and both are bound by dimensions 3m1k×3m2k\frac{3m_1}{k}\times\frac{3m_2}{k}, then the entire pattern is lattice periodic with respect to v1v_1 and v2v_2.

Proof. We assume k≥8k\ge8 throughout. We must show that for any (a,b)(a,b) and (c,d)(c,d) separated by αv1\alpha v_1 and βv2\beta v_2, that P[a][b]P[a][b] must equal P[c][d]P[c][d]. Note that since the middle region of the pattern is proven to be lattice periodic, it is sufficient to prove P[a][b]=P[a′][b′]P[a][b]=P[a'][b'], where a′=a+λ1xv1+λ2xv2a'=a+\lambda_1xv_1+\lambda_2xv_2 and b′=b+λ1yv1+λ2yv2b'=b+\lambda_1yv_1+\lambda_2yv_2 for some integers λ1,λ2\lambda_1,\lambda_2 such that (a′,b′)(a',b') lies within the middle region. This is because, by the same proof, P[c][d]P[c][d] can also be linked to an index in the middle region, so then by lattice periodicity, P[a][b]P[a][b] must equal P[c][d]P[c][d].

Since v3v_3 and v4v_4 are linear combinations of v1v_1 and v2v_2, it is sufficient to show that after some applications of v3v_3 and v4v_4 (or their negative versions), (a,b)(a,b) 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 PP as the previous.

Case 1: v3v_3 or v4v_4 is horizontal or vertical.

Without loss of generality, let v3v_3 be horizontal, and since v4v_4 is distinct, it must have a non-zero yy component. Without loss of generality, let v4v_4 be in quadrant 4 or be vertical with negative yy component.

To map (a,b)(a,b) to a cell in the middle region, attempt to first ensure its yy coordinate is within [m2k,m2−m2k]\left[\frac{m_2}{k},m_2-\frac{m_2}{k}\right]. If b<m2kb<\frac{m_2}{k}, then repeatedly do the following: repeatedly add v3v_3 until a>m12a>\frac{m_1}{2}, then subtract v4v_4. If b>m2−m2kb>m_2-\frac{m_2}{k}, then repeatedly do the following: repeatedly subtract v3v_3 until a<m12a<\frac{m_1}{2}, then add v4v_4. Once m2k<b<m2−m2k\frac{m_2}{k}<b<m_2-\frac{m_2}{k}, aa can be put within m1k\frac{m_1}{k} and m1−m1km_1-\frac{m_1}{k} by repeatedly adding or subtracting v3v_3.

Case 2: v3v_3 and v4v_4 lie in orthogonal quadrants, with neither being horizontal or vertical. Without loss of generality, let v3v_3 be in quadrant 4 (and −v3-v_3 in quadrant 2) and let v4v_4 be in quadrant 3 (and −v4-v_4 in quadrant 1).

Subcase 1: m1k<a<m1−m1k\frac{m_1}{k}<a<m_1-\frac{m_1}{k} or m2k<b<m2−m2k\frac{m_2}{k}<b<m_2-\frac{m_2}{k}.

Without loss of generality, let m1k<a<m1−m1k\frac{m_1}{k}<a<m_1-\frac{m_1}{k} and b>m2−m2kb>m_2-\frac{m_2}{k}. Then, repeatedly apply v3v_3 if a<m12a<\frac{m_1}{2} and v4v_4 otherwise; since the xx components of v3v_3 and v4v_4 are bounded by 3m1k\frac{3m_1}{k}, these operations cannot push aa out of the range m1k…m1−m1k\frac{m_1}{k}\ldots m_1-\frac{m_1}{k}. Since bb decreases with each operation, eventually bb will be within m2k…m2−m2k\frac{m_2}{k}\ldots m_2-\frac{m_2}{k}.

Subcase 2: aa isn’t between m1k…m1−m1k\frac{m_1}{k}\ldots m_1-\frac{m_1}{k} and bb is not between m2k…m2−m2k\frac{m_2}{k}\ldots m_2-\frac{m_2}{k}.

Without loss of generality, let a<m1ka<\frac{m_1}{k} and b>m2−m2kb>m_2-\frac{m_2}{k}. Then, repeatedly subtracting v4v_4 will either push (a,b)(a,b) into the middle region, in which case we are done, or into the zone where Subcase 1 can be used.

Lemma 3.3. Given v1v_1 and v2v_2, 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 3m1k×3m2k\frac{3m_1}{k}\times\frac{3m_2}{k}.

Proof. Let v1v_1 and v2v_2 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 v2v_2 to ensure its (1,1)(1,1) direction component is opposite from v1v_1’s.

Repeatedly do the following with the current period v3v_3, starting from 0, until v3v_3 lies in Q2Q_2 or Q4Q_4: if v3v_3’s (1,1)(1,1) component matches v1v_1’s, add v2v_2 to it; otherwise, add v1v_1.

v3v_3’s (1,1)(1,1) component is bounded by the components of v1v_1 and v2v_2. Since v1≠±v2v_1\ne\pm v_2, over the process, v3v_3’s (1,−1)(1,-1) component will eventually exceed such a bound, putting v3v_3 in Q2Q_2 or Q4Q_4.

Bound on v3v_3’s size: before the final application of v1v_1 or v2v_2, v3v_3’s (1,−1)(1,-1) component was bounded by its (1,1)(1,1) component, which is bounded by v1v_1’s or v2v_2’s (1,1)(1,1) component. Then v1v_1 or v2v_2 is applied once. Hence v3v_3 is the sum of 3 vectors bounded by m1k×m2k\frac{m_1}{k}\times\frac{m_2}{k}, so it is bounded by 3m1k×3m2k\frac{3m_1}{k}\times\frac{3m_2}{k}.

If this new period v3v_3 is a period of the entire pattern, then by lemma 3.2, the pattern is lattice periodic with respect to v1v_1 and v2v_2. Otherwise, since the middle region of the pattern is periodic with respect to v3v_3 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 v1v_1 and v2v_2. At every iteration, we perform the following.

Find one surviving shift, Sinit=(Xinit,Yinit)S_{\mathrm{init}}=(X_{\mathrm{init}},Y_{\mathrm{init}}), and let Sc=(Xc,Yc)=(m12k,m22k)S_c=(X_c,Y_c)=\left(\frac{m_1}{2k},\frac{m_2}{2k}\right). Add Sc−SinitS_c-S_{\mathrm{init}} to each column in the deterministic sample, taken modulo v1v_1 and v2v_2 so that they remain middle columns. This translates the surviving shift to (Xc,Yc)(X_c,Y_c).

Search for a surviving shift not on the lattice defined by (Xc,Yc)(X_c,Y_c), v1v_1, and v2v_2. If none exists, deterministic sampling is complete. If another exists, denote it (Xo,Yo)=So(X_o,Y_o)=S_o.

If a column exists where ScS_c and SoS_o 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 ScS_c or SoS_o. Otherwise, v3=(Xc−Xo,Yc−Yo)\mathbf{v}_3 = (X_c - X_o, Y_c - Y_o), which is not a linear combination of v1\mathbf{v}_1 and v2\mathbf{v}_2, is a period of the pattern.

Note that linear combinations of v1\mathbf{v}_1 and v2\mathbf{v}_2 tile the plane in parallelograms, and so v3\mathbf{v}_3 must lie in or on the edge of some such parallelogram. Let its corners be vP1\mathbf{v}_{P1}, vP2=vP1+v1\mathbf{v}_{P2} = \mathbf{v}_{P1} + \mathbf{v}_1, vP3=vP1+v2\mathbf{v}_{P3} = \mathbf{v}_{P1} + \mathbf{v}_2, and vP4=vP1+v1+v2\mathbf{v}_{P4} = \mathbf{v}_{P1} + \mathbf{v}_1 + \mathbf{v}_2, where all corners are linear combinations of v1\mathbf{v}_1 and v2\mathbf{v}_2.

Divide the parallelogram into 4 similar ones by dividing across the lines joining the midpoints of opposite sides. v3\mathbf{v}_3 will lie in or on the edge of one; without loss of generality, let it be the parallelogram with vP1\mathbf{v}_{P1} as a vertex. Then, the triangles defined by the vectors (v3−vP1)(\mathbf{v}_3 - \mathbf{v}_{P1}) and v12\frac{\mathbf{v}_1}{2}, as well as (v3−vP1)(\mathbf{v}_3 - \mathbf{v}_{P1}) and v22\frac{\mathbf{v}_2}{2}, form disjoint regions within the parallelogram. If the former triangle is smaller in size, make (v3−vP1)(\mathbf{v}_3 - \mathbf{v}_{P1}) and v1\mathbf{v}_1 the new periods; otherwise, make them (v3−vP1)(\mathbf{v}_3 - \mathbf{v}_{P1}) and v2\mathbf{v}_2.

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 v1\mathbf{v}_1 and v3−vP1=vΔ\mathbf{v}_3 - \mathbf{v}_{P1} = \mathbf{v}_{\Delta}. Since the triangle defined by v12\frac{\mathbf{v}_1}{2} and vΔ\mathbf{v}_{\Delta} is at most half of a quarter of the area of the parallelogram defined by v1\mathbf{v}_1 and v2\mathbf{v}_2, the parallelogram defined by v12\frac{\mathbf{v}_1}{2} and vΔ\mathbf{v}_{\Delta} is at most 14\frac{1}{4} the area of the parallelogram defined by v1\mathbf{v}_1 and v2\mathbf{v}_2. Hence the parallelogram defined by v1\mathbf{v}_1 and vΔ\mathbf{v}_{\Delta} has area at most half that of the parallelogram defined by v1\mathbf{v}_1 and v2\mathbf{v}_2.

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 v1\mathbf{v}_1 and v2\mathbf{v}_2 is halved or the total shifts (modulo v1\mathbf{v}_1 and v2\mathbf{v}_2) is halved, keeping the total iterations and the deterministic sample size O~(1)\widetilde{O}(1).

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 (δx,δy)(\delta_x,\delta_y) where ∣δx∣≤3m1/k|\delta_x| \le3m_1/k and ∣δy∣≤3m2/k|\delta_y| \le3m_2/k, such that:

  • the middle region of the pattern is periodic with respect to (δx,δy)(\delta_x,\delta_y). This can be implied from there being no middle column (a,b)(a,b) at which some 2 shifts (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2) differ, where (x2−x1,y2−y1)=(δx,δy)(x_2-x_1,y_2-y_1) = (\delta_x,\delta_y); but

  • there is some pattern index (c,d)(c,d) with P[c][d]≠P[c+δx][d+δy]P[c][d] \ne P[c+\delta_x][d+\delta_y].

Define a pattern index (x,y)(x,y) to be:

  • good if P[x][y]=P[x+δx][y+δy]P[x][y] = P[x+\delta_x][y+\delta_y],

  • bad if P[x][y]≠P[x+δx][y+δy]P[x][y] \ne P[x+\delta_x][y+\delta_y],

  • neutral if P[x+δx][y+δy]P[x+\delta_x][y+\delta_y] is out of range.

Lemma 3.6. If there is an m1k×m2k\frac{m_1}{k} \times\frac{m_2}{k} rectangle in the pattern, RR, 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 RR be at index (Xr,Yr)(X_r,Y_r), and let one bad index be at (Xb,Yb)(X_b,Y_b). Let RR and the index in RR shifted by (δx,δy)(\delta_x,\delta_y) be as in the period-breaker setting; in particular RR contains no neutral cells.

Consider the columns (Xr+m1k,Yr+m2k)\left(X_r+\frac{m_1}{k},Y_r+\frac{m_2}{k}\right) and (Xr+m1k+δx,Yr+m2k+δy)\left(X_r+\frac{m_1}{k}+\delta_x,Y_r+\frac{m_2}{k}+\delta_y\right). For any shift (a,b)(a,b), these store the indices P[Xr+m1k−a][Yr+m2k−b]P\left[X_r+\frac{m_1}{k}-a\right]\left[Y_r+\frac{m_2}{k}-b\right] and P[Xr+m1k−a+δx][Yr+m2k−b+δy]P\left[X_r+\frac{m_1}{k}-a+\delta_x\right]\left[Y_r+\frac{m_2}{k}-b+\delta_y\right]. Note that these are an index in RR and the index shifted by (δx,δy)(\delta_x,\delta_y), respectively.

Make the deterministic sample columns (Xr+m1k,Yr+m2k)\left(X_r+\frac{m_1}{k},Y_r+\frac{m_2}{k}\right) and (Xr+m1k+δx,Yr+m2k+δy)\left(X_r+\frac{m_1}{k}+\delta_x,Y_r+\frac{m_2}{k}+\delta_y\right) with characters P[Xb][Yb]P[X_b][Y_b] and P[Xb+δx][Yb+δy]P[X_b+\delta_x][Y_b+\delta_y]. Since these are the characters stored by the shift (Xr+m1k−Xb,Yr+m2k−Yb)\left(X_r+\frac{m_1}{k}-X_b,Y_r+\frac{m_2}{k}-Y_b\right), denoted S0=(X0,Y0)S_0=(X_0,Y_0), at least one shift survives this deterministic sample. Additionally, these characters are distinct, as (Xb,Yb)(X_b,Y_b) is bad.

Without loss of generality, let bad indices only exist in the row of RR with YY indices YbY_b. Then, for any shift with yy-coordinate not equal to Y0=Yr+m2k−YbY_0=Y_r+\frac{m_2}{k}-Y_b, the index the first column is mapped to cannot have yy index YbY_b, 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 yy coordinate Y0Y_0 will survive.

From here, deterministic sampling can proceed analogously to the 1-D case.

Any index in the inner middle region — i.e. with 4m1/k≤x≤m1−4m1/k4m_1/k\leq x\leq m_1-4m_1/k and 4m2/k≤y≤m2−4m2/k4m_2/k\leq y\leq m_2-4m_2/k — is automatically good, due to the middle region being periodic with respect to (δx,δy)(\delta_x,\delta_y). 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 4m1/k≤x≤m1−4m1/k4m_1/k\leq x\leq m_1-4m_1/k together with y≥m2−4m2/ky\geq m_2-4m_2/k (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 yy-coordinate; call it (xb,yb)(x_b,y_b).

If xb≤m1/2x_b\leq m_1/2, the rectangle with top left corner at (xb,yb)(x_b,y_b) 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 (xb,yb)(x_b,y_b) 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 0≤x≤4m1/k0\leq x\leq4m_1/k and 0≤y≤4m2/k0\leq y\leq4m_2/k. Use Dürr–Høyer search to find, among such bad indices, the one with minimum yy-coordinate, tiebroken by maximum xx-coordinate, xb,ybx_b,y_b. This selection ensures that the region P[xb:xb+m1k][yb:yb+m2k]P[x_b:x_b+\frac{m_1}{k}][y_b:y_b+\frac{m_2}{k}] contains only good indices other than (xb,yb)(x_b,y_b), 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 O~(M)\widetilde{O}(\sqrt{M}) time.

Proof. Each form of deterministic sampling takes O~(1)\widetilde{O}(1) iterations, and each iteration utilizes a constant number of O~(M)\widetilde{O}(\sqrt{M}) Grover’s or Dürr–Høyer queries. The period breaker algorithm also uses a constant number of O~(M)\widetilde{O}(\sqrt{M}) Grover’s or Dürr–Høyer queries followed by O~(1)\widetilde{O}(1) iterations of a constant number of O~(M)\widetilde{O}(\sqrt{M}) Grover’s or Dürr–Høyer queries. Hence, the total time complexity of deterministic sampling is O~(M)\widetilde{O}(\sqrt{M}).

□\square

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 PP. 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 m1/(2k)×m2/(2k)m_1/(2k) \times m_2/(2k) 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 m1/(2k)×m2/(2k)m_1/(2k) \times m_2/(2k), 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 R[0…r1−1][0…r2−1]R[0 \ldots r_1 - 1][0 \ldots r_2 - 1], where without loss of generality r1<r2r_1 < r_2. Suppose we are given a binary function on (i,j)(i,j) with 0≤i≤r10 \le i \le r_1 and 0≤j≤r20 \le j \le r_2, assigning each index a value in {0,1}\{0,1\}. Call indices mapped to 1 good and indices mapped to 0 bad.

The skyline aims to answer, for each row ll from 0 to r1−1r_1 - 1, the maximum kk such that R[0…l][0…k]R[0 \ldots l][0 \ldots k] contains only good indices. Formally, the skyline is the sequence (l,kl)(l,k_l) such that f(R[i][j])=1f(R[i][j]) = 1 for all i≤li \le l and all j≤klj \le k_l.

We solve this recursively. At every stage of the recursion we construct the skyline on a sub-rectangle parameterized by xmin⁡,xmax⁡,ymin⁡,ymax⁡x_{\min}, x_{\max}, y_{\min}, y_{\max}, with x=xmax⁡−xmin⁡+1x = x_{\max} - x_{\min} + 1 rows and y=ymax⁡−ymin⁡+1y = y_{\max} - y_{\min} + 1 columns. Initially xmin⁡=0x_{\min} = 0, xmax⁡=r1−1x_{\max} = r_1 - 1, ymin⁡=0y_{\min} = 0, ymax⁡=r2−1y_{\max} = r_2 - 1.

Let xyxy, the total number of cells relevant to the current portion of the skyline construction (within xl,xr,yb,ytx_l, x_r, y_b, y_t), 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 xx-coordinate of a “midpoint” — initialized at (xl+xr)/2(x_l + x_r)/2 — that splits the skyline into two equal-area regions.

At each step of the binary search, for the trial xx-coordinate xtx_t we use Grover’s algorithm (Dürr–Høyer) to find the bad index of least yy-coordinate, yty_t, within the region R[xmin⁡…xt][ymin⁡…ymax⁡]R[x_{\min} \ldots x_t][y_{\min} \ldots y_{\max}]. If no such index exists, we set yt:=ymax⁡+1y_t := y_{\max} + 1. The two resulting half-areas are (xt−xmin⁡)(ymax⁡−yt)(x_t - x_{\min})(y_{\max} - y_t) and (xmax⁡−xt)(yt−ymin⁡)(x_{\max} - x_t)(y_t - y_{\min}); binary search equalizes them.

Once the correct xx-coordinate of the midpoint is found, a second binary search — this time on the yy-coordinate — refines the area balance exactly.

Lemma 5.1 (Area Bound). If both halves have exactly equal area, each must have at most 14\frac{1}{4} of the area of the larger enclosing region.

Proof. Let the left region have dimensions a×ba \times b and the right region have dimensions c×dc \times d, where the enclosing region has dimensions (a+c)×(b+d)(a+c) \times(b+d) and ab=cdab=cd. It suffices to show

2(ab+cd)≤(a+c)(b+d)⟺ab+cd≤ad+bc⟺(a−c)(d−b)≥02(ab+cd) \le(a+c)(b+d) \Longleftrightarrow ab+cd \le ad+bc \Longleftrightarrow(a-c)(d-b) \ge0
⟺(a−ab/d)(d−b)≥0⟺a(d−bd)(d−b)≥0\Longleftrightarrow(a-ab/d)(d-b) \ge0 \Longleftrightarrow a\left(\frac{d-b}{d}\right)(d-b) \ge0
⟺ad(d−b)2≥0,\Longleftrightarrow\frac{a}{d}(d-b)^2 \ge0,

which is clearly true since aa and dd are positive and (d−b)2≥0(d-b)^2 \ge0. □\square

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 O(1)O(1) Grover searches over a region of size the (larger) remaining dimension, so the base case also costs O~(xy)\widetilde{O}(\sqrt{xy}), consistent with the recurrence below.

Lemma 5.2 (Skyline Construction Cost). Constructing the skyline for a block of area A=r1r2A=r_1r_2 costs O~(A)\widetilde{O}(\sqrt{A}).

Proof. At a node of the recursion with region area AA, the two binary searches (for xtx_t then yty_t) each take O(log⁡A)O(\log A) steps, and each step is one Grover search over a region of size at most AA, costing O(A)O(\sqrt{A}). So the cost at a single node, excluding its recursive calls, is O(Alog⁡A)O(\sqrt{A}\log A). By Lemma 5.1, the node recurses into 2 children each of area at most A/4A/4, giving

T(A)=O(Alog⁡A)+2T(A/4).T(A)=O(\sqrt{A}\log A)+2T(A/4).

At recursion depth tt there are at most 2t2^t nodes, each of area at most A/4tA/4^t, so the total cost at level tt is

2t⋅O(A/4tlog⁡(A/4t))=O(Alog⁡(A/4t))=O(Alog⁡A).2^t\cdot O\left(\sqrt{A/4^t}\log(A/4^t)\right)=O\left(\sqrt{A}\log(A/4^t)\right)=O(\sqrt{A}\log A).

The recursion bottoms out after at most t=O(log⁡A)t=O(\log A) levels, so summing across all levels,

T(A)=O(Alog⁡2A)=O~(A).T(A)=O(\sqrt{A}\log^2 A)=\widetilde{O}(\sqrt{A}).

□\square

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 r1r_1), so that the total information stored is at most O~(r1)≤O~(r1r2)\widetilde{O}(r_1) \le\widetilde{O}(\sqrt{r_1r_2}).

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 (i,j)(i,j). Suppose we are given:

  • a notion of “good” and “bad” text cells supplied by a O~(1)\widetilde{O}(1) oracle (whose definition differs per case — see below), and

  • a residue condition that constrains which shifts are candidates (“in T\mathcal{T},” “in the surviving class,” or “in the lattice coset through (xm,ym)(x_m,y_m)” depending on the case).

Four-corner skylines. Construct skylines of good cells based from, respectively, the bottom-right corner of block (i,j)(i,j), the bottom-left corner of block (i+2k,j)(i+2k,j), the top-right corner of block (i,j+2k)(i,j+2k), and the top-left corner of block (i+2k,j+2k)(i+2k,j+2k). 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:

  • (xu,yu)(x_u,y_u): the bad index of minimum yy-coordinate in the top strip T[(i+1)m1/2k…im1/2k+m1][jm2/2k…(j+1)m2/2k]T[(i+1)m_1/2^k\ldots i m_1/2^k+m_1][j m_2/2^k\ldots(j+1)m_2/2^k];

  • (xD,yD)(x_D,y_D): the bad index of maximum yy-coordinate in the bottom strip T[(i+1)m1/2k…im1/2k+m1][jm2/2k+m2…(j+1)m2/2k+m2]T[(i+1)m_1/2^k\ldots i m_1/2^k+m_1][j m_2/2^k+m_2\ldots(j+1)m_2/2^k+m_2];

  • (xl,yl)(x_l,y_l): the bad index of maximum xx-coordinate in the left strip T[im1/2k…(i+1)m1/2k][(j+1)m2/2k…jm2/2k+m2]T[i m_1/2^k\ldots(i+1)m_1/2^k][(j+1)m_2/2^k\ldots j m_2/2^k+m_2];

  • (xr,yr)(x_r,y_r): the bad index of minimum xx-coordinate in the right strip T[im1/2k+m1…(i+1)m1/2k+m1][(j+1)m2/2k…jm2/2k+m2]T[i m_1/2^k+m_1\ldots(i+1)m_1/2^k+m_1][(j+1)m_2/2^k\ldots j m_2/2^k+m_2].

(Here we have renamed the bottom-strip extreme to (xD,yD)(x_D,y_D) to avoid clashing with the period-breaker gap (δx,δy)(\delta_x,\delta_y).)

Shared inner-region bad-cell screening. Use Grover’s search to test whether the shared region

T[(i+1)m1/2k…im1/2k+m1][(j+1)m2/2k…jm2/2k+m2]T[(i+1)m_1/2^k\ldots i m_1/2^k+m_1][(j+1)m_2/2^k\ldots j m_2/2^k+m_2]

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 (x,y)(x,y) satisfying the residue condition of the case, the full pattern instance consists only of good cells if and only if:

  • (x,y)(x,y) lies within the top-left-corner skyline,

  • (x+m1,y)(x+m_1,y) lies within the top-right-corner skyline,

  • (x,y+m2)(x,y+m_2) lies within the bottom-left-corner skyline,

  • (x+m1,y+m2)(x+m_1,y+m_2) lies within the bottom-right-corner skyline,

  • xl<x<xrx_l < x < x_r, and

  • yu<y<yDy_u < y < y_D.

This conjunction can be checked by an O(1)O(1) 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.

4 Skylines and extended regions for block $(i,j)$

Figure 1. 4 Skylines and extended regions for block (i,j)(i,j)

Pattern Matching if no Other Shifts Remain in the Ricochet Zone of a Surviving Shift

Divide the text into blocks of size n1/(2km1)×n2/(2km2)n_1/(2km_1) \times n_2/(2km_2).

For each block (i,j)(i,j), use the skyline algorithm to find a skyline of the region T[im1…(i+1)m1][jm2…(j+1)m2]T[i m_1 \ldots(i+1)m_1][j m_2 \ldots(j+1)m_2] 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 O~(M)\widetilde{O}(\sqrt{M}) deterministic-sample matches lying just outside corners of the skyline.

We then maintain a list T\mathcal{T} of candidate match positions, sorted by increasing xx-coordinate, initially empty. For each deterministic-sample-match position (x,y)(x,y) encountered along the skyline, proceed as follows:

  1. If T\mathcal{T} is empty, add (x,y)(x,y) to it and continue to the next match along the skyline.

  1. Otherwise, let the last element of T\mathcal{T} be (xp,yp)(x_p,y_p). Use the witness table to either find an index (xd,yd)(x_d,y_d) in the text at which pattern instances based at (x,y)(x,y) and at (xp,yp)(x_p,y_p) would disagree, or determine that no such index exists.

  1. If no such (xd,yd)(x_d,y_d) exists (either in T\mathcal{T} or in the witness table), add (x,y)(x,y) to T\mathcal{T} and continue to the next match along the skyline.

  1. If the pattern instance at (x,y)(x,y) matches the text at (xd,yd)(x_d,y_d), remove (xp,yp)(x_p,y_p) from T\mathcal{T} and restart from step 1. Otherwise, continue to the next match along the skyline.

By construction, only positions in T\mathcal{T} can match the pattern, and no two pattern instances based at positions in T\mathcal{T} disagree at any text index.

Build, in O~(M)\widetilde{O}(\sqrt{M}) time, a query structure that given xx- and yy-coordinate ranges returns an index into T\mathcal{T} falling in that range; queries cost O~(1)\widetilde{O}(1).

Define a O~(1)\widetilde{O}(1) 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 (xi,yi)(x_i,y_i) as follows. First, query T\mathcal{T} for an element (xr,yr)(x_r,y_r) with xi−m1≤xr≤xix_i-m_1 \le x_r \le x_i and yi−m2≤yr≤yiy_i-m_2 \le y_r \le y_i; this ensures the pattern instance based at (xr,yr)(x_r,y_r) covers (xi,yi)(x_i,y_i). If no such (xr,yr)(x_r,y_r) exists, label (xi,yi)(x_i,y_i) bad. Otherwise, label (xi,yi)(x_i,y_i) good if T[xi][yi]=P[xi−xr][yi−yr]T[x_i][y_i] = P[x_i-x_r][y_i-y_r] and bad otherwise.

Apply the four-corner skyline verification from § 6 with this good/bad oracle and the residue condition “(x,y)∈T(x,y) \in\mathcal{T}” 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 v=(xv,yv)v=(x_v,y_v). Without loss of generality, assume m1≤M≤m2m_1 \le\sqrt{M} \le m_2.

For each block (i,j)(i,j), use the skyline algorithm to find a skyline of T[i m1…(i+1)m1][j m2…(j+1)m2]T[i\,m_1\ldots(i+1)m_1][j\,m_2\ldots(j+1)m_2] 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 vv. 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 xvx_v. In each we identify a single class that could contain all possible pattern matches.

Finding the Surviving Class if xv=0x_v=0

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 yvy_v below it. There are at most O(M)O(\sqrt{M}) such classes. All indices within one such class share an xx-coordinate.

We reduce these classes down to one surviving class via repeated pairwise duels. In each duel, between class 1 (with xx-coordinate x1x_1) and class 2 (with xx-coordinate x2x_2), assume WLOG x1<x2x_1 < x_2. Let i1i_1 be the index in class 1 of lowest yy-coordinate, and i2i_2 the index in class 2 of highest yy-coordinate. Since — by the skyline’s structure — the yy-coordinate of i2i_2 exceeds the yy-coordinate of every index in class 1, the overlap region of the pattern instances at i1i_1 and i2i_2 sits entirely within every pattern instance based at an index in class 1 or class 2, with one potential exception: i3i_3, the index of class 2 with lowest yy-coordinate, if y(i3)<y(i1)y(i_3) < y(i_1).

Using the witness table, find an index at which the pattern instances at i1i_1 and i2i_2 disagree. If i2i_2 matches the text at this disagreement index, then no index in class 1 can match the pattern, and class 2 wins the duel. Otherwise, i1i_1 matches at the disagreement; the only candidate in class 2 that might still match is i3i_3. Then duel i3i_3 against the index in class 1 of highest yy-coordinate: since the overlap region of these two pattern instances lies inside every pattern instance in class 1, if i3i_3 matches at the disagreement index, class 2 wins; otherwise class 1 wins.

Finding the Surviving Class if xv≠0x_v \ne0

For every xx-coordinate xix_i present in the block, consider the deterministic-sample match (xm,ym)(x_m,y_m) on the skyline with the greatest xx-coordinate not exceeding xix_i (if no such match exists, every index in the block with xx-coordinate xix_i lies outside the skyline and cannot match the pattern). Every index in the block with xx-coordinate xix_i is either in the ricochet zone of (xm,ym)(x_m,y_m), or outside the skyline and hence not a pattern-match candidate.

Hence, the only index with xx-coordinate xix_i that could match the pattern is the at-most-one index that is an integer multiple of vv away from (xm,ym)(x_m,y_m), i.e. (xi,ym+yvxv(xi−xm))(x_i, y_m + \frac{y_v}{x_v}(x_i-x_m)), and only when ym+yvxv(xi−xm)y_m + \frac{y_v}{x_v}(x_i-x_m) is an integer.

Since there is only one possible surviving index per xx-coordinate, at most O~(M)\widetilde{O}(\sqrt{M}) surviving indices remain overall.

Maintain a list TT of candidate indices, sorted by increasing xx-coordinate, initially empty. At all times TT contains only indices whose pattern instances pairwise have no index of disagreement, so TT can contain indices from at most one class.

For each surviving index (xi,yi)(x_i,y_i), in order of increasing xix_i, repeatedly do:

  1. If TT is empty or already contains elements from (xi,yi)(x_i,y_i)’s class, add (xi,yi)(x_i,y_i) to TT.

  1. Otherwise, duel (xi,yi)(x_i,y_i) against the last element of TT by consulting the witness table’s disagreement index. If (xi,yi)(x_i,y_i) matches the text at the disagreement index, remove the last element of TT and repeat; otherwise skip (xi,yi)(x_i,y_i).

In the end, TT contains indices from at most one class — the surviving class.

Pattern Matching Once the Surviving Class Is Known

Let (xr,yr)(x_r,y_r) be any index in the surviving class.

Define a O~(1)\widetilde{O}(1) 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 (x,y)(x,y): find an integer aa (and in the xv≠0x_v \ne0 sub-case, this takes the form of using the period relation once) such that (x,y)+av=(x′,y′)(x,y)+a\mathbf{v}=(x',y') lies inside T[xr…xr+m1][yr…yr+m2]T[x_r\ldots x_r+m_1][y_r\ldots y_r+m_2], by using the intersection of the four inequalities xr<x′x_r<x', x′<xr+m1x'<x_r+m_1, yr<y′y_r<y', y′<yr+m2y'<y_r+m_2. If no such aa exists, (x,y)(x,y) is bad. Otherwise, (x,y)(x,y) is good iff P[x′−xr][y′−yr]=T[x′][y′]P[x'-x_r][y'-y_r]=T[x'][y'].

Apply the four-corner skyline verification from Section 6 with this oracle and with residue condition “(x,y)(x,y) belongs to the same class as (xr,yr)(x_r,y_r)” to detect any pattern match in the block.

Pattern Matching for a Lattice-Periodic Pattern

Let the two periods be v1\mathbf{v}_1 and v2\mathbf{v}_2.

Use Grover’s search to find some deterministic-sample match (xm,ym)(x_m,y_m). By the ricochet property, the pattern either matches at an integer linear combination of v1\mathbf{v}_1 and v2\mathbf{v}_2 away from (xm,ym)(x_m,y_m), or matches nowhere in the block.

Define a O~(1)\widetilde{O}(1) 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 (x,y)(x,y): find integers a,ba,b such that (x,y)+av1+bv2=(x′,y′)(x,y)+a\mathbf{v}_1+b\mathbf{v}_2=(x',y') lies inside T[xm…xm+m1][ym…ym+m2]T[x_m\ldots x_m+m_1][y_m\ldots y_m+m_2], using the intersection of the four inequalities xm<x′x_m<x', x′<xm+m1x'<x_m+m_1, ym<y′y_m<y', y′<ym+m2y'<y_m+m_2. Then (x,y)(x,y) is good iff P[x′−xm][y′−ym]=T[x′][y′]P[x'-x_m][y'-y_m]=T[x'][y'].

Apply the four-corner skyline verification from Section 6 with this oracle and with residue condition “(x,y)(x,y) is an integer linear combination of v1\mathbf{v}_1 and v2\mathbf{v}_2 away from (xm,ym)(x_m,y_m)” to detect any pattern match in the block.

Time Complexity

As shown earlier, the time complexity of deterministic sampling is O~(M)\widetilde{O}(\sqrt{M}).

Per block, the cost for creating the 4 block skylines is shown to be O~(M)\widetilde{O}(\sqrt{M}), and finding the nearest bad cells on the edges and checking if the shared region only contains good cells are all O~(M)\widetilde{O}(\sqrt{M}) Grover’s or Dürr–Høyer algorithm queries. In the 1st case of pattern matching, per block, there is an O~(M)\widetilde{O}(\sqrt{M}) cost of finding the initial skyline shifts, another O~(M)\widetilde{O}(\sqrt{M}) to duel them to create T\mathcal{T}, and a final O~(M)\widetilde{O}(\sqrt{M}) cost to create a query structure for elements of T\mathcal{T} amounting to a O~(M)\widetilde{O}(\sqrt{M}) additional cost.

In the 2nd case of pattern matching, per block, there is an additional O~(M)\widetilde{O}(\sqrt{M}) cost to finding the skyline shifts and a O~(M)\widetilde{O}(\sqrt{M}) cost to find the surviving class.

In the 3rd case of pattern matching, there is an additional O~(M)\widetilde{O}(\sqrt{M}) cost per block to find a deterministic sample match.

Hence, the total cost per block in any case is O~(M)\widetilde{O}(\sqrt{M}). Querying over the O(N/M)O(N/M) blocks with Grover’s search, the total complexity arrives to O~(N/M×M)=O~(N)\widetilde{O}(\sqrt{N/M}\times\sqrt{M})=\widetilde{O}(\sqrt{N}).

Theorem 7.1. Given a pattern P[0..m1−1][0..m2−1]P[0..m_1-1][0..m_2-1] and a text T[0..n1−1][0..n2−1]T[0..n_1-1][0..n_2-1] and a witness table as oracles, (where m1m2=M≤n1n2=Nm_1m_2=M\le n_1n_2=N) finding whether PP occurs in TT can be found by O~(N)\widetilde{O}(\sqrt{N}) 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. [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. [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. [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
  4. [5]H. Ramesh and V. Vinay. String matching in O(√n + √m) quantum queries. Journal of Discrete Algorithms, 1(1):103–110, 2003.DOI
  5. [6]Uzi Vishkin. Deterministic sampling—a tool for fast parallel string matching. SIAM Journal on Computing, 20(1):22–40, 1991.
  6. [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
  7. [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
  8. [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
  9. [21]M. Crochemore, L. Gasieniec, and W. Rytter. Two-dimensional pattern matching by sampling. Information Processing Letters, 46(4):159–162, 1993.
  10. [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.
  11. [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.
  12. [26]A. Amir and G. Benson. Two-dimensional periodicity in rectangular arrays. SIAM Journal on Computing, 27(1):90–106, 1998.DOI
  13. [29]A. Montanaro. Quantum pattern matching fast on average. Algorithmica, 77(1):16–39, 2017.
  14. [30]Q. Wang and M. Ying. Quantum algorithm for lexicographically minimal string rotation. arXiv preprint arXiv:2012.09376, 2020.DOI
  15. [31]S. Akmal and C. Jin. Near-optimal quantum algorithms for string problems. Algorithmica, 85(8):2260–2317, 2023.
  16. [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.
  17. [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
  18. [34]D. Gibney and S. V. Thankachan. Compressibility-aware quantum algorithms on strings. arXiv preprint arXiv:2302.07235, 2023.arxiv.org/abs/2302.07235
  19. [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

Paper details

vlnc:W_acrat4yc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents