# A graduate student solved the problem of confirming quantum computing

#### Urmila Mahadev spent eight years in the master's program 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 201? 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 computation,” made it “obvious that she is a rising star,” 3-3313 said. Scott Aaronson

, a computer science specialist from the University of Texas at Austin.

Mahadev, who was 28 at the time, had been in the master's program at the University of California at Berkeley for the seventh year — much longer than the period most students need to lose their patience and want to finish their studies. And now, finally, she was able to make "an excellent doctoral thesis," said 3-3319. Umes Vazirani

, her curator at Berkeley.

Records 3r3172. in his blog

Thomas Vidic A computer scientist from the California Institute of Technology, who previously collaborated with Mahadev, called its result "one of the most outstanding ideas that emerged at the intersection of quantum computing and theoretical computer science in recent years."

Researchers in the field of informatics are delighted not only by what the Mahadev protocol is capable of, but also by a radically new approach to help 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.”

3r3185. The long road

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 at Berkeley, in an explanatory note indicating that she was interested in all aspects of theoretical informatics - except for quantum computing.

“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 for Wazirani. He introduced her to the question of finding a protocol to confirm quantum computing, and this task “really made her image work,” said Vazirani.

“The protocols are like puzzles,” explained Mahadev. “It’s easier for me to deal 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 decomposing large numbers into factors - it is believed that a large quantum computer will be able to solve it effectively, 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 result was quantum-correct — 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 simply solve them; it cannot even recognize whether the proposed solution will be correct. As a result, in 200? 3–3–3120. Daniel Gottsman

- a theoretical physicist from 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 says.

For four years, researchers in the field of quantum computing have found a partial answer. Two different teams 3r3131. shown

that 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 201? 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 a 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 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 201? working on another task, Mahadev and Wazirani made a breakthrough, which will later be decisive. Together with 3r3145. By Paul Cristiano

, a computer scientist from OpenAI, a company from San Francisco, 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-in-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 ? 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, because they are confused - for example, if we use the square function, then if the output state is ? 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 201? Mahadev understood how to create trap functions on which the secret state method is based, using cryptography called “3r3167. Training with errors 3r3172.” (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 3r3r1616. Zvika 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 capable of generating 3r3171. provable 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 that interest me, so this pastime cannot be called a waste."

3r3185. Carved into 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 Mahadev understood to make a quantum computer promise to do any specific 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 does the computer know what measurement is needed.

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.

"It's so muchwonderful idea! - wrote Vidic. “She amazes me every time Urmila explains her.”

Mahadev’s confirmation protocol — along with a random number generator and blind encryption — depends on the assumption that quantum computers cannot crack 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, Vidik wrote. The only way in which a quantum computer can fool a protocol is if someone from the world of quantum computing thinks up 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. “It will be possible to start thinking about this topic if everything goes as it should, at the next stage in the 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 need 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 become a 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.”

3r33232. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d! ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () ();

## Comments 1