Is the intuition of quantum parallelism always correct?

I recently read in Section 7.5.2 of Quantum Computing: A Gentle Introduction by Eleanor Rieffel and Wolfgang Polak a section in which they criticize the view of quantum parallelism in quantum algorithms. Specifically they address the Bernstein-Vazirani problem from the point of view of N.D. Mermin in Copenhagen Computation: How I Learned to Stop Worrying and Love Bohr. I am still learning this topic so please correct me if I make mistakes below...

Background: The Bernstein-Vazirani subroutine has an oracle function $$U_{f_a}$$ which takes input $$\left| x_n \right>\left|y\right> \rightarrow \left| x_n \right>\left|y\oplus x \cdot u \right>$$, where $$\cdot$$ implies the Hamming distance of $$x \land y$$ modulo $$2$$ (or as Mermin argued the inner product of $$x$$ and $$y$$ modulo $$2$$).

Now in the initial explanation the authors present the solution "in terms of quantum parallelism"; they apply the Walsh-Hadamard and Hadamard gate to the $$\left| x_n \right>\left|y\right>=\left| 0_n \right>\left| 1 \right>$$ respectively $$H_n \otimes H$$ and input the, now in superposition, $$n$$-qubit and $$1$$-qubit registers into the $$U_{f_a}$$ subroutine. After applying this oracle function the states are put through $$H_n \otimes H$$ again returning $$\left| a \right>$$ and the initial $$\left| 1 \right>$$ respectively. All good so far...

$$\\$$

Question: Now what I find intuitive is that the $$H_n$$ gate puts the register of $$1$$s in the state:

$$\displaystyle W\left| 1_n \right> = \frac{1}{\sqrt{2^n}}\sum_z(-1)^{1 \cdot z}\left| z \right>,$$

and that the oracle function phase shifts all $$n$$ qubits with $$e^{2\pi i}=1$$ if a qubit is not shared between the input and $$a$$ (the inner product of the compared qubits $$=0$$), and with $$e^{\pi i}=-1$$ if it is shared (inner product $$=1$$).

Due to the Walsh-Hadamard transformation on the register of $$\left| 1_n \right>$$, all $$n$$-qubit states possible are being compared from which I infer that the term quantum parallelism comes $$-$$ Comparable to the solution for the Deutsch problem in which through superpositions the entire function domain can be explored in one function call. By cleverly re-applying the Walsh-Hadamard transformation the non-trivial phase shift information can be extracted in the form of $$\left| a \right>$$.

$$\\$$

And what I understand but don't know how to feel about: is that the authors argue that the function $$U_{f_a}$$ is actually a series of $$C_{not}$$ gates that act upon the ancilla qubit if $$a$$ is $$1$$. Due to the Walsh-Hadamard and Hadamard transformations before and after $$U_{f_a}$$ the $$C_{not}$$ gates are inverted in the subroutine, thus, flipping the qubits in the $$\left| x_n \right>$$ register where $$a$$ is $$1$$.

The reason I do not know how to feel about this interpretation is that the authors emphasize that the $$C_{not}$$ flip interpretation is the right way of looking at this algorithm.

First of, it implies that the oracle function $$U_{f_a}$$ must be fixed or somehow able to be adaptively computed. But more importantly, this interpretation somewhat rids itself of the interpretation of linear combinations of the states $$-$$ i.e., apparently the "right way" of looking at this algorithm is that Hadamard gates flip a $$C_{not}$$ and not that the initial states are put into a linear combination of the standard bases through which an exponentially increasing domain of a function can be sampled and cleverly interfered yielding the final solution.

Thus, my question is:

TLDR; How should you view a quantum algorithm as utilizing quantum parallelism, and what is defined to be the "right way" of interpreting quantum parallelism in such algorithms.

• – glS
Nov 1 '19 at 17:14

Intuition is just that - intuition. It's is not an absolute of "this is how it works", but rather something that helps you get some sort of intuition about what's happening. In that sense, there is no "right" or "wrong". It's what helps you. Different people understand things in different ways. You just have to be clear that every intuitive explanation has its limitations - they're rarely a complete description - and there's no substitute for actually doing the maths.

So, the quantum parallelism intuition is particularly useful because it is easily described even to a layman (which is what you want from intuition), which is why it has been over-played in the media. Its limitation is that it fails to explain why some algorithms get a speed-up and others don't - because it's not just about parallelism, but how you make the comparison at the end of the computation.

So, this isn't a question with a single "correct" physical answer. In general, though I would say that the parallel nature of quantum algorithms is dramatically overplayed, especially in older literature and a lot of the popular science press. Remember that whatever parallelism is happening as your quantum state evolves, once you measure you're going to collapse all of that. Put another way, even if many worlds are involved in calculating your answer, in the end you're only going to have access to one of them. The trick to designing quantum algorithms is to find some feature of the problem that you can leverage to drive up the probability that the world you end up in is one with the right answer. The upshot of this is that you can take or leave parallelism as a matter of philosophical taste, or according to how useful it is to you grokking/designing a particular algorithm.

With that in mind I think it's fair to say that there are two main schools of thought about the role of parallelism in quantum computing. I'll call them "Deutsch" and "Aaronson." The "Deutsch" way of thinking goes heavy on the implications of parallelism and has connections to the many-worlds picture of quantum mechanics. Faced with the power of something like Shor's Algorithm, a Deutsch would ask "where" the numbers are factored, if not in many interfering worlds.

An Aaronson, on the other hand, might take a more instrumental approach. In other words, if it works, go with it, but don't try to shoehorn the whole field into your favorite way of thinking. Quantum algorithms that show speed-up over their known classical counterparts tend to rely on a sort of synergy between the specifics of the problem and the idiosyncrasies of quantum. There's a sort of Rube-Goldberg flavor to the whole endeavor, where things work thanks to careful alignment of pieces and parts and a good bit of luck, rather than because they rely on a single conceptual resource like parallelism. Many algorithms don't necessarily fit best into the parallelism way of thinking. Analog quantum simulators, for instance, or some of the algorithms being considered for benchmarking quantum supremacy like random circuit selection. In these cases you might be better off thinking about the benefits of running quantum software on its "native" hardware, or the classically confounding effects of entanglement respectively.

Finally, as far the the connection to many-worlds is concerned, as Scott Aaronson (in case it wasn't clear, the inspiration for this school of thought) noted in his excellent book "Quantum Computing Since Democritus", one thing that everyone can agree on is that interference between amplitudes is a key computational resource for a quantum computer. If you want to imagine that that is happening in parallel worlds, then those worlds are interacting with each other, and don't really seem very separate.

I hope this helps.