Summary
At the beginning of this chapter, we introduced several basic complexity classes and discussed their relationships. The time needed to solve NP-hard problems grows exponentially with the problem size, which is a strong motivation for exploring alternative approaches, such as analog adiabatic quantum computing. Even though quantum optimisers also solve NP-hard combinatorial optimisation problems in time that grows exponentially with problem size, the prefactor in the exponent may be smaller than for known classical algorithms. Additionally, we can expect to find an approximate solution in polynomial time, which provides a strong motivation for many practical applications of adiabatic quantum computing.
We then introduced the principles of AQC based on the adiabatic quantum theorem. The physical realisation of AQC – quantum annealing – has been contrasted with its classical counterpart – simulated annealing. We highlighted two main sources of computational power...
