Hacking at Quantum Speed with Shor's Algorithm | Infinite Series
Channel:PBS Infinite Series · Length:16:36 · Published:2017-04-28 · Views:238532
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
- The Mathematics of Quantum Computers | Infinite Series · PBS Infinite Series · 12:35
- But what are Hamming codes? The origin of error correction · 3Blue1Brown · 20:05
- Keynote by John Carmack at Oculus Connect 2014 · kungfl · 1:36:59
- Susan Crawford on Captive Audience: The Telecom Industry & Monopoly Power in the New Gilded Age · Berkman Klein Center for Internet & Society · 1:05:24
- The effects of DBS on the motor symptoms of Parkinson's Disease · Andrew Johnson · 4:03
- Pranks Destroy Scam Callers- GlitterBomb Payback · Mark Rober · 26:40
- Tesla Autonomy Day · Tesla · 3:52:20
- Bret Victor - Inventing on Principle · Rui Oliveira · 54:20
- Alexander Pope Wrote a 35-Page Takedown of a Historian · CGP Grey · 21:32
- [CVPR'21 WAD] Keynote - Andrej Karpathy, Tesla · WAD at CVPR · 31:31
- Andrej Karpathy - AI for Full-Self Driving at Tesla · Matroid · 30:08
- Quantum Computing for Computer Scientists · Microsoft Research · 1:28:22
- Behind the Scenes of iOS Security · Black Hat · 51:31
- Why Electronic Voting Is Still A Bad Idea · Tom Scott · 12:00
- But how does bitcoin actually work? · 3Blue1Brown · 25:15
- Diffie-Hellman Key Exchange · Art of the Problem · 8:38