2020-11-06

What was the impact of the foreign old man’s move 25 years ago?

By yqqlm yqqlm

In the 1980s, when physicists first proposed the idea of ​​a quantum computer, it sounded very optimistic, but it could only be presented in words.

Later in 1995, last month 25 years ago, applied mathematician Peter Shor published a paper that changed everything at that time.

getInterUrl?uicrIvZQ=a5e337c3dd770eb01a228048d550bd22 - What was the impact of the foreign old man’s move 25 years ago?

Figure 1|Peter Shor (Source:TQD)


Peter Shor’s paper

Shor’s paper shows how quantum computers overcome a key problem. These machines will process information in the form of qubits, which are quantum versions of ordinary bits that can process 0 and 1 at the same time.

But as we all know, quantum states are susceptible to noise, which leads to loss of information. His error correction technology (used to detect errors caused by noise) shows how to make quantum information more reliable.

<

div class=”pgc-img”>getInterUrl?uicrIvZQ=7df39515e330ac05c6a8215da80d4ddc - What was the impact of the foreign old man’s move 25 years ago?

Figure 2|Papers published by Peter Shor in 1995 (Source:American Physical Society)

< /div>

Shor currently works at the Massachusetts Institute of Technology in Cambridge, and he is also a poet who has published a collection of poems.

As early as 1994, he discovered how to use quantum computer models for calculations, which shocked the physics and computer science communities.

He proposed an algorithm—prime factor decomposition algorithm, which allows quantum computers to convert Decompose integers into prime factors. Most Internet traffic today is protected based on encryption technology with large prime numbers. Cracking these codes is very difficult, because classical computers are very slow in decomposing large integers.

getInterUrl?uicrIvZQ=147149c91e1e92bcc27f12b9e3a96de0 - What was the impact of the foreign old man’s move 25 years ago?

Figure 3|Paper published by Peter Shor in 1994 (Source:Institute of Electrical and Electronic Engineers)

Quantum computers are now a reality, although they are not enough to calculate numbers with more than two digits. But it is only a matter of time before quantum computers threaten Internet encryption.

Interview content

“Nature” interviewed Shor and asked about his The impact of work-and the development trend of Internet security.

1. Before your prime factorization algorithm appeared, quantum computers were purely to satisfy theoretical curiosity Heart?

My paper does make people understand that these machines can do some useful things.

Computer scientist Daniel Simon, before I came to my conclusion, he solved a problem he posed, which showed that quantum computers (than ordinary computers) are much faster.

But even with Simon’s algorithm, it is impossible to know whether these machines can be used for their purposes.

2. How did people react after you announced your prime factorization algorithm?

At first, I only got an incomplete result. Later, in April 1994, I gave a report on this topic at Bell Labs.

The news spread very quickly. That weekend, computer scientist Umesh Vazirani called me and said,”I heard that you can perform prime factorization on a quantum computer. Tell me how you do it.”

getInterUrl?uicrIvZQ=0d8c3f119d5ad4ff0305737504ac6928 - What was the impact of the foreign old man’s move 25 years ago?

Figure 4|Umesh Vazirani (Source:Berkeley School of Engineering)

At that time, I actually hadn’t really solved the problem of prime factorization. But what’s amazing is that within five days of the end of the report, my results became successful in the prime factor decomposition in people’s reports. And in these five days, I did solve the decomposition problem, so I can tell Umesh how I did it.

At the time, people were asking me for my unfinished paper, so I could only show them the rough draft.

3. But there are still many experts who believe that quantum computers will lose information before they complete calculations, right?

One of the objections is that in quantum mechanics, if you measure a system, you will inevitably interfere with it.

I demonstrated how to measure the error without measuring the calculation-then you can correct the error without breaking the calculation.

After I published a paper on error correction in 1995, some skeptics were also convinced that quantum computing is feasible.

4. Error correction relies on”physical” and”logical” qubits, the difference between the two Yes?

When you write down an algorithm for a quantum computer, you will assume that qubits are noise-free. These noise-free qubits are logical qubits, and there are no noise-free qubits in our quantum computers.

In fact, if we try to run our algorithm without noise intervention. The occurrence of that error is inevitable.

Physical qubits are one of the noisy qubits in quantum computers. In order to run our algorithm without any errors, we need to use physical qubits to encode logical qubits, which will use quantum error correction codes.

getInterUrl?uicrIvZQ=a08e09478fa50381add2e73e00771260 - What was the impact of the foreign old man’s move 25 years ago?

Figure 5|Qubit (source:medium)


The best method we know has considerable overhead. This method provides many physical qubits for each logical qubit.

It is quite complicated to calculate how many qubits this technology needs. If you want to use surface codes (the best option at the moment) to build a quantum computer, then each logical qubit needs about 100 physical qubits to support, or more.

5. In 2019, Google demonstrated its”quantum advantage”-that is, 54 qubits Quantum computers can solve a time-consuming and lengthy problem on classical computers. What is your response?

This is definitely a milestone. It shows that quantum computers can do better than classical computers—at least when it comes to human-dominated factors.

Even though Google has done some promotional activities, there is no doubt that this quantum computer is indeed impressive.

Before it can work miracles, it needs some perfection work. In addition, the quantum computer made by the startup IonQ may be better than Google and IBM to some extent.

6. When quantum computers can decompose large prime numbers, they can crack the ubiquitous Internet encryption system”RSA”, what do you think of this?

Yes, but the first person to crack RSA was either the NSA (National Security Agency) or some other large organization.

In the beginning, these computers will run very slowly. If you have a computer that can only crack one RSA key per hour, you must use it to crack information about national security risks.

Compared to reading the emails of the general public with quantum computers, the National Security Agency has more important things to do-they will read the emails of the Chinese ambassador, haha.

7. Is there an encryption system that can replace RSA and is safe in the age of quantum computers—— That is”post-quantum encryption”?

I think we will have a post-quantum cryptosystem that can replace RSA.

But RSA is not the most important issue at the moment. The top priority is that there are other ways to undermine the security of the Internet, such as poorly programmed software, viruses, and sending information to some malicious players.

I think the biggest obstacle to replacing RSA with a secure post-quantum cryptosystem is our unremitting efforts and programming time. I think this is something we know how to do, but whether we can do it in time is still unknown.

getInterUrl?uicrIvZQ=6563192ab24d4e62735f217a76b6a9c7 - What was the impact of the foreign old man’s move 25 years ago?

Figure 6|RSA algorithm (source:Exabeam)


8. Will there be a risk of catching us by surprise?

Yes. In order to fix the error (the millennium bug) that occurred in 2000, people have made great efforts.

And people need to work harder to switch to the post-quantum era. But if we wait too long, it will be too late.

Showing the black technologyTechnology NewsDigital PuzzleTechnology< /a>knowledge sharing< /p>

<

p style=”text-align:start”>Follow Quantum guest, get first-hand information in the quantum field