Do you guys not know there are already quantum computers?
https://youtu.be/60OkanvToFI

TheUltimatum wrote:

This looked helpful.

On quick glance that really does look helpful, thanks.

Yes, that's a great explanation for non-mathematicians/non-physicists, thanks again. May be what @gtoal has been waiting for! Key point for me is that you have to ditch / modify the lots-of-computers-working-in-parallel concept. Now have some idea of why Shor's algorithm (never previously understood at all) takes a roundabout approach to the factoring problem. The roundabout approach then exploits the constructive/destructive interference aspect of quantum physics, so that the right answer (or something pointing you in its direction) in theory appears when you eventually make a measurement. Or something like that…

gtoal wrote:

I warn you that this explanation is likely to be utter nonsense. It's just what I've worked out for myself from the explanations I've heard, none of which were ever boiled down to something simple that a non-physicist could understand.

Graham, you might find it amusing that there's a community of people (usually PhDs!) who constantly complain with much animosity about how the run-2^N-computations-in-parallel-and-pick-the-right-answer explanation is bogus fake news spread by the popular science media to get more clicks. When questioned about how these things actually work, they always say something along the lines of "no, no, it's about interference“ and then start talking about complex-valued probabilities and promising that this all works out. Which to me always felt like a bit of a cop-out, because even though it's not at all intended that way, it always comes across as some version of ”your explanation is wrong, and the right explanation is too hard for me to explain to you. Go study some math."

I think it comes down to a communication gap. :-(

Here is my (limited, of course) understanding: you know how sound can be represented by a wave, like, say, a sine wave? Imagine two horns are playing sine waves of the same amplitude (volume) at you: it makes sense that you'd hear twice as much noise because the wave crests and troughs add up and get exaggerated. Now, imagine one of the horns moves away from you just a little bit, so that one wave crests when the other troughs. Now, what happens? The crests and the troughs “cancel out”, and in theory you should hear silence!

That's a little weird. It turns out that this happens, though, with not just sound (horns) but also light (flashlights) — in fact, if you shine a flashlight through a piece of cardboard with two holes, then depending on where you look you either see very bright light from both holes, or no light at all! (You can't just use two flashlights because the phases need to line up.)

I find the example with light hard to visualize, but here's one with water. http://hyperlearningspace.weebly.com/uploads/1/4/9/4/14946194/8631739_orig.jpg That criss-cross pattern implies that depending on where in the ocean you are, you either get a LOT of wave or very little wave. In fact, this effect happens with pretty much anything that moves in a wave (including The Wave: imagine two waves going around a football stadium: depending on how they're timed, they could either lead to very excited people or very confused people when the waves meet…).

Anyway, the example with light is particularly concerning, because we're used to thinking of light as discrete particles (a bunch of experiments only really make sense if light is “quantized” in discrete lumps). But here, it's exhibiting this wave-ey property where you can add light and get less light because it cancels itself out, so to speak. At the single-light-particle level, this is hard to explain without saying worrying things like "the particle went through both slits", and this is what all the excitement is about.

Quantum computers, in theory, exploit the “canceling out” idea by saying: “can we choreograph a set of things to happen so that the wrong answers cancel out?” It turns out that for VERY SPECIFIC PROBLEMS we know how to do this: one example is Shor's algorithm for factoring integers. In general, we don't really know how to reduce problems to make the wrong answers cancel out — doesn't it sound hard? — and of course we don't really know how to build this kind of computer at a scale where it's useful.

—

I'm not a big fan of Scott Aaronson's explanations, not because they're sub-par (he's a brilliant scientist), but because his writing contains a lot of philosophy interspersed in between the actual explanations. There's a lot of “so philosophically, this means God chose the 2-norm because …” in there, which I find distracting, especially since those remarks really only sink in after you've understood the concepts.

Here's a more-to-the-point paper, in my opinion: https://arxiv.org/pdf/0708.0261.pdf

Here's a few useful videos: https://www.youtube.com/watch?v=IrbJYsep45E, https://www.youtube.com/watch?v=wUwZZaI5u0c&spfreload=10, https://www.youtube.com/watch?v=12Q3Mrh03Gk&spfreload=10 that finially helped me kind of understand quantum computers. and break my “run 2^N computations in parallel and magically pick the right one” misconception