Fetching the paper…
Reading the bibliography…
The $d$-dimensional pattern matching problem is to find an occurrence of a pattern of length $m \times \dots \times m$ within a text of length $n \times \dots \times n$, with $n \ge m$.
A fast string searching algorithm
R. Boyer and S. Moore · 1977
Earlier work this paper cites.
Fast pattern matching in strings
D. Knuth, J. Morris, Jr., and V. Pratt · 1977
Earlier work this paper cites.
The complexity of pattern matching for a random string
A. Yao · 1979
Earlier work this paper cites.
Deterministic sampling – a new technique for fast pattern matching
U. Vishkin · 1991
Earlier work this paper cites.
Sublinear approximate string matching and biological applications
W. Chang and E. Lawler · 1994
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Quantum mechanics helps in searching for a needle in a haystack
L. Grover · 1997
Earlier work this paper cites.
Two- and higher-dimensional pattern matching in optimal expected time
J. Kärkkäinen and E. Ukkonen · 1999
Earlier work this paper cites.
A hidden shift quantum algorithm
J. Twamley · 2000
Earlier work this paper cites.
A guided tour to approximate string matching
G. Navarro · 2001
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
A. Ambainis · 2002
Earlier work this paper cites.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Earlier work this paper cites.
A sublinear algorithm for weakly approximating edit distance
T. Batu, F. Ergün, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami · 2003
Cited alongside, same era.
Hidden translation and orbit coset in quantum computing
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen · 2003
Cited alongside, same era.
Quantum search on bounded-error inputs
P. Høyer, M. Mosca, and R. de Wolf · 2003
Cited alongside, same era.
String matching in O ~ ( n + m ) \widetilde{O}(\sqrt{n}+\sqrt{m}) quantum time
H. Ramesh and V. Vinay · 2003
Cited alongside, same era.
Towards quantum template matching
D. Curtis and D. Meyer · 2004
Cited alongside, same era.
The quantum query complexity of the hidden subgroup problem is polynomial
M. Ettinger, P. Høyer, and E. Knill · 2004
Cited alongside, same era.
Algorithms on Strings
M. Crochemore, C. Hancart, and T. Lecroq · 2007
Later among the works it cites.
V. Giovannetti, S. Lloyd, and L. Maccone · 2008
Later among the works it cites.
M. Rötteler · 2009
Later among the works it cites.
Quantum algorithms for highly non-linear Boolean functions
M. Rötteler · 2010
Later among the works it cites.
Quantum algorithm for the Boolean hidden shift problem
D. Gavinsky, M. Roetteler, and J. Roland · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space, 2004
O. Regev · 2004
Cited alongside, same era.
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem
G. Kuperberg · 2005
Cited alongside, same era.
The power of strong fourier sampling: Quantum algorithms for affine groups and hidden shifts
C. Moore, D. Rockmore, A. Russell, and L. Schulman · 2005
Cited alongside, same era.
Quantum algorithms for some hidden shift problems
W. van Dam, S. Hallgren, and L. Ip · 2006
Cited alongside, same era.
Quantum algorithm for a generalized hidden shift problem
A. Childs and W. van Dam · 2007
Cited alongside, same era.
Shift finding in sub-linear time
A. Andoni, H. Hassanieh, P. Indyk, and D. Katabi · 2013
Later among the works it cites.
Easy and hard functions for the boolean hidden shift problem
A. Childs, R. Kothari, M. Ozols, and M. Roetteler · 2013
Later among the works it cites.
Reduction from non-injective hidden shift problem to injective hidden shift problem
M. Gharibi · 2013
Later among the works it cites.
Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem
G. Kuperberg · 2013
Later among the works it cites.
M. Ozols, M. Roetteler, and J. Roland · 2013
Later among the works it cites.
Quantum property testing, 2013
A. Montanaro and R. de Wolf · 2035
Closest in time.