How Quantum Computers [Will] Break The Internet - QFT and FFT. My Engagement with AI Claude2

On of the best videos on Quantum Computers is this video

How Quantum Computers Break The Internet... Starting Now - YouTube

By Veritasium - YouTube

I uploaded the text into Anthropic \ Claude 2 and the following is my interaction with Claude2 the ‘Helpful, Honest, and Harmless’ AI Assistant to better engage with this video and better understand the topic.

First, I asked for a summary of the video.

• Quantum computers pose a threat to current encryption methods like RSA because they can quickly factor large prime numbers. This enables them to break the public key cryptography used today.
• Governments and other entities are already intercepting and storing encrypted data now in order to decrypt it later when quantum computers become available. This is known as "store now, decrypt later" or SNDL.
• New encryption methods are being developed that can withstand attacks from both classical and quantum computers. These include lattice-based cryptography which relies on finding closest vectors in a lattice.
• Key experts argue we need to transition to new post-quantum cryptography now before quantum computers advance enough to break current encryption schemes. New standards like those from NIST are helping drive this transition.
• The timeline for when quantum computers will be able to break encryption is uncertain, but estimates have rapidly declined in recent years as quantum computers advance. We may only be years away from the point where they pose a real threat.

Let me know if you have any other specific questions! I'm happy to discuss the key points from the transcript in more detail.

Next, I asked for a Summary of Shor's algorithm

Here is a summary of Shor's algorithm for factoring integers using a quantum computer:

• The goal is to find the prime factors p and q of a large integer N. This allows breaking RSA encryption, which relies on the difficulty of factoring large primes.
• First, randomly choose a number "a" that is coprime to N.
• On a quantum computer, put qubits in a superposition of all possible states from 0 to 2^n. Use these as exponents to raise a to, modulo N. This creates a periodic function.
• Apply the quantum Fourier transform to the qubits. This reveals the period of the function.
• The period tells you the order of a modulo N. If this order is even, it can be used to construct a non-trivial factor of N.
• Apply the classical Euclidean algorithm to this new number and N to extract the factor p. Divide p into N to get q.
• So in summary, Shor's algorithm harnesses the power of a quantum computer to find the period of a function related to N. This period helps construct factors p and q quickly, even for very large N. It demonstrates how quantum computers can break current public-key cryptography.

Let me know if you need any clarification or have additional questions!

about 14 minutes into the video, it outlines how Shor's algorithm work - I thought this was a great summary on how a Quantum Computer algorithm works in general, I asked Claude to reformat the text:

Now we are ready to use a quantum computer to factor any large product of two primes.

First we split up the qubits into two sets. The first set we prepare in a superposition of zero and one and two and three and four and five and six and seven and eight and nine, all the way up to 10 to the power of 1,234. Yeah, this is a huge superposition, but if we had perfect qubits, it would require only around 4,100.

The other set contains a similar number of qubits all left in the zero state for now.

Now we make our guess G, which most likely doesn't share factors with N. We raise G to the power of the first set of qubits and then we divide by N and store the remainder in the second set of qubits leaving the first set of qubits as it was.

Now we have a superposition of all the numbers

we started with and the remainder of raising G to the power of those numbers divided by N. And through this operation, we have entangled our two sets of qubits, but we can't just measure this superposition. If we did, we would get a random value and learn nothing. But there is a trick we can use.

If we don't measure the entire superposition, but only the remainder part, we will obtain some random remainder. But this remainder won't occur just once. It will occur multiple times every time it comes up in the cycle. Imagine we were doing this with the example from before with N equals 77 and G equals eight. If the remainder we measured was say 15, then there would be multiple terms in our superposition. Because there are multiple exponents you can raise G2 that give this same remainder,

exponents 4, 14, 24, 34, and so on. They are each separated by 10, and that value is the exponent that satisfies our equation.

So more generally after measuring the remainder, we will be left with a superposition of states that all share the same remainder and the exponents will all be separated by the same amount r. This is the number we are looking for. Since the remainder is now the same for all states, we can put it to the side

and we now have a superposition that is periodic. Each term is separated from its neighbors by an amount R. If we now apply the quantum Fourier transform to this superposition of states and I'm simplifying a little here, we will be left with states containing one over R.

So all that's left to do now is perform a measurement and find R by inverting it, and that's it for the quantum part. Now, as long as r turns out to be even we can use r to turn our bad guess g into two numbers that likely share factors with N. And as long as these terms themselves are not a multiple of N, we can use Euclid's algorithm to find the factors of N and break the encryption.

Here are some key pictures from the video

I then asked for the text to be simplified.

Here is the text simplified to a high school level:

Now we can use a quantum computer to factor any large number that is the product of two primes.

First we divide the quantum bits into two groups. The first group we put into a superposition of all possible values from 0 to a very large number.

The other group we leave as 0 for now.

We make a guess for a number G that probably does not share factors with the number N we want to factor.

We raise G to the power of the values in the first group and divide by N, storing the remainder in the second group.

Now we have a superposition of all the possible values from the first group and their remainders from dividing by N.

By measuring just the remainder group, we get a random remainder, but it will occur multiple times.

The exponents that produced that remainder will be separated by some number r.

This r is the period we are looking for.

Now the first group is periodic with period r.

By applying a Fourier transform, we can extract 1/r.

Inverting this gives us r.

If r is even, we can use it to generate new guesses for factors of N.

