Hacking at Quantum Speed with Shor's Algorithm | Infinite Series

Channel:PBS Infinite Series · Length:16:36 · Published:2017-04-28 · Views:238532

Watch on YouTube

Summary

PBS Infinite Series explains how Shor's algorithm lets a quantum computer break RSA encryption, building on earlier episodes about cryptography and the math of quantum computers. It works through the idea step by step.

Why HN recommends it

HN recommends it as a clear, worked explanation of Shor's algorithm for building intuition.

I thought this example of Shor's algorithm was pretty good — HN, 2019

Cryptography · Quantum computing

Subtitles (excerpt)

How might quantum computers destroy computer security? By utilizing Shor's algorithm. [MUSIC PLAYING] Last week, we made a ton of progress toward our goal of hacking into an encrypted message. Remember, popular forms of cryptography work by multiplying together two large prime numbers and using those primes as keys to recover the message. So to crack the code, we'll need to find the prime factors of a really big number. But that would take a classical computer a long time. Way longer than the encrypted information is probably useful for. But Shor's algorithm allows us to quickly factor large numbers using a quantum computer. To learn about the outline and big picture of Shor's algorithm, check out last week's episode. After that, come back here, because we're about to dive into the quantum portion of that algorithm. For that, it will also be helpful if you have some background knowledge about how a quantum computer works. Luckily, we've got an episode for that, too. There's a popular notion that a quantum computer is just a bunch of classical computers working side-by-side in parallel. That's kind of true and kind of false. Let's see how. We'll start by looking at one classical computer.

On Hacker News

I'd recommend Charles Petzold's Code: [LINK] Which does a great job building up computing from bits all the way to a adders, CPUs, and assembly language (with the historical background around it too). I think the easiest way to get an idea for Quantum Computing and what the difference is comes from watching a specific example, I thought this example of Shor's algorithm was pretty good: [VIDEO] — fossuser, 2019-10
It's not that they can execute a computation faster in the traditional sense. It is that you can exploit the quantum behaviour in some types of computation (e.g. factoring primes) to make the answer more probable, and thus more likely to be "observed", when you read the state of the quantum computer and thus make it easy to locate the correct answer compared to traditional algorithms. PBS Infinit… — msclrhd, 2018-11
You should check out these videos, one of them might give you an understanding! - [LINK] | Quantum Computers Explained - [LINK] | The Mathematics of Quantum Computers - [VIDEO] | Hacking at Quantum Speed with Shor's Algorithm - [LINK] | A series by the author of the standard textbook These are videos I particularly like! — adamisntdead, 2018-04
A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo. Here's what really happens. If you have a string of n-qubits, when you measure … — stcredzero, 2018-02

Related videos