Quantum Information & Computation
Volume 25, Issue 4
RESEARCH ARTICLE Open access

Reducing T-Count In Quantum String Matching Algorithm Using Relative-Phase Fredkin Gate

Byeongyong Park, Hansol Noh, Doyeol Ahn

Author affiliations
  • Byeongyong Park1
  • Hansol Noh1
  • Doyeol Ahn1
  1. Department of Electrical and Computer Engineering and Center for Quantum Information Processing, University of Seoul, 163 Seoulsiripdae-ro, Dongdaemun-gu, Seoul, Republic of Korea

pp. 299-314 · 10.2478/qic-2025-0016

Read PDF View on Reference Global
On this page

Abstract

The string-matching problem, ubiquitous in computer science, can significantly benefit from quantum algorithms due to their potential for greater efficiency compared to classical approaches. The practical implementation of the quantum string matching (QSM) algorithm requires fault-tolerant quantum computation due to the fragility of quantum information. A major obstacle in implementing fault-tolerant quantum computation is the high cost associated with executing T gates. This paper introduces the relative-phase Fredkin gate as a strategy to notably reduce the number of T gates (T-count) necessary for the QSM algorithm. This reduces the T-count from 14 N3/2 log2 N – O(N3/2) to 8 N3/2 log2 N – O(N3/2), where N represents the size of the database to be searched. Additionally, we demonstrate that our method is advantageous in terms of other circuit costs, such as the depth of T gates and the number of CNOT gates. This advancement contributes to the ongoing development of the QSM algorithm, paving the way for more efficient solutions in the field of computer science.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum circuit
  • quantum string matching
  • T-count
  • relative phase Fredkin gate
  • Grover’s search algorithm

Suggested citation

Byeongyong Park, Hansol Noh, Doyeol Ahn (2025). Reducing T-Count In Quantum String Matching Algorithm Using Relative-Phase Fredkin Gate. Quantum Information & Computation, 25(4), 299-314. https://doi.org/10.2478/qic-2025-0016

Download BibTeX

