2
$\begingroup$

What are the differences between Quantum Computing and Parallelism?

thanks in advance

$\endgroup$
  • 1
    $\begingroup$ It would be nice if you could flesh out your question a little, to show what similarities you see between quantum computation and parallelism. (Your post should ideally be at least three times the length of your question title.) $\endgroup$ – Niel de Beaudrap Dec 20 '13 at 17:02
  • $\begingroup$ imho this is an open question that neither physics nor CS can answer adequately/definitively right now, with me for 1 conjecturing a deeper, undiscovered link. but the conventional wisdom is that there is little or only superficial connection. if you dig deeply you can find some authorities eg aaronson referring to "parallelism" but its considered more a conceptual analogy/metaphor than any underlying physical reality. yet there seem to be natural similarities between interference/entanglement and parallelism.... this question also seems tied up with (outside) the copenhagen interpretation... $\endgroup$ – vzn Dec 21 '13 at 20:54
  • $\begingroup$ fyi earlier attempt to link QM/parallelism shot down in flames =( $\endgroup$ – vzn Dec 26 '13 at 21:23
  • $\begingroup$ @vzn: that may be because your answer was not self-contained, nor even particularly constructive (you basically tell them that there exist references without indicating even who wrote them or when, and that it's up to them to find them). And, as my answer indicates, it is not actually convincing that there is a connection between the two. $\endgroup$ – Niel de Beaudrap Jan 1 '14 at 16:47
  • $\begingroup$ the answer immediately prefaced/conceded it as a sketchy idea, but its no defense. guess theres no room for that around here eh? ← rhetorical question. votes spk for themselves. newbies take note/be warned :/ $\endgroup$ – vzn Jan 2 '14 at 2:30
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ there does seem to be an inherent parallelism to aspects of interference & optics, eg the double slit experiment. the light rays run in parallel through two slits and interfere before/after(?) exiting the slits. $\endgroup$ – vzn Dec 21 '13 at 20:51
  • $\begingroup$ @vzn: Indeed: and in a Mach-Zehnder interferometer, this can be made even more stark by making the potential paths of the light literally parallel. But this is not the parallelism of parallel processing. There is little ability for the two "paths" to represent independent computations, unless you are content to abandon any meaningful possibility of destructive interference (and therefore of any quantum-mechanical advantage). Is then the most "parallel" quantum computation a randomized one? This is not what most people intend. $\endgroup$ – Niel de Beaudrap Dec 22 '13 at 8:14
  • $\begingroup$ think optical gates are a simple refutation of the assertion that light cannot be used in parallel computation. see also optical computing. assertions about the inherent nonexistence of parallelism in qm or optics (and which cant be utilized for computation) seem shaky, sketchy, unproven, unsubstantiated, etc. $\endgroup$ – vzn Dec 24 '13 at 0:19
  • $\begingroup$ @vzn: "optics" is related to, but not synonymous with, "quantum". If you have either a clear and quantitative argument for how quantum computing can be described in terms of interacting parallel processes, or have specific counter-arguments to my points above, please provide them to substantiate your own claims. $\endgroup$ – Niel de Beaudrap Jan 1 '14 at 17:52
  • $\begingroup$ niel we can prob both agree a "clear and quantitative argument for how QM can be described in terms of interacting parallel processes" (or for the contrary position) would be a breakthru in the field & is not being pursued by the larger research community at this time... for me it is something like a working hypothesis & work in progress... on the other hand imho aaronsons recent ideas about boson sampling are further circumstantial evidence that there is a link... $\endgroup$ – vzn Jan 2 '14 at 2:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.