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

<p>In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. If the <em>vast majority</em> 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 &mdash; 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 <em>interact</em>: a partial answer in one cannot be communicated to another, and as with the purely randomized computation, we cannot choose which one we <em>observe</em> &mdash; 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.</p>

<p>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, <em>e.g.</em>&nbsp;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.</p>

<p>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 <em>impose</em> 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 <em>differences</em> between these quantum-superpositions-of-performing-a-bit-flip-or-not?</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-21T20:51:54.123Z
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.
vzn
CC BY-SA 3.0
2013-12-22T08:14:08.187Z
@vzn: Indeed: and in a [Mach-Zehnder interferometer](http://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_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.
Niel de Beaudrap
CC BY-SA 3.0
2013-12-24T00:19:26.800Z
think optical gates are a simple refutation of the assertion that light cannot be used in parallel computation. see also [optical computing](http://en.wikipedia.org/wiki/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.
vzn
CC BY-SA 3.0
2014-01-01T17:52:13.567Z
@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.
Niel de Beaudrap
CC BY-SA 3.0
2014-01-02T02:18:42.343Z
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...
vzn
CC BY-SA 3.0
2014-01-05T20:34:17.493Z
@vzn: The main reason why there is not much research being put into the question is that the consensus is largely that there is no strong link between the two, for reasons much as I describe above. Perhaps you could indicate how you think Aaronson+Archipov's recent work is suggestive of parallelism? This aside, what "working hypothesis" do you have about the connection between quantum computation and parallelism? If it's just "there's some sort of link", I wouldn't get too excited about calling it a 'working' hypothesis (what work is it doing?).
Niel de Beaudrap
CC BY-SA 3.0
2014-01-05T21:02:46.317Z
"consensus" ≠ proof. imho nothing definitive seems to have been written on the subj incl by either of us :|
vzn
CC BY-SA 3.0
2014-01-06T23:47:28.363Z
@vzn: I'm not sure why you would think I might be mistaking consensus for proof. I am not saying the subject is utterly closed: I'm explaining the reason why there's no research, and indicating that the prognosis for a substantial link is poor.
Niel de Beaudrap
CC BY-SA 3.0
2014-01-07T02:18:34.317Z
didnt say that. see also [absence of evidence ≠ evidence of absence](http://en.wikipedia.org/wiki/Evidence_of_absence). your expert diagnosis of a "poor prognosis" is somewhat amusing. this now reminds me of controversy over the copenhagen interpretation of physics which was challenged by einstein as nonlocal and/or incomplete, and further clarified by bell mathematically. currently there exists no such "bell-like-mathematical test" for parallelism in QM. for now, compare +9 on your anti- vs -5 on my pro- connection position. agreed there is a consensus against the pro-parallelism connection.
vzn
CC BY-SA 3.0
2014-01-07T04:53:16.063Z
@vzn: well, we're here to provide the best answers that we can, the ones which represent the state of our knowledge, aren't we? I have at least attempted to provide an answer of substance, indicating *why* people think the way they currently do. If you did the same, your answers on such subjects would get more positive votes. Compare yourself to Einstein if you will, but his objections were much better substantiated than yours. Until you begin to consistently back up such assertions with good arguments, your answers on these topics are likely to continue to attract negative votes.
Niel de Beaudrap
CC BY-SA 3.0
2013-12-20T17:01:16.173Z
2013-12-20T17:41:33.747Z
2013-12-20T17:41:33.747Z
Niel de Beaudrap
<p>What are the differences between Quantum Computing and Parallelism?</p>

<p>thanks in advance</p>

CC BY-SA 3.0
2013-12-20T17:02:43.303Z
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.)
Niel de Beaudrap
CC BY-SA 3.0
2013-12-21T20:54:04.777Z
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...
vzn
CC BY-SA 3.0
2013-12-26T21:23:11.097Z
fyi [earlier attempt to link QM/parallelism](http://cstheory.stackexchange.com/a/12157/7884) shot down in flames =(
vzn
CC BY-SA 3.0
2014-01-01T16:47:29.853Z
@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.
Niel de Beaudrap
CC BY-SA 3.0
2014-01-02T02:30:00.063Z
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 :/
vzn
CC BY-SA 3.0
2014-01-02T17:35:45.897Z
coincidentally, heres a recent twist by fortnow, [analogs between qm computing and parallelism](http://blog.computationalcomplexity.org/2013/12/analogs-between-quantum-computng-and.html). not so much merely on their technical/theoretical similarity but as a comparison of the larger ideas/concepts as TCS research programs in a broad historical context (spanning decades).
vzn
CC BY-SA 3.0
2014-01-05T20:42:00.270Z
@vzn: "the answer immediately prefaced/conceded it as a sketchy idea" More to the point, your answer wasn't a sketch: it didn't even hint how to find your claimed references. It simply was not a useful answer. As for your link on analogs between quantum computing and parallelism, the comparison is between *how the fields developed*, that is the *histories* of the fields, not between the subject matter of the two fields. So I do not see how your comment is relevant.
Niel de Beaudrap
<quantum-computing><dc.parallel-comp>
Differences between Quantum Computing and Parallelism
user17629
# Differences between Quantum Computing and Parallelism

(Asked by: username_0 on 2013-12-20)

What are the differences between Quantum Computing and Parallelism?

thanks in advance

**Tags:** quantum-computing, dc.parallel-comp

> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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...  
> **username_2**: fyi [earlier attempt to link QM/parallelism](http://cstheory.stackexchange.com/a/12157/7884) shot down in flames =(  
> **username_1**: @username_2: 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.  
> **username_2**: 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 :/  
> **username_2**: coincidentally, heres a recent twist by fortnow, [analogs between qm computing and parallelism](http://blog.computationalcomplexity.org/2013/12/analogs-between-quantum-computng-and.html). not so much merely on their technical/theoretical similarity but as a comparison of the larger ideas/concepts as TCS research programs in a broad historical context (spanning decades).  
> **username_1**: @username_2: "the answer immediately prefaced/conceded it as a sketchy idea" More to the point, your answer wasn't a sketch: it didn't even hint how to find your claimed references. It simply was not a useful answer. As for your link on analogs between quantum computing and parallelism, the comparison is between *how the fields developed*, that is the *histories* of the fields, not between the subject matter of the two fields. So I do not see how your comment is relevant.  

---

## 1 answers

### Answer by username_1 on 2013-12-20. Score: 12

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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @username_2: Indeed: and in a [Mach-Zehnder interferometer](http://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_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.  
> **username_2**: think optical gates are a simple refutation of the assertion that light cannot be used in parallel computation. see also [optical computing](http://en.wikipedia.org/wiki/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.  
> **username_1**: @username_2: "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.  
> **username_2**: 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...  
> **username_1**: @username_2: The main reason why there is not much research being put into the question is that the consensus is largely that there is no strong link between the two, for reasons much as I describe above. Perhaps you could indicate how you think Aaronson+Archipov's recent work is suggestive of parallelism? This aside, what "working hypothesis" do you have about the connection between quantum computation and parallelism? If it's just "there's some sort of link", I wouldn't get too excited about calling it a 'working' hypothesis (what work is it doing?).  
> **username_2**: "consensus" ≠ proof. imho nothing definitive seems to have been written on the subj incl by either of us :|  
> **username_1**: @username_2: I'm not sure why you would think I might be mistaking consensus for proof. I am not saying the subject is utterly closed: I'm explaining the reason why there's no research, and indicating that the prognosis for a substantial link is poor.  
> **username_2**: didnt say that. see also [absence of evidence ≠ evidence of absence](http://en.wikipedia.org/wiki/Evidence_of_absence). your expert diagnosis of a "poor prognosis" is somewhat amusing. this now reminds me of controversy over the copenhagen interpretation of physics which was challenged by einstein as nonlocal and/or incomplete, and further clarified by bell mathematically. currently there exists no such "bell-like-mathematical test" for parallelism in QM. for now, compare +9 on your anti- vs -5 on my pro- connection position. agreed there is a consensus against the pro-parallelism connection.  
> **username_1**: @username_2: well, we're here to provide the best answers that we can, the ones which represent the state of our knowledge, aren't we? I have at least attempted to provide an answer of substance, indicating *why* people think the way they currently do. If you did the same, your answers on such subjects would get more positive votes. Compare yourself to Einstein if you will, but his objections were much better substantiated than yours. Until you begin to consistently back up such assertions with good arguments, your answers on these topics are likely to continue to attract negative votes.  

---

