Peter Shor changes everything
In April 1994, Peter Shor extended Simon's algorithm technique to the discrete logarithm problem, using a quantum Fourier transform to find the periodic structure hidden in numbers. He presented the result at a weekly Bell Labs seminar known for rigorous questioning, and within days word had spread through the academic community. Computer scientist Umesh Vazirani called Shor on the weekend and said, 'I hear you can factor efficiently with a quantum computer,' immediately identifying where Shor's work was heading. Shor later admitted that if he hadn't already solved the factoring piece in those four days between the seminar and Vazirani's call, the phone call would have sent him into a panic, knowing everyone would now race toward the same result.
- Shor initially saw Simon's problem as 'useless' in direct application but recognized its mathematical structure could be redirected toward something with real-world consequences.
- Bell Labs held a weekly Tuesday seminar, and it was at one of these sessions that Shor first presented his discrete logarithm result.
- Vazirani is identified as a computer scientist currently at the University of California, Berkeley.
- Shor recounted the story of Vazirani's phone call himself at a UCLA symposium a few years before the episode was recorded.
Transcript
This chapter, from the episode video's captions · 592 words
1:49:51The idea is the construction of this has a functional application to cryptography >> because of some of the mathematical underpinnings. >> Yes. >> That define the problem. >> Exactly. >> And you know, Peter Short, he looked at it and was able to see those mathematical underpinnings in the construction. >> Yeah. >> Of the Simon problem, right? Of Simon's problem. He looked at this and he's like, "This looks useless, >> but there's a way that this can be used to solve something that I think a lot of people are going to care about." Okay, so he sets out to extend Simon's technique to something called the discrete logarithm problem. April 1994,
1:50:32he succeeds. He figures out how to effectively how to effectively do like a discrete 4A transform. You know, in Forier transforms, we we've discussed this a lot. for your transforms are when you go from the time domain of a signal to the frequency domain where you're you're extracting the frequencies that are relevant in whatever thing right in this case this is like a frequency of numbers type thing right um and he shares this logarithm result at Bell Labs he was at Bell Labs um every Tuesday they used to have this weekly seminar he presents it at the seminar um it's known for rigorous and direct questioning the presentation is very wellreceived And over the following days, everyone
1:51:14kind of realizes what Shore is going for. Okay. >> Shore's technique to the discrete logarithm problem gets out and he starts getting phone calls from the academic community because now it's spreading. Okay. Bell Labs had this seminar. The f the people who attended the seminar are talking to their friends. They're talking to their friends. um through the grapevine umesh vaz vazirani he's uh another computer scientist who currently is at um the university of California Berkeley he phones Peter Shore on the weekend so Tuesday is when he gave the seminar on the weekend >> uh Vaserani phones yeah he got that
1:51:55phone call and Vaserani understands exactly where this is going and on the phone call he says I hear that you can factor efficiently with a quantum computer Mhm. >> Right. And Peter Shore immediately is like this guy. >> He's like he all he immediately like saw the through line. Right. >> Right. >> In those four days though, Peter Shore spent all of cuz I'm sure he got those comments in the seminar like a >> because basically he sort of had an incomplete map. >> Yeah. And and he had an inkling that this could probably work and now he got feedback that it could probably work. More importantly, he got feedback from people who could definitely make it work, right? And he's like, I need to
1:52:36lock in. >> Yeah. Yeah. >> Like, this is my thing, right? That I mean, he Peter Sh gave a gave a presentation at UCLA like 2 or 3 years ago, um, like a symposium, and he was literally talking about this and he said, you know, when Vaserani telephoned him, it's like, I hear you can factor efficiently with a quantum computer. He was like, "I had been working for 4 days and fortunately I had figured out how to do that. If I hadn't and like I got that phone call, I would have panicked because I'm like, okay, so now literally everybody is going after the factoring algorithm, right, that he is now known for." Peter Shaw
From How Quantum Computing Actually Works (Part 1)
Part I of our quantum computing deep dive traces the field from Bell and Feynman to Deutsch and Shor—and explains what quantum computers actually do differently from classical machines.