11-860 — Advanced Topics: Quantum Computing Lab — Spring Semester 2020

March 2 & 4 / Week 7

Shors Algorithm

Before Class

Read Chapter 12 in the Octopus Book Watch a lecture by Shor. Read paper on cracking RSA 2048 in 8h10min

Summary

Shor’s algorithm is what truly ignited the QC space. With the promise of easily breaking RSA this makes QCs a serious threat to our current security technologies. Interestingly, Shor’s algorithm is not provably faster than any classical algorithm. But… proving that may require the collapse of the P vs. NP problem, so don’t hold your breath.

Notes

• Reminder to bring computer to class.