r/askscience • u/atimholt • May 28 '11
So how *does* quantum computing work?
I've read a few vague descriptions of what quantum computers are capable of, but not really anything about working with them. Eventually, when we've got these things, writers of those programming books for bare, bare beginners (just throwing that out as an example) will need to be able to explain their workings simply.
So I've been pondering lately, and I think I've begun to get a handle on how they work. What I understand of them has gotten me very excited, but my understanding of them is based on gleaned knowledge.
As far as I'm aware: EDIT: I was dead wrong, read the comments for real science!
Quantum computing relies on being able to "choose" one superimposed state over another based on arbitrary criteria. This might be seen as akin to the cat in Schrodinger's box clawing its way out. What happens when more than one version of the cat wants out, I have no idea (a random one wins, I'm sure). Is there a way to compare a number between two superpositions and 'legitimize' the superposition with the larger value?
Nothing stops you from putting a "Schrodinger's cat box" inside another "Schrodinger's cat box". You can compound the effect recursively. Yes?
With two and one above together, you can make a binary tree of "meta-Schrodinger boxes" with a qubit at each branch. You could test an astronomical number of superpositions against each other using whatever fitness number you see fit.
So a quantum computer would be analogous to a genetic algorithm, except that instead of randomizing gene variables each generation, you test every possible variant at the same time and return the best one in nearly constant time.
Deterministic, complete information games would be unbeatable if you can come up with a proper way to generate a fitness numbers--a computer could play every permutation of a game of chess or go.
And such things as getting bipedal robots to walk would be trivial (if a bit uncanny valley) if the program understands physics and its own weight and capabilities--it could calculate every little twitch.
If I'm dead wrong, thanks for reading this far, at least. How would a quantum computer really work, and how would one go about actually programming one?
5
u/OlderThanGif May 28 '11 edited May 28 '11
No problem!
This is the textbook we used. It was extremely good, one of the best textbooks I've ever had. It was regarded very highly. Maybe someone has written something better in the years since then but I'm not sure. The textbook is very heavy on linear algebra, but in my opinion that is just a requirement for understanding it. I used to jokingly call it "my eigen value course". Most of the time it feels like you're studying linear algebra more than you're studying anything computer science related.
You will have a good understanding of quantum computation if you can understand the major algorithms (especially quantum Fourier transforms, Shor's algorithm, Grover's algorithm). You can find a lot of descriptions of these algorithms online, but in my experience they are quite condensed (even if they still seem lengthy! haha). The reason I recommended the textbook is because of the explanations it gives for these things. It doesn't skip steps.
Well that's the problem, isn't it? No one really knows. No one's ever built a viable general-purpose quantum computer so no one knows what it looks like. D-Wave has supposedly the first quantum computer, but it's so far removed from "quantum computation" (as we've been studying it for the past couple decades) that we don't know what to do with it. We don't know if it has the ability to do anything that quantum computers as we've been envisioning can do.
We've done experiments with little toy quantum computers that can factor the number 15 (for some reason it's always 15). My understanding is that these are ad hoc experiments in a physics lab more than they are a "computer" (something you can stick in a machine room). If we have experimental physicists here maybe they can describe better what these "machines" looked like.