Introducing quantum parallelism and interference
In this section, we will look at quantum parallelism and quantum interference: two mechanisms that are often used in combination in quantum algorithms to reduce the number of computation steps compared to classical ones. Thanks to this, you will be able to understand how to take advantage of quantum computing to design algorithms.
Quantum parallelism
In a classical computer, information is kept in memory registers consisting of bits with values equal to either 0 or 1. Quantum memory registers differ because each of their constituting qubits can be in a superposition of the and basis states, leading the quantum memory register itself to potentially be in a superposition of states. From this ability to represent several states, which can be viewed as inputs to a function into one single state, arises a quantum phenomenon known as quantum parallelism. Applying a function to a state in superposition produces the superposition of...