Is Quantum Computing really parallel?

This is one of those apparently simple questions that really made my head spin when I first learned about quantum computing. Many articles on the web claim that quantum computers can run high numbers of computations in parallel, solving problems in mere hours that would take even the best classical supercomputers thousands of years to solve. While statements like these are not completely false, there are some important limitations to keep in mind.

In this article, you will learn to which extent quantum computing can be considered parallel, which restrictions apply, and under which circumstances we can use quantum parallelism to speed up computation.

Enjoy!

What is parallel processing?

Any problem that can be divided into independent subproblems has the potential to be solved more quickly using parallel computation.

Let’s assume we want to square a list of 1.000.000 numbers.

Since we are dealing with an old computer, each squaring operation takes approximately 1 second. If we squared the numbers one after another the whole computation would require 1.000.000 seconds to complete. In other words: approximately 278 hours.

Since our individual computations are independent, we can speed up the computation by parallelising individual operations. After all, determining the square of one number does not influence what the square of another number will be.

This way, if we had two processing cores at our disposal instead of one, we could execute two computations in parallel splitting the overall processing time in half. With four cores, the resulting processing time would be 1/4 of our original calculation, and so on. The more cores we have to execute calculations on, the bigger our time gain for the computation as a whole. As long as the individual computations are independent, we can parallelise.

With 100 cores, the full computation would only require 2.8 hours in contrast to the 11.6 days sequential execution would take.

How is Quantum Computing parallel?

In Quantum Computing, Superposition enables us to work not only with distinct 1s and 0s, as in classical computing, but with the probability distribution over these states *. Whenever an operation is applied to a system in a state of superposition, all of its composing states are updated at once.

* Technically speaking, we are dealing not with a probability distribution but rather with a distribution of probability amplitudes. I will cover this distinction in more detail in a future article. For now, let’s ignore it for the sake of simplicity and move on.

In mathematical terms, all quantum computing operations are distributive. An operation applied to a superposition state gets distributed to its component states.

$$ O(|0> + |1>) = O(|0>) + O(|1>) $$

In this regard, quantum computing is parallel. An operation (aka. quantum gate) applied once can affect multiple states “in parallel”.

There is however an important restriction to consider: all operations we wish to perform on a quantum computer have to correspond to unitary matrices. We might be able to manipulate multiple states at once, but how we can manipulate these states is very limited.

The Unitarity Constraint

While my post on the physical basis of the unitarity constraint is still in the making, let’s focus on the implications for now. In a quantum computer, all operations we wish to execute (aside from measurement) must correspond to unitary matrices.

In mathematical terms, a matrix is unitary if its conjugate transpose equals its inverse. To derive the conjugate transpose, take the transpose of a matrix and flip the signs of all of its complex coefficients.

Based on this restriction, we can derive that all operations we wish to perform have to correspond to an invertible matrix (since \(U U^\dagger = U U^{-1} = I\)) and have a determinant of value 1 (\(|det(U)| = 1\)).

Many operations common in classical computing are not invertible.

Even operations as simple as a logical OR or AND are not invertible, since we cannot restore the input from its output for all possible input pairs. If an OR operation returns 1, we do not know whether one, two, or both input bits were in a state of 1 before the computation. Similar behaviour holds for the logical AND operation.

While there are ways to make non-reversible operations reversible through the use of additional qubits, in general, we cannot simply transfer the operations we would execute classically to a quantum computer and expect speedup through parallelization.

All operations we wish to perform without additional cost (mostly in the form of ancillary qubits) have to correspond to unitary matrices. So, even if a problem can be parallelized in theory, to use the parallelism enabled by quantum superposition, we have to find a way to encode our problem in terms of unitary matrices.

Grover’s Algorithm: A Case Study

One algorithm that manages to do just that, is Grover’s Algorithm.

Grover’s Algorithm can find an entry within an unstructured list of N items in \(\sqrt{N}\) steps. In contrast, the best any classical algorithm can do is check the elements one by one, in the worst case requiring a total of N steps. Due to its quantum advantage and applicability, Grover’s Algorithm is among the most popular quantum algorithms and one of the algorithms most likely to find near-term application.

The algorithm first places the computer in a state of equal superposition using Hadamard gates. Then, an oracle function is applied that marks the looked-for component state with a phase value of -1. This is where the speed-up due to the distributive nature of quantum superposition comes in. A single operation affects all of the component states of the superposition at once.

Finally, Grover’s diffusion operator increases the amplitude of the marked state while simultaneously reducing the amplitudes of all other states. This makes it increasingly more likely to receive the target state upon measurement compared to all other possibilities.

While Grover’s algorithm uses quantum superposition to apply a single operation “in parallel”, it requires another operator to retrieve the encoded information. Without the diffusion operator (in my eyes the main contribution of Grover’s algorithm), which happens to correspond to a unitary matrix, the encoded information would be lost upon measurement.

For more details on the algorithm and its inner workings, have a look at my other blog post: How does Grover’s Algorithm work?

Summary

When an operation is applied to a superposition state, it gets distributed to all states comprising the superposition, effectively resulting in parallel computation. Since all quantum operators have to be unitary, the types of computations that can be performed in this manner are quite limited. How to translate the characteristics of a problem or a solution approach into unitary operations is among the main challenges in quantum algorithm design.