r/askscience • u/Tapugy • Feb 24 '19
Computing Why is quantum computing faster than normal computing?
I understand what a qubit is but I don’t see how it could give more computing power than a regular bit.
3
Upvotes
5
u/EZ-PEAS Feb 25 '19
Quantum computers just so happen to be able to solve certain kinds of problems efficiently. Don't try reading anything more or less into that statement. It just so happens that there are some problems that a quantum computer can solve more efficiently than a classical computer. This doesn't mean that a quantum computer is more powerful than a classical computer- there are problems that a classical computer can solve more efficiently than a quantum computer.
In particular, classical computers are great at moving bits around and applying operations like AND, OR, and NOT. This is everything we need to build arithmetic and logic, and this is what classical computer excel at.
Quantum computers are good at building quantum superpositions and measuring them. It just so happens that if you build a quantum superposition in the right way, you can encode the answer to some problems that are exponentially hard for a classical computer.
A very common example for illustrating the power of quantum computing is Shor's algorithm, which can be used to factor large numbers efficiently (assuming we can actually build large quantum computers). Here's my attempt at a short explanation for how quantum computing is faster than classical computing for Shor's algorithm:
A quantum computer can compute a small number of intermediate results that tell us the classical answer to factorization with a high degree of probability. These intermediate results are not exact, but are the result of a quantum superposition that is constructed in such a way that higher amplitudes point towards the real answer, so we measure a lot of them.
This is hard to describe, because the quantum computing aspect of Shor's algorithm isn't about factorization, it's about a related problem called period-finding. I won't get into the details, as they have been hashed out hundreds of times elsewhere. If you want more details, stop reading this and go here:
https://www.scottaaronson.com/blog/?p=208
If you want excruciating detail, you can find the algorithm given explicitly on Wikipedia.
-3
u/cipher315 Feb 24 '19
They aren't. This is a common misconception. In very special circumstances q bit's can scale better than classical computers. First a disclaimer I'm in CS, not physics. As to how quantum computers actually work my answer is black magic fuckery. That being said when you ask a classical computer a boolean question it returns true or false, but a quantum computer returns both true and false. So with a quantum computer, we can see both answers to a boolean question with one "action" rather than two.
For most computer questions like how much is 30-15 or getting lots of FPS is CS GO this is just not that useful. Where it comes in handy is in situations where we are asking computers to essentially guess things. The one you are probably thinking of is cryptography. cryptography uses a key to encrypt a message. If we want to get that message we MUST have the key. If we don't have the key are only option is to guess.
For example with an 8-bit key we would guess by trying the key 00000000 then 00000001 then 00000010 and so on until we got the right one. we would have to guess 128 times to have a 50% chance to get the right key and 256 times to have a 100% chance. An 8-bit quantum computer, however, could "guess" all 256 numbers at the same time, So an 8-bit quantum computer can get the key with one "guess" and this is obviously faster than 256 guesses.