Quantum Theory and Computational Complexity

The Physics arXiv Blog has a really interesting article about the connection between quantum theory and the question of whether or not P = NP. The article starts with the question of why we can't observe quantum phenomena at the macroscopic scale. Arkady Bolotin of Ben-Gurion University says that the key to understanding the problem is to treat it as a problem of computational complexity.

Briefly—see the article for details—the idea is that while it is possible to solve Schrödinger’s equation for simple systems at the quantum scale, it becomes increasingly difficult as the number of particles increases. Bolotin asks what if it's impossible to solve Schrödinger's equation for macroscopic systems in reasonable time. He shows that it is indeed impossible providing P ≠ NP.

The article outlines the argument in terms accessible to those not expert in quantum mechanics. To my—mostly uninformed—mind this provides a persuasive argument for the notion that P ≠ NP. It's not a proof of course but it is persuasive. If you have the slightest interest in the P ≠ NP problem or are fascinated by the counter intuitive results of quantum mechanics, I'm sure you'll enjoy the article.

This entry was posted in General and tagged . Bookmark the permalink.
  • A quick comment from someone in the area. (This is just my understanding, and I have no problem with being argued wrong).

    The complexity of solving a quantum Hamiltonian does indeed relate to the NP-hard problems. However, the blog rather overstates the meaning of this.

    Namely:
    1. The assumption that P =/= NP does not limit the size of quantum states;
    2. The assumption that macroscopic quantum states (like the mentioned cat state) exist does not imply P = NP.

    The reason is: the simple fact that there exists a quantum system which implements the solution of its own (NP-hard) Hamiltonian does not imply there exists an efficient algorithm for this task.

    • jcs

      I'm a complete laymen in this area so I'm in no position to argue for or against the position posited in the article. I do find the connection between quantum theory and the (arguably) most important problem in CS fascinating though.