Graduate student solved the problem of confirming quantum computing

Urmila Mahadev spent eight years in the magistracy in search of an answer to one of the most basic questions of quantum computing: how do we know that the quantum computer did at least something at the quantum level?

In the spring of 2017, Urmila Mahadev was in a good position, in terms of the majority of graduate students. She has just solved the most important problem of quantum computing - the field of computer studies, deriving its capabilities from the strange laws of quantum physics. Together with her earlier works, Mahadev's new result, describing the so-called. “Blind calculations,” made it “obvious that she is a rising star,” said Scot Aaronson , a computer scientist at the University of Texas at Austin.

Mahadev, who was 28 at the time, had been in the magistracy at the University of California at Berkeley for the seventh year — much longer than the term most students need to lose their patience and want to finish their studies. And finally, she was able to make "an excellent doctoral thesis," said Umes Vazirani , her curator at Berkeley.

But Mahadev did not finish studying that year. She does not even consider this question. She hasn't finished yet.

For more than five years she worked with another research task, which Aaronson called "one of the most basic questions that can be asked in the field of quantum computing." Namely: if you ask a quantum computer to perform a calculation for you, how do you know if it follows your instructions, and in general, does it do something at the quantum level?

This question may soon cease to be purely academic. Researchers hope that it will not take many years, and quantum computers will be able to offer exponential acceleration in solving a variety of problems, from simulating a situation in the vicinity of a black hole to simulating the coagulation of large proteins.

But as soon as a quantum computer can perform calculations that the classic is not capable of, how can we know that it is conducting them correctly? If you do not believe the usual computer, in theory you can carefully examine each step of its calculations on their own. But quantum computers inherently resist such checks. To begin with, their work is extremely difficult: to record a description of the internal state of a computer, consisting of only a few hundred quantum bits, or qubits, you will need a hard disk larger than the observed Universe.

And even if you had a place to write this description, it could not be disassembled. The internal state of a quantum computer is usually a superposition of many not quantum, but classical states (as in the Schrödinger cat, which is both alive and dead). But as soon as you measure the quantum state, it will immediately collapse into one of the classical ones. Take a look inside a 300-qubit quantum computer - and you will only see 300 classic bits, zeros and ones politely smiling back at you.

“A quantum computer is powerful, but mysterious,” said Vazirani.

Given these limitations, computer scientists have long thought about whether a quantum computer can provide an absolutely reliable guarantee that it actually did what it says. “Will the interaction between the quantum and classical worlds be strong enough to make such a dialogue possible?” Asked Dorit Aharonova , a computer science specialist from the Hebrew University of Jerusalem.

In the second year of the magistracy Mahadev captured this task, and she does not even quite understand why. In subsequent years, she tried to use one approach to her, then the other. “I had many such moments when it seemed to me that I was doing everything correctly, and then everything broke - either very quickly, or in a year,” she said.

But she refused to give up. Mahadev demonstrated such a level of unwavering determination that Vazirani had never met before. “In this sense, Urmila is quite extraordinary,” he said.



And now, after eight years of master's degree, Mahadev succeeded. She created an interactive protocol with which a user who does not have quantum capabilities, however, can, with the help of cryptography, curb a quantum computer and send it anywhere, having full confidence in who the quantum computer obeys orders. Mahadev’s approach, Wazirani said, gives the user "a pressure lever that the computer cannot get rid of."

“It’s absolutely amazing” that a graduate student was able to achieve this result alone, said Aaronson.

Mahadev, now a postdoc researcher at Berkeley, presented her protocol in October 2018 at the annual Symposium on the Basics of Computer Science , one of the largest computer conferences that was held this year in Paris. The participants awarded her work with prizes “the best work” and “the best student work” - a rare award for a specialist in theoretical computer science.

The entry in his blog , Thomas Vidic , a specialist in computer science at the California Institute of Technology, in the past collaborated with Mahadev, called it the result of "one of the most outstanding ideas that have emerged at the intersection of quantum computing, and theoretical computer science in recent years."

Researchers in the field of informatics are pleased not only with what the Mahadev protocol is capable of, but also with a radically new approach that helps to cope with this problem. Using classical cryptography in the quantum field is “a truly innovative idea,” wrote Vidic. “I think that many other results will grow on these ideas.”

