We recently looked at Quantum Computing value proposition.
Quantum Computer can solve some problems by several order of magnitude. This brings today’s intractable problems to be easy to solve tomorrow.
Not all problems have this property. In this article, we’ll look at some problems that do.
This is a technical-light article with no mathematics.
Classical Computers are good at cryptography. They can encrypt and decrypt relatively quickly. Every time a web site uses HTTPS, encryption / decryption is done at the sending and receiving ends seamlessly.
By contrast, they are pretty bad at cracking cryptographic code. That problem is related to the factoring problem, i.e. finding two prime factors of a giant integer.
For instance, if we take the following integer:
Can we easily tell what are the two prime numbers which product would yield that integer (hint: no)?
The best known algorithm known is exponential in complexity. A little more formal would be to say that for an integer of n bits, cracking the code will take O(en) steps.
Shor algorithm is a quantum algorithm. It solves the factoring problem in polynomial complexity. Polynomial isn’t linear but it’s way better than exponential.
What does this polynomial vs exponential complexity means? Complexity captures how the computation time evolves with problem size. Exponential complexity grows much faster than polynomial.
This is what makes cryptography useful: for big enough keys, it is too hard to break with today’s computers.
By contrast, a Quantum Computer would easily break today’s Internet cryptography. No HTTPS communication would be private. Blockchains (e.g. Bitcoins) rely on similar cryptography and would easily be hacked.
Post Quantum Cryptography is already a flourishing field so not everything is lost. But it gives a idea of the power of Quantum Computing.
The basic problem of a lot of material research have similar mathematical communalities. It is about finding a big molecule having a couple of interesting properties. This could be pharmacology, agriculture (e.g. finding fertilizer catalyst), nanotechnology, etc. .
This requires simulating a very large amount of big molecules.
Classical Computers are unable to find solutions with large molecules in tractable timescale. By tractable timescale, we mean less than a few years.
An exciting avenue would be to find a Super Conductor at room temperature. Currently known super conductor materials have super conductivity property at very low temperature.
Finding new catalysts would largely improve the Carbon Capture / Sequestration problem.
Quantum Computing could enable the creation of interesting new material. Today those materials are simply out of reach for computational reasons.
Training complex Machine Learning models is an optimization problem (see our introduction articles). It consists in finding an optimal parameter within a huge parameter space.
We’ve looked at often cited problems that would benefit from Quantum Computing.
Disruptive technologies do not only solve problems that couldn’t be solve yesterday. It typically opens up new scenarios that were not considered before.
Public Cloud Computing brought the notion of pay per use. This was quickly pushed to “pay per minute” (and even seconds in some cases). This eventually made possible serverless computing. Serverless computing isn’t something would have been conceived on premise.
In a similar vein, scenarios aren’t on the table today because their prerequisites do not exist yet. Once Quantum Computing enables those prerequisites, the real disruption will begin.