In computer science, parallelism refers to the execution of multiple tasks at the same time. This definition changes somewhat when applied to quantum computing, because only one task is being completed at a time. However, a problem with multiple solutions can have all of its solutions found at the same time. This distinction is explored in our article titled "Real-world Applications of Quantum Simulation.”
One of the principles of quantum mechanics, the one which makes this possible, is quantum entanglement. In quantum computing, the entanglement of each additional qubit exponentially grows the state space. The application of even one single-qubit operation on any of those entangled qubits can affect the entire state space in a kind of massive quantum parallelism. As an example, an operation on a 10-qubit system can affect up to 2N, which in this case is 210, which is 1,024 amplitudes simultaneously. The classical equivalent would require 1,024 processors, or cores, each updating one value in parallel.
For an example of this computational power, the Medium article “Quantum Parallelism” by Madali Nabil briefly describes Grover’s Search Algorithm. Although the author overestimates the algorithm’s speedup over classical approaches, the algorithm has nonetheless been proven to be optimal at what it does. Then, for an example of an even more powerful quantum algorithm, our “HHL” page describes the HHL Algorithm, which leverages quantum parallelism to solve linear systems of equations exponentially faster than classical approaches. And, for further reading beyond these examples, the ScienceDirect “Quantum Parallelism” page has some excerpts that might be helpful in selecting a book.
Computer scientists sometimes put forth a second definition of quantum parallelism. In the absence of quantum entanglement, operations can still be performed on all qubits at the same time. Using the same 10 qubits as before allows 10 simultaneous operations with each time step. However, this is more analogous to a supercomputer with many, many processors than it is to the massive quantum parallelism previously described. Nonetheless, in principle, a quantum computer with a thousand qubits could act like a classical computer with a thousand processors. That’s a far cry from 21000 processors, but it still gets mentioned from time to time.
It is worth noting that although there are no quantum advantages to it, parallel quantum computing is currently being researched. The notion is to divide problems wherever entanglement is weak, execute operations on multiple quantum processors, and then classically merge the results. However, this is meant to be a solution to having quantum computers that are too small to solve real-world problems. Execution of the same algorithm on a single, large, fault-tolerant quantum computer, if it were possible, would be both simpler and faster.
Quantum computers are remarkably inefficient at solving simple problems. However, they can be remarkably efficient at solving classically intractable problems – problems that cannot be solved efficiently with classical computers. This means that the applications of quantum computing are going to be limited to extremely challenging problems. Examples of such challenging-to-intractable problems include:
A good rule of thumb is that most applications that are possible today will continue to be solved classically in the future. The applications that are not possible today, or otherwise require tremendous time and classical resources, are the applications fueling investments into quantum computing.
Although quantum computation has the potential to disrupt entire industries, the path to achieving such breakthroughs is not a simple one. Just a few of the challenges that must be addressed along the way include:
Solutions to all of these problems are currently being researched. And while the road to fault-tolerant quantum computing is a long one, steps toward this goal are happening every day.