Quote:
Originally Posted by SR71
ES?
|
Yes, hello! Sorry, I missed the page.
Quote:
Quote:
|
I guess in the world of quantum computing, you are actually using a completely different way of doing the computing. So you're using what's called parallelism, quantum parallelism. So instead of doing calculations in the classical world one after the other, albeit very fast, you actually do these calculations in parallel.
|
|
I think she may be simplifying it a bit, as we already have true parallelism outside of quantum computing. It has existed for decades and is happening in your computer right now if you have a dual-(or more)-core processor. It's happening on an even greater scale in your graphics card as it calculates which color to paint each pixel on your screen at the exact same time. So, while parallelism is definitely cool, that's not what makes quantum computing so powerful. Regular parallelism can't give us the kind of exponential speed-up necessary to solve the types of problems she's talking about here:
Quote:
Quote:
|
And there are certain kinds of calculations where if you can do things in parallel, you can get a predicted exponential speed-up in the computation. And I guess that's one of the reasons why quantum computation is quite an exciting field at the moment. If you can actually realize them then there are certain tasks that you can do which would be much faster than you can do with classical computers.
|
|
So, for example, factoring numbers belongs to a class problems that are called NP-complete, which means that they can't be solved in polynomial time. The larger your problem gets, the amount of time it takes to solve the problem grows exponentially. But! With NP-complete problems, if you already have a proposed answer, you can verify it in polynomial time. So if I ask you to factor 12,118,699, it would take a very long time. But if I told you that the factorization was 3557*3407, you could check my work lickety split.
Last I heard (late last year) they had this one quantum computer factor the number 15. Big whoop, right? I can do that in my head. But seriously, factoring numbers is a very hard problem for traditional computers to do, but it has cool applications in spying and war-making, so the nerds make their prototypes do it as a parlor trick to get governments to throw money at them and it is very effective.
So with quantum computing, you have this black box (I'm a computer scientist, not a physicist, so I get to believe in magic and let them do the work, but I assume this is where the quantum parallelism and exponential speed-up happens) where I give it my problem, and it gives me an answer in polynomial time, but there's a possibility it won't be right. But suppose I know it has a 10% chance of being right. I just run my program 10 times and check each answer. That still takes loads less time than solving the problem straight out.
That's as much as I can remember from a 3-hour workshop I took last year. I'm taking the full course this fall, so hopefully I'll be more useful after that.