The Quantum Pontiff

My favoritest ( 😉 ) meeting SQuInT will be having it’s nineth conference in Albuquerque February 17-19. Whoop, another chance to visit the rattlesnake museum!

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.

Via Geomblog, I see that David Deutsch has won the 2005 $100,000 Edge of Computation Science Prize (see the post here.) Here is the award citation:

Although the general idea of a quantum computer had been proposed earlier by Richard Feynman, in 1985 David Deutsch wrote the key paper which proposed the idea of a quantum computer and initiated the study of how to make one. Since then he has continued to be a pioneer and a leader in a rapidly growing field that is now called quantum information science.
Presently, small quantum computers are operating in laboratories around the world, and the race is on to find a scalable implementation that, if successful, will revolutionize the technologies of computation and communications. It is fair to say that no one deserves recognition for the growing success of this field more than Deutsch, for his ongoing work as well as for his founding paper. Among his key contributions in the last ten years are a paper with Ekert and Jozsa on quantum logic gates, and a proof of universality in quantum computation, with Barenco and Ekert (both in 1995).
One reason to nominate Deutsch for this prize is that he has always aimed to expand our understanding of the notion of computation in the context of the deepest questions in the foundations of mathematics and physics. Thus, his pioneering work in 1985 was motivated by interest in the Church-Turing thesis. Much of his recent work is motivated by his interest in the foundations of quantum mechanics, as we see from his 1997 book.

Congrats to David Deutsch!