How to theoretically compare the complexity of quantum and classical algorithms?

Question

I am working on reducing an NP class problem to a QUBO so can be solved with QAOA. I know that there is not a practical way to compare the performance as there is no QPU with enough qubits. I am doing the conceptual analysis of the performance, but not sure how I can theoretically compare the complexity of a Quantum algorithm with the Classical algorithm. Currently, I have considered the depth of the quantum circuit vs the time complexity of the classical algorithm. Are there any other metrics of a quantum algorithm for performance evaluation ?

Also, gate complexity(number of gates required) is also a way to evaluate the computational complexity, but I don't find it logical to use gate complexity as a metric to compare with the time complexity of a classical algorithm as execution of the circuit can happen in parallel. Also, I am not sure of considering the optimization(Transpilation) process. Suggestions are welcome.

Answer 1

To analyze the complexity of Quantum Algorithms we use what is known as Query Complexity. The Query Complexity of an algorithm is the number of times it must Query the solution associated with the problem. The advantage of analyzing algorithms through query complexity is the fact that they make it very straightforward to prove lower bounds on algorithms and hence demonstrate supremacy.

For instance, the query complexity of Grover's algorithm is $O(\sqrt N)$, but the query complexity of a classical linear search is $O(N)$. We can also show using the adversarial method that the lower bound on the query complexity of a Search is $\Omega(N)$ this shows us the Quantum Algorithm is optimal.

You can read more on the details of query complexity and analyze the query complexity of search in the links provided.