  The circuit-level implementation of a quantum string-matching algorithm,
which matches a search string (pattern) of length $M$ inside a longer text of
length $N$, has already been demonstrated in the literature to outperform its
classical counterparts in terms of time complexity and space complexity.
Higher-dimensional quantum computing is becoming more and more common as a
result of its powerful storage and processing capabilities. In this article, we
have shown an improved quantum circuit implementation for the string-matching
problem with the help of higher-dimensional intermediate temporary qudits. It
is also shown that with the help of intermediate qudits not only the complexity
of depth can be reduced but also query complexity can be reduced for a quantum
algorithm, for the first time to the best of our knowledge. Our algorithm has
an improved query complexity of $O(\sqrt{N-M+1})$ with overall time complexity
$O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)$ as
compared to the state-of-the-art work which has a query complexity of
$O(\sqrt{N})$ with overall time complexity $O\left(\sqrt{N}\left((\log
N)^{2}+\log (M)\right)\right)$, while the ancilla count also reduces to
$\frac{N}{2}$ from $\frac{N}{2}+M$. The cost of state-of-the-art quantum
circuit for string-matching problem is colossal due to a huge number of Fredkin
gates and multi-controlled Toffoli gates. We have exhibited an improved gate
cost and depth over the circuit by applying a proposed Fredkin gate
decomposition with intermediate qutrits (3-dimensional qudits or ternary
systems) and already existing logarithmic-depth decomposition of $n$-qubit
Toffoli or multi-controlled Toffoli gate (MCT) with intermediate ququarts
(4-dimensional qudits or quaternary systems). We have also asserted that the
quantum circuit cost is relevant instead of using higher dimensional qudits
through error analysis.
