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.

At some point in my university career I was torn. I was interested in theoretical computer science, pure math (particularly functional analysis) and quantum mechanics. I decided the natural career path was to become John von Neumann. It’s not an easy job, but I hear there is an opening.

Indeed, they’ve been having trouble filling that positon for some time.

Maybe a better question is: why didn’t von Neumann invent

classicalcomputational complexity theory? As you mentioned, that would certainly have been a first step toward inventing quantum computing!My own answer is simply that (1) von Neumann had a huge amount on his plate, and (2) he died in 1957. (Indeed, it was while he was dying in a hospital that Gödel sent him his famous letter about P vs. NP. But we don’t know if von Neumann ever even saw this letter, let alone thought about it.)

Some of von Neumann’s papers from the fifties show that he

wasaware of computational scaling as an issue, and of polynomial scaling being better than exponential scaling. Probably, this was one of many things that he died before he was able to follow up on.Interestingly, Feynman did

nothave a particularly good appreciation of complexity — if you read hisLectures on Computation, complexity never appears even once! And even in his famous 1982 talk on quantum computers, complexity only appears as one of many issues to be considered.What isn’t often appreciated about Feynman is that he managed the computational department at Los-Alamos in his early twenties, arranging stacks of calculation cards that contained solutions of partial diffential equations running through a mill of secretaries with hand-calculators. He was always therefore conscious of the actual practical aspects of calculations, and this influenced his formulations of problems— he often stated the results algorithmically as opposed to algebraically. This computational point of view was taken to an extreme by Feynman’s collaborator Wolfram, but it is reflected in many of Feynman’s works of the 50’s and 60’s (for instance, the path integral and He4 work, which is formulated in terms of ground state properties, including the imaginary time connection with stochastic processes, which allows the ground-state properties to be more efficiently solved by Monte-carlo on a probabilistic computer than the naive diagonalization of an enormous dimensional matrix, or the diagrams, which reduce the algorithmic complexity of internal propagators by unifying the antiparticle and particle propagators, which are separate in the old fasioned perturbation theory).