The words out of your mouth will literally be ignored, misheard, or even contorted to the opposite of what they mean, if that’s what it takes to preserve the listener’s misconception
Scott Aaronson on why quantum computers don’t speed up computations by parallelism, a popular misconception.
The misconception isn’t exactly that quantum computers speed up computations by parallelism. They kinda do. The trouble is that what they do isn’t anything so simple as “try all the possibilities and report on whichever one works”—and the real difference between that and what they can actually do is in the reporting rather than the trying.
Of course that means that useful quantum algorithms don’t look like “try all the possibilities”, but they can still be viewed as working by parallelism. For instance, Grover’s search algorithm starts off with the system in a superposition that’s symmetrical between all the possibilities, and each step changes all those amplitudes in a way that favours the one we’re looking for.
For the avoidance of doubt, I’m not in any way disagreeing with Scott Aaronson here: The naive conception of quantum computation as “just like parallel processing, but the other processors are in other universes” is too naive and leads people to terribly overoptimistic expectations of what quantum computers can do. I just think “quantum computers don’t speed up computations by parallelism” is maybe too simple in the other direction.
I agree that “parallelism but in other universes” is a weird phrasing.
What happens with quantum computation is cancellation due to having negative probabilities. The closest classical analogue seems to me to be dynamic programming, not parallel programming—you have a seemingly large search space that in fact can be made to reduce into a smaller search space by e.g. cleverly caching things. In other words, this is about how the math of the search space works out.
If your parallelism relies on invoking MWI, then it’s not “real” parallelism because MWI is observationally indistinguishable from other stories where there aren’t parallel worlds.
No, it’s one of those right/wrong differences. I changed my mind about how to structure the sentence—from “I don’t think X is quite right” to “I think X is not quite right”—and failed to remove a word I should have removed. (I seem to be having trouble with negatives at the moment: while trying the last sentence, my fingers attempted to add “n’t” to both “should” and “have”!)
Wait, American/British? I think we live within 10 miles of one another. Admittedly, I was born in the US, but I haven’t lived there since I was about 4.
Consulting for the engineering department at the moment, but my time’s my own, and I’m intrigued enough to put myself out. You choose place and time, and I’ll try to be there.
It may even be that we have better ways of communicating than blog comments! I am lesswrong@aspden.com, 07943 155029.
In general, of course it is. (I think “couldn’t care less” / “could care less” is an example, though my Inner Pedant gets very twitchy at the latter.) But I think it’s unusual to have such big differences in idiom, and I suspect they generally arise from something that was originally an outright mistake (as I think “could care less” was).
Scott Aaronson on why quantum computers don’t speed up computations by parallelism, a popular misconception.
The misconception isn’t exactly that quantum computers speed up computations by parallelism. They kinda do. The trouble is that what they do isn’t anything so simple as “try all the possibilities and report on whichever one works”—and the real difference between that and what they can actually do is in the reporting rather than the trying.
Of course that means that useful quantum algorithms don’t look like “try all the possibilities”, but they can still be viewed as working by parallelism. For instance, Grover’s search algorithm starts off with the system in a superposition that’s symmetrical between all the possibilities, and each step changes all those amplitudes in a way that favours the one we’re looking for.
For the avoidance of doubt, I’m not in any way disagreeing with Scott Aaronson here: The naive conception of quantum computation as “just like parallel processing, but the other processors are in other universes” is too naive and leads people to terribly overoptimistic expectations of what quantum computers can do. I just think “quantum computers don’t speed up computations by parallelism” is maybe too simple in the other direction.
[EDITED to remove a spurious “not”]
I agree that “parallelism but in other universes” is a weird phrasing.
What happens with quantum computation is cancellation due to having negative probabilities. The closest classical analogue seems to me to be dynamic programming, not parallel programming—you have a seemingly large search space that in fact can be made to reduce into a smaller search space by e.g. cleverly caching things. In other words, this is about how the math of the search space works out.
If your parallelism relies on invoking MWI, then it’s not “real” parallelism because MWI is observationally indistinguishable from other stories where there aren’t parallel worlds.
Negative (and imaginary) phase. The probability is the norm of the phase and is always positive.
I just don’t think <-> I just think, or is this one of those American/British differences? Also, nice recursion in the grandparent.
No, it’s one of those right/wrong differences. I changed my mind about how to structure the sentence—from “I don’t think X is quite right” to “I think X is not quite right”—and failed to remove a word I should have removed. (I seem to be having trouble with negatives at the moment: while trying the last sentence, my fingers attempted to add “n’t” to both “should” and “have”!)
Wait, American/British? I think we live within 10 miles of one another. Admittedly, I was born in the US, but I haven’t lived there since I was about 4.
Ahh, the mysterious ‘g’. Hi there. We really should have lunch sometime!
Yup, ’tis I. (No, wait, I’m two letters of the alphabet off.)
Yes, we should. At weekday lunchtimes I’m near the Science Park; how about you?
Consulting for the engineering department at the moment, but my time’s my own, and I’m intrigued enough to put myself out. You choose place and time, and I’ll try to be there.
It may even be that we have better ways of communicating than blog comments! I am lesswrong@aspden.com, 07943 155029.
Inserting a ‘not’ where it shouldn’t be is not an American/British difference.
But is it not possible that whether it should or shouldn’t be there is a matter of the dialect of the speaker?
In general, of course it is. (I think “couldn’t care less” / “could care less” is an example, though my Inner Pedant gets very twitchy at the latter.) But I think it’s unusual to have such big differences in idiom, and I suspect they generally arise from something that was originally an outright mistake (as I think “could care less” was).
And in particular, such a twisted usage does not fall neatly across the America/Britain divide.
Especially in this particular case where it was pretty clearly an editing error.
So Data can’t set his phasor to NP-hard? :)