Quantum Computing (Advanced topics in computer science series) [Paperback]

This is the best text I have seen on quantum information and computation theory, covering all major areas clearly, thoughtfully and thoroughly: quantum algorithms and computational complexity, error-correction and fault-tolerant computation, cryptography, communication complexity, quantum channels, theory of entanglement and (very briefly) potential physical realizations. Although much of the interest in this field has been driven by hope of eventually building a quantum computer able to crack otherwise unbreakable codes, Gruska places the discoveries in a broad context: "...historically much of fundamental physics has been devoted to discovering the fundamental particles of Nature and the equations which describe their motions and interactions. Now it appears that a different program may be equally important. Namely, to discover the ways Nature allows, and prevents, information to be expressed and manipulated, rather than particles to move." Although intended for computer science students, Gruska's text can be read profitably by anyone with an undergraduate mathematical background who wants a lucid but uncondescending explanation of quantum mysteries, physicists' historical efforts to make sense of them, and the amazing uses they can be put to in information processing. There is a live web site for errata and updates.

Quantum Computing is a new and quickly expanding area of research both for physicists and for computer people. If you visit Amazon.co.uk web site, you see that only a couple of books related to Quantum Computing is available, and none of them can be used as a textbook. Strangely enough, Internet contains much more information. You can find good lecture notes at Umesh Vazirani (Berkeley), John Preskill (Caltech), Michaelmas Term Seminar (Oxford) home pages. However Jozef Gruska's book "Quantum Computing", McGraw Hill, 1999 seems to be the first real textbook on the subject.The text covers basic quantum mechanics needed to understand the strange behavior of the objects considered, the mathematics of Hilbert space, the notion of entanglement, Quantum Fourier Transform, the surprising algorithms by P. Shor and L. Grover , results on quantum automata and complexity of quantum algorithms, quantum information theory and much-much more. In 1982 Nobel prize winner physicist Richard Feynman noticed that a precise simulation of quantum processes by a deterministic computer demands an exponential slowdown. He explicitly turned everybody's attention to the fact that we can look to this effect from another point of view. There are some processes such that they can be speeded up enormously if we use a quantum simulation of them instead of a computation on a classical computer. There are rather strange features of quantum information processing. The most striking one is that nobody is able to copy the information. In the classical world the possibility to make a copy of your data to a personal floppy disc is considered as essential. Not so in a quantum computer. Only unitary operations with the data are possible. Of course, this is only one distinction from the classical computation. On the other hand, quantum computers (when they will be built) may be most efficient in some cases. After preceding discoveries by Bernstein/Vazirani (1993) and Simon (1994) Peter Shor (Bell Labs) surprised the world in 1994 showing quantum algorithms for factorization of integers and computation of discrete logarithms in polynomial time. These algorithms immediately turned the problem of building a quantum computer into a highly practical and even strategic problem because most of the Public Key Cryptography is based on the assumption that the above-mentioned algorithms demand VERY MUCH TIME. The problems of Quantum Computation became interesting for Theoretical Computer Science as well. Much research is done on quantum finite automata. There are languages recognizable by deterministic finite automata but not recognizable by quantum finite automata (A. Kondacs and J. Watrous , 1997). On the other hand, there are languages for recognition of which quantum finite automata are more concise than both deterministic and and probabilistic finite automata (A. Ambainis and R. Freivalds, 1998).