Quantum Computing

Preface

Quantum computing is one of the most intimidating topics within the academic area, often being represented as "the science that makes no sense" even by its main theorists, under the dogma that no one really understands in depth the phenomena that happen in this field, this article has as one of its objectives to present this theme in a simple way, presenting the historical motivations behind its emergence, what are the theories and scientific bases that support it, what feats we would be able to do with its implementation and how (Partially , since it's not something you learn that easy) it actually works.

Introduction

Classical computing as we know it today was conceived by Alan Turing as an initial way of proving that it was possible to perform operations, based on number theory and its formal rules, via an automated machine. Although such an idealized machine did not exist in his day, Turing emphasized that the model would be possible and efficient. Even with some other ways of solving problems, with something that would become the classical computer, being proposed, this model introduced by Turing was the most consecrated, due to its "simplicity" that made it the most accessible and intuitive model

Historical Motivations

Within computation we have two classes or sets of algorithms: Those whose answer is computed quickly, called the efficiently computable ones, which we associate to the set $P$ , where $P$ is defined as the class of problems that are solved in the Turing Machine with a polynomial number of steps in the input size. And those whose answer is not computed efficiently because we don't know of efficient algorithms to solve them (if they even exist), so we don't know if these algorithms exist in the class $P$ , but they sure are in the superclass of $P$ , which we call $NP$ , with $P \subset NP$ . We want to develop techniques for the solution or discovery of algorithms present in the class $NP$ that we could not conclude with normal computing, due to limits imposed by the complexity class of the problem, a classical computer, however powerful it may be, would not be able to solve such problems in a timely manner. It is worth mentioning that, despite the names, a problem $NPC$ ( $NP$ Complete) is also a subset of the class $NP$ as $P$ . Computing paradigms (the usual being the Turing Machine) with the possible ability to solve these problems are often treated as mathematical fictions, physically impossible implementations, among these paradigms we have the example:

Nondeterministic Turing machine;
DNA Computing;
Membrane computing;
Quantum Computing;
Real or Analog Computing;

And we call this segment of computational models Hypercomputation, initially presented by Turing in a 1939 article . However, despite being often treated

as "mathematical fictions" as mentioned, we have exceptions among the models, those with which some kind of implementation would be possible, among those presented we have Real Computing and Quantum Computing. But it is worth saying that the idea that hypercomputing exists, physically speaking (and not just mathematically), can be refuted. In a short article about the problem $P=NP$ this idea is lightly introduced, the physical existence of hypercomputing requires that $P\not= NP$ , as this would serve as evidence that digital physics (that all phenomena in physics could be described or modeled as digital information processes) is false, giving rise to hypercomputing

Quantum Physics

Having said all that about hypercomputing, deepening the need for computational models capable of solving all $NP$ problems in polynomial time, it is then necessary to know which theories are possible for the development of these models, among the main ones we have quantum physics, obviously being related to the quantum computational model

Quantum physics seeks to explain subatomic phenomena, that is, it is one of the theories used in explaining situations of dimensions close to or below the atomic scale, it is impossible to explain the subject without going deeper and taking an extremely technical position on the subject, the book "The Principles of Quantum Mechanics" by Paul Dirac is a great example of how a base can be extremely taxing, so we usually take care of explaining only famous quantum phenomena such as superposition and juxtaposition, in a simple way.

Basis for Quantum Computing

The main component in quantum computing is the qubit or quantum bit, this is the basic unit of information in quantum computing, although a qubit can be used to repre- sent a normal bit, that is, information in binary format, it can also present information as in a quantum state, in other words, it can appear as the superposition of states 0 and 1, and we will go a little deeper into this.

To represent a state, a variety of particles can be used, such as electrons and photons, but we would have a unit of measure to read the states of each particle used. When electrons are used to represent a qubit, meaning is assigned to its "spin", the particle's angular momentum, such as spin up and spin down for binary values. Similarly, when a photon is used as a function of a qubit, its polarization, vertical or horizontal, can be used to read the state

Of course, a qubit is capable of representing continuous values in nature, and not binary values as our symbology, relating its states between 0 and 1, but we define a limit for this. Classical computing works from binary data, and readjusting an en- tire computer science to use another base would make it difficult to integrate these components

Quantum Model (qubits and bits)

Classical computing receives this name because it seeks to develop computational full- ness through manipulations of matter, based on the laws governed by classical physics, the Newtonian one.

For us it is extremely simple to think about the idea of the bit, because its state has only two options, yes or no, off or on, positive or negative, etc... We can relate any material around us as if it were a bit (or a set of bits), it is extremely simple, based on some property to read its state, change it and keep it the way we want, and then, with several objects that have a property in common, we can assign a meaning and based on its measurement, compile an information

Therefore, there will always be two states that matter can undergo. In a scenario in which we have a necessary amount of information that must be represented in two alternatives, we relate two possibilities for a unit of material, we would need $n$ units of material (bits), to represent an information $x$ , such that $n = \log_2{x}$ , and when we know the amount of bits $n$ and we want to know how many possibilities there are, we just do the inverse $(i.e.\ x = 2^{n})$ .

In the use of qubits we have a more complicated issue, due to the high volatility of the material being measured. We could imagine a photon in transit, such a photon transmitting information such as its polarization, when we measure it to know its orientation or polarization, we do not model it based on the classical bit, but we question its orientation for a reason that will be explained. One of the main problems of binary modeling is that this matter measurement process causes a collapse of the detected orientation, and with that the corruption of information. In this way, it is not possible to measure all the properties of the particle (either velocity or orientation), as this implies its collapse, which brings us the principle of uncertainty, as we cannot avoid it.

Such corruption occurs because the information measurement processes are aggres- sive for the matter being observed, that is, the measurement requires a certain level of interaction that is enough to cause collapse in the quantum state of the matter, the only value obtained is the selected one, the rest, like the overlay, will be lost.

However, we could think about which situation this volatility in question might be interesting. We continue with the example of the photon used in data traffic. Let's imagine two people, $A$ and $B$ who need to exchange a message, and there is a third person $C$ who has the objective of intercepting the photon in transit sent by $A$ , reading it, and sending it again to recipient $B$ . Based on uncertainty, it is possible to check the confidentiality and integrity of the transmitted data, because if any qubit of the message is intercepted by C and sent back to $B$ , its state will be collapsed, and the data will no longer be valid or correspond to that which was assigned to it at first, serving then as a possible module for a cryptographic algorithm to check if the data can be intercepted or not.

Qubit Notation

To understand the phenomena of quantum mechanics, one must first understand the Hilbert spaces and the concept of the notation bra-ket $\braket{\psi_2|\psi_1}$ , introduced by Paul Dirac for describing states, this notation is a representation of a vector, being possible that its contents are complex, real, or imaginary numbers. It is worth remembering that a tensor, just to be mentioned, is a particular case of a vector. To understand the phenomena of quantum mechanics, one must first understand the Hilbert spaces and the concept of the notation bra-ket $\braket{\psi_2|\psi_1}$ , introduced by Paul Dirac for describing states, this notation is a representation of a vector, being possible that its contents are complex, real, or imaginary numbers. It is worth remembering that a tensor, just to be mentioned, is a particular case of a vector.

In bra-ket notation, the "bra" represents a row vector and is denoted by $\bra{}$ , the "ket" represents a column vector and is denoted by $\ket{}$ , the row vector being a transpose the column vector and vice versa. So, to represent the states, we can use the notation as follows:

\bra{0} = (1\ 0)\ \ \ \ \ \ \ \ \ \ \ \ \ket{0}= \begin{pmatrix} 1 \\ 0 \end{pmatrix}

\bra{1} = (0\ 1)\ \ \ \ \ \ \ \ \ \ \ \ \ket{1}= \begin{pmatrix} 0 \\ 1 \end{pmatrix}

Qubits can be symbolized in two states, pure and mixed, if we can demonstrate the state of a qubit purely using linear combination, that means that it is in a pure state . A qubit in its pure state is usually denoted as follows:

\ket{\psi} = \alpha\ket{0}+\beta\ket{1} = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}

