Quantum Parallelism

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 2^N, which in this case is 2¹⁰, 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.

What is Quantum Parallelism?

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 2¹⁰⁰⁰ 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.

Applications of Quantum Parallelism

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:

• Speed. Problems that grow in complexity exponentially may be solvable with exponentially greater efficiency, resulting in exponential speedups in computation time.
• Scale. Problems that grow in memory requirements, such as simulating molecules in quantum chemistry, beyond the capacities of supercomputers, can be solved with relatively small quantum computers.
• Randomness. Problems that require humanlike decision making – such as generating art, language, and music – are already being prototyped.  
• Search. Problems with massive search spaces can have all possible solutions found at the same time and with mathematically-proven optimality.
• Security. Cryptographic schemes that rely on the multiplication of prime numbers will become vulnerable to decryption.

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.

The Challenges of Quantum Parallelism

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:

• Control. Achieving quantum computational advantages is going to require large numbers of qubits, and yet controlling relatively small numbers of qubits is currently difficult.
• Timing. Realizing accurate results will require the precise timing of quantum operations, to a degree of precision beyond the capabilities of traditional clocks.
• Coherence. Realizing accurate results will require qubits that maintain their quantum states without errors for much longer durations than is currently possible.
• Efficiency. Quantum algorithms, such as amplitude encoding, need to become classically feasible to implement, due to their complexity and memory requirements.

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.

‍