Quantum computing: the story of one of the greatest quantum technologies (Part 2)

Quantum computing: the story of one of the greatest quantum technologies (Part 2)

In the first part, we briefly introduced quantum computing and discussed how it came about. In this part, we will explain the theoretical foundations needed to better understand the field.

Principles and Concepts

Bits or binary digits are at the heart of all modern digital equipment, from computers to iPads and high-resolution TVs. Today's computers use voltage levels to encode bits. Old mechanical computers used the location of the gear for this purpose. The only requirement is that the physical system have two clearly distinguishable states or modes that are sufficiently stable so that they do not automatically switch from bit-0 to bit-1 or vice versa.

When we have the ability to store and manipulate 0s and 1s, then we have the basis to build all digital devices. We are all very familiar with digital devices that use bits. Feynman predicted that very small physical devices would be controlled by quantum mechanics rather than classical mechanics, meaning they would not necessarily behave like their larger counterparts. For example, a quantum-scale robot could take an object simultaneously and move it right and left simultaneously. Until you make a measurement, you won't know what the robot is doing. When you observe and record the result permanently, the behavior of the robot will be determined. This story sounds crazy, but it's really what happens in the quantum world.

Likewise, bits are eventually recorded in the state of some physical system. Thus as devices become smaller, the size of the physical systems used to encode those bits will be smaller, so that from one point we will have to describe them by quantum physics instead of classical physics. At this point, our common sense assumptions about how bits behave are no longer valid. In fact, on the quantum scale, you can't necessarily read a bit without changing its value, you can't reproduce it without disrupting it. You may not be able to erase it, and sometimes when you read one bit, the state of another bit changes. So encoded bits in quantum-scale objects no longer behave like ordinary bits.

So when computers get small enough to deal with quantum bits instead of classic bits, a new set of physical effects emerge that can be used to achieve innovative functions. As a result, many new opportunities arise.

Fortunately, quantum systems have certain properties that can be encoded as physical states in bits. For example, when measuring the spin of an electron, we always obtain one of two possible values of spin-up or spin-down. This intrinsic discontinuity, which is a kind of quantum quantization, allows us to consider the electron spin as a natural binary digit or bit.

Such intrinsic discontinuity is not unique to spin systems. Any two-state system, such as the polarization plate of a polarized photon or discrete levels of energy in an excited atom will work just as well. If a quantum system is used to represent a bit, regardless of the type of physical property used, the resulting system is called a quantum bit or a qubit.

The promise of quantum computing is that quantum computers have the ability to efficiently run algorithms that are difficult to implement for classical computers. Such algorithms are not only theoretically attractive, but are also very practical, such as integers factorization based on RSA algorithm. Despite this promise, many aspects of quantum computing are still mysterious. For example, it is unclear which problems quantum computers can solve more efficiently than their classical counterparts. Quantum computers are not universally superior to classical computers, as there are many algorithms that are as difficult to quantum computers as classical computers. On the other hand, there were problems that were previously thought to be solvable only with quantum computers, but efficient classical algorithms were discovered that eliminated quantum supremacy for those problems. In fact, it is still not well understood why quantum computers are more powerful than their classical counterparts. In spite of the above, there are some quantum algorithms that provably outperform their best classical counterparts. This computational supremacy has been proven, and even if its territory remains uncertain, it is sufficient to attract interests and research in the field.

There are significant challenges in the way of implementation of quantum computing. These challenges include the weird hardware needed to build quantum computers as well as the difficulty of designing and implementing quantum algorithms. The first hurdle we need to overcome is to extract the computation result. One of the fundamental features of quantum mechanics that makes quantum computing efficient is the fact that a physical property (such as angular momentum) can be in a superposition, meaning it can be simultaneously in all its possible states. In the case of a quantum bit or qubit, this means that instead of having 0 or 1, it can have both 0 and 1 at the same time. As a result, quantum computers can compute an exponential combination of possible values in the problem state space simultaneously.

However, the superposition is very fragile and sensitive. Interaction with external forces can easily make a qubit decoherent, such that it is reduced to one of the 0 or 1 states, and it is impossible to know for sure what its value will be in the future. However, when qubit was read (measurement was done), its state is reduced, so that from that moment on, whenever qubit is read, it always shows the same state with 100% probability. Since decoherence occur easily, one of the major challenges in building a practical quantum computer is to keep the qubits isolated until their value is read. The challenge is both physical and algorithmic.