No-cloning theorem

If we want to store a state, store information contained in a qubit for future use, we could perhaps clone the state of that qubit to another one that is blank. So we would have a state qubit $\ket{\psi}$ , and another "blank" state $\ket{0}$ , being the state $\ket{\psi}$ arbitrary. The tensor product would be applied to have a particle with a resultant state identical to the particle of arbitrary state $\ket{\psi}$ , such that:

\ket{\psi} \otimes \ket{0}\ =\ \ket{\psi} \otimes \ket{\psi}

However, this is impossible, due to the fact that, in order to clone an arbitrary state qubit $\ket{\psi}$ to another "blank" state $\ket{0}$ , it would be necessary to measure the arbitrary state qubit and that would cause it to collapse, so the original qubit would be lost. Qubits whose quantum state is already known can be cloned, as they have already been collapsed, the action would be analogous to writing a classical bit, and therefore a qubit of unknown state cannot be cloned.

To prove the unfeasibility of cloning the state, a demonstration by contradiction can be used, using two particles, and their respective states $\ket{\psi}$ and $\ket{\phi}$ :

\ket{\psi} \otimes \ket{0}\ =\ \ket{\psi} \otimes \ket{\psi}

\ket{\phi} \otimes \ket{0}\ =\ \ket{\phi} \otimes \ket{\phi}

