Quantum computing in quarantine

02 June 2020, Iris Proff

© Arco Mul

Christian Schaffner is a researcher based in Amsterdam, but currently spending a sabbatical in Berkeley, California. In Berkeley, he is taking part in the “Quantum Wave in Computing” at Simons Institute for theoretical computer science. Christian, what is it like over there?

Christian Schaffner: Simons institute is great! Jim Simons made a lot of money in investment banking, but he also has a heart for theoretical physics and computation, so his foundation founded this institute. It is an art to create places that allow for a good research atmosphere. But here, this worked very well.

The institute runs semester-long programmes on different topics, where they invite researchers from all over the world. This semester there was one program on quantum computing and one on cryptography at the same time. This was great for me, as I could attend both!

What happened over the course of this semester?

Each program had 4 week-long workshops. Next to that, we set up our own weekly seminar series. We also had a bunch of reading groups and open problem sessions, where people gathered after lunch people around the white board to discuss.

When the Corona crisis started, everything moved online. This kind of science is doable online, but it’s a pity to have missed out on connecting with more people in the second half of my sabbatical. Most people left and took the last flights back to their home countries, but my family and I stayed on in Berkeley. We now have remote cooking sessions with a bunch of famous cryptographers. Very interesting!

Quantum computing in a nutshell

Before we dive into the hot topics of quantum computing – maybe you can give me a crash course. What is special about a quantum computer?

Classical (that is, non-quantum) computers encode information in bits, which can be either 0 or 1. But quantum computers work on qubits, which cannot only be 0 or 1, but both at the same time. They are in a superposition of states. But as soon as you measure the state of the qubit, it will be either 0 or 1 – you destroy the quantum state by looking at it and what you get is a classical bit.

How does this help me?

The cool thing about qubits is that if you have multiple of them, the dimension of the state space grows exponentially. This is a key feature. With 1 qubit you have 2 dimensions, with 2 qubits you have 4 dimensions, and with n qubits, you have 2ⁿ states that these qubits can be in at the same time. Exponential growth – we know this from Corona – is really fast!

Currently, the biggest quantum computer has 53 qubits. That is not a lot, but 2⁵³ is already a huge number – it’s about the memory size that a classical computer can handle. In principle, everything that a quantum computer does can also be done on a classical computer, but not as efficiently. In terms of computing capabilities, quantum computers are not more powerful, they might just be a lot faster.

How to crack the cryptographic code

Cryptography is one of the key applications of quantum computers – and your research field. How will this fast quantum computing affect our cryptographic systems?

It turns out that most of the currently used public-key cryptography can be cracked by quantum computers if they are big enough. In public-key cryptography, a key consists of a public and a secret key. You can encrypt a message to my public key and only the person who has the secret key – hopefully only me – can decrypt it.

A common public-key system is based on a mathematical problem called factoring. The private key consists of two prime numbers and the public key is the product of these numbers. It’s easy to take the product of two prime numbers, but it’s very hard to find these factors, if you only know the product. It would take many years. But not for a quantum computer! If your quantum computer has a few million qubits, then you can crack current public-key cryptography.

You said current quantum computers have 53 qubits and you would need a million. Sounds like this will only happen in some distant future?

It’s far away, but then again, maybe exponential growth applies here as well. People conjecture that there might be some quantum Moore’s law. We don’t know how quickly this will happen. Nobody knows.

So the reason why quantum computers can solve the factoring problem is because they can try many things at the same time?

No, big mistake! Because of the exponential state space, people say that you can do many things in parallel. This is true, but the problem is that you need to measure at the end to get a result. And this measurement collapses the quantum state of the qubits. Even though your qubits are in all output states at the same time, as soon as you measure, you get a single classical outcome corresponding to only one random input state. So you didn’t gain anything, because you could as well just select a random input and compute on that.

You have to be more clever. If you want to program a quantum computer, you need to exploit quantum interference.

Hm, I remember interference from physics class in high school – but then we talked about interference between waves.

Exactly. A quantum state can be described as a wave, where the amplitudes correspond to the probabilities that the quantum bit will be either 0 or 1 when measuring it. These waves can reinforce each other, or they can cancel out. To achieve a speed-up in a quantum computation, you want to make sure that the things you don’t like cancel out and the things you are looking for reinforce each other. That way, you increase the probability to end up at the right result, when you measure your qubits. Programming a quantum computer is like composing a nice piece of music – nice harmonies should reinforce each other, while dissonant sounds cancel out.

Using this trick, a quantum computer can solve the factoring problem in polynomial time, whereas on a classical machine it takes exponential time. That’s a lot faster! The cryptographic community is currently evaluating various proposals how to replace current public-key cryptography with quantum-secure variants. Together with other researchers at QuSoft, my group is part of this process.

Can you also use the advantages of quantum computers themselves to create a quantum-secure cryptography?

