Simon’s algorithm
Simon's algorithm, proposed by Daniel Simon in 1993, solves a specific period-finding problem exponentially faster than any classical randomized algorithm. The problem asks: given a function that maps pairs of binary inputs to the same output, find the hidden bitwise XOR that links each matched pair. Mathematician Peter Shor, then on the STOC program committee, recognized that this period-finding structure could be mapped onto cyclic groups over integers, pointing toward applications in cryptography.
- The STOC program committee initially rejected Simon's paper, dismissing it as another artificial black-box puzzle with no practical relevance, much like Deutsch-Jozsa before it.
- Simon's concrete example uses three-digit binary numbers where eight possible inputs collapse to only four outputs, each output shared by exactly two inputs.
- Shor's key insight was that period finding over an algebraic group, which Simon had demonstrated a quantum computer could do fast, could also be applied to cyclic groups over integers, a structure that appears in cryptographic problems.
Transcript
This chapter, from the episode video's captions · 459 words
1:46:58>> Um 1993 computer scientist um Daniel Simon he formulates a quantum algorithm that demonstrates exponential speed up over um a classical randomized algorithms where he's trying to consider a function that's guaranteed to have a hidden period under bitwise exor edition. Um if I don't I don't really want to get into it. effectively like there's a function that has some kind of period. In this case, this is a a function that maps threedigit binary numbers to other three-digit binary numbers except there's um two inputs always map to one input. Okay? So, there's eight different binary numbers, but there's only four
1:47:39different outputs. And like the two green inputs map to the same one 0 1 1 0 1 and the two red outputs map to the same 0 0, right? And it turns out the bitwise exor of the inputs is the same. It's 1 0 1 1 0 for both. If you were to take the bitwise exor of both of the inputs. Okay. The idea is given I have a function like this with this constraint. Can you figure out what is that invariant bitwise exor for the two matched? This is another contrived problem. >> It's it's very similar. It has a similar construction but it but it and it creates >> it's a bit more complicated. creates a different mapping that ultimately is trying to accomplish the same concept.
1:48:20>> Yeah, it's like it's like we're we're now trying to think of problems that a quantum computer could do very very fast that a classical computer can't do very very fast. It's okay if you didn't understand that. The idea is there's some type of period in my function and this thing is trying to figure out what that period is. Okay. Simon submits his findings to the 1993 IE symposium on theory of computing. Okay. And the program committee rejects the paper >> because it dismisses it as just another another artificial blackbox puzzle. It's like, oh, we got another Deutsch Joa here, right? It's like, who cares? >> Okay, when would I encounter such a periodic bitwise exor edition function,
1:49:03>> right? >> Mathematician Peter Shore is on the committee for the STOC. This is Peter Shore when he was a young man. Um, and Shore advocates to accept that manuscript because he recognizes that this formulation represents a period finding over an algebraic group. Okay. >> Okay. Why is this important? He realizes that if period finding can be mapped to something that a quantum computer can do, period finding can also be mapped to cyclic groups over integers. Meaning like there's some weird
1:49:43algebraic math over integers and that can be applied to computational problems in cryptography.
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.