# Generally speaking, are quantum speedups always due to parallelization of a given problem?

We know that quantum computers use the wave-like nature of quantum mechanics to perform interference. Sometimes we can use this interference to perform specific algorithms that will cause enough interference to have speedup relative to a classical computer.

But, generally speaking, are quantum speedups always due to parallelization of a given problem?

The converse statement might be more clear: Is there an example of quantum speedup for an algorithm in which the classical equivalent is not parallelizable?

EDIT: To try to make this even more clear, imagine that I have a classical problem that I will apply some specific classical code to solve (such as searching for a certain element in a list by looping through each element and checking if it matches the described element).

Practically speaking: If I were to optimize this code with a GPU, I would identify what parts of my code can be parallelized. (and I probably wouldn't be thinking of things like P=NP). For GPUs, I don't think I need to solve some general proof about P=NP or NP = CP in order to get an intuitive sense that GPUs speed up code when things can be parallelized.

Are quantum computers the same? Generally speaking (in the same way I am thinking about GPU speedup), are speedups always do to parallelization?

• What do you mean by "classical equivalent not parallelizable"?! If you mean "the problem cannot be solved rapidly by testing an exponential number of possibilities in parallel", then this amounts to asking whether there are problems in BQP which are not in NP, which is believed to be true, but proving it (e.g. through an example) would be a super-duper-major result not only in quantum complexity, but also with regard to classical complexity (as it would, e.g., separate NP and PP). Mar 2, 2021 at 21:43
• @user1271772, I edited the question to respond more clearly to Norbert, not to you. I think you understood the essence of my question and answered it appropriately. Mar 2, 2021 at 23:50
• @StevenSagona As far as I am concerned, your edit made the whole thing not any more clear. The reason for quantum speedup cannot be pinpointed to simple "parallelism" or "not parallelism". This way of relating quantum and classical is simply to simplistic. Moreover, the type of parallelization you think of will not help classically: You can't just double the number of GPUs for every new qubit indefinitely. If $N$ qubits can be simulated on $2^N$ GPUs, already for $100$ qubits, those GPUs will exceed the weight of the earth by far. Mar 2, 2021 at 23:58
• smbc-comics.com/comic/the-talk-3
– glS
Mar 3, 2021 at 2:03
• There are issues in that question - to answer "yes", I would have to prove a speed up. Such proofs don't exist except with respect to certain oracles. All the oracle cases that I know fit your "parallelisable" condition. To answer "no" I would have to prove that there exists no BQP-complete problem that satisfies your "parallelisable" condition. Both are horrifically scary issues. Mar 3, 2021 at 8:37

## 2 Answers

I can see what you mean. For the Deutsch problem, we can formulate it (or think of it) in such a way that the goal is to evaluate $$f(0)+f(1)$$ in base 2. Classically we have to evaluate $$f(0)$$ and $$f(1)$$ to get this sum, so we need to do two evaluations of the function to get the answer. A quantum computer only needs to input the superposition state $$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$$ once and it gets enough information about what the black box function does to $$|0\rangle$$ and to $$|1\rangle$$ individually, in order to be able to evaluate the sum modulo two successfully.

But a classical computer can parallelize the evaluation of $$f(0)$$ and $$f(1)$$.

Are there quantum algorithms that provide a speed-up without this type of parallel evaluation of a function for all possible binary-string inputs?

Well there's an entirely different type of quantum computing called "adiabatic quantum computing" or AQC which does not involve gates or circuits. There's a mathematical proof that it is equivalent to circuit-based quantum computing in terms of computational power, from the perspective that AQC devices can simulate all circuit-based quantum computing algorithms with an overhead which is only polynomial scaling with respect to the size of the problem.

In AQC, you are solving a problem by efficiently finding the ground state of a Hamiltonian which is $$2^n \times 2^n$$ in size if there's $$n$$ qubits. In the case where the Hamiltonian is diagonal in the computational basis, this problem can be parallelized by just checking each possible state in the computational basis, in parallel. However when the Hamiltonian is not diagonal, the only way to solve the problem (in general) on a classical computer is to find the eigenstate with the smallest eigenvalue, which means solving an eigenvalue problem. The solving of an eigenvalue problem can be parallelized but not in the way that I think your question is considering. It is not the type of parallelization where we are checking $$2^n$$ things at the same time, and the speed-up due to parallelization is nowhere near the quantum speed-up. Then since circuit-based quantum computers can also simulate adiabatic quantum computers with overhead that only scales polynomially with respect to the input size, we can argue that circuit-based quantum computers can also solve problems that can't be parallelized (in the sense discussed earlier) on a classical computer: in fact we've had circuit-based algorithms for Hamiltonian simulation since before we knew about the proof that AQC and CBQC were equivalent from a computational complexity perspective.

Essentially, if you want to find the ground state of a molecule's Hamiltonian, or the ground state of some model condensed matter Hamiltonian (for example) like a Hubbard Hamiltonian, quantum computers (or quantum "simulators") can do the job more efficiently (from a computational complexity perspective) compared to classical computers, and while classical computers can attempt to solve the problem in parallel, that parallelization is only whatever small amount of parallelization is possible when solving eigenvalue problems.

I don't know if there's any classical computation worth doing on a quantum computer that cannot at all benefit from parallelization because even the multiplication of two scalar numbers like 13.254621 and 17.169920 is parallelized at some level (for example multiple logic gates in hardware are working in parallel), but if we can interpret your question as parallelization in the Deutsch problem sense, then I would say that the answer is yes.

• Thanks. Yeah the motivation is basically that GPUs, and simply connecting computers together through the internet give a massive potential parallel processing power, which grows much much faster than More's law. So I'm a bit skeptical/worried that any significant speedup will always get washed out by more practical GPUs over time, which appear to boost the same types of problems that quantum computers can solve. Mar 2, 2021 at 23:47
• @StevenSagona I recommend trying to simulate the google supremacy experiment on GPUs. Mar 2, 2021 at 23:57

I am going to answer your question as you phrased it in the comments:

"I am asking if you can give me an example of classical code (that is not parallelizable) that can be sped up by a quantum computer"

where, as I understand you, "not parallelizable" means that we have no idea how to parallelize it.

• Specifically, it is known that quantum computers can approximate the so-called Jones polynomial at specific points. It is not known how this problem can be parallelized in a useful way.

• Another example is the simulation of the time evolution of general quantum systems. It is not known how to parallelize this.

Now I apologize for that, since I know that you don't like this theoretical approach, but I think if one can make a more general or stronger statement at no extra cost, one should make it:

Any problem which is proven to be BQP-complete (like the above) will do: For none of these problems, we know of efficient ways to parallelize them. If there would be such ways, this would mean that the problem is in NP (in essence, you can think of NP as the class of problems which can be massively parallelized, by "searching all solutions at once"), and - as I mentioned in the comments - this would not only be a most major result, but there is also significant evidence that it does, in fact, not hold.

• "Another example is the simulation of the time evolution of general quantum systems. It is not known how to parallelize this." Time evolution amounts to matrix exponential, which can be parallelized, for example by doing each term of the Taylor series on a different CPU. Versions of MATLAB's expm are optimized to run on GPUs. It's not going to be 2^n speed-up, but there's parallelization. My answer gives the same example but for energies rather than dynamics. Mar 3, 2021 at 14:12
• @user1271772 Very likely any problem can be parallelized to some extent - I'd say it will even depend on the details of how you formulate it to which extent such a paralelliziation is possible. Moreover, note that what is given in the Hamiltonian as a sum of local terms, it is rather unclear to me whether the best classical simulation method consists in building the exponentially big Hamiltonian matrix, rather than e.g. Trotterization. Mar 3, 2021 at 16:08
• That's exactly what my answer says in its last paragraph. As for the rest, you made the same error almost 3 years ago when you confused "Trotterization" with "Taylor series". A Taylor series of $e^A$ is $I + A + \frac{A^2}{2} + \cdots$, whereas a Trotterization of $e^{A+B}$ is $(e^{A/N}e^{B/N})^N$. Bottom line: $e^A$ can be parallelized, whether calculating each term of the Taylor series on a different CPU or GPU, or by Trotterizing, or by one of the various ways to do exp(A), but this parallelism is different from the parallelism in the Deustch problem. Mar 3, 2021 at 16:45
• When I write trotterization, I mean trotterization. I think I know the difference. I'm impressed, though, that you remember what I wrote three years ago. Mar 3, 2021 at 17:02
• Why on earth would you diagonalize? Mar 3, 2021 at 18:27