INTRODUCTION TO QUANTUM COMPUTING PART 3

Welcome to the third article of our blog on quantum computing, where we will describe in detail how the Quantum Parallelism works with a little review of Qubits concepts from a graphical description.

Well, we are going to talk about how Qubits works by means of the quantum rules. First, the number of states in which the qubit can be quite increased. It´s not just limited by zero and one; but is able to be in a mixture of the two states in any proportion. For example, the higher an arrow points, the more relevant the zero state is in the superposition, and the lower the arrow points the more relevant the one is. The more relevant one of the states of the superposition is, the more probability of measuring it has. This set of states can be visualized with the Bloch sphere.

Source: Qiskit Textbook [https://qiskit.org/textbook/ch-states/introduction.html]

In a qubit the only thing that can be measured is whether it is in the zero state or in the one state. The initial state forces the qubit to align with the vertical axis in this alignment or projection that really see.

Multiple Qubits

When working with individual qubits, it is known that the two possible outcomes at measuring are 1 or 0. Using multiple qubits allows two or more possible results represented by strings or groups of concatenated qubits. Let us consider the example of two qubits in superposition, each one with 50% probability of measuring one and 50% of measuring zero. The following image represents this situation.

The possible outcomes, each one with 25% probability, are represented by the following qubit strings respectively 11, 10, 01 and 00.

What is Quantum Parallelism

It is the quantum computing tool that makes possible to evaluate a function simultaneously on all possible n-bits strings [1] thanks to a consequence of the quantum superposition that allows to keep and process all possible information for a given size or length of a unique string of bits which turn allows to know the result of several operations simultaneously increasing exponentially the calculation speed. Namely it is like a superpower of quantum computing of simultaneously or parallel processing which could allow the evaluations of thousands of combinations at the same time reducing the time processing exponentially.

Deutsch´s algorithm was the first to take advantage of the inherent parallelism of quantum superposition states. According to Qiskit Textbook [2], the Deutsch-Jozsa problem consist of to know if a binary function (That only works with 0s and 1s) is constant or balance where the first means that for any input string of 0s and 1s, the output is always a string of only 0s or only 1s, and the second one means that exactly the half-output are 0s and the other half-output are 1s.

For example, if we have a machine of switches, two lightbulbs as input and we need to know if the machine turn off or turn on all lightbulbs or it will give 50% ON and 50% OFF no matter if any or all are ON or OFF, a classical solution will make the following:

For two lightbulbs which can be ON or OFF (0 or 1) we have combinations.

Classical solution for two lightbulbs

According to the previous figure, a classical computer has to test each combination one by one for getting the result of problem with 100% of certainly which in this case the Switches Machine (function) is constant because all lightbulbs turn off (i.e., the Switches Machine or “function” is constant). Note that if all lightbulbs had turned on the solution would also be constant.

If we need to check a different Switches Machine 2 with six lightbulbs which can be ON or OFF (0 or 1) we have combinations.

Classical solution for six lightbulbs

In the previous example, we had to test each of 64 combinations to see that the Switches Machine 2 turns off all combinations of lightbulbs from 0 to 31 and turn on all combinations of lightbulbs from 32 to 63. It means that the Switches Machine 2 (Function) is balanced because the 50% are OFF and 50% are ON.

Now, the quantum solution for the first example of two lightbulbs and the Switches Machine 1 would as shown in the following figure:

Quantum solution for two lightbulbs

As seen in the previous figure a quantum computer using quantum parallelism just has to execute a unique test with the qubits in quantum superposition and by means of an oracle, we could get that the Switches Machine or function is Constant because the probability of gets all OFF is 100%.

For the second example with six lightbulbs and the Switches Machine 2:

Quantum solution for six lightbulbs

As seen in the previous figure, the quantum solution just had to execute one attempt with the six qubits in quantum superposition for getting that the Switches Machine 2 is Balance because the probability of gets all OFF is 0%.

For the Deutsch-Jozsa problem and others, no matter what the string size of bits is 2 with combinations, 6 bits with combinations, 10 bits with combinations or 128 bits with combinations, a classical computer has to test the half of all possible combinations plus 1 one by one for getting the answer with 100% of certainly (even taking ages in the case of 128 bits) and a quantum computer big enough with just one attempt and one oracle qubit can resolve the problem in a few moments with 100% of certainly (Including the case of 128 bits and others bigger than).

References 

1. • 2022. Quantum parallelism — where quantum computers get their mojo from. [online] Available at: <https://towardsdatascience.com/quantum-parallelism-where-quantum-computers-get-their-mojo-from-66c93bd09855> [Accessed 4 July 2022].

   • org. 2022. Learn Quantum Computation using Qiskit. [online] Available at: <https://qiskit.org/textbook/preface.html> [Accessed 4 July 2022].

About the authors