Entanglement – spooky action at a distance

The quantum property of entanglement was referred to by Einstein as Spooky action at a distance. Two particles in a system are entangled if one particle in a system cannot be described without taking the other part into consideration. In a quantum computer, qubits demonstrate this property. So, the probability of observing the configuration of one qubit will depend on the probability of observing the configuration of its entangled other half. This property of qubits exists in a quantum system, even when the entangled pair are separated by a good distance. This means, if one qubit spins in a clockwise direction, its entangled pair could spin in a counter-clockwise direction, even when miles apart.

Recently, scientists in China have demonstrated entanglement at a distance of up to 1,200 kilometres. Source: https://phys.org/news/2018-01-real-world-intercontinental-quantum-enabled-micius.html

This experiment was conducted between a satellite and earth, where entangled particles were used to communicate instantaneously. The challenge in making entanglement happen over long distances is that the particles often get lost when transmitted through fiber optic networks. However, scientists have recently used laser beams on the world's first quantum-enabled satellite called Micius, to communicate using entangled photons across three different earth stations in China. Previous attempts at quantum communication were limited to a few hundred kilometres; this was primarily due to data channel losses that occurred in optical fibers.

Apart from long distance communication, quantum teleportation (which is based on entanglement) is an important concept in cryptography. Quantum teleportation is the process of transmitting information between two entangled qubits that could be separated by a long distance. In contrast to traditional means of secure data transmission, this method relies on entanglement of qubits and not on complex encryption functions. Quantum teleportation could be significant as it could soon be the foundational element of a secure internet or any communication network. In the next section, we discuss a Bloch sphere, which helps visualize the states of qubits.

Bloch sphere

A Bloch sphere, named after Felix Bloch, is a three dimensional, geometric representation of a qubit's states as points on the surface of the sphere. It also helps us understand how a qubit's state changes when put through a gate (operations). As it represents one qubit, it is not meant to demonstrate the entanglement property, where interactions between multiple qubits need to be considered. This section is mathematical by necessity, but it will be the only section in the book that uses math to this extent.

The poles of the Bloch sphere represent the classical states of a bit: and .

Figure 2: A Bloch sphere

The state of the qubit, , diagrammatically represented by a Bloch sphere, can be given as:

Equation 1: Quantum computing for computer scientists, N. Yanofsky and M. Mannucci, Cambridge Press, 2008.

In this representation, corresponds to the latitude and corresponds to the longitude of the qubit. Any point in the Bloch sphere can be represented by the range of values that and can take, given by and .

This means that:

• When , and that represents the state of the classical bit.
• When , and that represents another state of the classical bit. This is because φ represents the longitude, and it is meaningless at the pole.

If took other values between 0 and , this would lead to a superposition state of the qubit. So, while the poles of the Bloch sphere derived from the equation represent the states of a classical bit, the state of a qubit can be given by any point in the sphere.

How does the Bloch sphere represent the possible changes in states of a qubit, especially when they are observed? Continuing from the discussion in Chapter 14, Interview with Dinesh Nagarajan, Partner, IBM, we know that the state of the qubit collapses to the classical states under observation. The angle represents the probability with which the state of the qubit will collapse to either of the two states. If the arrow that represents the Bloch sphere is closer to the North Pole of the sphere, the state collapses to and vice versa. In the next section, we look at one of the most impactful algorithms in the history of quantum computing.

Shor's algorithm

Peter Shor and his work have perhaps had the most impact on the evolution of quantum computing. In 1994, he proposed a polynomial time quantum algorithm for identifying prime factors. Richard Feynman [1982, 1986] had already proposed the idea of quantum computing to be more powerful than classical computers. However, Shor was the first to bring to light a practical application of quantum computers. Using his algorithm that demonstrates identification of prime factors of a large number, he inspired a generation of scientist to focus on the algorithmic acceleration possible using quantum computers.

Factoring has been a mathematical challenge for a long period of time. Think about the number 35. It has two prime factors: 5 and 7. Similarly, the number 142 has two prime factors: 11 and 13. If there was a large odd number N whose prime factors have to be identified, we will need to divide N by all prime numbers up to to identify the factors. This is a brute force method and is computationally intensive. Modern-day RSA cryptography relies on prime factoring to encrypt all our data. Passwords for our logins, credit card details, and other sensitive information rely on the computational difficulties of factoring to be safe from hackers.

As it stands today, RSA 2048 has numbers going up to 617 decimal digits. While the factorization process has gone up through the RSA bit ranking, cracking an RSA 2048 number is a few years away. The Shor's algorithm provides a theoretical model to simplify factorization.

Factorization of a number can be simplified if the period of the modular exponential function is calculated. Let us take an example to understand the modular operation and the concept of period. That will help us go through the factoring algorithm.

