# Query complexity on Quantum Pattern Matching of Mateus Algorithm

I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $$O(\sqrt{N})$$, apart from the cost of setting up the initial state: $$\frac{1}{\sqrt{N-M+1}}\sum_{k=1}^{N-M+1}|k,k+1,...,k+M-1⟩$$

After that, they conclude that the algorithm has an efficient compile time of $$O(N\log^{2}(N)\times |\Sigma|)$$ and a total runtime of $$O(M\log^{3}(N)+N^{3/2}\log^{2}\log(M))$$, but query complexity $$O(\sqrt{N})$$.

My question is, if I devise an algorithm with, for example, a processing step of $$O(N^{2})$$ circuit complexity but $$O(\sqrt{N})$$ query complexity. Is it completely fine to say that it is faster than a classical equivalent with, for example $$O(N)$$ complexity? I'm a bit stuck trying to figure this out.

• Is your question along the lines of the difference between circuit complexity and query complexity? Given an oracle for some Boolean function $f$, the classical circuit complexity implementing this function is not that much better than the quantum circuit complexity. But Grover’s algorithm gives a reduction in the quantum query complexity. Jun 22 at 1:31
• More or less, my problem is when you take a circuit with some complexity and then it is used as a black box; after that, we call the black box as much as we need. I've tried to figure out where is my mistake here, it has to be not that simple I think. Do the above is not like keep the dust under the carpet? Jun 22 at 6:30