Yes, the best-known method is quantum key distribution. It allows two players to exchange keys, such that their messages are secure against attackers that have an infinite amount of time. Classical public key cryptography can never work this way. If you had an infinite amount of time, you could just search through all possible factors and at some point, you will encounter the right ones.

But in quantum key distribution, you are sending quantum states. When such a message is intercepted by an eavesdropper who tries to extract information from it, the quantum states will be disturbed – and this can be detected.

On the verge of the quantum internet

Where else – other than cryptography – could quantum computers bring about a change?

People are trying to create a quantum internet. In a quantum internet you want to have qubits at two places in the world that are entangled. Entanglement is something strange. It does not exist in the classical world, but you can think of it as a strong form of correlation.

Say I have a qubit here in Amsterdam and you have a qubit in Berkeley that is entangled with mine. If I now measure the state of my qubit and it’s 1, what would that mean for you?

It would mean that if I do the same measurement, I will also see a 1. Whoever measures first will determine the bit on the other side as well. And the change happens instantly.

That sounds like I can instantly transmit information from one place to another. But relativity theory tells us that nothing can travel faster than the speed of light. How does this fit together?

The clue is that even though the quantum state changes instantly, you cannot send me information via our entangled qubits. This is because you cannot know or influence what the outcome will be. It will be a random bit. That means, entanglement does not violate relativity theory – information still cannot travel faster than the speed of light.

Intriguing. But if you can’t send information with it, what could you use a quantum internet for?

You might use it to exchange encryption keys. But one of the main issues I see with the quantum internet is that it’s unclear for what – besides science – it will be useful.

“Quantum mechanics is the right description of nature. Classical information theory and classical computing are just a special case of the real thing.”

– Christian Schaffner –

Quantum simulations could help discovering materials

Turning to another topic, I heard that quantum computing can also be useful to discover new materials. How?

Quantum simulations were another hot topic here in Berkeley. In fact, this was the original proposal by Richard Feynman, who is considered the inventor of quantum computing. He was wondering: how to understand the quantum nature of things? Let’s build a computer that can simulate quantum systems! Quantum computers are particularly good at simulating quantum systems because they have quantum features themselves.

Such simulations could help to develop new materials, like fertilizers or new drugs. These are often big and complicated molecules and it’s not well understood how they behave on a quantum level. Quantum computers could help here. Instead of synthesizing a candidate for a new material in the lab and testing it, you could just simulate it. That could save a lot of time.

Quantum chemistry seems to be one the prime applications of quantum computers for the nearer future. They might be useful already without error correction.

What do you mean by error correction?

Current quantum computers are small and very noisy, because the quantum states are so vulnerable to outside influences. That means you always have to error correct them. But the currently best error correcting codes are using 50 qubits to get one error-corrected qubit – it scales pretty badly. For cracking our cryptographic code, you would only need a few thousand perfect qubits. But in practice, using such noisy qubits you will need several layers of error correction – that’s why you end up with a few million.

What’s the fuss about quantum supremacy?

All applications we talked about so far are still far from being feasible. What can we do with quantum computers today?

We had some heated discussions here in Berkeley about Google‘s claim to have reached quantum supremacy. Google says they can do something on their 53-qubit computer which cannot be done on a classical computer in reasonable time.

What is reasonable time?

Exactly! And what is reasonable money or reasonable energy? Quantum supremacy is a hard-to-define concept. Moreover, this supremacy experiment was not about doing anything useful. They did what quantum computers are good at, namely sample from a certain probability distribution. Google claims it would take ten thousand years to run this computation on the world’s best supercomputer. Now IBM says they could reproduce it in 3 days… In the end, it is a PR fight.

Anyway, we are at the point where you can do something on a quantum computer, even though not useful, that you cannot easily do on a classical machine. We are at the supremacy threshold. And because of the exponential scaling, if you add 10 more qubits, it’s clear that you can do quantum computations which will take prohibitively long on a classical computer.

For me as a theorist it’s easy to add qubits, I just need to write it down! But in practice, it’s ridiculously hard to engineer.

Speeding up complicated computations and enabling difficult simulations are also some of the promises of artificial intelligence (AI). How does quantum computing relate to AI?

AI seems to be a step ahead. Our mobile phones are full of neural networks doing useful things for us. But quantum computing has not had a big impact on our world yet. It’s more of a promise. The next challenge after the supremacy is established is: can we do something useful on a quantum computer? It could still be that the whole field dies out because it’s too complicated or too expensive to build or just doesn’t work for some reason.

Aren’t you afraid that all your efforts will be in vain then?

That’s the luxury of fundamental research. We spin our ideas, see how far we get. We often don’t know where we will end up on this journey. Hopefully, our research will lead to a better understanding of quantum theory itself.

Quantum mechanics is the right description of nature. Classical information theory and classical computing are just a special case of the real thing. If there is a reason why large quantum computers cannot be built, this can probably be turned into an assumption on which one can build cryptographic systems.