The story I heard 3-4 years ago was if you asked a physicist working on quantum computing what is actually happening when you turn on the system, you'd get one of two answers:
1) Each time we turn it on, for every qubit in the system, an entire universe identical to ours is created with its own quantum computer working on the problem. Once one of the computers in this "network" of universes comes up with the answer, it disseminates that answer to the other computers in the other universes.
2) I don't want to talk about it.
As far as quantum computers go, I could just as readily believe that every time you turn one on, the whole of reality is paused for 1 femtosecond while the system spends 10^25 years working the problem in its own reference frame and then un-pauses reality once it has the answer. Or perhaps a quantum computer essentially DMs the Flying Spaghetti Monster who instantly provides the answer. These are no less fantastical to me anyway.
But as a non-physicist sitting on the sideline writing comments on /., perhaps it's just because I don't understand the problem being posed to the system and do not have any context. For example, suppose a grain of sand could be randomly oriented in 3d space in 20 different ways. Then you asked a quantum computer what is the orientation for every grain of sand on the planet. The answer comes back in less than 1 second, and upon checking 1 million random grains of sand, they all matched the predictions of the QC.
In that situation, yeah, I'd be wondering how the F QC did that and start looking at explanations that are closer to magic than known science.