Grad Student Solves Quantum Verification Problem

Since its theoretical inception in the 1980s, quantum computing has been touted as the next great leap in information technology. By exploiting the strange properties of quantum particles, quantum computers could theoretically perform operations that would be impossible or take an extremely long time on a classical digital computer.

However, despite recent advancements in quantum computing technology, there is still a lingering, pressing question regarding the technology: namely, if you ask a quantum computer to perform a computation for you, how do you know that it has actually done what you instructed, or done anything “quantum” at all?

The question might sound academic, but it points out a potentially problematic feature of quantum computing systems. If you distrust a regular computer, you could theoretically open it up and check each step of the computation for yourself to verify that the computer actually did what it was told to do. Not so with quantum computers. The inner state of a quantum computer consists of a superposition of classical states. So, if you tried to observe the inside of a quantum computer, the superposition would collapse into one definite state. In other words, if you peeked under the hood so to speak, of a 300 qubit quantum computer, all you would see is a 300 classical bits—1s and 0s. Quantum computers by nature have this “black box” feature, so how, then, is one supposed to verify that a quantum computer is actually performing the operation one thinks it is?

Now, a grad student from UC Berkley may be on the cusp of solving this long-standing problem in quantum computing. In a recent paper, Urmila Mahadev, a graduate student in the physics department at the Univesity of California Berkely, outlines an interactive protocol that allows a completely classical observer to verify without a doubt that a quantum computer is doing what it is supposed to be doing. The protocol involves the construction of a “secret state” in the quantum computer—a state whose description is known to the classical verifier but not to the quantum computer itself. The quantum computer then entangles the secret state with the state it is supposed to measure. Once the computer measures the intended state, both the measured state and the secret state collapse to one definite classical state. Since the computer does not know the makeup of the secret state but the classical verifier does, by checking the results of the operation the verifier can determine if the quantum computer actually performed the operation it was asked. The paper can be read in full on the preprint publication arXiv.

Black Boxes And Secret States

Quantum computers by their very nature are secretive. Classical computers store information in binary bits which take on a value of either 1 or 0. Quantum computers, on the other hand, store information in qubits, which can take on a value of 1, 0 or a superposition of the two. After constructing two superposition qubits, the quantum computer will entangle those two qubits so that measurements of those states will always correlate with each other. Measuring one qubit will instantaneously collapse the superposition in the entangled qubit to a definite state which can allow for fast and powerful computations. This design leads to an epistemic problem though; any attempt to observe a quantum computer while it is operating will collapse the entangled qubit superpositions so it will appear to the observer as if the computer is just behaving like a classical computer.

The question of whether it is possible to construct a classical verification scheme for a quantum computer was first proposed by physicist Daniel Gottesman in 2004. Within 4 years, scientists gave a partial answer by showing that a quantum computer could prove its results to a verifier who had access to a small quantum computer of her own. However, this response just seems to push the question back one step further, for then the verifier needs a way to verify that her quantum computer is working as intended, which would involve another quantum computer, and so on.

Enter the work of Urmila Mahadev. The current study builds on work of hers conducted in 2016 in which she describes a cryptographic method to create a “secret state” in a quantum computer. The process involves creating a “trap-door” function, a function that is easy to perform but hard to reverse unless you have a secret cryptographic key. This function needs to be 2-to-1; having two inputs that correspond to each output. Think of the square function which has two inputs to each output (both -3 and 3 map to 9 as an output) You then ask the computer to build a superposition of all possible input states to this function, perform the function on this superposition, which creates a new superposition composed of the possible outputs of the function.

The computer then measures the output superposition collapsing it to a definite state and, since the two are entangled, the input state will collapse to a superposition of the corresponding inputs. So if you’re using the square function and a measurement gives you an output of 9, the input state collapses to a superposition of 3 and -3. Most importantly, because they have the secret key, the outside verifier knows the composition of the input state, but the computer does not, and the computer cannot check the input state because doing so would collapse the superposition and destroy the original information. Thus, the input state is a “secret” to the computer itself.

How To Build A Quantum Verifier

Armed with the knowledge of how to create a secret state, one can construct a classical quantum verifier as follows: First, you construct a secret state by the method previously described. Mahadev’s work uses a type of cryptography called Learning With Errors (LWE) to construct a suitable trapdoor function. After creating a secret state, the computer entangles that state with the state it is supposed to measure. Only then is the computer told what kind of measurement to perform. When the computer measures the intended state, the entangled secret state will correspondingly collapse. Since the computer did not know the composition of the secret state, it will not know the composition of the new secret state, but the verifier will because they possess both the original key and knowledge of what measurement was performed. If the results look like a correct proof, the verifier can be sure the computer actually did what it was told.

Essentially, Mahadev’s protocol forces the computer to behave a certain way to get the desired result. If the computer were not actually using quantum phenomena, then the only way it could give the correct result is by checking the composition of the secret state. However, doing so would collapse the secret state which inevitably prevents the computer from giving the correct result as the original information would be destroyed. Therefore, if the computer gives the correct result, then it must be that it is using quantum phenomena to do so, otherwise, we could detect traces of interference.

Mahadev’s verification protocol depends on the assumption that LWE cryptography, which is used to generate the trap-door function used to construct the secret state, cannot be cracked by quantum computers. This is still an open theoretical question, but so far no evidence has been found showing it to be breakable.

Mahadev’s protocol is still a ways off from being implemented in actual quantum computers as it requires a lot of processing power. However, the field of quantum computing has seen numerous advancement is the past 10 years, with some successful practical implementations. Given the rapid pace of progress, it could be that Mahadev will see her work implemented in actual quantum computers within the next 10 years.