Quantum computation was put on the map, so to speak, with Peter Shor’s discovery in 1994 that quantum computers could efficiently factor numbers. It is interesting to contemplate how this discovery will be viewed in our distant future. We are now over ten years out from Shor’s discovery. Perhaps this is too short of time to make a judgement, put let’s be arrogant and try to make such a historical judgement. Along these lines, I’d claim that Shor’s algorithm is one of the most significant discoveries about algorithms in modern history. There are a certain group of algorithms, like Euclid’s algorithm for computing a greatest common denomenator, which, in my mind are among the most beautiful, eternal algorithms which we know. (Algorithms from the code book, so to speak.) I would like to make the claim that Shor’s algorithm belongs in the same category as these algorithms. First of all Shor’s algorithm solves a problem, factoring, which feels like one of those problems which lies very close to the base of mathematics. Certainly most of us learned about factoring numbers at a very young age, and indeed the view of a number as a product of its factors shapes in a deep way the manner in which we think about integers. Second, Shor’s algorithm use of period finding reveals in a deep way how quantum theory changes the way we can process information. That global properties of symmetric quantum states can be extracted from quantum systems, but not for their equivalent classical systems, is a deep observation and one which we are only now beginning to push in new directions.
So, I’ll claim, Shor’s algorithm is a very profound discovery which will be thought of for centuries to come as one of our humanities most beautiful discoveries. Interestingly, I think, this also puts a huge cloud over those of us working to try to discover new quantum algorithms. For instance, Sean Hallgren’s discovery that quantum computers can efficiently solve Pell’s equation is an awesome result, but viewed in light of factoring, well it’s just hard to compete! Certainly one effect of this is that looking for new quantum algortihms has gained a reputation as being a very difficult field. And indeed, if you define difficult as coming up with something which is more deep that Shor’s algorithm, then working towards new quantum algorithms can seem a hopeless task. Indeed this is one of ther reasons there has been so much focus on the hidden subgroup problem: an efficient algorithm for this problem would lead to efficient algorithms for the graph isomorphism problem and certain k-shortest vector in a lattice problems, and these are big problems, whose solution would represent big progress in algorithms. So we in quantum algorithms, set our sights extermely high, because Shor set a bar which is at world-record pole-vault heights. Certainly this point of view argues for working on much smaller progress in quantum algorithms: understanding more basic simple primitives even if they don’t lead to algorithms which are “better than Shor.” I, myself, struggle with thinking along these lines: our expectations are high and it is hard to not try to jump over the Shor barrier. But perhaps those with better self control can move in these directions and maybe, if we are lucky this progress will eventually show us new ways that quantum computers can outperform they nasty rivals, classical computers.
O brave new quantum world!
I agree, your analysis is arrogant. 🙂
Okay, it’s not all that arrogant, but I don’t completely agree with your conclusions. Research in science, especially algorithms, can be likened to an easter egg hunt. If you are a talented easter egg hunter, you are more likely to find jeweled eggs. However, if the egg that you found is 100 times more valuable, that does not prove that you are 100 times as talented.
I have the deepest respect for Peter Shor for what he has done. Several of his papers, not just that one, are brilliant. But his algorithm was also an easter egg waiting to be found. There was a clear progression of papers leading to it: First Feynman, then Deutsch, then Deutsch-Jozsa, then Bernstein-Vazirani, then Simon.
In particular, people working on quantum algorithms (maybe I can count as one of them) should not feel any shame for not making more progress. Who knows where the easter eggs are now. My perspective may be a bit different because I have tenure. I choose to work on this. If I find something, great. If not, that’s the way the egg rolls.
“The sad thing about quantum simulation is that [its] results…will be more important…than the algorithm itself.”
Man, you just painted “theorist” in bright red letters on your forehead with that one! That’s like saying, “The sad thing about Google is that people actually use the search results, rather than admiring the beautiful indexing system they’ve built.”
I’m a life-long (well, quarter of a century, anyway) systems geek/engineer. I think the systems themselves are fascinating and beautiful. But part of what makes them so is that they are useful.
I’m just a tad too young to have been involved in the first wave, even if I had been in the right field, but I was a student at Caltech just as VLSI was evolving; I remember some of the anxiety over the fact that we were crossing the threshold in which computers could no longer be designed by hand, we had to depend on computers to do it.
I’m reminded of the story of Seymour Cray. When told that Apple had bought a Cray to design Macintoshes with (thermal simulations), he got quiet for a moment, then said, “That’s funny, I use a Mac to design a Cray.”
I’m working as hard as I can on designing one for you :-). This week I’m actually optimistic that one can be built before I retire; some days, I think we can do it in under a decade.
I agree about Shor, btw. So what’s the Turing Award committee waiting for? It only took them thirty five years or so to getting around to recognizing that the Internet is important.
The Turing Award is for lifetime achievement. I’d not presume to think that Peter Shor’s best days are behind him :).
Some Turing Awards have indeed been presented for individual results; Cook/Hartmanis+Stearns/RSA.
some might argue that even Hopcroft and Tarjan got theirs for a single result. But in all cases, the “single result” in retrospect laid the foundations for a field (NP-Completeness/Complexity theory/cryptography/Data structures and algorithms respectively). It is debatable whether the Shor-factoring laid the foundation for quantum computing as much as it is the shining star of the field.
In my opinion, it is an historical accident that we live in a world in which efficient algorithms for integer factoring are so important. As beautiful a number-theoretic tour-de-force as Shor’s algorithm is, I would be surprised if this is the best that quantum mechanics can muster. Shor’s algorithm may have set a high mark, but the developers of quantum mechanics have set an even higher mark. Indeed, I have heard John Preskill refer to quantum mechanics as “The crowning intellectual achievement of the 20th century.”
If I had to guess (with all the caveats and admonitions about prognostications acknowledged), I would conjecture that the ultimate “killer app” for quantum computers will be quantum simulation. What quantum systems will quantum computers of the future simulate? My crystal ball isn’t very clear on this issue. 🙂 One thing I’m certain they will simulate, though, is even more advanced quantum computers. We use today’s classical computers to design tomorrow’s—it stands to reason that the same will be true for quantum computers.
The sad thing about quantum simulation is that it is the kind of tool which, while we can theorize about algorithms for it, is a tool whose results will be more important, in some sense, than the algorithm itself: i.e. if quantum simulation can be used to engineer quantum materials with extreme technological implications, then in a real sense this can only occur once we’ve built a quantum computer. Whereas Shor’s algorithm is a result we can grasp today without even building a quantum computer. This shouldn’t stop us from thinking about algorithms for quantum simulation, but it certainly makes it harder to quantify what their impact will be.
Heh. Well I meant sad as in, “I really really want one of these machines to play with so that I can do quantum simulations and discover how to build room temperature superconductors, but damnit I’m going to have to wait until we build one!”
Quick question(s), in particular for Dave, Rod and Andrew:
Given a quantum computer, which physical system would you simulate?
What algorithm would you use to do this? And what kind of useful
answers will you expect to get out of the simulation?