The result of a (mod b) is the remainder when a is divided by b. A few examples are as follows:

12 (mod 5) = 2

21 (mod 7) = 0

18 (mod 7) = 4

The next step is to understand the concept of period. Say N is the number we need to find the factors of, and x is a co-prime to N. We use the following power function:

x^a Mod (N)

Now, to go through the factoring algorithm, let us take an example.

Say N = 91 and x = 3 (co-prime to N). When two numbers are co-primed, their greatest common divisor (gcd) is 1, applying the above power function to derive the period:

3⁰ Mod (91) = 1

3¹ Mod (91) = 3

3² Mod (91) = 9

3¹ Mod (91) = 27

3⁴ Mod (91) = 81

3⁵ Mod (91) = 61

3⁶ Mod (91) = 1

3⁷ Mod (91) = 3

As you can see, the sequence starts repeating itself after six increments of a. This is the period, which in this case is "6". Identifying the period is a hard problem to solve in factorization. However, once that is done, the factors can be arrived at using the following methods:

As r = 6, N =91, and x = 3 in this example, we can arrive at:

According to the factoring algorithm:

gcd(28,91) or gcd(26,91) will be a non-trivial factor of 91, where gcd stands for greatest common divisor. And in this case, gcd(26,91) = 13. Once that has been identified, the other factor can be identified as 7.

That is a simple example of how the factoring algorithm works. Shor proposed that some of the steps in this factoring algorithm happen in a quantum computer, while the pre-processing and the post-processing took place in a classical computer. These are the steps that describe the algorithm:

Step 1: In the above example, pick 3 as the co-prime to 91 using a classical computer.

Step 2: Create two quantum registers. Register 1 will h store the increments of a, in x^a Mod (N). Register 2 will store the results of x^a Mod (N).

Step 3: Apply Quantum Fourier transforms to register 1 and compute the period r = 6 in parallel.

Step 4: Once the period is identified, find the gcd and arrive at the non-trivial factor of 91 using classical computers.

Shor's algorithm provided a way to do the modular exponentiation and identify the period using quantum computing. Every element in the sequence x^a Mod (N) contributes to the amplitude of the period of the sequence. For all periods calculated, other than the right one, the spin of these contributions is in different directions, and hence cancel one another out. The true period, the contribution from the sequence, points in the same direction and gets chosen as the right value with a high probability. We will now look at Grover's algorithm, which offers an increase in search performance on unstructured data.

Grover's algorithm

Lov Grover published a paper in 1996 describing Grover's algorithm. The application of Grover's algorithm to unstructured searches provides a quadratic speed up. If you want to find an item in a database and if the data is not sorted, using Grover's algorithm implemented using quantum computers can provide better performance than classical computers.

When a name had to be identified from N names within a database, and if the names were sorted, a classical computer could perform a binary search to find the name in logarithmic time. If the names were not sorted, then the search would involve scanning up to the N-1 name to find the right one.

If S_a is the element we are trying to find from the database of N elements, using Grover's algorithm can help solve the problem with attempts. Qubits are prepared so that all numbers are in a uniform superposition using a Hadamard gate. Measuring the qubits at this stage would show that all results were equally likely:

Figure 3: Achieving uniform amplitudes

The following equation represents the uniform magnitude of all strings:

Now, an oracle gate is applied to flip the amplitude of s_a and leaves the rest unchanged:

The graph can now be represented as:

Figure 4: Flipping the amplitude string that matches

Now the amplitude of the desired element S_a has been flipped (to negative). Hence, the mean of the amplitudes would have been reduced. This is where the Grover diffusion operator is introduced to increase the amplitude of S_a absolutely.

All this operator does is to flip the amplitudes at the average. This results in the amplitude of S_aincreasing to about in magnitude. The amplitudes looks like the following diagram:

Figure 5: Flipping amplitudes at the mean

This process of applying the oracle gate and the Grover diffusion gate is repeated until the amplitude is significant enough. Care must also be taken that the amplitude of S_a is not too large that the mean amplitude turns negative, which in turn will start reducing the amplitude of S_a. At the point when the amplitude is almost one, the measurement of the qubits will provide the right answer. It can be demonstrated that this process, when repeated for about , provides accurate results.

Takeaway: The Shor and Grover algorithms laid the foundations for quantum computing and identified practical use cases that these algorithms can help solve.

We will now move on to quantum annealing, which is a technique used to address optimization problems.

Quantum annealing

We have seen how superposition of qubits achieved by operations using gates can solve real-world problems. There are other methods to arrive at an optimized solution. Quantum annealing is the process of arriving at global minima using quantum fluctuations. The quantum tunneling effect can help with transition between states in a quantum annealer.

During the quantum annealing process, the information required for optimization is modeled into a physical system. This process involves codifying an optimization problem of several correlated variables into a physical system (represented by qubits in superposition).