Then, we look at the dot product of the states, before and after applying the tensor product for cloning the states.

Before cloning:

\ket{\phi} \otimes \ket{0} \quad \cdot \quad \ket{\psi} \otimes \ket{0} =\braket{\phi|\psi} \cdot\braket{0|0}

After cloning:

\ket{\phi} \otimes \ket{\phi} \quad \cdot \quad \ket{\psi} \otimes \ket{\psi} =\braket{\phi|\psi} \cdot\braket{\phi|\psi}

With the dot product we conclude that:

\braket{\phi|\psi}\cdot\braket{\phi|\psi}= \braket{\phi|\psi}^{2}

To this equation, only two solutions would be possible: $\braket{\phi|\psi}^{2} = 0$ or $\braket{\phi|\psi}^{2} = 1$ , however, for the result to be $0$ the vectors must be orthogonal to each other, and for the result to be $1$ the vectors must be equal.

Portanto, só seria possível efetuar a clonagem de um qubit caso este e o qubit que recebe o dado sejam ortogonais entre si . Caso essa propriedade não seja satisfeita não será possível clonar o qubit em observação.

Superposition

Superposition is one of the fundamental principles of quantum mechanics, that two (or more) quantum states can be superimposed, as a linear combination, and that its result will still be a quantum state that will only be defined when it is measured. When a state is formed by the superposition of other states, it will have the properties that are intermediate between the states, and we can associate a "weight" that indicates to which state our superposition tends . It should also be taken into account that overlapping states can also be overlapping.

To make overlap more meaningful, we need to define exactly what it means and how we identify an overlap, the intention is not to explain all the details. We say that a state $A$ is perhaps formed by the superposition of states $B$ and $C$ when a result present in the observation made on the system in a state $A$ has a finite possibility of also being present in an observation in at least least one of the $C$ and $B$ systems.

The two-slit experiment carried out by Thomas Young is a good example to observe the overlapping phenomenon .

Superposition is why a vast number of classical bits are needed to describe the state of a quantum bit.

Juxtaposed and entangled states

Let $Q_1$ and $Q_2$ be quantum systems configured in different states $\ket{\psi_1}$ and $\ket{\psi_2}$ separately, which are united without interacting with each other.

Because these states are configured separately, they are found in different Hilbert spaces $H_1$ and $H_2$ , Hilbert spaces are a generalization of Euclidean spaces that are not restricted to a finite number of dimensions.

A global quantum system $Q$ can be described as the juxtaposition of the quantum systems $Q_1$ and $Q_2$ .

The state $\ket{\psi}$ of $Q$ can be described as the tensor product of the states $\ket{\psi_1}$ and $\ket{\psi_2}$

\ket{\psi_1} \otimes \ket{\psi_2} \in {H_1} \otimes {H_2}

Let $\ket{\psi}$ be the state of an $H$ space, $\ket{\psi}$ can be said to be juxtaposed when $\ket{\psi}$ can be described as the tensor product \cite{ tensorprod} of states belonging to subspaces of $H$ , thus being able to associate state vectors to individual subsystems of a quantum system $Q$ for example.

Consider the state $\ket{00} + \ket{11}$ known as EPR pair this state cannot be described as the tensor product of its Qubits separately, as there are no $\alpha_1, \beta_1, \alpha_1,\beta_2$ that satisfy the equation

