Why This Quantum Pioneer Thinks We Need More People Working on Quantum Algorithms
By Olivia Lanes and Robert Davis
There are a lot of classical computer algorithms — probably too many to count. However, researchers have so far devised perhaps only dozens of algorithms for quantum computers. One might assume this is because the first classical algorithm meant to be run on a machine was published over 150 years ago, while the first quantum algorithms didn’t appear until the past few decades. But maturity isn’t the only reason for the discrepancy, according to quantum computing pioneer Dorit Aharonov.
Dorit Aharonov is widely considered to be one of the world’s leading experts in quantum algorithms. She has been a member of the quantum computing research community since the late 1990s, and was one of the key architects of the quantum threshold theorem, a cornerstone of the field whose implication is that we can correct errors provided our hardware is good enough. Aharonov has had a front-row seat to more than two decades of advances in quantum computing, so it’s no surprise she has strong opinions about the current state of quantum algorithm research. In a recent interview, she made a compelling case as to why quantum computing needs many more researchers contributing to quantum algorithm development.
“Today’s quantum ecosystem is extremely vibrant, and there is a lot of energy and focus on particular questions,” Aharonov said. “I think there are advantages and disadvantages to that. I would like to see more stamina from the community when it comes to looking into the more difficult questions that have less immediate reward — like, for example, deeply understanding quantum algorithms.”
The Arduous Hunt for Quantum Advantages
Aharonov has long argued that, despite all its progress, the quantum computing research community still understands relatively little about devising quantum algorithms that offer meaningful advantage over classical methods. “Quantum algorithmic advantage manifests when two conditions are met,” Aharonov said. “One is that quantum computation can somehow access some structure in the problem, and two is that classical computation cannot — or it’s not easy for it to access that structure.” The challenge is that today’s researchers only know of a handful of problem structures that meet those criteria.
To understand how particular kinds of problem structures enable quantum advantage, one need look no further than the most famous example of algorithmic advantage in all of quantum computing: Shor’s algorithm. In classical computer science, there is no known efficient method for finding the factors of large integers — a fact which undergirds much of modern cryptography. However, factorization is a highly structured problem, as evidenced by the fact that any factorization problem can be reduced to what is known as a period finding problem. Unlike classical computers, quantum computers can employ the properties of quantum superposition, entanglement, and interference to solve period finding problems relatively efficiently. This means that factoring large integers meets both of the conditions for quantum advantage: It has a problem structure that quantum computing can access, and that classical computing cannot — at least, not as far as we know.
Quantum researchers have so far found only a few additional problem structures that lead to quantum advantage — examples include linear equations and certain types of highly symmetric systems. Aharonov feels there is still a great deal of work to be done. “We don’t really understand what are the structures that quantum computation can grasp and classical computation cannot,” she said. “I think there is probably a plethora of other structures which quantum computation can somehow access with an exponential advantage, and we still don’t see them.”
When asked why there aren’t more researchers working to develop new approaches to quantum algorithms, Aharonov offers a simple explanation: It’s very, very difficult.
To be sure, there are many people working today on certain types of quantum algorithms, such as VQE algorithms and quantum approximation optimization algorithms (QAOA). However, Aharonov says that the search for new approaches to quantum algorithm design have not received the same attention in recent years. She suggested that researchers may avoid these areas because they require deep knowledge of many different topics in advanced mathematics, including combinatorics, random walks, and group representation theory, to name just a few.
“The thing is that people have tried a lot with few successes, but I don’t think that too many people have tried enough,” Aharonov said. “I think there are more algorithms down that road — very interesting ones — but it will probably be difficult to come up with them.”
For Aharonov, the depth and breadth of the mathematical theory that fits into quantum computing research is one of the key qualities that makes quantum computation so distinct from other areas of computer science.
“One very, very interesting thing about quantum computation is that it touches so many different fields in mathematics,” she said. “It’s not like that in classical computation. It’s really something that is special for quantum computation because it’s somehow ‘complete’ — quantum computation is some kind of completion, mathematically, of classical computation. I think of this as maybe similar to the fact that the complex numbers are an algebraic closure of the real numbers. And quite similarly again, the problems in the quantum model often have richer connections between them; they somehow ring ‘right,’ mathematically.” This, ultimately, is why Aharonov feels quantum computation is so beautiful.
“There are so many different universal models of quantum computers, each one based on a completely different algorithmic approach — like adiabatic computation, quantum walks, measurement-based quantum computation, topological quantum computation, and more — and they are all essentially equivalent,” she said. “You don’t really know which direction the next quantum algorithm will come from.”
Ideas at the Forefront of Quantum Computation
While Aharonov would like to see more researchers joining the search for new quantum algorithms and new problem structures that are amenable to quantum computation, she also believes there are a lot of people currently doing excellent work in the field. As a recent example, she points to a 2021 paper by András Gilyén, Matthew Hastings, and Umesh Vazirani that offers new insight on a form of quantum computing called “stoquastic adiabatic quantum computation.”
Adiabatic quantum computation (AQC) centers on controlling the gradual evolution of a quantum state over time, such that a given input state evolves into a state representing the desired solution. This is in contrast to gate-based models of quantum computation, which take input data and derive solutions by applying specific gate operations to that data. AQC was originally created to solve optimization problems, but researchers have since figured out how to employ it for just about any category of quantum algorithm — meaning it could one day become an alternative to gate-based models for universal quantum computation. (And indeed, Aharonov herself published a paper in 2007 proving this to be the case.) Stoquastic adiabatic quantum computation simply refers to cases of AQC where the Hamiltonian matrix that describes the total energy of the quantum system does not have the “sign” problem, meaning that all of the off-diagonal elements in the Hamiltonian matrix are real, non-positive (i.e., negative) numbers.
Stoquastic Hamiltonians are common in nature, and they are easier to work with than other kinds of Hamiltonians. However, it’s an open question as to whether universal AQC is possible with a stoquastic Hamiltonian, or whether stoquastic adiabatic optimization is capable of achieving an exponential speedup over classical optimization techniques. In their paper, Gilyén et al. were able to demonstrate a sub-exponential speedup for a stoquastic AQC algorithm that searches an undirected graph with vertices labeled by n-bit strings to find a specific “Exit” vertex given the “Entrance” vertex.
That’s a significant achievement, but Aharonov notes that it comes with a few important caveats. For one thing, it’s important to bear in mind that the researchers’ results concern a contrived “toy” problem, rather than a problem whose solution might provide some real-world value. Still, Aharonov believes the paper could lead to important insights.
“Previous papers, and in particular Hastings’ first papers on topological obstructions, manage to show that stoquastic adiabatic computation is capable of understanding something about the global structure of a problem. The Gilyén, Hastings & Vazirani paper actually manages to show that this could lead to a provable, almost-exponential advantage! I think this is very interesting,” Aharonov said, adding that further study could improve our understanding of how AQC with stoquastic Hamiltonians is able to understand the topological or global structures of the Hamiltonian, or of the graph upon which the Hamiltonian is defined.
(For more on this subject, see the previous Hastings paper on topological obstructions Aharonov mentions, here. See also follow-up works by Stephen P. Jordan and others, here and here.)
Aharonov suggested that the Gilyén et al. paper raises new hopes about how strong adiabatic stoquastic Hamiltonian computation really is — though providing stoquastic adiabatic quantum algorithms for more practical problems may prove challenging. “The Gilyén, Hastings and Vazirani algorithm might be very impractical in the sense of just implementing it,” she said, “even if just for demonstrations.”
Chart Your Own Path
It will take much more research to answer questions such as those raised by the Gilyén et al. paper. However, Aharonov suggests that the beauty and elegance of quantum algorithms makes the pursuit of these answers well worth the effort. Asked to name an example of something from the field of quantum algorithms that she finds especially striking, Aharonov turned to what she says is a common favorite among quantum computing researchers, Kitaev’s Phase Estimation algorithm.
“The phase estimation algorithm demonstrates one particularly amazing feature or ability in quantum algorithms, which is the ability to use a single quantum bit, entangled to no matter how large a quantum system, to estimate the inner product between two possible states of that system. So if you have two states, which could each be as complex as a description of the entire universe, and you entangle them to a single qubit, the state of that qubit somehow manages to know something about the inner product of these two extremely complicated states.”
For Aharonov, it’s observations like these that make the search for new quantum algorithms so rewarding, and she is hopeful that more researchers will join the hunt. However, she also hopes those researchers will resist the urge to follow the crowd, focusing all their energy on the topics and questions that are receiving the most attention. “I’m sure that there are many, many questions that someone original and creative could think about, and that no one else is interested in,” Aharonov said. “So I would say invent your own questions. Think about the questions, not just about the answers. When it comes to quantum computing, I believe that some of the most interesting questions have not yet been asked.”
References
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2008). Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation. In SIAM Review (Vol. 50, Issue 4, pp. 755–787). Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/080734479
Bringewatt, J., Dorland, W., Jordan, S. P., & Mink, A. (2017). Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians. ArXiv. https://doi.org/10.48550/ARXIV.1709.03971
Gilyén, A., Hastings, M. B., & Vazirani, U. (2021). (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. ACM. https://doi.org/10.1145/3406325.3451060
Hastings., M. B. (2013) Obstructions to classically simulating the quantum adiabatic algorithm. In Quantum Info. Comput. 13. https://dl.acm.org/doi/10.5555/2535639.2535647
Jarret, M., Jordan, S. P., & Lackey, B. (2016). Adiabatic optimization versus diffusion Monte Carlo methods. In Physical Review A (Vol. 94, Issue 4). American Physical Society (APS). https://doi.org/10.1103/physreva.94.042318
