A Quantum Leap in Verification
On October 7th 2018, Urmila Mahadev, a graduate student in computer science at University of California, Berkeley, presented a breakthrough algorithm with the power to change quantum computing as we know it. Dr. Thomas Vidick, a professor at the California Institute of Technology and past collaborator with Mahadev on quantum computing, declared Mahadev’s discovery “one of the most outstanding ideas… at the interface of quantum computing and theoretical computer science in recent years.” At the Symposium of Foundations of Computer Science, Mahadev’s work was awarded prizes for both best paper and best student paper. Mahadev also won the small yet prestigious $25.00 Aaronson prize of well-known researcher Dr. Scott Aaronson for solving the problem of “quantum verification,” posed way back in 2004.
Yet before we can dive into what makes this breakthrough truly phenomenal, it is worth first reviewing the foundations of quantum computing. Traditional computers, like the phone, desktop, or laptop you’re reading this article on, work by representing data as bits, or ones and zeros. Everything from the text you’re reading right now to each file on your hard drive is encoded as a series of these ones or zeros, stored in the circuitry of your computer. Qubits, or quantum bits, use the quantum properties of atoms to store a combination of both one and zero at the same time. By taking advantage of the fact that qubits can store not just one or zero, but combinations of both at the same time, quantum computers can perform several calculations at once, speeding up computations dramatically.
Nonetheless, quantum computers have one major big drawback: they’re hard to inspect. They manage to store a lot of information in very few qubits, and worse, the act of observing them forces them out of their combination and into either zero or one, breaking the computation the quantum computer was performing.
With this in mind, how do we ensure a quantum computer does what we told it to? Methods exist to check that traditional computers perform what they say they will, but since quantum computers entirely collapse when observed, it seems impossible to keep them honest. And keeping them honest is important. For instance, imagine you are a medical researcher trying to discover a drug to inhibit a certain chemical pathway in humans. It’s five years in the future, and drug discovery is still a very computationally hard problem, so you connect your laptop to the giant quantum computer in your lab and start running simulations. But for all you know, this black-boxed behemoth could be lying to you or simply broken inside. You need to get busy doing life-saving research, but also make sure that your results are correct. Mahadev’s algorithm allows for just this.
By using special encryption that even quantum computers can’t break, Mahadev found a way to verify–with a traditional computer–that a quantum computer performs exactly the computations requested of it. Several researchers had previously been able to show that verification of quantum computers was possible if the traditional computer was able to communicate with a small, trusted quantum sidekick, or if the quantum computer being verified was actually two separate computers unable to talk to each other. Mahadev was the only one able to show that neither of these conditions are needed.
The key, unique insight in Mahadev’s work was to use post-quantum cryptography. Although it hasn’t been proven yet, certain ways of encoding information are thought to be so secure that even a quantum computer with the right algorithm couldn’t decode data encoded by them in a reasonable amount of time (see here for more on what “reasonable” means). The nice thing about the use of post-quantum cryptography, as Vidick notes, is that it provides a win-win: for someone to break Mahadev’s algorithm, they’d have to discover a way of breaking cryptography previously thought to be unbreakable in a reasonable timespan, a rather incredible feat itself.
The post-quantum cryptography algorithm that Mahadev’s paper used is known as Learning With Errors, or LWE. The basis of LWE is that, given a secret list of numbers, one can quickly put together equations based on those numbers with approximate answers very quickly. If we give exact answers, then solving for these numbers is pretty fast too. But if we give approximate answers, it takes far longer to estimate the secret numbers accurately. This asymmetry between ease of building the equations and difficulty of solving them lets us hide secrets from prying eyes.
Since a classical computer can encode a message with LWE that a quantum computer can’t decode, we can use LWE to transform our data into a form that the classical computer can read but the quantum computer cannot. The quantum computer can still perform calculations on the data as told, but it has no ability to do anything malicious since it can’t get any information from the data it’s working on. It’s as if I gave you a paragraph in French, and a step-by-step guide on how to translate it to German, but you spoke neither language. All together, by using these “secret states,” as they’re called, Mahadev developed a way to ensure that the quantum computer does exactly what it’s told to a tee.
While this result appears to be the solution to a major problem, it holds the promise of many more exciting results to come, including faster versions and physical, real implementations of Mahadev’s work. With this comes the promise of verifiable quantum computation, and the assurance that the computers that perform critical, life-saving work in the near future do exactly what we tell them to.
- Klarreich, Erica. “Graduate Student Solves Quantum Verification Problem.” Quanta Magazine October 8, 2018. Print.
- Mahadev, Urmila. “Classical Verification of Quantum Computations”. FOCS 2018. October 7-9, 2018, IEEE Computer Society , October 7, 2018. 259-267. Print.
- “The Quantum Wave in Computing.” Quantum Frontiers. August 5, 2018. Web. November 7, 2018 <https://quantumfrontiers.com/2018/08/05/the-quantum-wave-in-computing/>.
- Regev, Oded. The Learning with Errors Problem. Web. November 7, 2018 <https://cims.nyu.edu/~regev/papers/lwesurvey.pdf>.