Although the power of classical computers has increased by millions of times over the past sixty years, there are still many problems that are too complex to solve. Even though we know how to write a program that would eventually arrive at a solution, it would take that program billions of years before it would finish. Two examples, of well know problems would include finding the prime factors of a 2048 bit RSA key or the well-known travelling salesman problem that everyone learns in school. As the number of bits in the RSA key or the number of cities for the travelling salesman increases, the number of operations required to compute a solution increases exponentially. There are many such problems of this nature including the areas of general optimizations, machine learning, protein folding, and quantum simulation.
There is a whole branch of computer science dealing with this called computational complexity and various algorithms have been classified as to whether they run in polynomial time or exponential time. Quantum computers take advantage of the inherent parallelism that can be obtained with a qubit in a superposition state and various clever algorithms have been developed to speed up the solution to these problems. A simple example is Grover’s algorithm that will perform a data base search. In a classical computer computer if you have have an unordered data base with N items it will take an average of N/2 comparisons. Before you find a specific item in the data base. Using Grover’s algorithm on a quantum computer it would take the square root of N operations to find that item. So a data base with 1 million items in it could be search with 500,000 operations on a classical computer and only 1,000 operations on a quantum computer for a factor of 500 speed-up. This speed-up factor get larger as the number of data base items increase.
By leveraging these type of speed-ups quantum computers will be able to solve problems that were previously unsolvable on classical computers.