At Last!
A quantum solution to the NP problem could be just round the corner, and then we can have satellite navigation with routes!
Oh, hold on...
The long-awaited arrival of quantum computers could be one step closer, as boffins from Oz have for the first time encoded quantum information in silicon. Unlike conventional computers, which store data on transistors and hard drives, quantum computers encode data in states of microscopic objects called qubits. The arrival of …
You can't prove that but it seems to be a law of nature (see most anything by Scott Aaronson and in particular NP-complete Problems and Physical Reality and this blog entry) Indeed, whenever you think up a physical machine with quantum powers to collapse NP to P, it fails through some unphysical assumptions you need.
As P = NP would actually would mean that things that are easy to check are easy to guess, immense powers of godlike computation would ensue and as this trick is not being performed in nature to all available evidence, the P = NP believers and agnostics have to be firmly placed in the camp of cranks and perpetuum mobilists.
Technically: BQP is strictly smaller than NP.
but then again there are special cases for graph theory called cliques (used for expression array analysis).
But generally the proof of P=NP is not going to exist without us solving the many-body problem first...
As the canonical physical problem we know (according to our best understanding) there is NP complexity behind the Schrodinger equation. The universe might need NP complexity to work, but things such as having a finite "c" seems to suggest something else is going on. This implies some of approximations might help at least reduce the search space....far from a solution but might be useful.
This is sort of what ab initio MD does; a pile of approximations/constraints that yield incredibly accurate results due to a greatly increased phase space for particles (and more accurate energetic states).
It really does make you wonder what is further on down there...more turtles?
P.
there is NP complexity behind the Schrodinger equation
That's the first time I have heard that kind of statement. You may want to provide citations.
The Schrödinger equation is a bog-standard differential equation. It solves nothing. You just let it run. Whether you need infinite precision at the density of reals is a matter of discussion, and I remember reading that the symbolic computation of the values would eschew the need of making physical use of the reals.
To solve the SE it starts to look NP complete pretty rapidly, so we approximate it. No citation necessary, just need to know the results we count on and the fact we only have:
1) Solved for hydrogen
2). Sort of solved for Helium (Hartree-Fock etc).
3) Everything else - See 1) (Slater orbitals, HF, DF etc...).
BTW "Bog standard differential equation" is the understatement of the week ;-)
This is not really my field (!) but I have written enough MD simulations to know that there are many approximations required, starting with the 2-body truncation of the many-body expansion. You gain very subtle improvements by expanding the terms, hence ab initio (Carr-Parinello) is useful for systems with known geometry (e.g. crystal structures of enzyme catalytic sites), and really useful (though still approximate) chemistry. When I first saw a visualization of protons hopping around ab initio water molecules, the hairs on my neck stood up....! *Phenomenal accuracy*.
I stand by my comment that the N-body problem is at the heart of why NP != P.
It is a fascinating constraint on the universe structure though...
P.
I can see the business applications now.
The main problem with conventional computing in addressing the needs of business is that whenever you come up with a correct answer that causes some bugger to change the question.
Hopefully a quantum computer will be able to deliver the right answer and the right answer to the new question at the same time.
Unlike conventional computers, which store data on transistors and hard drives, quantum computers encode data in states of microscopic objects called qubits.
Well, the "qubit" is the mathematical representation of a superposition of two distinct states, whereas transistors and hard drives are physical machines. Apples and oranges?
Also, the qubit is not very interesting. Interesting is:
1) Get a bunch of N qubits together
2) Wire them up so that some Hamiltonian is being implemented
3) Let the machinery run, thus moving the "state space vector" in the 2^N dimensional complex space (entanglement!)
4) After some time, measure the qubits along the projective axes, getting a classical 0..1. string with classical probabilities (collapse the wavefunction!)
5) If 2) was good, 4) is probably the solution to your problem.
Here, we are at 1).
Also, the last time I checked, modern conventional computers "store data ... in states of microscopic objects". Certainly my eyesight isn't good enough to distinguish the individual transistors and magnetic domains in my computer's chips and drives.
That whole "Unlike conventional computers" sentence had rather a bit of the Fry-nature.
And as an addendum to your item 1: for practical interesting problems, the "bunch" needs to be pretty big. Certainly much bigger than anything anyone's demonstrated so far.