You lie. You die

 But remember that you’re using a trapdoor function. You have the trapdoor’s secret key, so you can easily figure out the two states that make up the input superposition. But the quantum computer cannot. And it can’t simply measure the input superposition to figure out what it is made of, because that measurement would collapse it further, leaving the computer with one of the two inputs but no way to figure out the other.

In 2017, Mahadev figured out how to build the trapdoor functions at the core of the secret-state method by using a type of cryptography called Learning With Errors (LWE). Using these trapdoor functions, she was able to create a quantum version of “blind” computation(opens a new tab), by which cloud-computing users can mask their data so the cloud computer can’t read it, even while it is computing on it. And shortly after that, Mahadev, Vazirani and Christiano teamed up with Vidick and Zvika Brakerski(opens a new tab) (of the Weizmann Institute of Science in Israel) to refine these trapdoor functions still further, using the secret-state method to develop a foolproof way for a quantum computer to generate provably random numbers(opens a new tab).

Mahadev could have graduated on the strength of these results, but she was determined to keep working until she had solved the verification problem. “I was never thinking of graduation, because my goal was never graduation,” she said.

Not knowing whether she would be able to solve it was stressful at times. But, she said, “I was spending time learning about things that I was interested in, so it couldn’t really be a waste of time.”

Set in Stone

Mahadev tried various ways of getting from the secret-state method to a verification protocol, but for a while she got nowhere. Then she had a thought:: Researchers had already shown that a verifier can check a quantum computer if the verifier is capable of measuring quantum bits. A classical verifier lacks this capability, by definition. But what if the classical verifier could somehow force the quantum computer to perform the measurements itself and report them honestly?

The tricky part, Mahadev realized, would be to get the quantum computer to commit to which state it was going to measure before it knew which kind of measurement the verifier would ask for — otherwise, it would be easy for the computer to fool the verifier. That’s where the secret-state method comes into play: Mahadev’s protocol requires the quantum computer to first create a secret state and then entangle it with the state it is supposed to measure. Only then does the computer find out what kind of measurement to perform.