Y. I. Manin, Computable and Uncomputable, Sov. Radio (1980), published in: Mathematics as Metaphor: Selected essays of Yuri I. Manin, Collected Works 20, AMS (2007), 69-77, [ISBN:978-0-8218-4331-4]

I have not been able to find a free copy of this essay online.

This 'paper' gets cited a lot as the first published appearance of the idea of a quantum computer, sometimes as a "gotcha" when somebody says Feynman came up with the idea. Feynman set out the idea in a 1982 paper (which we'll come to), but Manin wrote this 2 years earlier on the other side of the Iron Curtain.

In fact it is not a paper, it is the introduction to a book that he wrote about computability theory. An English translation of the introduction has been published in Manin's Collected Works; I don't know if the whole book has ever been translated.

In the introduction, he talks about the concept of an algorithm in a very general sense: the first example of an algorithm that he gives is an enzyme. The idea of a quantum computer does not appear until the last 2 pages.

There are some nice turns of phrase in the introduction: computer science "must work on the brink of the abyss of uncomputability".

There are some naughty comments about intuitionism/constructivism in there too: work on computable analysis is "often strongly motivated by a philosophical or simply emotional bias going back to concerns about the 'foundations of mathematics'."

He sketches the work by Gödel, Church and Turing on how many different models of computation lead to the same set of functions as being the "computable" functions, namely the recursive functions. He spends most of his time on Matiyasevitch's result that the recursive functions are the same as those given by Diophantine equations (i.e. a function \(f\) is computable if and only if there exists a polynomial with integer coefficients \(P(x,y,z_1,\ldots,z_n)\) such that \(f(a)=b\) if and only if there exist integers \(c_1,\ldots,c_n\) such that \(P(a,b,c_1,\ldots,c_n) = 0\)).

Most of the introduction is concerned with language. He says that the work on machine translation has shown that the Meaning-Text theory is an important framework for analysing language (ah, the days before machine learning was king), and the possibility of algorithms for computing a text's semantic meaning and vice versa. 

"The relation between text and its meaning should be compared to the relation between a program and its output, or a program and its implementation, rather than the relation between a snapshot of reality and reality itself."

He discusses different numeral systems, systems for naming numbers, both real ones from history and theoretically possible ones, such as Kolmogorov's result on the existence of a numeral system where each number has the shortest name possible (at a cost: each number has more than one name, and the algorithm for computing a number from its name is complex).

Finally, with less than 2 pages to go, he introduces the idea of a quantum computer. Except he doesn't - he doesn't propose building a machine that works by quantum principles (which Feynman very explicitly does). He argues that, in understanding DNA replication, we should analyse it as a "quantum automaton" instead of a classical machine. He argues that a quantum system has many more states than a similarly sized classical system, but gives credit for this observation to Poplavskii in 1975. He ends with some vague thoughts about how it might be possible to analyse the behaviour of a quantum automaton.

It seems clear to me that he is talking about understanding existing quantum phenomena, and not proposing the construction of a type of machine. Feynman very much was proposing the construction of a machine, and arguing that this would be a good thing to do.

This is not a criticism of Manin at all; rather a criticism of the battles over academic priority. Now, if A comes up with an idea and B then uses A's work, of course B should give A credit. But if A and B come up with the same idea independently, it is really not important if one was two years (or five minutes) before the other. Maybe we have to draw that distinction for the purposes of patent law, or for academic prizes; but in general science is a giant global cooperation, not a competition.

When you look at the history of any idea, there are always precursors and almost always very similar ideas proposed more or less simultaneously. It's not a 'fact' that Manin came up with the idea of a quantum computer before Feynman. You could make an argument for Feynman, Manin or Poplavskii (and probably others) as the first to come up with the idea. I would favour Feynman, because, out of the three, he was the one who proposed building an actual machine.

Manin was clearly a very deep thinker. His 10-page introduction to a book on computability theory ranges from the number system of the Duwei people (who had no words for numbers above 20) to whether an enzyme can be considered a computer. It's made me want to read more of his work (add it to the very long list!)

Next: It's time to start the mathematical part of this project with a subject that I missed out on as an undergraduate and have regretted ever since, topology. K. Jänich, Topology, Undergraduate Texts in Mathematics, Springer, Berlin (1984), [ISBN:9780387908922]