When Does Classical Computing Beat Out Quantum Computing?

Let me start out with the following premise.   While quantum computing will be great for those problems where classical computing solutions are intractable, if both classical and quantum approaches can both solve a problem, classical will almost always win.  The reasons for this are simple.   For the foreseeable future, classical technology will be cheaper, the systems will be more available, and end users will be more familiar with how to use them.

An example of where this thesis will play out is in the area of cryptography.  Current systems of public key cryptography are all based upon the computational problem of factoring a large prime number.  While multiplying two large number together to result in the large prime is easy, doing the reverse is exponentially difficult on a classical computer.  Commonly used public key system, such as RSA encryption, is based upon this assumption. The advent of quantum computing may threaten the security of these public key system due Shor’s quantum factoring algorithm.   This is a theoretical technique formulated by Peter Shor in 2004 to use a quantum device to calculate such a factorization orders of magnitude faster could be achieved on the fastest classical computer.  However, this technique would still require a quantum computer with many thousands of qubits which does not exist today.  But projections are that such computers will indeed be available 10-15 years from now.  So the industry is starting to look for alternative encryption methods that would not be susceptible to attack because the algorithms would not be based upon large prime number factorization or anything else that could be easily calculated using either a classical or a quantum computer.

It turns out there are both classical and quantum approaches to solving this problem.  The classical approach is called post-quantum cryptography (also called quantum resistant cryptography) and was the subject of a NIST report that you can see here.  These algorithms use new public key algorithms, such as the lattice-based algorithm, that are not dependent upon factoring a large prime number and are not breakable by a quantum computer.   And, there are several startup, established companies, and government agencies that are researching this technology.  These organizations include Google, NIST, and startup companies Isara, Post-Quantum, and evolutionQ.   Since these solutions will run on classical computers they would not require any significant changes in the hardware infrastructure.

The quantum approach is being used by ID Quantique, Qubitekk, Quintessence Labs, SeQureNet, QuantumCtek, the Chinese Academy of Sciences, and others that use the properties of quantum mechanics to create an uncrackable communication channel.  These companies have built impressive systems that provide quantum key distribution over long distances.   In fact, the Chinese Academy of Sciences recently demonstrated a video call that used a quantum key distributed over an orbiting satellite.

But the question remains, which approach will win out?  Based upon the premise stated at the beginning, my forecast is that the post-quantum classical techniques will become the dominant approach over time. There will be concerns that someone may possess a secret algorithm, either quantum or classical, that would enable breaking this encryption, but a lot of work will be performed by various parties to certify the algorithms by ensuring that no ways to break them have been found.  Nonetheless, there will be small usage of a true quantum approach, but this will remain primarily used by government agencies that want absolute assurance that their encryption cannot be broken due to fundamental concepts, such as the No-Cloning theorem, present in quantum mechanics. But in the end, economics will win out and the classical approach will dominate because it is the lowest in cost.

Leave a Reply

Your email address will not be published. Required fields are marked *


This site uses Akismet to reduce spam. Learn how your comment data is processed.