What Can Quantum Machine Learning Do?
University of Waterloo, Institute for Quantum Computing and Perimeter Institute
Rotman School of Management, University of Toronto
ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology
[this article was originally published on March 6, 2018 on Quantum Machine Learning weblog]
In August 2017, I participated in the 34th International Conference on Machine Learning, one of the world’s most important academic events in the field of machine learning. I am going to guess I was the only economist-in-training who took a twenty-two-hour trip from Toronto to Sydney to participate in a conference that, at first glance, could not be more irrelevant to economics. But as a researcher interested in micro and macroeconomic implications of the dramatic progress in machine learning research and application, I had my own reasons to make this effort. When I attended the conference, it was only a few months after we had launched the world’s first entrepreneurship program for quantum machine learning startups at the Creative Destruction Lab, and only a couple of weeks before the program officially started in September. So, as Australian Federal Minister of Industry was giving his welcome message to conference participants, I wondered what would happen if I were to go up onto that stage in this enormous theatre full of machine learning scientists, shout, “Quantum Machine Learning,” then freeze time and then read and record everyone’s mind! The most frequent thought I’d see in the audience’s heads is probably something along the lines of “crazy guy!” But apart from that, would at least some of them be intrigued? Or would they ask, “What can this QML of yours do that our classical machine learning can’t?” As it turns out, this is the big question that everyone is asking. Given the newness of this frontier of science, there have been very few people who have found real applications where quantum machine learning significantly outperforms classical machine learning. Nevertheless, here I set out to present an application area in which quantum machine learning can in fact outperform classical machine learning.
In an earlier blogpost, Peter Wittek and I provided a high-level idea about leveraging quantum computers in enhanced machine learning. We also touched on some of the major challenges and opportunities ahead for scientific and technological progress in QML. In order to present an application area in which QML outperforms machine learning, Peter and I teamed up with Roger Melko to dive deeper into one of the application areas in which QML can produce staggering improvements in results over its classical counterpart. Roger is a quantum many-body physics professor at the University of Waterloo and affiliates with the Perimeter Institute and the Institute for Quantum Computing. He is a Chief Scientist at the Creative Destruction Lab and engages in various capacities with the participants of CDL’s program to help them build scalable QML technologies that solve difficult commercial problems left unsolved by our current supercomputers. The case we would like to explore here is the application of QML in the design of chemical compounds. However, in order to fully understand the magnitude of the technological and commercial value of QML in this particular case, it is critical to have an overview of the field of quantum chemistry and the concept of the many-body problem in physics.
Assemblies of electrons, nuclei, magnetic moments, atoms or qubits, such as those encountered in molecules, materials, or quantum computers, are fundamentally complex. This means that understanding the behavior that arises from the microscopic equations of motion is typically intractable, even for numerical simulations performed on massive supercomputers. Manifestations of this complexity are encountered every day by scientists and engineers working on understanding novel matter, materials, devices, and molecules. It is the fundamental roadblock to many areas of progress in science and technology, such as building ultra strong, lightweight materials, superconductors for advanced energy applications, or novel substrates for classical and quantum computing. An everyday manifestation of such complexity is in drug discovery, where investigators routinely have difficulty in predicting the behavior of chemical compounds, like those used in anticancer drugs. In each of these applications, there are so many in-motion particles of so many complex compounds that modeling how each of these particles interact and affect each other is essentially impossible. This complexity has its origins in the size of the quantum state space, which grows exponentially with the number of particles. Such exponential growth is reminiscent of the “curse of dimensionality,” a fundamental problem encountered in many machine learning tasks.
A major goal of quantum chemistry is to predict the structure, stability, and reactivity of molecules. In principle, this requires solving the Schrödinger equation for the many-electron problem. Think of the Schrödinger equation as the only lock that, if you open it, you can predict all the chemical properties of a compound. The exact solution to this equation is very difficult to obtain. In fact, the Schrödinger equation has only been solved for very simple quantum objects, such as the hydrogen atom. In cases involving more particles (“bodies”) than just a proton and an electron, the solution must be approximated - this is the many-body problem in quantum physics. A manifestation of the classical equivalent to the many-body problem is the three-body problem, for example the one involving the moon, the earth, and the sun. The motion for this system of celestial objects does not have an analytical solution - that is, we cannot on paper solve all the ways in which these three masses affect each other. Just recently, two scientists, XiaoMing Li and ShiJun Liao at Shanghai Jiaotong University, China, have determined roughly 600 new families of periodic orbits for such three-body systems.
Back to the quantum case: Calculations for approximating the Schrödinger equation are routinely done in chemistry departments at universities around the world, for a broad range of molecular systems. Typically, various approximation schemes help circumvent the “curse of dimensionality.” However, when one requires a detailed and accurate picture of how all of the electrons interact with each other in a molecule, standard approximations may break down. Therefore, in many important cases, chemists remain in the dark. In order to perform accurate molecular electronic structure calculations, the essential quantum complexity of the many-body electron problem must be tackled. If successful, one would be able to predict the outcome of many chemical reactions, the characteristics of novel drug candidates, the properties of new materials, and even the structures and behaviour of the building blocks of life such as proteins, sugars, and DNA.
This leads us to the question, “What kind of computer are we going to use to simulate physics?” This is the question Richard Feynman asked in his lecture on quantum computing in 1981. He proposed the idea that with a suitable class of quantum computers one could imitate any quantum system, including the ones seen in chemistry. Feynman wondered whether quantum physics could be simulated by a universal computer - that is, a computer that can perfectly simulate nature. He was specifically encouraging people who are trying to build computer simulations of the world to think about quantum mechanics and look at computers from a different point of view. Seth Lloyd, a physics professor at MIT and a Chief Scientist at the Creative Destruction Lab, was the first scientist to confirm that exponential speedups for simulations using quantum computers are possible. Lloyd is also a pioneer of the idea of quantum-enhanced machine learning. An interesting challenge here is that problems such as those in many-body physics are so complex that we must resort to gross simplifications in order to run simulations on classical computers. In the process, we lose properties that affect both the quantitative and the qualitative aspects of the simulation. Just recently, though, a group of researchers led by ETH professors Markus Reiher and Matthias Troyer showed that in fact a quantum computer with a number of qubits that is within reach for early quantum devices can calculate the reaction mechanism of a complex chemical reaction in a few days. The researchers chose an enzyme called nitrogenase, which enables certain microorganisms to split atmospheric nitrogen molecules. The reaction is so complex that it is nearly impossible to know exactly how it works and it remains as one of the greatest unsolved mysteries in chemistry.
The last missing piece of the puzzle is what learning algorithms bring to the table. Reinforcement learning is a form of machine learning related to optimal control theory: it allows a learning algorithm to control some system under consideration without having an explicit model of the system. A paradigmatic example is playing Atari games: just by looking at the screen and poking the controls, a reinforcement learning agent can achieve superhuman performance. When it comes to quantum systems, reinforcement learning forms a transition point between the classical and the quantum regimes.
To begin with, we can use reinforcement learning for classical learning and for control over quantum systems. For instance, we can use a learning algorithm to adapt to external noise in quantum computing or to compensate for decoherence, but also for estimating parameters in an unknown quantum process. Taking this idea further, we can quantize reinforcement learning. Quantum-enhanced reinforcement learning algorithms for large-scale quantum information processing systems are likely to be a major application area of quantum machine learning. Going back to our earlier example of drug discovery, we can run a quantum simulation of the chemical compounds in question and apply a quantum reinforcement algorithm to drive the search towards a particular goal. Integrating quantum simulations and quantum machine learning can take quantum many-body physics and quantum chemistry to the next level, where a quantized reinforcement learning algorithm would drive the discovery of new materials through their quantum mechanical properties.
In summary, many important problems in quantum many-body physics, from materials design to drug discovery, suffer from an exponential “curse of dimensionality,” which makes them intractable to standard computational methods. Will machine learning be able to lift this curse? As pointed out by Feynman and others, some of such intractability can be overcome with quantum hardware, the likes of which we can almost see on the horizon today. What new discoveries will this hardware bring to the quantum many-body problem? Finally, will the combination of quantum hardware and machine learning - i.e., “quantum machine learning” - provide new, unprecedented power to tackle the Schrodinger equation? Perhaps some fledgeling startup team at CDL will be the first to find out.