undefined | Better HN

0 pointscodekilla8y ago0 comments

Imagine you have a classical bit string 0101, there are 2^4 possible different configurations of this string, and the classical computer will always exist in ONE of them.

A quantum computer, with a qubit register 0101, can be put into a superposition state between all 4 qubits, where the state of the qubit register is ALL 2^4 different configurations simultaneously....now scale that up to 50-100-1000 qubits and you get the idea. The quantum computer has a ridiculous advantage in terms of holding state spaces.

0 comments

jcranmer8y ago

That argument is patently wrong: it's the quantum bullshit fallacy.

The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer.

The quantum bullshit fallacy is that, since an entangled N-qubit is represented as a 2^N-dimension vector with complex arguments, it's really a computation on 2^N elements in O(1) time. The first sign that this is fallacious is that the basis here isn't of size 2^N but of size 2^N - 1. We're still only capable of reading N bits of information out of an N-qubit register; the fact that classical simulation requires a much larger state space to compute the probability doesn't mean that there's an inherent ability to freely vary through all of those states to represent the entire state space.

codekillaOP8y ago

Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.

smallnamespace8y ago

As you say, N qubits can be thought of as a distribution over its possible 2^N values, but you can't ignore the starting distribution, which may be very far from the set of classical bits that you want to operate over (and therefore may take an exponential number of quantum operations to realize).

So one very simplified model to think of what quantum computation is that you can do parallel operations to a distribution over your 2^N vector of classical bits, but you don't get to specify an arbitrary starting distribution, you can only start with relatively 'simple' distributions.

This restriction is what makes the claim 'you can compute over 2^N values simultaneously' at best very incomplete — yes, you can do that, as long as you're fine not being able to start from arbitrary starting values. But this is a big restriction!

codekillaOP8y ago

What do you mean exactly by starting distribution? I'm definitely not saying you get the answer to every problem in a single evaluation step, no one ever said that.

1 more reply

jcranmer8y ago

If you have an N-bit classical computer in a black box, you get at most 2^N possible outputs. If you have an N-qubit quantum computer in a black box, you can get at most 2^N possible outputs, not 2^2^N. We write the N-qubit registers as a vector of 2^2^N elements to make the math work, but measurement means we still can only distinguish between 2^N possible values.

monktastic18y ago

Well, only in the same sense that the vector (1, 1) is "both (1, 0) and (0, 1) simultaneously." It's still a single vector in a 2^N dimensional space. It just happens to be expressed in terms of a basis that makes it look complicated.

j / k navigate · click thread line to collapse

0 comments

jcranmer8y ago

That argument is patently wrong: it's the quantum bullshit fallacy.

codekillaOP8y ago

smallnamespace8y ago

codekillaOP8y ago

What do you mean exactly by starting distribution? I'm definitely not saying you get the answer to every problem in a single evaluation step, no one ever said that.

1 more reply

jcranmer8y ago

monktastic18y ago

j / k navigate · click thread line to collapse