>simultaneously in every state
Bunk. Quantum solvers often do not find the desired answer and have to be run repeatedly to build confidence that it has probably been discovered. Ergo an exhaustive search of the problem is not being performed, because if it was, it would find the right answer on the first try. No exhaustive search, no voodoo data in all states at once.
Information is physical. A thing can only be what it is and have the state that it has. Explanations that violate logic are not scientific but pseudoscientific.
A quantum computer is just another example of a physical system that can be configured to find minimums. That we have started to make electronic systems capable of it does not make them magical, nor does applying the label quantum.