Variational What Now?
Variational What Now?
They are likely to solve valuable industrial problems using imperfect near-term quantum computers.
A class of methods for using near-term quantum computers to solve certain optimization problems.
In the summer of 2016, the buzz around quantum computing was becoming audible outside of the academic community. IBM had just launched its publicly available quantum processor through the IBM Q Experience and many groups were racing to achieve a quantum advantage through Aaronson and Arkhipov’s boson sampling proposal. That buzz provided an encouraging background tune as I worked to finish my Ph.D. and land a postdoc position in quantum computing.
My final postdoc interview was with the Aspuru-Guzik group of the Harvard Chemistry and Chemical Biology department. To prepare, I read through papers from the group. One paper stood out among the rest: “Scalable Quantum Simulation of Molecular Energies”, a collaboration between the Aspuru-Guzik group and Google. The paper described the results of an actual quantum computation on Google’s quantum computer. The quantum computation ran an algorithm called the “variational quantum eigensolver” (VQE), which apparently could be useful for chemistry calculations. I wrestled with two questions as I read the manuscript:
I didn’t fully answer these questions in time for the interview. But, a few months later, I was fortunate to be joining the group as a postdoc. Only through the patient explanations from fellow group members did I start to appreciate the value of this work and the new paradigm in quantum computing that it was creating.
Three years later I can empathize with the person trying to answer the 2019 versions of these questions. Today, not only is Google exploring VQE. The growing quantum industry, including us at Zapata, IBM, Microsoft, Rigetti, etc. are developing this method. And we are not only interested in VQE, but we are exploring a growing suite of other variational quantum algorithms including variational quantum factoring, variational quantum compiling, variational quantum linear systems solver, and many others. I will try to answer the 2019 versions of my 2016 questions:
You may have read about Shor’s factoring algorithm and Grover’s search algorithm. These quantum algorithms make one feel that magic machines are just around the corner. But this enthusiasm quickly melts away when we reach the sobering section on quantum error correction. Shor’s and Gover’s require the quantum computer to do almost exactly what we program it to do– no room for (uncorrected) error. And unfortunately, near-term quantum computers aren’t expected to be correcting errors substantially enough.
Yet, do we need the quantum computer to do exactly what it is programmed to do? Think of a bicycle with slightly misaligned handlebars. Does this prevent you from riding it home? The hopeful answer to this question is no. The pessimistic answer is that we will need substantial quantum error correction for these devices to be useful.
Regardless of the answer, the first to achieve quantum advantage will surely have been those pushing each generation of devices to their limits along the way. Variational quantum algorithms provide a framework for trying to make use of these “along-the-way” quantum computers. This is why companies like Zapata are dedicating themselves to the development and implementation of variational quantum algorithms.
Imagine that you are driving home one night through gnarled and trafficky city streets. Despite being a local, you still pull out your phone and ask Google maps to direct you. Running through all possible routes would require too much computation– orders of magnitude more compute time than Google is willing to spend on you. Nevertheless, it suggests a way home. Is the suggested route the best one? Not always. But the quality is usually enough for practical use.
How does Google maps do this? The app does not search through all possible routes. Instead, it ends up searching through a well-motivated subset of routes and partial routes. An important ingredient to this approach is to use knowledge of the problem to guide the targeting of a well-motivated subset, known as heuristics.
Variational quantum algorithms also use heuristics to generate well-motivated answers to optimization problems. Why are variational quantum algorithms robust to error? The key feature is that error does not affect the validity of the suggested optima. It only alters the quality of the average suggested routes. More error leads to an essentially random search. Less error enables a more targeted search. Despite this error, variational quantum algorithms use the quantum computer as a novel heuristic for discovering better optimization solutions.
We have entered a new era in quantum computing. Commercial application is meeting innovative science. As they say, “necessity is the mother of invention”. The need has been commercial applications for near term quantum computers. The invention has been variational quantum algorithms. Stay tuned as we build from these efforts and work to develop and discover the true potential of quantum computing.
For further reading, examples of variational quantum algorithms are:
Sharing our understanding of the current state of AI and quantum.