Urmila Mahadev’s eight–year–long quest to solve the quantum verification problem as a grad student
Let’s say you ask a quantum computer to do something for you, like you would a normal computer. How can you know if it’s done anything at all, let alone the task you asked it to do? In fact, how can you check if a quantum computer’s quantum calculations are actually correct?
This is the “quantum verification problem.” Consider a computer that doesn’t use fancy quantum bits to calculate something: we call this a “classical computer” with its 1s and 0s that can’t simultaneously be both 1 and 0. If you ask a classical computer to do some computation for you, but you don’t actually trust it, you can—in theory—trace its computation history sequentially to “verify” whether the steps are correct. You’ll see each and every 1 and 0 with no assumptions. However, this doesn’t really work for quantum computers. Not only would writing down every step of this “computation history” for a quantum computer require a great deal more space (exponentially more, in general), but you hit another block when it comes to actually checking a quantum state.
Quantum states are often superpositions of “classical states” (so here, superpositions of the classical 1s and 0s would be an example of a quantum superpositional state, and one example of why researchers think quantum computers would be much faster for certain problems). But when quantum states are actually observed, they “collapse” into one of their component classical states, like taking a snapshot in time. How difficult! With all these challenges, how can we actually know whether or not a quantum computer is lying to us?
Starting from her second year of grad school, Urmila Mahadev began to delve into this predicament. It took a lot of trial and error, as is usually the case in trying to tackle these difficult problems with all sorts of different approaches. Six years later, leveraging developments in cryptography, Mahadev was able to develop an effective protocol to conduct a sufficient verification of quantum computation, proving that it was indeed possible. Her paper, titled “Classical Verification of Quantum Computations” won both “Best Paper” and “Best Student Paper” at the Symposium on Foundations of Computer Science, which are incredible distinctions for a grad student researcher.
Mahadev’s ground-shaking result follows in the growing new academic field of quantum cryptography, combining quantum computing, theoretical computer science, quantum mechanics, and cryptography. The growth of computing technology alongside further research developments in quantum mechanics hold many tantalizing possibilities for how to build secure systems using the unique information-related properties of the world at the quantum level, and Mahadev’s massive hunt to move the field monumentally forward will serve as both a future cornerstone and a fantastic example of the ingenuity and diligence of grad student researchers.
Comments are closed.