Algorithms for Quantum Computers
Within a few years quantum computers could catch up to or even outperform classical computers thanks to significant work on hardware and the algorithms to run on it.
Quantum computers exploit quantum mechanics to perform calculations. Their basic unit of computation, the qubit, is analogous to the standard bit (zero or one), but it is in a quantum superposition between two computational quantum states: it can be a zero and a one at the same time. That property, along with another uniquely quantum feature known as entanglement, can enable quantum computers to resolve certain classes of problems more efficiently than any conventional computer can.
This technology, while exciting, is notoriously finicky. A process called decoherence, for example, can disrupt its function. Investigators have determined that stringently controlled quantum computers that have a few thousand qubits could be made to withstand decoherence through a technique known as quantum error correction. But the largest quantum computers that laboratories have demonstrated so far—the most notable examples are from IBM, Google, Rigetti Computing and IonQ—contain just tens of quantum bits. These versions, which John Preskill of the California Institute of Technology named noisy intermediate-scale quantum (NISQ) computers, cannot perform error correction yet. Nevertheless, a burst of research on algorithms written specifically for NISQs might enable these devices to perform certain calculations more efficiently than classic computers.
Increased access to NISQ machines for users around the world has contributed greatly to this progress, enabling a growing number of academic researchers to develop and test small-scale versions of programs for the machines. An ecosystem of start-up companies focused on different aspects of quantum software is blossoming as well.
Researchers see particular promise in two kinds of algorithms for NISQs—those for simulation and for machine learning. In 1982 the legendary theoretical physicist Richard Feynman suggested that one of the most powerful applications of quantum computers would be simulating nature itself: atoms, molecules and materials. Many researchers, myself included, have developed algorithms to simulate molecules and materials on NISQ devices (as well as on the fully error-corrected quantum computers of the future). These algorithms could enhance the design of new materials for use in areas ranging from energy to health science.
Developers are also assessing whether quantum computers would be superior at machine-learning tasks, in which computers learn from large data sets or experience. Tests of a rapidly growing set of algorithms for NISQ devices have shown that quantum computers can indeed facilitate such machine-learning tasks as classifying information by categories, clustering similar items or features together, and generating new statistical samples from existing ones—for instance, predicting molecular structures likely to display a desired mix of properties. At least three research groups have independently reported progress in developing quantum versions of a machine-learning approach known as generative adversarial networks (GANs), which has taken the machine-learning field by storm in the past several years.
Although a number of algorithms do seem to work well on existing NISQ machines, no one has yet produced formal proofs that they are more powerful than those that can be performed on conventional computers. These proofs are difficult and can take years to complete.
In the next few years researchers most likely will develop larger and more controllable NISQ devices, followed by fully error-corrected machines with thousands of physical qubits. Those of us working on algorithms are optimistic that algorithms for NISQ will be effective enough to achieve an advantage over state-of-the-art conventional computers, although we might have to wait until fully error-corrected machines are available.