Quantum Algorithms and the Future of Post-Classical Computing
The era of classical computing is coming to an end, and the scientists are anticipating the arrival of quantum computing be designing ambitious quantum algorithms that tackle maths greatest challenges.
As a millennial elder, I came of age just as the most important human invention since the wheel started showing up in our mailboxes in the mid-1990s: software CDs offering free trials for services like America Online, Compuserve, and Prodigy. Those first exploratory steps into this revolutionary digital space came when we were old enough to clearly remember life before the Internet but still young enough to embrace the technology in ways our parents couldn’t.
We gladly ran up thousand-dollar credit card bills binging on chat rooms, message boards, instant messaging, and other primordial internet content–that’s right kids, back then we had to pay for the Internet by the hour–but that was mom and dad’s problem, we had an entire civilization-altering transition to participate in. Transformational progress on a global scale normally takes time, generations even, to achieve but we pulled it off in less than a decade and spent another decade pushing the limits of what was possible with a computer and an Internet connection and, unfortunately, we began running into those limits pretty quickly.
For all intents and purposes, the Internet is the tour de force of classical computing. Networked together, billions of computers of every shape and size collaborate through algorithms, radio signals, and fiber optic cable to produce a way of life that as far as we know is unique in the universe. Even more incredible is that classical computing accomplished this in less than two generations of human beings, a rate of technological progress without historical precedent.
In the 25 years since Peter Shor published the first quantum algorithm–which showed that prime factorization of integers could be done on quantum computers in polynomial time–mathematicians and computer scientists have developed other quantum algorithms that tackle problems that classical computers struggled to solve. Of those dozens of quantum algorithms, many of them are orders of magnitude faster than the most efficient classical algorithm we know of and are only possible because of the unique quantum environment they operate in.
Some of the most important work in the quantum computing field has been creating algorithms that simulate different quantum systems that pop-up in everything from laser technology to medicine. These algorithms are going to be able to outperform similar classical computing simulations by a wide margin. Currently, classical algorithms that perform molecular simulation are limited in the kinds of molecules that it can simulate. These algorithms are usually restricted to molecules with fewer than 70 spin-orbitals, any more than that, and the complexity of the simulation grows so quickly as to become intractable.
Meanwhile, a single qubit can represent one of these orbitals efficiently enough so that a quantum computer with only 100 qubits–the D-Wave 2X quantum computer has 1152 qubits, though it was built to run a spacific algorithm, not as a general purpose quantum computer–would allow for molecular simulations that classical computers aren’t even close to being capable of simulating and probably never will. These simulations can potentially reveal all manner of previously unknown compounds that can provide novel therapies for any number of diseases.
There are quantum algorithms for everything from depth-first searches and quantum walks over a graph to solving systems of linear equations, differential equations, and even making progress on certain classes of optimisation problems, such as adiabatic optimisation. What these algorithms lack, however, is a sufficiently powerful quantum computer with enough qubits to run.
That won’t be the case forever, though, and when the time comes to take these algorithms off the shelf and put them to work, some of the most frustratingly intractable, exponentially- and factorially-complex problems in business, administration, medicine, engineering, and more will be resolved in superpolynomial time or faster. These gains are the real deal and they’re guaranteed by their logic to work; the only question is just how long it will take for these computers to arrive.
Source:https://interestingengineering.com