(\alpha_1\ket{0} + \beta_1\ket{1}) \otimes (\alpha_2\ket{0} + \beta_2\ket{1} = \ket{00} + \ket{11}

States that cannot be described by tensor products are called Entangled states, that is, they are states of a system whose subsystems do not have individual state vectors.

Gates

The gates in a quantum computer are a consequence of modeling or idealizing the quantum computer, which would initially operate as a Turing machine, with its cells under some kind of quantum superposition. One of the main theories in use in the development of quantum gates is the quantum circuit model, which is exactly what this idea of quantum gates proposes, something that the Turing machine does not specifically do.

When we talk about quantum gates, we are talking about transformations in a quantum state, remember then that a quantum state is represented by a bra-ket, that is, they are represented by vectors whose elements can include complex numbers, by deduction, these gates that transform quantum states must be able to be represented by transformation matrices.

Quantum Transformations

As we mentioned, quantum states are vectors and the gates that change their nature are transformation matrices, so we need to define these matrices, which we call \textit{unitary matrices} (A unitary matrix is one whose inverse is its transposed conjugate).

If we could define the transformation matrix of the NOT logic gate (binary, therefore, logic) as being:

U_{NOT} = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} \quad \text{pois} \quad \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}

we could bring this into quantum computing, where we define the state $\ket{0}$ as the vector (1, 0) and the state $\ket{1}$ as the vector (0, 1).

However, unlike classical computing, the gates do not necessarily need to return 0 or 1, let's take for example the application of the NOT gate in unitary quantum states, which does not have an analogous case in classical computing :

U_{NOT} \quad \frac{1}{\sqrt{2}} (\ket{1} + \ket{0}) = \frac{1}{\sqrt{2}} (\ket{0} - \ket{1})

Where we define the state $\ket{0} = \frac{1}{\sqrt{2}} (\ket{0} - \ket{1})$ and the state $\ket{1} = \frac{1}{\sqrt{2}} (\ket{0} + \ket{1})$ , the root in these equations is related to the chance of finding this state (0 or 1) in singular quantum states, I won't go very deep into this even because it is outside my area and needs a more intense study.

Conclusion

Quantum computing defines a new logical paradigm that is intended to be a new standard, but not completely replace classical computing. It can help us reach higher levels, such as simulations of the universe that are closer to reality (If hypercomputing actually exists) and performing extremely complex calculations (Such as factoring prime numbers, which makes the use of encryption algorithms such as RSA unfeasible , elliptic curve, etc...), so in the end quantum computing is proposed as the next responsible for a computational revolution. It is no wonder that several governments and even private companies (With the support and encouragement of their respective governments) started this race for the quantum computer, several prototypes (even if limited) have already been made and progress continues, so that in the future, closer it seems, an ideal computer is finally available.

References

[1] Tai-Danae Bradley. "The Tensor Product, Demystified". Em: (2018).

[2] Selmer Bringsjord e Taylor Joshua. "P=NP". Em: (2004).

[3] Devopedia. "Qubit". Em: (2022).

[4] Paul Adrien Maurice Dirac. The Principles of Quantum Mechanics. International series of monographs on physics. Clarendon Press, 1981. isbn: 9780198520115.

[5] A. Einstein, B. Podolsky e N. Rosen. "Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?" Em: Phys. Rev. 47 (10 mai. de 1935), pp. 777–780.

[6] Marı́a de los Ángeles Fanaro, Marcelo Arlego e Marı́a Rita Otero. "The double slit experience with light from the point of view of Feynman’s sum of multiple paths". Em: Revista Brasileira de Ensino de Fı́sica. (jun. de 2014).

[7] Por Daniel Mendes Fernandes. Criptografia Quântica.

[8] Tony Hey. "Quantum computing: an introduction". Em: Computing & Control Engineering Journal 10.3 (1999), pp. 105–112.

[9] André Luı́s Bignatti, Luiz Fernando Bittencourt e Francisco Summa Netto. "Introdução à Computaçâo Quântica". Em: (2004)

[10] Eric M. Pinto et al. "Sobre os Estados Emaranhados". Em: Physicae Organum Revista dos Estudantes de Fı́sica da UnB 1.1 (mar. de 2015).

[11] José Victor Soares Scursulim. "Computação Quântica e Teoria Quântica de Correção de Erros". Em: (2021).

[12] Quentin Truong. "Introduction to Quantum Programming". Em: (2019)

[13] universosquanticos. "Clonar ou Não Clonar: Eis a Questão!" Em: (2018).