Abstract
Quantum computational models enable the design of algorithms that are often significantly more efficient than their most competitive counterpart classical solutions. Recently, strides have been made to take advantage of the quantum computational framework in tackling problems arising in the context of text processing. Our work fits in such a research direction. We focused on challenges arising from string comparison problems and, specifically, on the alignment of fixed-length substrings that are found within two input strings. To be precise, given two input strings, x and y, both of length n, and a value \(d\leqslant n\), we want to verify the following conditions: the existence of a common prefix of length d, the presence of a common substring of length d starting at position j (with \(0\leqslant j<n\)) and, the presence of any common substring of length d starting at the same position of both strings. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach yields polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.
A preliminary version of this paper appeared on arXiv [6].
This work is partially funded by ICSC - Centro Nazionale di Ricerca in High-Performance Computing, Big Data and Quantum Computing, co-founded by European Union - NextGenerationEU.
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
Similar content being viewed by others
References
Balauca, S., Arusoaie, A.: Efficient constructions for simulating multi controlled quantum gates. In: Groen, D., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (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)
Bieganski, Riedl, Cartis, Retzel: Generalized suffix trees for biological sequence data: applications and implementation. In: 1994 Proceedings of the Twenty-Seventh Hawaii International Conference on System Sciences, vol. 5, pp. 35–44 (1994)
Cantone, D., Faro, S., Pavone, A.: Quantum string matching unfolded and extended. In: Kutrib, M., Meyer, U. (eds.) Reversible Computation, RC 2023. LNCS, vol. 13960, pp. 117–133. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38100-3_9
Cantone, D., Faro, S., Pavone, A., Viola, C.: Longest common substring and longest palindromic substring \(\tilde{\cal{O}}(\sqrt{n})\) time (2023)
Cantone, D., Faro, S., Pavone, A., Viola, C.: Quantum circuits for fixed substring matching problems (2023)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press (2001)
Fang, M., Fenner, S., Green, F., Homer, S., Zhang, Y.: Quantum lower bounds for fanout. Quantum Info. Comput. 6(1), 46–57 (2006)
Le Gall, F., Seddighin, S.: Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems. Algorithmica 85(5), 1251–1286 (2023)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 212–219. ACM, New York (1996)
He, Y., Luo, M.-X., Zhang, E., Wang, H.-K., Wang, X.-F.: Decompositions of \(n\)-qubit Toffoli gates with linear circuit complexity. Int. J. Theoret. Phys. 56, 2350–2361 (2017)
Høyer, P., Spalek, R.: Quantum fan-out is powerful. Theor. Comput. 1, 81–103 (2005)
Kaye, P., Laflamme, R., Mosca, M.: An Introduction to Quantum Computing. Oxford University Press (2006)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press (2011)
Niroula, P., Nam, Y.: A quantum algorithm for string matching. npj Quantum Inf. 7, 37 (2021). https://doi.org/10.1038/s41534-021-00369-3
Pavone, A., Viola, C.: The quantum circular shift operator. In: 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, 15–18 September 2023 (2023)
Ramesh, H., Vinay, V.: String matching in \({\tilde{o}}(\sqrt{n}+\sqrt{m})\) quantum time. J. Discret. Algorithm. 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
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cantone, D., Faro, S., Pavone, A., Viola, C. (2024). Quantum Circuits for Fixed Matching Substring Problems. In: Arai, K. (eds) Intelligent Computing. SAI 2024. Lecture Notes in Networks and Systems, vol 1018. Springer, Cham. https://doi.org/10.1007/978-3-031-62269-4_43
Download citation
DOI: https://doi.org/10.1007/978-3-031-62269-4_43
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-62268-7
Online ISBN: 978-3-031-62269-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)