Quantum Parallelism and Its Benefits in Algorithms

The classical system are those systems which are well- defined, thus the state of an object or particle at any instance of time is perfectly known. However, the quantum mechanical description is contradictory in this regard. In quantum mechanics, the exact state of the object or particle is unknown. This follows the famous Heisenberg uncertainty relation. The quantum state is unknown until it is measured, thus this makes the measured result classical. In quantum mechanics, the object is defined by a wave-function, which is coherent superposition of all possible states occupied by the particle. This can be understood by the idea, if you are observing the door, you know it is open or closed but if say, the door is not in front of you, then in this case there is only a guess. Whether the door is open or closed, the guess can be accurate on the knowledge of door. If the door is often open, then probability of door being open is more but there still probability of door being close. The maximal probability is door being open 50% and close 50% of the time. The quantum object having equal probability of existing in two or more different states at once, is known as quantum superposition, the property is the result of physical phenomena of interference. In quantum computing, this superposition is exploited for computing many problems in parallel. This phenomenon is known as quantum parallelism. Quantum parallelism is allowing for computers that exist in 0s and 1s to exist in superposition of 0 and 1 as, These quantum systems are also known as qubits, qubits. Now, we know that the qubits occupy three combinations i.e., 0,1 and superposition, where the base is still 2, because binary logic is being used. This makes performance of quantum computers faster i.e., the classical computer requires separate runs for each input for computation, while the quantum computer is able to perform exponentially many inputs in a single run. In simple words, the quantum processor can simultaneously pursue classical paths, which makes it more powerful in comparison to classical processors. However, this superposition state is highly sensitive, a minute attempt to measure this state results in collapse of the wave-function. Here, we have to keep in mind that, the quantum parallelism cannot be used if measured but all possible combinations can be explored one by one for all combinations. The experimental difficulties aside, the quantum parallelism found its first practical use in Dutch Joza algorithm, Grover’s algorithm and Shor’s algorithm. Here, we only talk about the use of parallelism is these algorithms, avoiding the rest.

Here, the quantum parallelism results in the exponential speed up as it performs the all-on brute force attack in a single step unlike the classical iteration method, where the brute force is implemented in an iterative loop i.e. step-by-step.

Shor’s algorithm: The implementation of Shor’s algorithm allows the parallel implementation of function,  . This process requires classical computers  steps for each computation of . Whereas, the quantum superposition results in implementation of combinations of modular function in a single step by using the control and target qubit approach to implement unitary operator of the function described above.  Here, due to modular function a periodicity in the states is observed, this periodicity is extracted by applying the quantum Fourier transform on the whole qubit register. Again, here measuring the state would have not given enough information. Further, classical evaluation methods like Chinese remainder theorem are used for estimation of coprime numbers that form the key of RSA

The basic functions of all these algorithms can be reduced in three simple steps,

  1. Apply superposition to all the qubits in one register.
  2. Have another register initialized as needed.
  3. Apply a controlled-unitary operation on the second register with control at the first register of qubits.

Here, controls can be on multiple and different qubit registers, which results in different state of second register for each respective control state. Here, the actual parallelism is applied. Further, different amplification or Fourier transform can be applied as per need. Here, measurement is not the solution


  1. How much resources are required for implementation of Grover’s search and Shor’s algorithm? How quantum parallelism is advantage in comparison to classical in this regard?

Leave a Reply

Your email address will not be published. Required fields are marked *