Why not von Neumann?

Anyone who read the comments on my last post will know that von Neumann is something of a hero of mine. Here’s a question that sometimes bothers me – why didn’t von Neumann think of quantum computing? Compare his profile with that of Feynman, who did think up quantum computing, and then ask yourself which one of them you would have bet on to come up with the idea.

• von Neumann: Worked on a variety of different subjects thoughout his career, including interdisciplinary ones. Was well aware of the work by Turing, Church, Post and others that later became the foundation for computer science and of the role of logic in this work. Is credited with the design of the basic architechture of modern computers. Worked on the mathematical and conceptual foundations of quantum mechanics and is responsible for the separable Hilbert space formulation of quantum theory that we still use today. Finally, at some point he was convinced that the best way to understand quantum theory was as a probability theory over logical structures (lattices) that generalize some of those from classical logic.
• Feynmann: Spent most of his career working on mainstream topics in quantum field theory and high energy physics. Only towards the end of his career did his interests significantly diversify to include the theories of computation, quantum gravity and the foundations of quantum theory. Conceived of quantum theory mainly in the “sum over paths” formalism, where one looks at quantum theory as a rule for attaching amplitudes to possible histories as opposed to the probabilities used in classical theories.

None of this is meant as a slight against Feynman – he was certainly brilliant at everything he did scientifically – but it is clear that von Neumann was better positioned to come up with the idea much earlier on. Here are some possible explanations that I can think of:

• The idea of connecting quantum mechanics to computing just never occurred to von Neumann. They occupied disjoint portions of his brain. Ideas that seem simple in hindsight are really not so obvious, and even the greatest minds miss them all the time.
• von Neumann did think of something like quantum computing, but it was not obvious that it was interesting, since the science of computational complexity had not been developed yet. Without the distinction between exponential and polynomial time, there is no way to identify the potential advantage that quantum computers might offer over their classical counterparts.
• The idea of some sort of difference in computing when quantum mechanics is thrown into the mix did occur to von Neumann, but he was unable to come up with a relevant model of computing because he was working with the wrong concepts. As alluded to in a paper of mine, Birkhoff-von Neumann quantum logic is definitely the wrong logic for thinking about quantum computing because the truth of quantum logic propositions on finite Hilbert spaces may be verified on a classical computer in polynomial time. The basic observation was pointed out to me by Scott Aaronson, but one needs to set up the model quite carefully to make it rigorous. I might write this up at some point, especially if people continue to produce papers that use quantum computing as a motivation for studying concrete BvN quantum logic on Hilbert spaces. Anyway, the point is that if von Neumann thought that replacing classical logic with his notion quantum logic was the way to come up with a model of quantum computing, then he would not have arrived at anything useful.
• As a mathematician, von Neumann was not able to think of any practical problem to do with quantum mechanics that looks hard to do on a classical computer, but could be done efficiently in the quantum world. As a physicist, Feynman was much better placed to realize that simulating quantum dynamics was a useful thing to do, and that it might require exponential resources on a classical computer.

As a von Neumann fan, I’d like to think that something other than the first explanation is true, but I am prepared to admit that he might have missed something that ought to have been obvious to him. Hopefully, someday a historian of science will take it upon themselves to trawl the von Neumann archives looking for the answer.