GOOGLE QUANTUM SUPREMACY (But Why do we need a "Quantum Computer"?)
A Quantum Computer is a computational device that can use quantum-mechanical phenomena such as quantum entanglement and quantum superposition to solve any specific problem faster than a conventional computer. However, these algorithms can not be used to get faster processing speed for mundane tasks, even these computers are slower than our conventional computers to perform day to day tasks.
SO, WHY DO WE NEED A "QUANTUM COMPUTER"?
In conventional computers, we have bits that are either 1 or 0 at a particular time. On the other hand for a quantum computer, we use quantum bits or Qbits. Qbits can be 1 or 0 simultaneously. This property of Qbits is called a quantum superposition, just like the cat in schrödingers experiment can be both dead and alive at the same time.
But how does this property help us to compute faster when we do not know what a Qbit represent, a 1 or a 0. Well, to really understand it one should know another quantum mechanical phenomenon called quantum entanglement. Quantum entanglement as my blog suggests is something fascinating which Einstein called 'Spooky action at a distance'. Let me elaborate on this further.
Let, for instance, we have two balls, they can only point in two directions, either up or down (there is no up or down in space but let's just say for our reference of Frame the two directions are up and down). Now let say we did some experiment on them and now these two balls are quantum mechanically entangled. This means that to know the state of both balls I just need to know the state of one and the other one will be just the opposite of the first one despite the distance between the two.
Put one ball in milky way galaxy and another in andromeda galaxy and do the same experiment you will know the state of both instantly as you examine the state of either one despite the spacial distance between the two.
Now, how can we utilize these phenomena to solve the real-world problem?
BY SHOR'S ALGORITHM!!
Shor's algorithm works for finding prime factors of numbers with the help of the quantum phenomenon. The general encryption that we use today to secure the information is based on these numbers (RSA cryptosystem) that are intractable on classical computers if you don't know the factors already. Meaning that it would take a significantly huge amount of time to find the prime factors of these numbers if we use a classical computer/ supercomputer.
However, if we use a quantum computation to find the prime factors using Shor's algorithm, we could find these factors in minutes. I will demonstrate how it works by taking an example.
Let's say that we have a number of N= 91 to be solved by Shor's algorithm.
(we know the prime factors of 91 already but for simplicity, I have chosen this number)
1. Pick a random number a, which is less than N (let's take 8).
2. Compute gcd(a, N), this can be done via the Euclidean Algorithm (very common).
3. If gcd(a, N) ≠1, then there is a non-trivial factor of N, so we are done.
4. If gcd(a, N) = 1 !! yayy we are in luck and can use Shor's algorithm !!
5. now we use n = 0, 1, 2, 3, 4 ... 91.
6. Now, we need to find (a)^n for all the values of n.
7. After that, we need to do modulo operation for all the values of (a)^n for 91.
which is d = mod((a)^n, 91);
8. Because these forms are in superposition we will not see all the values in a quantum computer. However, a classical computer has to calculate all the values.
9. Let's do the quantum step by over self (cuz this calculation is easy peasy).
For instance, we get a value of d = 64 after the 7th step.
10. corresponding this value we get the n value as:
86 90
11. we can see that the spacing between these is 4 which is the value of r.
12. Then (a^(r/2) + 1) or (a^(r/2) - 1) would be a better guess and might have the greatest common divisor with N which is greater than 1.
Following is the MATLAB code:
Alternate way:
As we can see this is easy for N= 91. The graph between n and mod values are a good sine wave and by Fourier Transformation we can find the frequency of the signal which is 0.25 as we can see below:
So frequency would be f= 1/r = 0.25 = 1/4 . Thus r = 4.
13. Finally
The Prime factors of 91 are 13 and 7.
This is how Shor's Algorithm works!!!
HOWEVER, IF I TRY THIS WITH BIGGER NUMBERS LIKE 125 OR 513 THE MOD BLOWS TO INFINITY!!!
AND I AM USING A 1.8GHz INTEL CORE i5 COMPUTER.
IN QUANTUM COMPUTER, ALL THESE CALCULATIONS HAPPENS SIMULTANEOUSLY. IT DOES NOT HAVE TO CHECK EVERY SINGLE GUESS ONE BY ONE, UNLIKE CLASSICAL COMPUTER. THAT'S THE QUANTUM LEAP.
WE NEED A QUANTUM COMPUTER TO SIMULATE ALL THE OUTCOMES OF AN EVENT EITHER IT IS A CHEMICAL REACTION OR A SPACE FLIGHT, SO THAT WE CAN MAKE REVOLUTIONARY CHANGE IN VERY FEW ATTEMPTS.
For more examples like this minutephysics has done the same calculations for a number 314191.
Go check it out. Factoring of 314191 by minutephysics
Comments
Post a Comment