Quantum Parallelism

Quantum parallelism arises from the ability of a quantum memory register to exist in a superposition of base states. Each component of this superposition may be thought of as a single argument to a function. A function performed once on the register in a superposition of states is performed on each of the components of the superposition. Since the number of possible states is $2^{n}$ where $n$ is the number of qubits in the quantum register, you can perform in one operation on a quantum computer what would take an exponential number of operations on a classical computer. This is fantastic, but the more superposed states that exist in you register, the smaller the probability that you will measure any particular one becomes.

Suppose that you are using a quantum computer to calculate the function $\mathcal{F}(x) = 2*x \bmod 7$, where $x$ is the superposition of integers between 0 and 7 inclusive. You could prepare a quantum register that was in a equally weighted superposition of the states 0-7. Then you could perform the $2*x \bmod 7$ operation once, and the register would contain the equally weighted superposition of 1,2,4,6,1,3,5,0 states, these being the outputs of the function $2*x \bmod 7$ for inputs 0 - 7. When measuring the quantum register you would have a $2/8$ chance of measuring 1, and a $1/8$ chance of measuring any of the other outputs. It would seem that this sort of parallelism is not useful, as the more we benefit from parallelism the less likely we are to measure the value of the calculated function for a particular input. Some clever algorithms have been devised, most notably Peter Shor's factoring algorithm, which succeed in using quantum parallelism on a function where there is interest in some property of all the inputs, not just a particular one.

This kind of parallelism is very appealing for simulation on a parallel computer. A $n$ bit quantum register contains a superposition of each of its $2^{n}$ possible base states, and we represent this by an array of $2^{n}$ complex numbers which are probabilities of measuring the quantum register to be the corresponding base state. To perform an operation on the quantum register, we simply modify each of the $2^n$ array locations. The calculations are independent of one another. By splitting the calculation of how to change the probability value of the array locations into even ranges, and assigning each range to a process elements, we can expect to achieve nearly linear speedup.