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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark S
    Jun 22 at 1:31
  • $\begingroup$ 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? $\endgroup$ Jun 22 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.