The solution to the problem is represented by the minimal energy state of the system, and the simplest function used to achieve this is called Hamiltonian. Quantum annealing powered by the quantum tunneling effect can address problems in logistics for example.

Quantum tunneling

Quantum tunneling is a quantum property where particles pass through high energy systems. In classical physics, when an electron encounters an electric field, it gets repelled if the electric field is stronger than that of the electron. Problems that are solved using quantum annealing rely on the quantum tunneling property of particles.

Figure 6: An electron approaching an electric field

Figure 7: An electron repelled by the electric field

Figure 8: An electron wave moving toward an electric field

Figure 9: An electron wave tunneling through an electric field

Tunneling is a property that was observed by Friedrich Hund in 1927. If an electron, that is traveling as a wave encounters an electric field that repels it, there is still a probability that it will pass through the electric field and find itself on the other side of the field (Figure 9). subatomic particles display tunneling properties during a radioactive decay, when particles escape an unstable nuclei.

Quantum annealing is a process that depends on the tunneling properties of particles. Let us look at a practical example where quantum annealing can be used.

The traveling salesman

The traveling salesman problem is a well-documented application of quantum tunneling. Say we have a salesman selling goods across a country. The optimal route for him to go through the country would depend on the number of cities in the country. If the country has three cities (A, B, and C), the optimal route could be A -> B -> C or A -> C -> B or B -> A -> C or B -> C -> A or C -> A-> B or C -> B -> A. The number of possible routes (6) is dependent on the number of cities here (3). The number of possible routes can be given by the factorial of the number of cities as:

3! = 3 * 2 * 1 = 6

When the number of cities doubles to 6, the number of possible routes would be 6! = 720, which is a drastic increase. Apart from the increase in the number of cities, there could be other issues such as traffic jams at a point in time, or a road that is particularly bad. The optimal route, therefore, may not necessarily be the shortest route. We first need to set up the system to identify the optimal solution.

Let's prepare the system in a quantum superposition of many possible solutions of the problem. The system can be now viewed as a landscape of peaks and valleys. Peaks are high energy states and are expensive. Valleys, on the other hand, represent low energy states. As we transition between one valley and another, the probability of each solution evolves. The lower energy options become the more likely solution, until the highest probability solution is identified as the optimal solution.

In simulated annealing, heat is used to go over peaks and transition between valleys. With quantum annealers, the quantum tunneling effect allows us to pass the high energy peaks through tunnels instead of climbing them, as in simulated annealing.

Quantum annealing is driven by an external magnetic field that plays the role of the temperature in simulated annealing: the quantum annealing starts with a high magnetic field (high temperature) and ends up with a low magnetic field (low temperature).

Quantum annealing is the process of feeding the information required for optimization into a physical system. The solution to the problem will be defined by the ground state (lowest energy state) of the system. The function used for this process is called the Hamiltonian function, which manages information on the energy levels of the system.

We can use the Hamiltonian to manage the energy levels of the system based on a framework of constraints. In the traveling salesman problem, we can have higher energy levels assigned to longer distances, bad roads, traffic jams, and road closures. The optimal route would be the one with the lowest energy level. Considering this, how do we identify the lowest energy solution?

The Hamiltonian function, and the terms we add to it to increase the energy levels, would create peaks and troughs in the energy space. We need to find the troughs without having to climb the peak energy levels. This can be achieved by quantum tunneling, as described above. While this allows us to move from one trough to the other, how can we identify the lowest trough? A quantum technique called adiabatic quantum computation can be used for the purpose.

The term adiabatic comes from the theory of thermodynamics and means without changing the amount of heat. In this process, the system is initialized at the ground state, and then slowly evolved into more complex Hamiltonians whose ground states encode the solution.

Each Hamiltonian encodes the correct assignment of variables by assigning an energy penalty to all of the incorrect configurations. The peaks in the landscape have a higher penalty and the valleys have a lower penalty. The optimal solution with the lowest energy level generally has an eigenvalue of 0. We can time evolve the system to:

H(s) = (1 ? s) H₀ + sH₁

At time s = 1, the Hamiltonian is H(1) = H_s, and the system will be in its ground state if the evolution has been slow. Eigenvalues and Eigenvectors are used across several real-world algorithms. They are used in modeling the physics of rotating bodies, oscillations of vibrating systems, and in risk modeling in investment banks.

Eigenvalues are defined below by Hoffman and Kunze (1971):

Eigenvalues are a special set of scalars associated with a linear system of equations (in other words, a matrix equation) that are sometimes also known as characteristic roots, characteristic values (Hoffman and Kunze 1971), proper values, or latent roots (Marcus and Minc 1988, p. 144).

Reference: http://mathworld.wolfram.com/Eigenvalue.html

