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

Park, Byeongyong; Noh, Hansol; Ahn, Doyeol

doi:10.2478/qic-2025-0016

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 14N^3/2 log₂ N – O(N^3/2) to 8N^3/2 log₂ N – O(N^3/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.

References

L. K. Grover (1997). “Quantum mechanics helps in searching for a needle in a haystack.” Physical Review Letters, 79, 325–328.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
H. Ramesh and V. Vinay (2003). “String matching in quantum time.” Journal of Discrete Algorithms, 1, 103–110.
Search in Google Scholar Back to article
P. Niroula and Y. Nam (2021). “A quantum algorithm for string matching.” npj Quantum Information, 7, 37.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
H. Schütze, C. D. Manning and P. Raghavan (2008). Introduction to Information Retrieval. Cambridge: Cambridge University Press.
Search in Google Scholar Back to article
R. R. Naik, M. B. Landge and C. N. Mahender (2015). “A review on plagiarism detection tools.” International Journal of Computer Applications, 125.
Search in Google Scholar Back to article
M. K. Vijaymeena and K. Kavitha (2016). “A survey on similarity measures in text mining.” Machine Learning with Applications: International Journal, 3, 19–28.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
A. Lopez (2008). “Statistical machine translation.” ACM Computing Surveys, 40, 1–49.
Search in Google Scholar Back to article
J. Tarhio and H. Peltola (1997). “String matching in the DNA alphabet.” Software: Practice and Experience, 27, 851–861.
Search in Google Scholar Back to article
C. Ryu, T. Lecroq and K. Park (2020). “Fast string matching for DNA sequences.” Theoretical Computer Science, 812, 137–148.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
I. Alsmadi and M. Nuser (2012). “String matching evaluation methods for DNA comparison.” International Journal of Advanced Science and Technology, 47, 13–32.
Search in Google Scholar Back to article
E. T. Campbell, B. M. Terhal and C. Vuillot (2017). “Roads towards fault-tolerant universal quantum computatio.” Nature, 549, 172–179.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
E. Knill (2004). “Fault-tolerant postselected quantum computation: schemes.” arXiv:0402171.
Search in Google Scholar Back to article
S. Bravyi and A. Kitaev (2005). “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Physical Review A, 71, 022316.
Search in Google Scholar Back to article
P. Aliferis, D. Gottesman and J. Preskill (2006). “Quantum accuracy threshold for concatenated distance-3 codes.” Quantum Information & Computation, 6, 97–165.
Search in Google Scholar Back to article
A. G. Fowler, A. M. Stephens and P. Groszkowski (2009). “High-threshold universal quantum computation on the surface code.” Physical Review A, 80, 052312.
Search in Google Scholar Back to article
A. Montanaro (2017). “Quantum pattern matching fast on average.” Algorithmica, 77, 16–39.
Search in Google Scholar Back to article
D. Maslov (2016). “Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization.” Physical Review A, 93, 022311.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
P. Selinger (2013). “Quantum circuits of T-depth one.” Physical Review A, 87, 042302.
Search in Google Scholar Back to article
Y. Nam, Y. Su and D. Maslov (2020). “Approximate quantum Fourier transform with O(n log(n)) T gates.” npj Quantum Information, 6, 26.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
C. Jones (2013). “Low-overhead constructions for the fault-tolerant Toffoli gate.” Physical Review A, 87, 022328.
Search in Google Scholar Back to article
K. Prousalis, A. Kydros and N. Konofaos (2025). “A quantum string-matching algorithm.” Advanced Quantum Technologies, 8, 2400250.
Search in Google Scholar Back to article
Y. Zhang, K. Lu, Y. Gao and M. Wang (2013). “NEQR: A novel enhanced quantum representation of digital images.” Quantum Information Processing, 12, 2833.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
P. Li, X. Liu and H. Xiao (2018). “Quantum image median filtering in the spatial domain.” Quantum Information Processing, 17, 1.
Search in Google Scholar Back to article
T. Li, P. Zhao, Y. Zhou and Y. Zhang (2023). “Quantum image processing algorithm using line detection mask based on NEQR.” Entropy, 25, 738.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article

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

Abstract

Paradigm

My account