On the other hand, simply isolating qubits until the user is ready to read them is not enough. If the user reads the qubits awkwardly, he will get a random result from the possible combinations of all their values. Obviously, when trying to compute valid answers efficiently for different problems, obtaining a random output is not a useful result. We have to manipulate the qubits so that we get the desired result when we read them. This increases the difficulty of designing quantum computing algorithms.

Because of these characteristics, many of the existing quantum algorithms are not definite, but instead return the correct answer with high probability. Although this is not a completely arbitrary state, the correctness of most of the answers can be checked quickly, and if the quantum algorithm returns an incorrect result, it can simply be re-executed. If the quantum algorithm is exponentially faster than its classical counterpart (which is often the case), the processing would be much faster than the implementation of a classical algorithm.

A clever designer can design the experiment in such a way as to include the replication of the qubits, such as the replication of a qubit, resulting in two separate readings. Unfortunately, such an approach is not possible, because quantum superposition cannot be reproduced. This is a major limitation, because it means that quantum data cannot be reproduced directly until it is decoherenced, which is no different from classical data replication at that time.

This situation is very difficult because even the best current designs of the quantum computer cannot completely prevent the decoherence of the input system. This indicates the need for quantum error correction. In principle, quantum error correction is similar to classical error correction, which relies on a few extra bits to restore a corrupted state, but no-cloning theorem increases the complication here. However, using special transformations of the quantum state, modified classical error correction techniques can be applied to quantum cases.

Another important principle of quantum mechanics is entanglement. The entanglement is a phenomenon where the two quantum states (here two qubits) are not mutually independent. In other words, manipulating state of a qubit will affect the state of the other entangled qubit. Entangling and detangling qubits is a crucial operation in quantum computers. In designing a standard computer, engineers spend a lot of time making sure each bit is independent of the other bits. But in a quantum computer, each qubit affects the other qubits around it to work together to come up with a solution. Superposition and entanglement are features that allow quantum computers to process information much faster.

Logic gates are another important component of quantum computing. Classical logic gates and quantum logic gates are both logic gates. A logic gate, whether classical or quantum, is a physical structure or system that takes a set of binary inputs (e.g. zero and one, apples and oranges, spin-up and spin-down, etc.) and gives a binary output, a 2, an orange, a spin-up where the Boolean function controls the output. The Boolean function is actually a rule of how to answer yes/no questions. The gates are combined to form circuits, then the circuits are combined to form processors or other computational components.

Classical gates operate on classical bits; and quantum gates operate on qubits. This means that quantum gates can have two key aspects of quantum mechanics that are completely out of the reach of classical gates: quantum superposition and entanglement. In quantum mechanics, these two concepts are abundantly talked about, but there is a less well-known but important concept called reversibility. Quantum gates are reversible. In fact, all quantum gates have a back button, while many classical gates do not, at least so far. This means that quantum gates never lose information. The qubits that are entangled in a quantum gate remain entangled and keep their information secure during transmission. On the other hand, many classical gates that exist in classical computers lose information. Classical calculations are irreversible, meaning that inputs cannot be calculated based on outputs. For example, if the output of a two-bit AND gate is 0, it would be impossible to know if the inputs were 00, 01 or 10. The only classical reversible logic gates are NOT or XOR.

In contrast, a reversible computer consists exclusively of reversible logic gates. A wide range of reversible gates can be made that can collectively perform the same calculations of irreversible gates. This concept is crucial for quantum computing, since all quantum transformations are unitary and therefore reversible. Therefore, all quantum gates themselves must be reversible. This complicates the design of quantum algorithms, as users who are only familiar with classical programming have difficulty for designing unique algorithms for reversible computation.

Note that the term "gate" must be conceptually taken into account when describing quantum gates. As we shall see, transformations on qubits is not necessarily applied to traditional gates. Also due to the superposition phenomenon, the states of qubits are expressed not as bits but as a matrix of bits, so quantum gates actually perform transformations on the matrices.

The simplest non-binary quantum logic gate is a controlled NOT gate (cNOT). The cNOT quantum gate can be used as a basis for making more general quantum gates. Quantum logic gates can be used to apply unitary transformations to the state of qubits (their probability matrices), without causing them to become decoherent. They can even be used to entangle and detangle qubits. Quantum parallelism stems from the fact that such transformations are applied simultaneously to all basic vectors in the qubit superposition.

It has been believed for many years that the ability to do this kind of operations is crucial to useful quantum computing and then to read meaningful results, but it has recently been discovered that these unitary transformations are not always necessary. Recent advances in quantum algorithms show that useful results can only be obtained by measuring and by reading the correct qubits in the correct order with the help of correct measurement techniques.

To be continued...
Tags :
Quantum Computing