I am a computer engineering major so I do not understand a lot of quantum science but from what I hear about quantum computers, it sounds like they are just massively parallel computers.

In quantum computers there are Qubits which are in a superposition state of 0 and 1. Two qubits are in the states 00, 01, 10 and 11 states simultaneously.

Now let us take a look at a NP-complete problem, boolean satisfiability problem. If it is a three variable satisfiability problem, classical computer would have to try every single combination, one after another. (000,001,010...)

But say if my computer has 8 cores I can ask each core to solve for just one of these combinations. So I will get the solution in polynomial time. For a N variable satisfiability problem I need 2^N cores and I will still be able to solve in polynomial time.

My question is, does the quantum computer do just that or is there more to it?

I am learning OpenCL and it utilizes the GPU which has a massively parallel architecture having thousands of cores(kind of). Then can it emulate a quantum computer to a certain extent?

  • 1
    $\begingroup$ Why don't you read about the Shor factoring algorithm and think about how you would implement it on a classical computer? Working this out yourself will, I think, give you a much better feel for the issues than any answer anyone can give you. $\endgroup$
    – WillO
    Oct 21, 2015 at 17:38
  • $\begingroup$ Shor algorithm is in my todo list for a while. I should look it up. $\endgroup$ Oct 21, 2015 at 17:40


Browse other questions tagged or ask your own question.