When physicists first thought of quantum computers in the 1
Shor’s paper shows how quantum computers can overcome a key problem. These machines process the information as a qubit (a quantum version of ordinary bits that can be “0” and “1” at the same time). However, as we all know, quantum states are easily affected by noise, leading to loss of information. His error correction technique (detecting errors caused by noise) shows how to make quantum information more reliable.
Sol is now studying at the Massachusetts Institute of Technology in Cambridge and is also a published poet. He shocked the physics and computer science communities the previous year when he discovered2 The first potentially useful but ominous way of using hypothetical quantum computers. He wrote an algorithm that would enable a quantum computer to decompose integers into prime numbers at lightning speed. Today, most Internet traffic is protected by encryption technology based on large prime numbers. Cracking these codes is difficult, because traditional computers are slow in breaking down large products.
Quantum computers are now a reality, although they are still too rudimentary to resolve numbers that exceed two digits. However, it is only a matter of time before quantum computers threaten Internet encryption.
nature Catch up with Shor and ask him about the impact of work and the direction of Internet security.
Before using factorization algorithms, were quantum computers mainly out of theoretical curiosity?
My paper must make people know that these machines can do some useful things.Before coming to my conclusion, computer scientist Daniel Simon solved a problem he posed that showed that the speed of quantum computers has doubled [than ordinary computers]. But even with Simon’s algorithm, it is not clear whether they can do something useful.
How did you react to the announcement of the factorization algorithm?
At first, I only had an intermediate result.I talked about this at Bell Labs [in New Providence, New Jersey, where I was working at the time] On a Tuesday in April 1994. The news spread quickly. That weekend, computer scientist Umesh Vazirani called me. He said: “I heard that you can consider a quantum computer and tell me how it works.” At that time, I had not really solved the factoring problem. I don’t know if you know the children’s game “phone”, but within five days, my results became a factor because people told each other. In those five days, I also solved the decomposition problem, so I can tell Umesh what to do.
Before I finished writing my thesis, various people were asking me about my thesis, so I had to send them an incomplete draft.
But many experts still believe that quantum computers will lose information before you actually complete the calculations?
One of the objections is that in quantum mechanics, if you measure a system, you will inevitably interfere with it. I showed how to measure errors without measuring calculations-then you can correct the errors without breaking the calculations.
After my 1995 paper on error correction, Some skeptics firmly believe that quantum computing may be feasible.
Error correction relies on “physical” and “logical” qubits. what is the difference?
When writing the algorithm of a quantum computer, you would think that qubits [the quantum version of a classical bit of information] These noiseless qubits described by this algorithm are logical qubits. In fact, there are no noise-free qubits in our quantum computers. In fact, if we try to run the algorithm without any noise reduction, errors will almost inevitably occur.
Physical qubits are one of the noisy qubits in our quantum computers. In order to run our algorithm without any errors, we need to use quantum error correction codes, which use physical qubits to encode logical qubits. The best way we know how to do this has considerable overhead, and each logical qubit requires many physical qubits.
Calculating how many qubits the technology needs is very complicated. If you want to build a quantum computer using surface code (currently the best candidate), you need about 100 physical qubits or more for each logical qubit.
In 2019, Google showed that its 54-qubit quantum computer can solve problems that cannot take a long time on classical computers. Demonstrated for the first time “quantum advantage”. What is your reaction to this?
This is definitely a milestone. It shows that quantum computers can do better than traditional computers-at least on a very artificial problem. Of course, Google participated in some publicity. But they also have a very impressive quantum computer. It still needs to get better before doing anything interesting. And start IonQ. It seems that they can make a quantum computer that is somewhat better than Google or IBM.
When quantum computers can decompose large prime numbers, this will enable them to break “RSA” (the ubiquitous Internet encryption system).
Yes, but the first person to crack RSA is either NSA [the US National Security Agency] Or other large organizations. At first, these computers will be slow. If you have a computer that can only crack one RSA key per hour, anything that is not prioritized or poses a national security risk will not be destroyed. Compared to reading your email, NSA has more important functions to use its quantum computer-they will read emails from the Chinese Embassy.
Is there a cryptographic system that can replace RSA and will remain secure even in the age of quantum computers-“post-quantum encryption”?
I think we have a post-quantum cryptosystem that can be replaced by RSA. RSA is not a big problem now. The biggest problem is that there are other ways to undermine the security of the Internet, such as poorly programmed software, viruses, and sending information to certain players that are not completely honest. I think the only obstacle to replacing RSA with a secure post-quantum cryptosystem is willpower and programming time. I think this is the method we know. It’s just not clear whether we will do it in time.
Is there a risk of being caught off guard?
Yes. The workload of resolving the year 2000 error was huge. To switch to post-quantum, you will need to put in tremendous effort. If we wait too long, it will be too late.
This interview has been edited for length and clarity.