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

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.

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.