Re: What does this actually mean?
The definition of "power" is the [upper limit of complexity of a problem] that can be solved in O(1) time.
The [upper limit of complexity of a problem] is O(2^[length in bits of the answer description]).
With a classical computer, in the worse case, each of the possible O(2^[length in bits of the answer description]) permutations in the answer space must be examined independently in time (or space with a parallel architecture). For example, password guessing a random password with a classical computer requires iterating O(2^[length in bits of the answer description]), matching the hash of guess against the target hash.
A quantum computer, given the hash as input, can potentially guess the password in faster than O(2^[length in bits of the answer description]) - it can potentially do it in O(1).
It works in a probabilistic manner, like a slot machine. Pull the handle once, and get one educated guess. With a good program (=quantum circuit), and no noise, a correct password can be yielded with certainty in a single pull of the handle.
The circuitry inside the computer has complexity O([length in bits of the answer description]^N) where N is some constant, hopefully small. But with any constant N it grows slower than O(2^[length in bits of the answer description]) as we consider longer answer descriptions. I.e., the complexity of the circuitry is polynomial bounded, but the complexity of the answer space is not.
Biting the hand that feeds IT
