Superposition

Superposition is one of the properties that differentiates a quantum computer from a classical computer. The qubits of a quantum computer can exist in 0s and 1s and linear combinations of both of these states. A quantum computer can achieve a special kind of superposition that allows for exponentially more logical states at once. This helps in solving problems such as factoring large numbers, which is typically hard for classical computers to solve. Classical computers are limited in terms of their ability to model the number of permutations and combinations that cryptography needs.

An example of the application of quantum computers in cryptography involves RSA encryption. RSA encryption involves two large prime numbers being multiplied to arrive at a larger number. The following examples should bring these challenges to life.

An exponential challenge

The story of the chessboard and rice brings to life the challenges in dealing with the exponential. When the game of chess was presented to a Sultan, he offered the inventor of the game any reward he pleased. The inventor proposed to get a grain of rice for the first square, two grains for the second, and four for the third and so on. With every square, the number of grains of rice would double. The Sultan failed to see what he was dealing with, and agreed to pay the rice grains.

A few days later, the inventor came back and checked with the Sultan. The Sultan's advisors realized that it would take a large quantity of rice to pay off the inventor. The 64th square of the chess board will need 2⁶³ grains of rice, which is 9,223,372,036,854,775,808 grains.

Figure 1: Chess board and rice grains

The five coins puzzle

Linear regression is one of the statistical modeling techniques used to arrive at the value of a dependent variable x from independent variables a and b. A function f(x) represents the relationship between x, a, and b.

Most real-world problems are often not as simple as arriving at the dependent variable from a few independent variables. Often, the independent variables a and b are correlated. Assume a and b interact with each other and their interactions affect the resultant variable x. All possible combinations of interactions of a and b need to be factored into calculating x. Assume, instead of just two variables, that x is dependent on a larger number of variables. The possible interactions between these variables make the problem hard to model for traditional computers.

Let's think about a game involving five coins. The aim of the game is to achieve either the smallest or the largest possible score after tossing them. Each coin has a value, which can be positive or negative, and can be heads or tails, which also translates to be positive or negative. The overall score in the game is calculated by each coin's state (heads or tails), multiplied by the coin's value, and adding the score of each coin together to derive a total.

Table 1: Detailing the five coins puzzle

If we wanted to get the lowest total possible total in this set up, we would need heads (+1) for all coins where the values are negative, and tails (-1) for all coins where the values are positive.

That would give us a total of -16, as shown in Table 2. Using the same logic, if I had to get the highest total, I would need heads for all coins where the values are positive, and tails where the values are negative, for a total of +16.

Table 2: Getting the lowest possible score in the five coins puzzle

Now, let's add one more variable to the mix. Let us call it the correlation variable. The correlation between coin1 and coin2 can be represented by C(1,2). We have to consider the coins as pairs as well as individual coins. We will have far more variables to deal with in this scenario.

For simplicity, if we have to find a total with just the first two coins:

Total = S1W1 + S2W2 + (C(1,2)*S1*S2)

However, if we wanted to identify the lowest total with just the two coins, we will need to trial it with both head and tail states for both the coins to get the minimal value for the total. That would be four states (HH, HT, TH, TT) for two coins. If we added yet another coin to the mix, the number of states would increase to eight states (HHH, HHT, HTH, THH, HTT, TTH, THT, TTT). The number of states to consider would be 2^N , where N will be the number of coins used to calculate the total. As we saw in the Chess example, this will quickly become a problem that is hard for conventional computers to solve. In a quantum computing world, the information of states could be stored more efficiently using superpositions. Qubits can be in both head and tail states at the same time.

A quantum computer addresses a quantum representation such as this and identifies the states of the coins to arrive at the lowest value. The process involves starting the system with the qubits in superposition, and adjusting the states to turn off the superposition effect. As the correlation variable is fed into the system simultaneously, the superposition states will be turned off, and classical states for each of the coins will be chosen (heads or tails).

Addressing the need for exponential computing power is a considerable difference that quantum computing brings to the world of problem solving. In real-world scenarios like simulating cancer cell behavior to radio therapy, modeling stock price actions to market risk factors, or finding the shortest and quickest flight route from source to destination, quantum computing can provide several answers with varying degrees of confidence.

As we discussed in Chapter 14, Interview with Dinesh Nagarajan, Partner, IBM, quantum gates act as operators that help qubits transition from one state to another. A quantum gate, in its basic form, is a 2 x 2 unitary matrix that is reversible, and preserves norms and probability amplitudes. Probability amplitude is a complex number that provides a relationship between the wave function of a quantum system and the results of observations of that system.

In simplistic terms, a qubit in a base state of 0 or 1 can be put into superposition or an excited state when it goes through a gate. An algorithm that uses quantum gates to interact with qubits and provide results is called a quantum algorithm. When a quantum computer is represented in a circuit diagram, the wires represent the flow of electrons through the circuit, and each gate represents a change in the pattern of movement of the electron. Therefore, quantum gates are effectively used to drive the system to produce a result. Unlike a classical computing algorithm, quantum algorithms often provide probabilistic results.

Takeaway: There are real-world problems that are currently unsolved, or are solved through approximations. Once quantum computers become mainstream, some of these complex problems can be addressed more effectively and with greater precision.

Let us now move on to the next quantum concept of entanglement.