Quantum
Computing: Solving Complex Problems
One of the motivating
ideas of quantum computation was that there could be a new kind of machine that
would solve hard problems in quantum mechanics. There has been
significant progress towards the experimental realization of these machines
(which I will review), but there are still many questions about how such a
machine could solve computational problems of interest in quantum
physics. New categorizations of the complexity of computational problems
have now been invented to describe quantum simulation. The bad news is that
some of these problems are believed to be intractible even on a quantum
computer, falling into a quantum analog of the NP class. The good news is
that there are many other new classifications of tractability that may apply to
several situations of physical interest.