Abstract
The string matching problem is one of the fundamental problems in computer science with applications in a variety of fields. Basically, it consists in finding all occurrences of a given pattern within a larger text. Despite its straightforward formulation, it has given rise to a huge number of solutions based on very different approaches and varied computational paradigms. But it is only very recently that the first solution based on quantum computation has been proposed by Niroula and Nam, allowing the problem to be solved in \(\mathcal {O}(\sqrt{n}(\log ^2(n)+\log (m)))\) time, with a quadratic speed-up compared to classical computation. To date, these two research fields have remained almost entirely separate, mainly because the technical aspects typical of the quantum computation field remain almost obscure to those involved in text processing. This paper aims to reconcile the two fields by unfolding the technical aspects of the Niroula-Nam quantum solution and providing a detailed general procedure working in \(\mathcal {O}(\sqrt{n}\log ^2(n))\) time that can be used as a framework for solving other string matching problems, including nonstandard ones. In this direction, the paper also proposes an extension of the algorithm to the approximate string matching problem with swaps, reporting the configuration of the occurrence together with its position, and achieving a quasi-linear \(\mathcal {O}(\sqrt{n}\log ^2(n))\) time complexity when \(m=\mathcal {O}(\log (n))\).
This work is partially funded by the National Centre for HPC, Big Data and Quantum Computing, Project CN00000013, affiliated to Spoke 10.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
If we assume to be able to implement the multi-controlled NOT gate in constant time [17], a Grover’s search on a dataset of n items achieves \(\mathcal {O}(\sqrt{n}T(n))\) time.
References
Ambainis, A.: Quantum search algorithms. SIGACT News 35(2), 22–35 (2004)
Balauca, S., Arusoaie, A.: Efficient constructions for simulating multi controlled quantum gates. In: Groen, D., et al. (eds.) Computational Science - ICCS 2022. LNCS, vol. 13353, pp. 179–194. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-08760-8_16
Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778–797 (2001)
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4–5), 493–505 (1998)
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Lo Monaco, S.G., Brandt, H.E. (eds.) Quantum Computation and Information. Contemporary Mathematics, vol. 305, pp. 53–74. American Mathematical Society (2002)
Cantone, D., Faro, S.: Pattern matching with swaps for short patterns in linear time. In: Nielsen, M., Kučera, A., Miltersen, P.B., Palamidessi, C., Tůma, P., Valencia, F. (eds.) SOFSEM 2009. LNCS, vol. 5404, pp. 255–266. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-95891-8_25
Fang, M., Fenner, S., Green, F., Homer, S., Zhang, Y.: Quantum lower bounds for fanout. Quantum Info. Comput. 6(1), 46–57 (2006)
Faro, S., Pavone, A.: An efficient skip-search approach to swap matching. Comput. J. 61(9), 1351–1360 (2018)
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 1996, New York, NY, USA, pp. 212–219. ACM (1996)
He, Y., Luo, M., Zhang, E., Wang, H.-K., Wang, X.-F.: Decompositions of \(n\)-qubit Toffoli gates with linear circuit complexity. Int. J. Theor. Phys. 56, 07 (2017)
Høyer, P., Spalek, R.: Quantum fan-out is powerful. Theory C. 1, 81–103 (2005)
Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323–350 (1977)
Montanaro, A.: Quantum pattern matching fast on average. Algorithmica 77(1), 16–39 (2017)
Niroula, P., Nam, Y.: A quantum algorithm for string matching. NPJ Quant. Inf. 7, 37 (2021)
Ramesh, H., Vinay, V.: String matching in \({\tilde{o}}(\sqrt{n}+\sqrt{m})\) quantum time. J. Discr. Algorithms 1(1), 103–110 (2003)
Rasmussen, S.E., Groenland, K., Gerritsma, R., Schoutens, K., Zinner, N.T.: Single-step implementation of high-fidelity \(n\)-bit Toffoli gates. Phys. Rev. A 101, 022308 (2020)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comp. 26(5), 1484–1509 (1997)
Toffoli, T.: Reversible computing. In: de Bakker, J., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 632–644. Springer, Heidelberg (1980). https://doi.org/10.1007/3-540-10003-2_104
Yao, A.C.: The complexity of pattern matching for a random string. Technical report, Stanford, CA, USA (1977)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cantone, D., Faro, S., Pavone, A. (2023). Quantum String Matching Unfolded and Extended. In: Kutrib, M., Meyer, U. (eds) Reversible Computation. RC 2023. Lecture Notes in Computer Science, vol 13960. Springer, Cham. https://doi.org/10.1007/978-3-031-38100-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-38100-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38099-0
Online ISBN: 978-3-031-38100-3
eBook Packages: Computer ScienceComputer Science (R0)