This brings us, finally, to a current PNAS paper by researchers at Columbia University and NEC Laboratories who have investigated the problem-solving abilities of adiabatic quantum computers. What they have shown is that, when adiabatic quantum computers are used to solve NP-complete problems, the energy gap between the lowest energy state and the next state up is not well behaved. Instead, it narrows faster than exponentially, meaning the adiabatic quantum computing cannot, even in principle, solve NP-complete problems faster than a classical computer.
What makes this work special is that it is more general than the papers that precede it. Rather than focusing on a specific problem,
the researchers looked at the statistics of how the energy gap behaves. They found that adiabatic quantum systems exhibit properties very similar to disordered quantum systems.