The world’s ability to exchange information at the speed of light from its connectivity has changed everything in the last 25 years. One of the fundamental enablements of this internet grid is secure exchange of information between systems and people. As we discuss in our Ethical Hacking & Cyber Security course, this secure information exchange rests on a set of cipher suites of symmetric encryption, asymmetric encryption, and hashing and there has always been an assumption that the brute force methods of cracking will be taking too long a time because of the tremendous processing time required to try all possible permutations and combinations. As we see in our course, all public key private key encryption today rests on a vast number of combinations of prime factors, integer factors, and discrete logarithms. Cracking things the brute-force way is an impossibility as it takes exponentially longer.
However, things could be changing in the future with quantum computing. Quantum Computing can allow successful brute force attacks if it can bring its potential into reality. Using quantum computing, a hacker can crack the password or the private key by trying several possibilities in a short period of time, which was close to impossible in the traditional non-quantum computing world.
Computer Engineers classify problems into three types: P, NP, and NP-complete.
- P Problems – Computers can solve efficiently in Polynomial time
- NP Problems – Whose solutions are verifiable in Polynomial time, but the very solving of it is an Exponential time problem
- NP-Complete – An efficient solution to any of these problems would provide a solution to all NP problems
If we want to solve NP problems in polynomial time, then the last hope is to broaden what we mean by a “computer”. And, quantum computers could be a far sighted hope for this problem.
How is Quantum Computing different?
Quantum computers don’t compute the way we know computing in the classical computers. Our classical computers depend on a bunch of registers and do AND/OR and CONDITIONAL operations in an intuitively understandable way. However, quantum computers do a different set of operations other than the traditional logical and conditional operations. This is where it is different.
Imagine, we have 1000 particles for our measurement. At any point of time, when we measure these 1000 particles, they’re either spinning up or spinning down. If the electron spins clockwise on its axis, it is described as spin-up; counterclockwise is spin-down.
Now, each particle can be spinning up or down, and hence the permutations possible are 2^1000. So, in the quantum computing world, we assign what we call “amplitude”, a value in terms of a complex number, to each of these permutations.
P1, P2, P3, P4, …., P1000
U, D, D, D,…………., D —> Amplitude A1 Assigned
U, U, D, D,…………., D —> Amplitude A2 Assigned
And so on… you know the drill.
But the catch is in the values of the amplitudes. They can be both positive and negative.
Now, we physically perform some operations on these particles – like hit these 1000 particles with radio waves or a laser pulse. After doing so, we check the final quantum state of these particles. Please note that we will still be able to capture only one of the physical states when we check at any point of time.
Then, how is this different from classical computing? It still feels the same. The difference is in the interference or superimposition of these particle amplitudes.
The intuition of this comes from particle physics that a good equilibrium solution generally has particles set in some positions. Meaning, while theoretically, a lot of possibilities are possible, particles naturally tend to equilibrium positions that deliver equilibrium solutions.
So, in a quantum computer algorithm, possibilities not leading to an equilibrium solution for an outcome would have the particle amplitudes cancel out each other. This would lead to situations where permutations leading to solutions will have amplitudes of a certain type, leading to cancelling or ruling out a lot of possibilities that don’t lead to solutions.
When amplitudes cancel out, the interference is called destructive interference. When amplitudes with the same sign add up, it is called constructive interference.
We cannot solve all problems in this way. There are only a handful of problems that are actually designed to test this solutioning, however even those problems don’t have a lot of practical application.
But, one of the problems to which this quantum framework of solutioning could possibly be applied is factorization. And, we know that public-private key cryptography largely rests on factorization. And, therefore, there is that unrest that quantum computing could possibly lead to a fundamental disruption of public-private key encryption, in which case all communication systems will end up in the open.
What class of problems (P, NP, …) can quantum computing solve?
There is a new class of problems called the Bounded Error, Quantum Polynomial Time (BQP). These are problems that are not NP-hard, but a set of NP-complete problems that could be solved in polynomial time by a quantum computer. Currently, it is found that exponential time problems that involve factorization could be solved in polynomial time using a quantum computer, however the evidence is not fully established as quantum computing has a huge amount of error in it.
Conclusion
We never know if quantum computing will see the light of the day in terms of practical applications. A major issue with quantum computing is the lack of fundamental tenets to solve the problems. But, never say never! There could be a possibility that it could be used for a specific set of applications involving factorization, but at this point the efforts and the error are still very high to be practical at scale.
Quantum Safe Encryption or Post-Quantum Cryptography (PQC) is the emergence of a suite of cryptography algorithms that are going to resistant and safe from quantum decryption to prepare for a post quantum world in case if such a risk arise in the future.
Hope this is useful, thank you.
You may like to read: IBM brings Quantum Computing to Cloud, The Mathematics of Sea Shells, Light Diffusion Explained, Basics of the Graph Paper, & How Minecraft teaches kids to code?