Urmila Mahadev, a graduate student at UC Berkeley, has come up with a solution to a major problem in quantum computation. She has found a way, using only classical computers, to know whether a quantum computer precisely follows given instructions
Intro to quantum computers
A computer is a machine that does calculations. Whether you are watching a Youtube video, writing an essay or playing a game, all your computer does is just add, subtract, multiply and divide numbers. Your computer does these calculations with the help of small electrical parts called transistors that act as switches. These switches are combined into logic gates, and logic gates in turn are connected to each other to form adding, subtracting, multiplying, and dividing mechanisms.
In our normal world, switches can be either on or off, electricity is either flowing through the circuit or not. We sometimes hear that computers work only with 0s and 1s because they store information of switches being off and on in bits that can be either 0 or 1 at one point in time. In the world of quantum physics, however, it is not that simple. A quantum object can actually be in different states at the same time or, more scientifically, the object can be is a superposition of different states. A famous example of a quantum object is Schrödinger's cat. This cat lives in a closed box. Inside that box there is also a deadly mechanism that may or may not activate. And until you, an outside observer, open that box, the cat is dead and alive at the same time. This cat is in the superposition of being dead and alive.
Quantum computers use quantum bits, or qubits. Qubits are quantum objects, usually electrons of atoms, that are spinning chaotically in each and every direction at the same time! If this is hard for you to grasp, do not worry. As some physicists say, 'It’s not that you understand it, you just get used to it'. So when qubits are spinning in all directions, we can think of them as rapidly alternating between 0 and 1. This along with a number of other curious properties such as entanglement of quantum objects are harnessed by special complex machines called quantum computers to conduct efficient calculations. Quantum computers may bring us closer to discovering the secrets of the universe by, for example, simulating black holes and protein folding, which are very computation-heavy operations.
Problem with quantum computers
The major problem with quantum computation is that we do not know how to check whether a quantum computer did all the instructed calculations or even generated the correct result. With classical computers this is really easy — all you need to do is check every step, you check every time a bit is 0 or 1. Quantum computation, however, does not have steps because it performs all steps at the same time and stops the moment you measure the result. Again, you cannot know whether the cat is dead or alive, until you open the box. Similarly, you cannot see whether the qubit is 0 or 1 without measuring it. Measurement collapses the superposition into a single unambiguous state. So, in a way, a quantum computer is a quantum computer only when you don’t look at it. As soon as you look at the qubits, they become classical bits. So if you cannot follow the process of computation, how do you know if the computation was correct?
Urmila Mahadev proposes a solution that predicates on a simple idea that if a quantum computer can do something that classical one can’t, we can still use classical means to check the result. As such we can construct such a function that is very hard to compute but is easy to verify, a trapdoor function.
For example, it is believed that quantum computers are really good at factoring numbers. For classical computers given a large number it is incredibly difficult to find its factors. This is the biggest pillar of modern cryptography. It takes a big number, a private key, multiplies it by another big number and outputs the third even bigger number, the public key. You can feed this public key to a computer but it will take hundreds of years to find its factors. But if a quantum computer does in fact find these factors, we can simply check the result by multiplying the generated numbers, which any classical computer can do. To illustrate we will use smaller numbers. We can have the quantum computer find factors of 2047 and when it gives 23 and 89, we can simply multiply those to verify the result.
Urmila Mahadev has come up with an interactive protocol that allows classical computers to verify quantum computation. They can do it by having the quantum computer measure its own qubits and output the result. For a while, the problem with this was the fact we could not trust the computer because we could not tell which superposition of superpositions the computer measured. Urmila implements the trapdoor function to first generate the output of a certain superposition and verify if qubit measurement belongs to that superposition.
Urmila approaches this problem using cryptography known as Learning with Errors cryptography which is a topic for another article. But nevertheless this is a big discovery that once again proves the sheer power of cryptography and prepares us for the post-quantum world.