How to Make Orthogonal Positions Parallel: Revisiting the Quantum Parallelism Thesis

How to explain why quantum computers are faster than classical computers? In the literature, one can find, arguably, two polar opposite positions espoused. One is that the source of quantum speedup is due to the fact that quantum computers could compute many values of a function in a single step. The alternative is that quantum computers don’t do this at all, and in fact perform the requisite computational task by doing fewer computations than classical computers performing the same task. In this paper, I utilize the mechanistic view of computers to shed light on the debate. I argue that the mechanistic view helps us understand that the polar opposite positions described above can be seen as consequences of conflicting intuitions about the appropriate computational description of quantum systems that perform computational tasks, and not a disagreement about the fundamental feature of quantum systems that allows for quantum speedup. The mechanistic view provides us with a principled means of understanding the usefulness and limits of computational descriptions of phenomena, and also helps us understand the essential differences between classical and quantum computers.