Differences between Quantum Computing and Parallelism

Question

What are the differences between Quantum Computing and Parallelism?

thanks in advance

Answer 1

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number generation) and parallelism.

In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. If the vast majority of those paths give quickly rise to a particular answer, then that is the answer. In quantum computation, one is tempted to consider these different computational possibilities as being more "real" than in randomized computation, for the reason that we can cause them to cancel each other out — which seems a little as though the different computational possibilities are distinct processes which communicate with one another to collaboratively give an answer. However, while these different computational paths do interfere, they do not interact: a partial answer in one cannot be communicated to another, and as with the purely randomized computation, we cannot choose which one we observe — that is chosen at random from among the possibilities whose amplitudes haven't been cancelled out. In the end, the result is (as with randomized computation) taken as a sort of uncontrolled democratic vote between different so-called "computational branches", with only a small chance of an upset due to getting the answer from a small minority of computations which cast the objecting vote.

By contrast, in a truly parallel computation, each parallel process is obviously and independently present for querying and inspection. The decomposition of the computation as being performed by a collection of communicating agents, or 'processes', is a much more meaningful description. Whether a particular part of the computation 'belongs' to a particular process is something which we might impose by fiat, e.g. if we design a piece of hardware or software which is given responsibility (by us) for performing that computation, but at least there we may consider the activity of an individual agent and in principle design a protocol so that it determines the final output of the computation. This is simply not what happens in the mathematical model of quantum computation.

In the end, one must remember that the (very rough) intuition that quantum computing involves any parallelism at all, is just part of a struggle to obtain robust insights into how quantum computation differs from classical computation. From a point of view of interpretations of quantum mechanics, it corresponds to the Many Worlds Interpretation: but it is dubious to say that any 'world' which is to be cancelled out by destructive interference 'exists' independently, as such. Especially in the case where we may have a large amount of destructive interference and tight control over something like time-reversible operations, the choice of how we decompose the state of the computation into multiple "classical looking" branches is likely to be a description that we impose on the system to understand it, not one that necessarily refers to the physics or the nature of the computation in itself. This is especially true if you consider the various transformations that we can apply on a single qubit: sure, we can describe them as variations on performing a bit-flip or not performing a bit-flip, but what is the meaning of the differences between these quantum-superpositions-of-performing-a-bit-flip-or-not?

Thus, the difference between quantum computation and parallelized computation is that the so-called 'parallel' processes in quantum computation are much more like the imaginary parallel processes of a randomized computation: they cannot be addressed directly, but only in statistical bulk.