[osweiller]

While this seems planted and trite (much like the "because it's 2015" answer), I have to confess that I don't get quantum computing.

A qubit can hold multiple values, it seems. Okay, that's a data density improvement (presuming a quibit is as dense as a traditional bit). How does that improve computing power (especially by the many magnitudes)? Do you multiply a qubit of infinite values against a quibit of infinite values and have all possible results? I just don't see the bridge from data density to a revolution in computing power.

Note that I'm not saying this as a cynic. I know that this is happening, and a lot of very smart people are excited by it. I just have never seen an explanation that bridges data density to calculation speed.

[galadran]

Note: This explanation is FAR from precise and is only trying to give an intuition

The key point is that qubits aren't limited to finite "multiple values", they can express an uncountable number of values. The best "short" answer is that a qubit can exist in a superposition (QM Term) of states. LOOSELY put it can have a probability of being a 0 and a probability of being 1 (with both probabilities adding to 1). This ability to encode information as the probability is the key to quantum computing.

When you measure (QM Term) the qubit, it takes on either the value 0 or 1 according to the probabilities you set it up with. This is computationally useful because with clever constructions you can make these probabilities meaningful.

For example Grover's Algorithm allows you to search an unsorted database for a particular item in O(sqrt(N)) time rather than the classical best O(N). The algorithm is successful with very high probability, note that because it uses the probabilistic nature of qubits, it itself can only be probabilistically correct, it just so happens you can make the probability of error very low (in theory lower than the chance your classical computer has a bit flip or similar)

The unfortunate restriction on QC is that you need enough qubits to encode your problem, if you can't hold the database in your "qubit memory" then you can't perform algorithm. In practice, building systems of qubits is extremely difficult and the current record is about 1000 as of 2015 I believe.

[q4h555qh5]

I'll try to answer this by presenting two types of computations a quantum computer is good at.

1) Quantum Simulation. So in a quantum system, your state can be in a superposition of states ("because waves"). There is a lot of information that resides in the way this system is in superposition and it determines how the system will interfere and evolve (amplification or destruction of certain states). Mathematically, it means you need to keep track of the complex amplitude of each of the 2^n states of a n-qubits system. On a classical computer, this means 2^n complex numbers are necessary to represent the quantum state.

However, on a quantum computer, you only need n-qubits to represent the quantum state, because qubits can be in superposition the same way any quantum state in nature can be. You can now do careful operations on your n-qubits state and simulate any quantum mechanical phenomena. It is therefore way easier to simulate quantum mechanics on a quantum computer than on a classical computer. This could be useful in many areas, like chemistry to simulate protein-folding.

2) Factorization (Shor's algorithm). It is possible to engineer a quantum state that is the superposition of all possible inputs. Then, it is also possible to carefully create interference so that non-solution of the factorization problems get lower amplitude, while solutions get bigger amplitude. At some points you can measure the state and collapse it in one of the state. Since the amplitude of the solutions is big compared to the amplitude of non-solutions, you get the solution with significant probability. You can then verify it using any classical computer because multiplying two numbers is easy. This algorithm breaks most of today public key cryptography used on the internet.

[inlineint]

One qubit could hold 0 and1 simultaneously and perform some operations/calculations on it simultaneously.

Two (entangled) qubits could hold 00, 01, 10, 11 simultaneously and perform calculations on these four values simultaneouslty.

...

100 (entangled) qubits could hold 2^100 distinct values simultaneously and perform calculations on them simultaneously.

That's the basic idea. The problem is keeping entangled state that's becomes harder and harder as number of entangled qubits grows.

Also there are limitations in extracting of calculations results from system of qubits, so not all algorithms can be speed up on quantum computers (but e.g. integer factorization can).

[riskable]

I was under the impression that the benefit of quantum computing was the ability to come to the "correct" answer for certain kinds of computationally complex problems instantaneously without having to actually "compute" them. So for example you'd spend a great deal of time up front engineering a way to present a problem to a quantum computer and when you execute said program it gives you the result that very moment without actually having to perform any traditional "operations".

So for example, let's say you wanted to figure out if some enormous number is prime. If you get your program right you could feed it to a quantum computer and all possible states of prime/non-prime would be measured at once resulting in the answer (state) being available the moment you "observe" it.

From this perspective quantum computing can be nearly infinitely faster than traditional computers while at the same time being mostly useless for every-day tasks such as surfing the web.

[anotheryou]

I'm no expert and might be horrible wrong on the math, but I imagine it like this:

2 bit => 2 ^ 2 => 1 of 4 possible state

2 qbit => 4 of 4 possible states. That's 4 times the information (although extraction of the information is limited)

With bigger numbers:

10bit => 1 of 1024 possible states

10qbit => 1024 of 1024 possible states (1024 times as much)

[Filligree]

> Do you multiple a qubit of infinite values against a quibit of infinite values and have all possible results?

The accurate answer would be "no", or at least "thinking that way will lead you to believe that they're more powerful than they are".

In particular, quantum computers won't allow you to solve NP-hard problems in less than exponential time, not unless there's something we're missing in the math.

That said? Since I don't have the chance to describe it better right now, you can start off by thinking "sorta, yes".

[alistproducer2]

There are some great explanation here, but I wanted to add an article that gave me some insight about the subject: http://arstechnica.com/science/2010/01/a-tale-of-two-qubits-...

[return0]

I couldn't recommend enough Michael Nielsen's on quantum computation. He has also written many articles:

http://michaelnielsen.org/blog/quantum-computing-for-the-det...

[empath75]

Google 'quantum complexity classes'.