**Quantum Computers**are computing systems that make use of Quantum Theory. They are different from digital computers and are much more powerful. Quantum Computers are still in nascent stage. But, once they are in use, they can break modern cryptosystem.

Let's understand what Quantum Computers
actually are and how they can break modern cryptosystem.

**Evolution of Quantum Computers**

Until the 19th century, Newtonian
theory dominated physics. But, in early 20th century, physicists
discovered that the laws of classical mechanics do not apply at the
atomic scale.

In 1900, German physicist Max Planck
introduced Quantum Theory as per which energy exists in individual
units called 'quanta'.

Further developments on Quantum Theory
were made gradually, as per which :

- Energy, like matter, consists of discrete units, rather than solely as a continuous wave.
- An elementary particle like an electron or a photon, can behave like either a particle or wave.
- Movements of elementary particles are random and unpredictable.
- The more precisely the position of some elementary particle is determined, the less precisely its momentum can be known. In other words, the more precisely one value is measured, the more flawed will be the measurement of the other value.

Later, the theory of quantum
superposition was developed. As per this theory, any two quantum
states can be added together or superposed to create another valid
quantum state. In fact, as long as we do not check to see the state
an elementary particle is in, it can be in all possible states
simultaneously.

To illustrate the above principle, a
thought experiment called Schrodinger Cat was described by Erwin
Schrodinger in 1935. As per this :

Suppose, a cat is pinned up in a steel
chamber along with a device that contains a tiny bit of radioactive
substance, an atom from which may decay in an hour. And, when the
atom decays, it would shatter a small flask of hydrocyanic acid
killing the cat.

So, it would mean, the cat will be
alive as long as no atom decays. But, if it does, the cat will be
killed by the poisonous hydrocyanic acid. But, we would not be
knowing whether the cat is alive or dead as long as we break the
steel chamber.

So, to draw an analogy, the cat will be
in a state of superposition of being alive and being dead, as long as
it is in the steel chamber. And, when we would break the steel
chamber, the cat will be either alive or dead.

And, as per theory of entanglement, two
elementary particles can be entangled with each other, so that there
is a correlation between the states they are in. For example, two
electrons can be entangled such that both of them always spin in
opposite directions. Quantum state of each particle cannot be
described individually, instead both the particles will be in a
quantum state as a whole.

And, based upon the principle of
superposition and entanglement, Quantum Computers are evolved.

In a digital computer, a bit can be in
a state '0' or '1'. So, n bits can represent exactly one value of the
possible 2

^{n}values. We can apply some operation on it and convert it into some other value.
In case of Quantum Computers,
elementary particles like an electron or a photon is used. This
elementary particle called 'qubit' can be in state '0', '1' or in
superposition of '0' and '1'. So, it is possible that n qubits are in
a superposition of 2

^{n}states simultaneously. We can apply some quantum operation on these n qubits and change its state.
And, this theory enables Quantum
Computers to write programs in a completely different way, which is
much more powerful than classical digital computers.

**How Quantum Computers can break Modern Cryptosystem**

Modern cryptosystem relies heavily on
the fact that, it is computationally infeasible to factorize a large
number into its prime factors. For example, in an RSA cryptosystem,
an attacker can easily derive the secret keys if he can take one
particular parameter and factorize it into its two prime factors.

But, in Quantum Computing, a large
composite number can easily be factorized into its prime factors in
real time.

Let's understand how it can be done.

Let's say,

N = a product of two prime numbers p and q

N = a product of two prime numbers p and q

x = a number not divisible by p and q

Let's take the series :

x mod N, x

^{2}mod N, x^{3 }mod N, x^{4 }mod N ...
As per Number Theory, these numbers in
the series will repeat themselves after a period d and d will surely
divide (p-1)(q-1)

So, in a Quantum Computer, we can
perform the steps below :

- We can take all the numbers of the above series and create a superposition of all the numbers.
- We can then apply some quantum operation to reveal the period d. As said earlier, the numbers repeat themselves after a period d.
- We can repeat the steps with different values of x, which would give different values of d.
- If we can get enough different values of d, we can derive (p-1)(q-1), as d always divides (p-1)(q-1).
- From (p-1)(q-1), we can calculate pq which is equal to N.

So, we can first reduce the problem of
factorization into another problem and then use Quanum Theoy of
superposition and entanglement to derive the unique prime factors,
which in effect beak the modern cryptosystem.

This was just an introductory article
to give some basic information on Quantum Computing. Hope you liked
it.

## No comments:

## Post a Comment