Real-world problems in computer science and engineering become intractable at large sizes due to the combinatorial explosion of the search space. Various heuristic optimization methods are used in practice; novel approaches that rely on the laws of quantum mechanics are also being investigated. In this talk I present physics-based analysis of the complexity of quantumannealing algotithm. In many cases, the complexity is governed by the phase transition bottleneck, where the dynamics slows down. But even for the most auspicious scaling at the phase transition, disorder may lead to the appearance of additional tunneling bottlenecks (inside the spin-glass phase) that require exponential annealing time.  Using an exactly-solvable model as an example, I will argue that in problems lacking inherent geometry the number of spin-glass bottlenecks grows logarithmically with problem size. This slow increase is responsible for a crossover from polynomial to exponential complexity as spin-glass bottlenecks become dominant. This general mechanism should be ubiquitous in heuristic optimization and not confined to quantum annealing. The "bottleneck density” can be used as a robust metric to compare efficacy of algorithms at intermediate sizes, as asymptotically efficient algorithms remain elusive.