Quantum annealing can be used to solve optimization problems. However, we may not have to wait for quantum computers to use the principles of quantum annealing and quantum tunneling to achieve results. Fujitsu have already created a "Quantum inspired digital annealer" to solve challenging optimization problems in financial risk management and financial portfolio rebalancing.

Takeaway: Quantum annealing can be used in optimizing problems across several industries. Finance, logistics, healthcare, and smart cities are all areas where this technique can be used to optimize complex problems.

Despite all these amazing possibilities with Quantum techniques, decoherence is a major challenge. Let's look at that next.

Decoherence

We discussed the Quantum Slit experiment in Chapter 1, Introduction to Quantum Computing and Blockchain, where we saw that photons moved through the slits and behaved like waves (interfering with themselves), even though they were sent one at a time. When a particle exhibits properties of a wave, where it interferes with itself, it is said to be coherent. Decoherence is the loss or the suppression of coherence in a system.

The wave function that explains the behavior of the particle collapses when the state of the particle is observed. This process of decoherence, in which the particle that was in a superposition of states collapses to one of the two classical states when observed, is considered a bridge between quantum and classical physics. The experiment could be on an electron in superposition, and if the observer is measuring the z-component of the spin, the experiment will output a definite value of the z-component of the spin. The x-component could still remain in superposition. This aligns with Bohr's interpretation that properties in the quantum world come into existence when observed.

We know that macroscopic objects, such as human beings, do not exhibit this property – adopting a given state only when observed. Of course, we all exhibit virtuous characteristics when we know we are observed, and sometimes vice versa, but this is not the case with inherent attributes such as alive or dead! On a more serious note, how can things in the quantum world exist in multiple states at the same time until they are observed?

Erwin Schrodinger devised a thought experiment to illustrate the counter-intuitive nature, and seeming absurdity, of this concept:

A cat, radioactive material, and poison gas were placed in a box. If radioactivity is detected, the flask containing the poison gas would be broken and the cat would die. The radioactive material was small enough that radioactivity may not be detected for some time. Thus, at any given time, those outside of the box would be unable to determine whether the cat was alive or dead. Thus, by quantum logic, the cat could be considered to be both alive and dead!

Schrodinger questioned how this could possibly be the case within the quantum world, when it is clearly not the case in the macroscopic world. All quantum experiments thus far, however, have affirmed the theory that quantum objects do indeed appear capable of existing in two states until observed.

Quantum Error Correction

Quantum Error Correction (QEC) is a critical process that makes the results of the quantum system reliable. In the initial days of quantum computing, correcting a quantum computer efficiently without triggering decoherence of the computation was considered highly non-intuitive. A lack of reliable error correction in a quantum system was a major roadblock because quantum algorithms use interference, which is fragile. This interference made quantum algorithms sensitive to imprecision in the system and to the coupling between the system and the rest of the world.

Some of the common reasons for errors include:

1. Preparation of the initial state of the system
2. Decoherence of qubits can occur due to interactions with the environment
3. Inaccuracies in gates
4. Imperfections in the measurement process

Peter Shor and Andrew Steane developed the first set of quantum error correcting codes. While Peter Shor identified that 9 qubits could be put together to perform error correction on one qubit, Steane discovered a 7-qubit error correction methodology.

Loss in quantum information due to interference with the environment can be addressed using the distribution of information. If the information is distributed across several qubits instead of one qubit, the information is safer. In classical computing, error correction using repetition code uses three bits to store copies of information from one bit. So, unless two of the copies are error prone, the information is intact. While this is a simple process in classical computers, with quantum computers, copying information from one qubit to another is more complicated.

It was Shor who proposed a method to generalize the repetition code method for quantum computers. The solution he proposed was to encode a qubit with the repetition code on the basis states.

Post-selected quantum computation was developed by Emanuel Knill, and demonstrated that quantum computing at scale could be achieved through error detection rather than error correction. The quantum computer would have error detecting circuits and if errors (noise) are detected to have breached a threshold, the relevant subroutine of the algorithm is reset and re-run. This addresses high levels of error tolerance but has high resource requirements.

Another useful method for dealing with quantum errors is to use quantum error correcting codes called stabilizers. These are quite useful tools for developers of quantum systems. The stabilizer code specification has numerous applications, including the design of preparation circuits, correction circuits, and fault-tolerant logical gates. Using stabilizers to define quantum error correction codes helps apply logical operations on encoded data using correction circuits. The 7-qubit method developed by Andrew Steane, which constructs a logical qubit using seven physical qubits, has the ability to correct single X or Z errors.

Takeaway: The key takeaway is that error correction in quantum computing is a non-trivial exercise. The complexities in QEC and the various options available to address them are worthy of a whole book. It is a critical aspect of quantum computing that has helped transform quantum computing from theories to a practical possibility.