Long way

Mahadev grew up in Los Angeles, in a family of doctors, and studied at the University of Southern California, where she moved from one area to another, initially convinced only that she herself did not want to be a doctor. Then she became very interested in the course of theoretical computer science, which was led by Leonard Eidlman, one of the creators of the famous RSA encryption algorithm. She entered the magistracy in Berkeley, in an explanatory note indicating that she was interested in all aspects of theoretical informatics - except for quantum computation.

“It was something completely alien, which I had the least idea about,” she said.

But, having got to Berkeley, she soon changed her mind under the influence of the available explanations of Wazirani. He introduced her to the issue of finding a protocol for confirming quantum computing, and this task “really made her imagination work,” said Vazirani.

“Protocols are like puzzles,” explained Mahadev. “It's easier for me with them than with other issues, because here you can immediately start thinking about the protocols, breaking them into pieces, and watching how they work.” She chose this task for her doctoral, taking a “very long way,” as Vazirani said.

If a quantum computer can solve a problem that the classic is not capable of, this does not automatically mean that the solution will be difficult to verify. Take, for example, the problem of expanding large numbers into factors - it is believed that a large quantum computer can solve it efficiently, but it remains beyond the capabilities of any classical computer. But even if a classic computer is not capable of factoring out a number, it can easily check whether the correct result was obtained quantum — it just needs to multiply all the factors, and see if they give the correct answer.

However, computer scientists believe (and have recently taken a step towards proof) that many tasks that a quantum computer could solve are devoid of such a feature. In other words, a classic computer cannot just solve them; it cannot even recognize whether the proposed solution will be correct. As a result, in 2004, Daniel Gottsman , a theoretical physicist at the Perimeter Institute in Waterloo, asked if it was possible to come up with any protocol by which a quantum computer could prove to a non-quantum observer that he actually did what he said.



For four years, researchers in the field of quantum computing have found a partial answer. Two different teams showedthat a quantum computer can prove its calculations, but not to a purely classical verifier, but to one that has access to another, very small quantum computer. Later, the researchers improved this approach, showing that the verifier needs only the ability to measure the state of one qubit at a time.

And in 2012, a team of researchers, which included Wazirani, showed that a completely classical verifier could verify quantum computations if they were carried out by a pair of quantum computers that did not communicate with each other. However, their approach was specifically designed for such a scenario, and the task seemed to be stumped, Gottsman said. "I think that, probably, there were people who thought that they could not go any further."

Around this time, Mahadev was faced with the problem of confirmation. At first, she tried to produce an "unconditional" result, without assumptions about what the quantum computer can and cannot do. But, after she had been working on the task without success for some time, Vazirani suggested instead the possibility of using “post-quantum” cryptography - that is, cryptography, which, according to the researchers, is beyond the capabilities of even quantum computers, though they do not know. (Methods such as the RSA algorithm used to encrypt online transfers are not post-quantum - a large quantum computer can crack them, because their security is based on the difficulty of factoring large numbers).

In 2016, working on another task, Mahadev and Wazirani made a breakthrough, which will later be decisive. Together with Paul Cristiano , a computer scientist from OpenAI, a San Francisco company, they developed a way to use cryptography to make a quantum computer go into a “secret state” —a state whose description is known to the classical verifier, but not the quantum computer itself. .

Their procedure is based on a “trap” function — one that is easy to perform, but hard to reverse, unless you have a secret cryptographic key. (At that moment, the researchers did not know how to make a suitable trap - it came later). The function must also have a two-to-one property, which means that for each set of output data there are two different sets of input data. For example, you can imagine a function that squares numbers — apart from the number 0, for each result (for example, 9) there are two corresponding input numbers (3 and -3).

Armed with such a function, you can force a quantum computer to go into a secret state as follows. First, you ask the computer to build a superposition of all possible inputs to the function (this may seem like a daunting task to the computer, but in fact it is simple). Then you tell the computer to apply the function to this gigantic superposition, creating a new state, which is the superposition of all possible output of the function. The superpositions of input and output will be confused, which means that measuring one of them will instantly affect the other.

Then you order the computer to measure the final state and report the result. The measurement collapses the state to one of the possible output data sets, and the input state collapses to match it as they are confused - for example, if we use the square function, then if the output state is 9, then the input state collapses to superposition 3 and -3.

