05 May

Quantum Computing

Quantum Computer. In recent years, we have heard this word a lot without ever having an explanation that did not leave us with the feeling of “things that you humans could never imagine”. Before launching into the quantum computer it’s necessary to present a fundamental concept of quantum mechanics. In short it is the “superposition” of states, where “state” means the physical state of the system such as location, speed, or loads. If we consider a hypothetical variable that in classical physics can have two possible values, 0 or 1, in quantum mechanics it can have contemporaneously the values of 1 and 0, and every linear combination of 0 and 1, until a measurement is carried out on it, at which point it takes on only one “classic” value.
Returning to Information Technology, as many people know, the computer memory consists of bits that can have the value of 0 or 1, while a quantum computer is based on qubits. A single qubit can be 0, 1, and any superposition of these two states, a pair of qubits can be in any superposition of 4 possible states, n qubits can be in every possible linear combination of 2n states, while an n bit can only be in one of these combinations. The operation of quantum computer is based on quantum logic gates that can represent as much as possible the problem and only after the computation takes place execute a measure on the system of n qubits, which then collapse into a classic combination of n bits.

But what is the advantage? Computation time. Quantum algorithms have been shown to offer a substantial reduction of computation time compared to many classical algorithms, especially on an issue of great importance to information security: factoring whole numbers into primes. Integer factorization into primes (or simply prime factorization) involves taking a number and writing it as a product of primes, for example 6 = 3 x 2. There is no algorithm that can perform this task in a timely way. Suffice it to say that by using the most efficient algorithm to factorize a 232-digit number it took 2 years of computing using hundreds of machines. Multiple encryptions are based on the difficulty of solving this problem using classical algorithms. To have an efficient algorithm for prime factorization would make these unsafe encryptions.

Moving instead to quantum algorithms, the factorization becomes much faster through an algorithm known as Shor’s Algorithm, which makes prime factorization a task that requires polynomial computation times depending on the size of the input. Because of this the spread of quantum computers would result in major problems regarding the security of emails, web pages and many other types of data and would require the development of new cryptographic systems. In any case, quantum computers are still in an embryonic phase and still do not have the computing power to endanger our data.

Currently there are several problems in the development of quantum computers, in particular that of quantum decoherence, which in practice boils down to isolating the system from the external environment to prevent interactions between the two that insert decoherence into the system. For traditional computers the standard method to lower noise and improve performance is to cool the system. For quantum computers the mode is the same, but in this case the temperature is on the order of a few mK (millikelvins) above absolute zero, the temperature of 0 K (Kelvin), -273.3° C, which is the lower bound for the temperatures at which the particles of the system are firm and have no thermal agitation. To reach these temperatures requires very high costs making the dissemination of quantum computers a distant event.

Despite being a technology still in development, quantum computers are already present. In particular I note the IBM quantum experience as a first approach to quantum computing: http://www.research.ibm.com/quantum/

For the more adventurous:

-768-bit RSA modulus of Factorization: http://eprint.iacr.org/2010/006.pdf

RSA is one of the first practical public-key cryptosystems.

-Polinomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a quantum computer: https://arxiv.org/pdf/quant-ph/9508027v2.pdf

Share this