Checking if these share factors with N using Euclid's algorithm,

we can find the factors of N and break the encryption.

I asked about how long it would take to run the algorithm.

The time it takes to run Shor's algorithm depends on several factors:

• The size of the integer N you are trying to factor. The larger N is, the longer the algorithm will take. Factoring a 1024-bit RSA modulus is estimated to take minutes on a sufficiently large quantum computer.
• The number of qubits available. To factor larger numbers, you need more qubits to represent the superposition of states. Estimates typically assume millions of logical qubits.
• Gate error rates and qubit coherence times. Noisy, imperfect qubits require more error correction and thus slow the algorithm. State-of-the-art quantum computers today have too much noise.
• Optimization of the circuits. More efficient circuit implementations of the modular exponentiation and quantum Fourier transform operations could reduce runtime. This is an active area of research.
• Parallelization. Parts of the algorithm can be parallelized across multiple qubits/gates. More parallelization reduces runtime.

So in general, estimates put factoring a 1024-bit RSA modulus at a few minutes on a quantum computer with millions of logical qubits and sufficiently low error rates. A 2048-bit modulus may take hours. But to achieve this type of performance is still beyond our current hardware capabilities and requires major improvements in qubit fidelity, error correction, and scale.

The runtimes are still exponentially faster than classical computers, which would take longer than the age of the universe for these sizes. But the absolute runtimes remain uncertain as hardware capabilities continue advancing.

Author's Note, as a communication engineer, we studied the Fast Fourier Transform. see this video on why the FFT is so important and uses in 4G and 5G

(11) The Remarkable Story Behind The Most Important Algorithm Of All Time - YouTube

The Fast Fourier Transform is used everywhere but it has a fascinating origin story that could have ended the nuclear arms race.

I asked Claude for more info on FFT and 4G and 5G

Here is a summary of how FFTs are part of 4G and 5G technology:

• 4G and 5G networks utilize OFDM (Orthogonal Frequency Division Multiplexing) as the modulation technique. OFDM divides the available spectrum into many closely spaced orthogonal subcarriers.
• To implement OFDM, FFTs are used to efficiently convert the signal between time domain and frequency domain. The transmitter uses FFT to convert from time to frequency before modulating the subcarriers. The receiver uses FFT again to demodulate and convert back to time domain.
• FFTs enable the parallel transmission and detection of data on many subcarriers in an OFDM system, allowing high spectral efficiency.
• FFTs also help in efficient implementation of channel estimation and equalization in OFDM systems.
• The computational efficiency of FFTs allows practical implementation of OFDM systems with large number of subcarriers, e.g. 4096 subcarriers in 5G NR.
•  FFTs play an integral role in enabling OFDM which is a core technology for 4G LTE and 5G NR wireless networks.

In summary, FFTs are an important component enabling the OFDM modulation used in modern cellular networks to provide high speed data connectivity.

Then I asked about the difference between QFT and FFT

The main differences between the quantum Fourier transform (QFT) and the classical fast Fourier transform (FFT) are:

• The QFT acts on quantum states represented by qubits, while the FFT acts on classical digital data.
• The QFT performs a Fourier transform on a superposition of states all at once. In contrast, the FFT operates on one data sample at a time in sequence.
• The QFT leverages quantum parallelism - it applies the Fourier transform to many states simultaneously due to superposition. The FFT does not have this inherent parallelism.
• The Fourier transform extracts the component frequencies from periodic functions. The QFT provides an exponential speedup for this extraction compared to classical FFT algorithms.
• The QFT relies on quantum gates and operations like controlled rotations on qubits. The FFT uses classical bit operations and matrix multiplications.
• The QFT outputs a quantum state representing a superposition of frequencies. To get useful information, this superposition must be measured, collapsing it to a single value. The FFT outputs the classical digital frequency data directly.
• The QFT requires fault-tolerant quantum computers with high qubit counts to be practically useful. The FFT is implemented widely on conventional digital hardware.

So in summary, the QFT brings the advantages of superposition and parallelism to provide exponential speedups versus the classical FFT. But it operates on quantum data using quantum operations rather than classical digital data.

My final thoughts on Claude2 and the future of education.

I thought this did a great job in helping me better engage with the video and answer questions and summarizing material. The future of Education Videos will be an AI assistant along with the video to help you learn and explore new ideas.

Edwin Hubble said "Equipped with his five senses, man explores the Universe around him and calls the adventure Science." 

I say, Equipped with hundreds of senses and sensors and tens of sextillion (tens of 10^21) transistors, "Computing Machines" (Computronium) process the Universe around it to achieve complex goals and Humanity calls that adventure AI.

Note, in the podcast Voices in AI – Today's leading minds talk AI with host Byron Reese. Bryon opens each podcast asking leading AI experts: “what AI is?” I would suggest those criticizing VP Harris to spend more time trying to educate the public on what is AI and how can humanity use AI for the good of humanity and avoid the harm. 

My high-level definition of AI: Non biological machines with the Ability to accomplish complex goals.

See the blog: Are You Smarter than your Grandparents? Intelligence X - Intelligence Augmentation IA- Collaborated | LinkedIn

“Intelligence, defined as ability to accomplish complex goals, can’t be measured by a single IQ, only by an ability spectrum across all goals.”  Max Tegmark, Life 3.0: Being Human in the Age of Artificial Intelligence