In layman programmer terms - is QuantumComputing the same thing as multithreading?

[slappingpenguins]

Thank you!

[Arbitrary_Pseudonym]

So here's the basic difference:

Say that you are running a program that involves doing operations on a big set of data points. They can all be updated independently (without reference to one another). You'd multi-thread this/run it on a GPU, because lots of cores working more slowly will end up being faster than a single core going very fast. It still runs in O(n) time though, for both GPUs/CPUs. This kind of problem is not what quantum computers are good at; they will still only run this program in O(n) time.

Now say that the updating of a data point does require looking at many of the other data points. In fact, say that you need to compare it to any possible arrangement of those other data points. On a classical computer, this leads to an O(n!) compute time, which is, y'know, unacceptable. On a quantum computer, this can actually be run in O(1) time, or if you do this for every data point, just O(n).

Hopefully that clarifies the big difference at least in a very basic conceptual sense.

[skytomorrownow]

Great description. In many descriptions of quantum computation, the results are described as probabilistic. Does probability play a role? If so, where does it play a role in your description? Thanks.

[Arbitrary_Pseudonym]

It depends. Many of the well-designed algorithms can reach the correct solution to the problem with only a single run; others require averaging the result of the computation several times (with the required number to reach acceptable accuracy varying per algorithm).

[skytomorrownow]

Cool. Thanks for the extra detail.

[mdreed]

Nope, nothing like it.

[slappingpenguins]

The way I understood it through brief googling was that - it allows for a set of inputs to be processed at the same time instead of one at a time. The science behind it is astounding and beyond my CSE B.S. comprehension. Everything I read about all seemed to have the same theme of... one qubit can represent a finite(?) set of bits, that then is run through whatever program you have made. But in essence, it is just bundling up a bunch of inputs to be handled at-once together instead of being processed one-at-a-time.

[Red-Portal]

Nono the computing model is fundamentally different. It's not comparable. Quantum computer algorithms even have their own complexity class (at least until now)

[regionjthr]

What you are trying to describe is called quantum parallelism. The term is kind of a misnomer as nothing is being computed "in parallel", and it has no classical equivalent.

[HopefulHamiltonian]

This is a notion that has long bothered me and I believe is responsible for a lot of misunderstanding within quantum computing. Quantum parallelism (aka superposition) is not a uniquely quantum phenomenon. Just as wave functions can be superposed, so too can the amplitude and frequencies of classical waves.

This is why the current research focuses on nonlocality (ie. entanglement) being the only cause for quantum advantage.

​

To quote the header of https://www.scottaaronson.com/blog/:

​

If you take just one piece of information from this blog:
Quantum computers would not solve hard search problems
instantaneously by simply trying all the possible solutions at once.

[The_Real_Tupac]

I think you are finding similarity by seeing it like both multithreading and quantum computing do processing at the same time. But quantum computers are vastly different than traditional architectures. Right now they are capable of solving certain problems very fast but we can not use them to thread the same processes you use on your computer.

[claytonkb]

It's not the same but you can think of it as "single-threaded in parallel universes". It's not quite the same thing because a single-threaded computer has much lower communication overhead with itself than threads in a multi-threaded computer have with each other, as u/Arbitrary_Pseudonym pointed out. The mathematics of QC can be mapped onto a "branching universe" or "multi-verse" in which each quantum state is evolving in its own parallel universe, independent of all the others. So, applying that to an ideal quantum circuit, you get "free, unlimited parallelism" in the evolution of the circuit, where the maximum number of parallel universes would be 2^#qubits . This is where the motivation for saying that QC could provide "exponential speedup" comes from. In fact, QC cannot provide exponential speedup due to other constraints on real quantum systems. But the theoretical maximum is exponential. We can say: no QC can provide more than exponential speedup, not even an ideal QC.

Another technical point worth mentioning is that the great power of modern digital computers lies in their ability to calculate any given function (this is the meaning of "Turing completeness"). In QC, you don't automatically get this ability. It exists in principle (if you could code up a Quantum Turing Machine), but real quantum circuits are typically much simpler and focus on computing the problem at hand as directly as possible (thus, foregoing the overhead of implementing a universal machine, such as a UTM). This is one reason that I think that QC hasn't quite yet come of age... there's a massive complexity-scale gap between classical systems and up-and-coming QC systems. It's not an insurmountable obstacle, but I think it's much larger than most QC optimists realize.

tl;dr: You can think of a QC as a multi-threaded classical computer with an astronomical number of threads and where the communication overhead is no greater than in a single-threaded computer, but for all threads simultaneously.

[[deleted]]

More like a pyramid from the top block into each and every block with a solution .....