# What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the difference or how are they different?

• Since no-one better informed has said anything, I shall give my impression, which is that a quantum processor maintains all possible states (for a given problem) simultaneously, while parallel computing is restricted by the number of (non-quantum) processors and/or the space available to store the states. May 15, 2017 at 10:08
• I don't think it's a duplicate, but I think this is definitely a related question: cs.stackexchange.com/questions/2718/…
– mrr
May 15, 2017 at 22:14
• – D.W.
Sep 3, 2020 at 17:13

Disclaimer 1: I am in no way, shape or form an expert on this topic. I am not even an amateur. All my knowledge on quantum computing comes from reading a single book and implementing a puny quantum circuit simulator. So please take everything I say with a table spoon of salt.

Disclaimer 2: Definitions are a tricky thing. Technically, quantum computing allows for a special form of parallel computing called quantum parallelism. In addition to quantum parallelism, the traditional concepts of parallel computing should still be applicable: You should be able to apply two or more arithmetic / logic / quantum operations to subgroups of Your quantum bits (qbits) in parallel.

With that out of the way, in the following I will try to point out two key differences between quantum parallelism and classical parallelism.

Out of my head, I can think of two key differences between classical parallelism and quantum parallelism:

• Classical parallelism requires multiple physical logical/arithmetic/processing units to operate in parallel. Quantum parallelism, on the other hand can be achieved by a single arithmetic/logic/processing unit, and the level of quantum parallelism increases with the number of qbits.
• During quantum computer operation, the qbits can be in an intricate, entangled state, which enables quantum parallelism. But as soon as You query a result (by measuring), the quantum state collapses to a classical bit state with each measured qbit becoming either 0 or 1. This limits the amount of information You can retrieve from a quantum parallel computation.

## Example

Let's say you have a classical computer with four bits of memory. At one point in time, this memory can be in one of 16 states: $$0000_2, 0001_2, 0010_2, \dots, 1111_2$$. We could, somewhat inefficiently, describe the memory state using a 16-dimensional state vector $$s$$ as follows:

• $$0000_2$$: $$s = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]$$
• $$0001_2$$: $$s = [0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]$$
• $$0010_2$$: $$s = [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0]$$
• $$0011_2$$: $$s = [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0]$$
• $$\dots$$
• $$1111_2$$: $$s = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]$$

For our classical computer, this state vector always contains exactly one $$1$$ and fifteen $$0$$ entries. If we, however, turn this classical computer it into a quantum computer, the quantum state $$s$$ can suddenly be any real-valued[1] vector as long as it has norm 1, i.e. $$s \in \mathbb{R}^{16}, \lVert s\rVert_2=1$$. This means our quantum computer can be in multiple classical bit states at the same time, e.g.

$$\hat{s} = [0,\sqrt{1/2},\sqrt{1/2},0,0,0,0,0,0,0,0,0,0,0,0,0]$$

Would be a valid quantum state which equally combines the classical states $$0001_2$$ and $$0010_2$$. Lets now say we want to apply a classical arithmetic operation to our quantum computer: A two-bit integer addition:

$$(\operatorname{bit}_4\operatorname{bit}_3)_2 \leftarrow (\operatorname{bit}_4\operatorname{bit}_3)_2 + (\operatorname{bit}_2\operatorname{bit}_1)_2 \mod 4$$

Where $$\operatorname{bit}_1$$ is the least significant qbit. In our state vector space, we can conveniently describe this operation as matrix multiplication $$A s$$, where $$A$$ is the following permutation matrix:

$$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

If we apply this operation to $$\hat{s}$$, we get:

$$t = A \hat{s} = [0, 0, 0, 0, 0, \sqrt{1/2}, 0, 0, 0, 0, \sqrt{1/2}, 0, 0, 0, 0, 0]$$

This means by applying our operation a single time to our quantum state, we have performed two classical operations. That is quantum parallelism. But there is a problem: We cannot query the result. If we try to measure the qbits of our new quantum state $$t$$, it will collapse into one of two classical states:

• $$t_1 = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]$$
• $$t_2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]$$

For all we know, this collapse happens randomly. In our simple example both $$t_1$$ and $$t_2$$ happen with equal probability of $$50\%$$.

Even though we have computed two additions in (quantum) parallel, we can only randomly retrieve one of the two results. That is the measuring problem. So in order make use of quantum parallelism the final output state should be either a classical state or close to a classical state so that it can be measured by running the computation a constant number of times.

[1] Technically $$s$$ could also be a vector of complex or quaternion values, maybe even octonions, depending on quantum computer.

For a parallel computer, we need to have one billion different processors. In a quantum computer, a single register can perform a billion computations. This is known as quantum parallelism. Also a quantum computer returns a single randomly-selected correct result, while a parallel computer can directly return all valid results. That's the reason why reading results out of quantum computers generally is slow and getting all results requires running the quantum computation enough times to be relatively certain that the random sampling has seen all possible results.

Hope this helps!

See this also: differences-between-quantum-computing-and-parallelism

• "In a quantum computer, all one billion computations will be running on the same hardware" is not exactly how I would put it. Similarly, "a quantum computer simply returns a single randomly-selected correct result" seems like a bad oversimplification. But I do appreciate that these simplifications may help for very unfamiliar people to start to grasp the ideas, I just think they may lead to misconceptions. Sep 4, 2020 at 12:59
• I think that's why i've provided the link. Still i'll edit my answer. Sep 4, 2020 at 17:24

One big difference is that in parallel computation separate processors need not be executing copies the same instruction at the same time in lockstep; they may be more loosely synchronized or in some cases completely desynchronized. In fact, separate processors need not be executing the same sequence of instructions. This is the distinction between SIMD [Single Instruction, Multiple Data] and MIMD [Multiple Instruction, Multiple Data] parallelism. Quantum computers are by nature SIMD (interpreting quantum superposition as equivalent to processor replication).

Phrased another way: With multi-core you can run all the different processes on a laptop simultaneously; you cannot do that with a quantum processor.

• If you are not saying that quantum computing = SIMD parallel (which I would take issue with), this does nothing to answer the question. May 10, 2017 at 19:50