But remember that we use the trap function. We have a secret key for a trap, so we can quite easily recognize the two states that make up the input superposition. A quantum computer can not. And he cannot simply measure the input superposition to find out what it consists of, since such a measurement will collapse it even further, leaving the computer with one of two options, without being able to calculate the other.

In 2017, Mahadev understood how to create trap functions on which the secret state method is based, using cryptography called “ learning with errors ” (LWE). With the help of such trap functions, she was able to create a quantum version of blind computing, with which cloud computing users can hide their data so that cloud computers cannot read it, even if they perform calculations with them. Soon after, Mahadev, Wazirani and Cristiano teamed up with Vidik and Zwika Brakerski (from the Weizmann Institute in Israel) to further improve the quality of these functions, and use the secret state method to develop a guaranteed way that a quantum computer is able to generate provably random numbers.

Mahadev could get a degree on the basis of such results, but she set out to continue working until she solved the problem of confirmation. “I never thought about releasing because my goal was not release at all,” she said.

Sometimes uncertainty in the ability to solve this problem pressed on her. But, she said, "I spent my time teaching things I was interested in, so this pastime can not be called a waste."

Carved in stone

Mahadev tried to use different approaches to the secret state method for organizing the confirmation protocol, but for some time this did not lead to anything. And then she got the idea: the researchers have already shown that the verifier can check a quantum computer, if he has the ability to measure quantum bits. By definition, a classic verifier does not have this possibility. But what if a classic verifier could somehow force a quantum computer to take measurements on its own and honestly report their results?

The difficulty will be how Makhadev understood to make a quantum computer promise to make any particular measurement before he finds out what kind of measurement the verifier asks him - otherwise the computer will be very easy to deceive him. This is where the secret state method comes into play. The Mahadev protocol requires the quantum computer to first create a secret state, and then to confuse it with the state that it should measure. And only then the computer will know what measurement needs to be taken.

Since the computer does not know the internal details of the secret state known to the verifier, Mahadev showed that the quantum computer could not cheat in any way without leaving undoubted traces of this. In fact, Vidic wrote, the qubits, which need to be measured by a computer, are “carved on a cryptographic stone”. Therefore, if the measurement results appear to be correct evidence, then the verifier can be sure that it is.

“This is such a wonderful idea! - wrote Vidic. “She amazes me every time Urmila explains her.”

Mahadev’s confirmation protocol — along with a random number generator and a blind encryption method — depend on the assumption that quantum computers cannot break into LWE. So far, LWE is widely regarded as the leading candidate for post-quantum cryptography, and soon the National Institute of Standards and Technology can approve it as a new cryptographic standard, with a substitute for being cracked with a quantum computer. But this is no guarantee that it is actually safe against quantum computers, Gottsman warned. “But so far everything is clear,” he says. “No one has yet found evidence of the possibility of hacking.”

In any case, the confidence of the protocol in LWE makes Mahadev's work advantageous anyway, Vidic wrote. The only way a quantum computer can fool a protocol is if someone from the quantum computing world comes up with how to hack LWE, which in itself will be a remarkable achievement.

The Mahadev Protocol is unlikely to be implemented on a real quantum computer in the foreseeable future. So far he needs too much computational power from a practical point of view. But in the future this may change when quantum computers grow, and researchers rationalize this protocol.

The protocol is unlikely to appear within, say, the next five years, but “this is not such a science fiction,” said Aaronson. “We can already start thinking about this topic if everything goes as it should, at the next stage of development of quantum computers.”

And, given how quickly this area is developing, this stage may come earlier than expected. After all, only five years ago, Vidic said, the researchers believed that until quantum computers could solve any problem that classical computers are not capable of, it would take many more years. "And now," he said, "people believe that this will happen in a year or two."

Mahadev, having solved his favorite task, remained in a somewhat confused state. Mahadev says she would like to understand what exactly made this problem so suitable for her. "Now I have to look for some other question, so it would be nice to find out." But experts in theoretical computer science consider the combination of quantum computing and cryptography, which Mahadev succeeded in, not the end of history, but only the beginning of the study of what might be the rich source of new ideas.

“It seems to me that many derivative ideas will follow,” said Aaronson. “I look forward to new results from Urmila.”