Martin Zwierlein

In May 1994, Artur Ekert visited Caltech to give a seminar about quantum cryptography. Near the end of the talk, Ekert revealed an exciting new development — just weeks earlier, Peter Shor had announced the discovery of an efficient quantum algorithm for finding the prime factors of large composite integers, a problem for which no efficient classical algorithm is known.

Perhaps I’ve embellished the memory over time, but I recall being awestruck by this news. I spent the next month at the Isaac Newton Institute attending a workshop about quantum black holes, and though it was a very good workshop and I had some great discussions, I spent most of my time there secretly trying to understand Shor’s paper, which Ekert had emailed to me. This took some effort, because I knew little about algorithms or computational complexity at that time (even less than I know now), but by the end of the workshop I felt I understood the ideas behind Shor’s algorithm pretty well. I did not yet realize that I was in the midst of a career transition from particle physics to quantum information science.
Continue reading →