Are quantum computer strictly "faster" than any massively parallel computer in terms of computational complexity?

Question

I've seen that quantum computing calculations have their own complexity classes https://en.wikipedia.org/wiki/Quantum_complexity_theory, namely BQP and QMA.

I've heard that this would beat any classical computer, but I wonder if it would also beat a custom-made massively parallel computer. By massively parallel computer I imagine a huge number of little mini-computers each with a tiny memory and all of them arranged in 3-dimensional space. Each mini-computer can communicate with its local neighbors. During one step each mini-computer performs some internal computation and then sends information to its neighbors. I suppose this massively parallel setup allows for faster computation that a classical computer?

How would one define an appropriate complexity class for such a massively parallel setup? I suppose one needs to limit the number of mini-computers used? Is there an existing computation class for that?

Are the quantum complexity classes faster than this massively parallel class (for large problem instances)?

By "faster" I generally mean faster for some problem and a sufficiently large problem size. I know that quantum computers are always probabilistic, so for comparison it's ok if the parallel computers implement a probabilistic method, too. In terms of resources (qubits, mini-computers) their scaling should be comparable (otherwise one method would outperform the other due to limitation of resources).

For the physics-minded people: If the quantum complexity class is faster than the massively parallel class, does that mean that quantum computers cannot be described by a conventional field theory? In a field theory each position in space has some information - essentially my mini-computers. During each time step there are simple local rules (a differential equation) according to which the information at each position evolves. This is the next-neighbor-communication of my mini-computers.

In the end, I'm looking for a rigorous answer to the question: If quantum mechanics were described by some differential equation (a field theory, essentially the massively parallel mini-computers), then quantum computing would be impossible, because quantum computing promises to be faster than any massively parallel classical computer?

Answer 1

Nope. For some problems, quantum computing is far more powerful than parallelization. If quantum computing can be made to work in practice and can scale (which is not yet known yet), then no, a massively parallel computer cannot do everything that a quantum computer can do.

Intuitively, the reason is that for some problems, quantum computing gives us an exponential boost over non-quantum algorithms. You can't make up for that exponential with parallelization, once problem sizes get large: the exponential turns into a really large number.

For instance, consider the problem of factoring large integers. Shor's algorithm allows to factor integers in polynomial time (approximately quadratic time in the size of the integer). The best non-quantum algorithms we know take sub-exponential time (approximately exponential in the cube-root of the size of the integer). The latter grows far faster than the former. So, if the integers are large enough, the gap between these two running times is tremendous and cannot be made up with a parallel computer.

For instance, suppose we want to factor a 100,000 bit number (that is a product of two large primes). Then the best non-quantum algorithms that are known are expected to take more than $2^{361}$ steps of computation (probably a lot more than that, actually). Now if you somehow managed to program every atom in the known universe, so that each atom is its own separate mini-computer, executing $10^9$ steps per second, and you ran this parallel computer (which takes up the entire universe) for the lifetime of the known universe, then that still would not be long enough to factor such a number. So no real classical algorithm could ever hope to factor such a number, no matter how much parallelization you use.

However, if quantum computing can be made to work in practice and if it scales, then in principle, we should be able to factor such a number. It might be difficult, but it is just a matter of engineering -- there is no fundamental limit preventing that.

---

This assumes you are interested in the amount of resources needed to compute something. If you don't care about the amount of resources, and just what can be computed in theory given unlimited resources, then there is no difference between quantum vs classical algorithms. Anything that can be computed by a quantum algorithm can be computed by a classical algorithm -- possibly with an exponential slowdown, or with exponentially more resources (e.g., exponential parallelization). In particular, there are classical algorithms for simulating the evolution of any quantum system. They're just incredibly slow for complex systems. If that is your perspective, you don't even need a parallel computer -- it suffices to use a sequential algorithm and let it run exponentially long.