Квантовые компьютеры УЖЕ ломают интернет [Veritasium]

Introduction to Quantum Computing

The video introduces the concept of quantum computing and its potential impact on cryptography. It explains how current encryption methods work and why they may become vulnerable in the future.

How Encryption Works

• Symmetric encryption involves using a shared key to encrypt and decrypt messages.

• Asymmetric encryption uses two keys, one public and one private, to encrypt and decrypt messages.

• Modern encryption methods use large prime numbers that are difficult to factorize as keys.

The Threat of Quantum Computing

• A powerful enough quantum computer could break all currently used asymmetric encryption algorithms within 5-10 years.

• While practical quantum computers do not yet exist, some governments are already collecting encrypted data for future decryption.

How Quantum Computers Work

The video explains how quantum computers differ from classical computers in terms of their basic building blocks (qubits vs bits), how they store information (superposition), and how they process it (quantum gates).

Qubits vs Bits

• Classical computers use bits that can be either 0 or 1.

• Quantum computers use qubits that can be both 0 and 1 at the same time due to superposition.

Superposition

• Superposition allows quantum computers to perform many calculations simultaneously by representing them as a combination of different states.

Quantum Gates

• Quantum gates manipulate qubits by changing their state based on certain rules, allowing for complex computations.

Applications of Quantum Computing

The video discusses some potential applications of quantum computing, including cryptography, optimization problems, and simulation.

Cryptography

• Quantum computers could break current encryption methods but also enable new ones that are more secure.

Optimization Problems

• Quantum computers can solve certain optimization problems much faster than classical computers, which has applications in fields such as finance and logistics.

Simulation

• Quantum computers can simulate complex systems that are difficult to model with classical computers, such as chemical reactions or the behavior of materials at the atomic level.

Factoring Large Numbers

In this section, the speaker explains how to factor large numbers using a mathematical trick and an algorithm called Euclid's algorithm.

Factoring with Euclid's Algorithm

• To factor large numbers P and Q, we can use a mathematical trick involving G, a number without common factors with N (P*Q).

• By repeatedly multiplying G by itself until it equals some multiple of N+1, we can find a value R such that G^R = mN + 1.

• We can then find the remainder when 8^R is divided by N. If the remainder is 1, we have found R.

• Using R, we can find two numbers that may have common factors with N: 8^(R/2)+1 and 8^(R/2)-1.

• Finally, we can use Euclid's algorithm to find the greatest common divisor of these two numbers and N. This will give us either P or Q.

Finding R

• The speaker demonstrates how to find values of R for different values of G by looking at the remainders when G is raised to increasing powers modulo N.

• The remainders form cycles on a logarithmic scale, with each cycle having a length equal to the period between repeated remainders. By finding where the remainder is equal to 1, we can determine the value of R needed for factoring.

Shor's Algorithm

In this section, the speaker explains how Shor's algorithm can be used to factor large numbers and break modern encryption methods.

How Shor's Algorithm Works

• If we have ideal qubits, we can use them to create a superposition of all possible factors of a number.

• We can then use a technique called modular exponentiation to find the period of this superposition.

• The period allows us to determine the factors of the original number using classical algorithms.

• To find the period, we measure only a subset of the superposition and use its residue values to calculate it.

• The period is related to a value R in an equation that helps us find common factors between two numbers.

• If R is even, we can easily find common factors using any number as G. Otherwise, we need additional qubits and more complex calculations.

Breaking Encryption with Shor's Algorithm

• With enough ideal qubits, we could break modern encryption methods that rely on factoring large numbers.

• As of 2019, we do not have enough ideal qubits for this task yet. However, progress in quantum technology is exponential and experts predict that it may happen soon.

• To protect against quantum attacks, researchers are developing new encryption methods that are resistant to Shor's algorithm.

• The National Institute of Standards and Technology launched a competition in 2016 for developing post-quantum cryptography algorithms. Four winners were announced in July 2022 which are resistant against quantum threats.

Introduction to Data Encryption

In this section, the speaker introduces the concept of data encryption and how it can be used to protect sensitive information.

Protecting Sensitive Information

• The speaker explains that making even a small mistake in data encryption can lead to significant consequences.

• Two users have their own set of convenient vectors that describe a lattice. These vectors are not shown to anyone else and are only available in less optimal versions.

• To send a message, the sender marks a point on the recipient's lattice and assigns it a value of seven. The sender then adds some noise so that the message does not land exactly on that point but somewhere nearby.

• Decrypting the message requires finding the nearest point to where it was sent, which is incredibly difficult without access to convenient vectors.

Importance of Data Encryption

• The task of protecting sensitive information has become increasingly important as technology advances.