Quantum annealing can be thought of as a black box solver that can find approximate solutions to hard optimization problems. For example, D-Wave quantum annealers can approximately solve quadratic unconstrained binary optimization (QUBO) problems, which are known to be NP-hard.
In this context, what is the computational complexity of quantum annealing? More specifically:
If the size of my problem is $N$, how long will I need to run the quantum annealing process (as a function of $N$) to obtain the exact solution?
Under an approximation algorithm / randomized algorithm setting, how many repetitions of quantum annealing will I have to perform to obtain an approximate solution that is within $\epsilon$ error of the exact solution (for example, $\epsilon = 0.1$ for getting a $10\%$ error)?
In my experience running problems on the D-Wave, I have noticed that a constant annealing time in conjunction with a constant number of repetitions can find exact solutions for smaller-sized problems. However, quantum annealing is not as accurate on larger-sized problems.