What makes quantum computers SO powerful?

Nation states and actors are storing encrypted data like passwords, bank details, and social security numbers because they believe quantum computers will break encryption within 10 to 20 years.

• Adversaries can decrypt valuable information stored today in the future • Targets include industrial research, pharmaceutical data, and government intelligence • Known as SNDL strategy

The National Security Administration warns that sufficiently large quantum computers could undermine all widely deployed public key algorithms. The US Congress passed legislation mandating agencies transition to quantum-resistant cryptography.

Quantum computers are still years away but already pose a threat due to Store Now Decrypt Later attacks.

Until the 1970s, secure communication required two parties to meet in person and share a secret key used for both encryption and decryption. As long as no one obtained the key, messages remained safe.

Sharing encryption keys over unsecured channels like phone lines or mail risked interception, making it impossible to communicate securely with people you've never met.

• Developed in 1977 by Rivest, Shamir, and Adleman • Uses asymmetric key system with different keys for encryption and decryption • Each person has two secret prime numbers multiplied to create a public number

Modern cryptography uses 313-digit prime numbers. Even with a supercomputer, factoring their product would take around 16 million years using the General Number Field Sieve algorithm.

• Classical bits exist in one state at a time: 0 or 1 • Two classical bits can represent four possible states: 00, 01, 10, or 11 • Calculations are performed on one state at a time

• Qubits can exist in arbitrary combinations of 0 and 1 states simultaneously • Two qubits can exist in superposition of all four states at once • Calculations are performed on all states simultaneously

Each additional qubit doubles the number of possible states. With 20 qubits you can represent over a million states simultaneously. With 300 qubits, you can represent more states than particles in the observable universe.

When you measure a quantum superposition, you only get a single random value and all other information is lost. Quantum computers require clever methods to convert superpositions into useful information.

In 1994, Peter Shor and Don Coppersmith figured out how to apply the quantum Fourier transform to extract frequency information from periodic signals.

• A normal Fourier transform identifies frequencies in a signal • Applied to a periodic superposition, it returns the frequency of the pattern • Results can be measured to extract useful information

The quantum Fourier transform enables extraction of frequency information from periodic superpositions, which is impossible to do efficiently on classical computers.

This technique is the foundation for Shor's algorithm, which can factor large numbers exponentially faster than classical algorithms.

For any number g that doesn't share factors with N, multiplying g by itself repeatedly will eventually yield a multiple of N plus one. Finding the exponent r where g^r equals N+1 is the key to factoring.

Using N=77 and g=8: when you raise 8 to successive powers and find remainders when divided by 77, the remainder 1 appears at exponents 10, 20, 30, etc. The pattern repeats every 10 powers.

• Once you find exponent r, rearrange the equation to create two terms whose product equals a multiple of N • These terms probably share factors with N • Use Euclid's algorithm to find the greatest common divisor

On classical computers, finding the period r is as slow as other factoring methods. Quantum computers can find r exponentially faster through superposition and the quantum Fourier transform.

• Split qubits into two sets • First set: superposition of all numbers from 0 to 10^1,234 • Second set: qubits in zero state to store remainders

Raise g to the power of the first qubit set, divide by N, and store the remainder in the second set. This creates entangled qubits with all possible exponent-remainder pairs.

• Measure only the remainder part to get a random value • This leaves a superposition where all remaining states share the same remainder • The exponents in this superposition are separated by the period r we're looking for

• Apply quantum Fourier transform to extract the period r • Use r with Euclid's algorithm to find prime factors • Break RSA encryption if r is even and resulting terms aren't multiples of N

Perfect qubits would require around 4,100 qubits to break RSA encryption, but real qubits need redundancy to correct errors.

• 2012: 1 billion physical qubits estimated needed • 2017: Estimate dropped to 230 million qubits • 2019: Further breakthroughs reduced estimate to 20 million qubits

IBM's quantum computers are nowhere near the number of qubits needed, but progress appears exponential.

The critical question is when the curve of quantum computer development will intersect with the threshold needed to break existing encryption.

• In 2016, NIST launched a competition to find quantum-resistant encryption algorithms • 82 different proposals were submitted from cryptographers worldwide • Proposals were rigorously tested and some were broken

On July 5th, 2022, NIST selected four algorithms for their post-quantum cryptographic standard. Three are based on lattice mathematics.

• Uses vectors that generate a lattice of points in high-dimensional space • Easy to encrypt with one set of vectors, hard to decrypt without the secret set • Security increases dramatically in higher dimensions

In three dimensions, finding the closest lattice point to a target is manageable. In a thousand dimensions, used in proposed encryption schemes, it becomes extremely difficult even for quantum computers.

A lattice is the set of all points you can reach by adding integer combinations of two or more vectors. Different vector sets can represent the same lattice.

• Finding the closest lattice point to a target is easy with well-structured vectors • Using poorly structured vectors makes it extremely difficult • Number of lattice points grows exponentially with dimensions

• Each person keeps a good vector set secret • Public key uses a hard-to-work-with vector set • Messages are encrypted by adding noise to a lattice point

Recipients with the secret good vectors can easily find the closest lattice point and decode the message. Adversaries without these vectors face an extremely difficult problem for both classical and quantum computers.

An army of researchers, mathematicians, and cryptographers work to ensure secret data stays protected and prevent mass surveillance.

• Protecting against quantum computer attacks • Keeping critical infrastructure safe • Enabling normal life despite quantum computing threat

Quantum computers and AI chatbots will play bigger roles in coming decades. Understanding how they work now is important for the future.

Brilliant offers interactive courses on quantum algorithms co-developed with Microsoft and Alphabet X, plus data analysis and cryptography courses to build foundational skills.