References (37)

  1. L. K. Grover (1997). “Quantum mechanics helps in searching for a needle in a haystack.” Physical Review Letters, 79, 325–328.DOI: 10.1103/PhysRevLett.79.325Google Scholar
  2. G. Brassard, P. Høyer, M. Mosca and A. Tapp (2002). “Quantum amplitude amplification and estimation”, in Contemporary Mathematics Series Millennium, Vol. 305. New York: American Mathematical Society, pp. 53–74.DOI: 10.1090/conm/305/05215Google Scholar
  3. H. Ramesh and V. Vinay (2003). “String matching in quantum time.” Journal of Discrete Algorithms, 1, 103–110.DOI: 10.1016/S1570-8667(03)00010-8Google Scholar
  4. P. Niroula and Y. Nam (2021). “A quantum algorithm for string matching.” npj Quantum Information, 7, 37.DOI: 10.1038/s41534-021-00369-3Google Scholar
  5. S. I. Hakak, A. Kamsin, P. Shivakumara, G. A. Gilkar, W. Z. Khan and M. Imran (2019). “Exact string matching algorithms: survey, issues, and future research directions.” IEEE Access, 7, 69614–69637.DOI: 10.1109/ACCESS.2019.2914071Google Scholar
  6. H. Schütze, C. D. Manning and P. Raghavan (2008). Introduction to Information Retrieval. Cambridge: Cambridge University Press.Google Scholar
  7. R. R. Naik, M. B. Landge and C. N. Mahender (2015). “A review on plagiarism detection tools.” International Journal of Computer Applications, 125.Google Scholar
  8. M. K. Vijaymeena and K. Kavitha (2016). “A survey on similarity measures in text mining.” Machine Learning with Applications: International Journal, 3, 19–28.DOI: 10.5121/mlaij.2016.3103Google Scholar
  9. H. Lu, K. Zheng, B. Liu, X. Zhang and Y. Liu (2006). “A memory-efficient parallel string matching architecture for high-speed intrusion detection.” IEEE Journal on Selected Areas in Communications, 24, 1793–1804.DOI: 10.1109/JSAC.2006.877221Google Scholar
  10. R.-T. Liu, N.-F. Huang, C.-H. Chen and C.-N. Kao (2004). “A fast string-matching algorithm for network processor-based intrusion detection system.” ACM Transactions on Embedded Computing Systems, 3, 614–633.DOI: 10.1145/1015047.1015055Google Scholar
  11. A. Lopez (2008). “Statistical machine translation.” ACM Computing Surveys, 40, 1–49.DOI: 10.1145/1380584.1380586Google Scholar
  12. J. Tarhio and H. Peltola (1997). “String matching in the DNA alphabet.” Software: Practice and Experience, 27, 851–861.DOI: 10.1002/(SICI)1097-024X(199707)27:7<851::AID-SPE108>3.0.CO;2-DGoogle Scholar
  13. C. Ryu, T. Lecroq and K. Park (2020). “Fast string matching for DNA sequences.” Theoretical Computer Science, 812, 137–148.DOI: 10.1016/j.tcs.2019.09.031Google Scholar
  14. A. A. Karcioglu and H. Bulut (2021). “Improving hash-q exact string matching algorithm with perfect hashing for DNA sequences.” Computers in Biology and Medicine, 131, 104292.DOI: 10.1016/j.compbiomed.2021.104292Google Scholar
  15. I. Alsmadi and M. Nuser (2012). “String matching evaluation methods for DNA comparison.” International Journal of Advanced Science and Technology, 47, 13–32.Google Scholar
  16. E. T. Campbell, B. M. Terhal and C. Vuillot (2017). “Roads towards fault-tolerant universal quantum computatio.” Nature, 549, 172–179.DOI: 10.1038/nature23460Google Scholar
  17. A. G. Fowler, M. Mariantoni, J. M. Martinis and A. N. Cleland (2012). “Surface codes: Towards practical large-scale quantum computation.” Physical Review A, 86, 032324.DOI: 10.1103/PhysRevA.86.032324Google Scholar
  18. E. Knill (2004). “Fault-tolerant postselected quantum computation: schemes.” arXiv:0402171.Google Scholar
  19. S. Bravyi and A. Kitaev (2005). “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Physical Review A, 71, 022316.DOI: 10.1103/PhysRevA.71.022316Google Scholar
  20. P. Aliferis, D. Gottesman and J. Preskill (2006). “Quantum accuracy threshold for concatenated distance-3 codes.” Quantum Information & Computation, 6, 97–165.DOI: 10.26421/QIC6.2-1Google Scholar
  21. A. G. Fowler, A. M. Stephens and P. Groszkowski (2009). “High-threshold universal quantum computation on the surface code.” Physical Review A, 80, 052312.DOI: 10.1103/PhysRevA.80.052312Google Scholar
  22. A. Montanaro (2017). “Quantum pattern matching fast on average.” Algorithmica, 77, 16–39.DOI: 10.1007/s00453-015-0060-4Google Scholar
  23. D. Maslov (2016). “Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization.” Physical Review A, 93, 022311.DOI: 10.1103/PhysRevA.93.022311Google Scholar
  24. J. A. Smolin and D. P. DiVincenzo (1996). “Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate.” Physical Review A, 53, 2855–2856.DOI: 10.1103/PhysRevA.53.2855Google Scholar
  25. A. Javadi-Abhari, M. Treinish, K. Krsulich, C.J. Wood, J. Lishman, J. Gacon, S. Martiel, P.D. Nation, L.S. Bishop, A.W. Cross, B.R. Johnson and J.M. Gambetta (2024). “Quantum computing with Qiskit.” arXiv:2405.08810.Google Scholar
  26. P. Selinger (2013). “Quantum circuits of T-depth one.” Physical Review A, 87, 042302.DOI: 10.1103/PhysRevA.87.042302Google Scholar
  27. Y. Nam, Y. Su and D. Maslov (2020). “Approximate quantum Fourier transform with O(n log(n)) T gates.” npj Quantum Information, 6, 26.DOI: 10.1038/s41534-020-0257-5Google Scholar
  28. K. Oonishi, T. Tanaka, S. Uno, T. Satoh, R. Van Meter and N. Kunihiro (2021). “Efficient construction of a control modular adder on a carry-lookahead adder using relative-phase Toffoli gates.” IEEE Transactions on Quantum Engineering, 3, 1–18.DOI: 10.1109/TQE.2021.3136195Google Scholar
  29. C. Jones (2013). “Low-overhead constructions for the fault-tolerant Toffoli gate.” Physical Review A, 87, 022328.DOI: 10.1103/PhysRevA.87.022328Google Scholar
  30. K. Prousalis, A. Kydros and N. Konofaos (2025). “A quantum string-matching algorithm.” Advanced Quantum Technologies, 8, 2400250.DOI: 10.1002/qute.202400250Google Scholar
  31. Y. Zhang, K. Lu, Y. Gao and M. Wang (2013). “NEQR: A novel enhanced quantum representation of digital images.” Quantum Information Processing, 12, 2833.DOI: 10.1007/s11128-013-0567-zGoogle Scholar
  32. P. Q. Le, F. Dong and K. Hirota (2011). “A flexible representation of quantum images for polynomial preparation, image compression, and processing operations.” Quantum Information Processing, 10, 63.DOI: 10.1007/s11128-010-0177-yGoogle Scholar
  33. S. Jiang, R.-G. Zhou, W. Hu and Y. Li (2019). “Improved quantum image median filtering in the spatial domain.” International Journal of Theoretical Physics, 58, 2115.DOI: 10.1007/s10773-019-04103-wGoogle Scholar
  34. P. Li, X. Liu and H. Xiao (2018). “Quantum image median filtering in the spatial domain.” Quantum Information Processing, 17, 1.DOI: 10.1007/s11128-018-1826-9Google Scholar
  35. T. Li, P. Zhao, Y. Zhou and Y. Zhang (2023). “Quantum image processing algorithm using line detection mask based on NEQR.” Entropy, 25, 738.DOI: 10.3390/e25050738Google Scholar
  36. D. Wang, Z.-H. Liu, W.-N. Zhu and S.-Z. Li (2012). “Design of quantum comparator based on extended general Toffoli gates with multiple targets.” Computer Science, 39, 302.Google Scholar
  37. H.-Y. Xia, H. Zhang, S.-X. Song, H. Li, Y.-J. Zhou and X. Chen (2020). “Design and simulation of quantum image binarization using quantum comparator.” Modern Physics Letters A 35, 2050049.DOI: 10.1142/S0217732320500492Google Scholar