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.