Peter Shor’s Quantum Computing Talk
I was just reading a book on quantum algorithms, which starts just like this:
Here is a bit of personal history: Peter Shor’s sister, Molly Shor was an assistant professor at Oregon State University when I was also there (I was at OSU from 1992 to 2005). Molly and a math professor (Rob Robson) told me about Peter’s work, and we invited him to give a talk at OSU. He came to Corvallis and actually gave his famous talk in my Computer Arithmetic class (held in Room 106 in ECE Building) on Wednesday 2pm in November 8, 1995.
How do I know the exact time? Well: I am keeping all of my emails since the very first day one I got an email address (March 1984); so I checked, and found the abstract and biography. I even have an email from Peter who says, “perhaps the Computer Arithmetic class is not the best place for it”, but in the end he agreed; I also turned my class time into “ECE Colloquium” and invited Math, CS and ECE graduate students and faculty.
Quantum Computing
Peter Shor, AT&T Bell Labs
ECE Colloquium
ECE Building, Room: 106
2:00 PM, Wednesday, November 8
Abstract
A computer is generally considered to be a universal computational device, in other words, it is able to simulate any physical computational device with a cost of at most a polynomial factor in the computation time. It is not clear that this is still true if quantum mechanics is taken into account. Several researchers, starting with David Deutch, have developed models for quantum mechanical computers and investigated their computational properties. I show that these computers can factor integers in polynomial time, much faster than the best known algorithm for factoring on classical digital computers.
Brief Biography of the Speaker
Peter Shor received his B.S. from Caltech in 1981, and his Ph.D. in Mathematics from M.I.T. in 1985. His dissertation was on applications of probability theory to bin packing algorithms. After spending a year at the Mathematical Sciences Research Institute in Berkeley, he went to AT&T Bell Labs, and has been here since, mainly working on algorithms in theoretical computer science.