부산대학교 도서관

The objective of this book is to provide the notion of computation in a mathematical way to both advanced undergraduate students and graduate students in mathematics and physics, as well as other scientists working in adjacent fields. This book covers three broad topics: the computation process and its limitations, the search for computational efficiency, and the role of quantum mechanics in computation. \par Chapter 1 is an introductory chapter which states the necessity of a comprehensive understanding of computation even for non-computer scientists and gives the organization of the contents. Chapters 2 and 3 introduce some preliminary notions: the idea of strings over a character set and the idea of a problem. Chapters 4 and 5 introduce the notion of computability---of having an algorithm to answer each of the questions in succession. It turns out that there exist problems that are not computable. That is, each question in the sequence has a definite answer, but there is no single algorithm for answering them all. The strategy is to construct the problem by using the computing language itself. These topics are discussed in Chapters 6 and 7. Chapter 8 discusses the mathematics as a formal logic and mentions the Gödel incompleteness theorem. \par Chapters 9--13 deal with computational efficiency. Chapter 9 introduces how to measure the ``difficulty'' of a computation, namely, the number of steps required to solve the problem. Chapter 10 contains two remarkable results, due to Blum, which serve to illustrate how computational difficulty works. The first result asserts that there exist essentially ``arbitrarily difficult'' problems. The second is to the effect that there exist problems for which there is no ``best'' algorithm. Whereas the notion of computability is essentially language-independent, that of difficulty is not. Better would be a notion of difficulty that attaches to the problem and the method of its solution. Chapters 11 and 12 represent a proposal to capture such a notion. Chapter 13 introduces the idea of incorporating probability into the computational process. \par Chapters 14--21 involve the use of quantum mechanics in the computational process. Rather than summarizing this large area of research, the author focuses on two issues. The first issue is to translate, into mathematics, the physics of utilizing quantum mechanics in the computational process. The second is to examine the issue of whether quantum mechanics can enhance computational efficiency. Chapter 14 is a very brief review of quantum mechanics. Chapter 15 expounds the Grover construction, in which quantum mechanics seems to hold out the prospect of enhanced efficiency. Chapter 16 discusses various issues---some of which turn out to be rather subtle---that arise in connection with the Grover construction. Chapters 14--16 are intended as an informal introduction to the idea of using quantum mechanics as an aid to computation. Chapter 17 specifies what is meant by a ``quantum-assisted computation'' and introduces a certain mathematical computer language. Chapter 18 shows that, provided matters are set up correctly, quantum-assistance will not enable one to solve any otherwise-noncomputable problems. Chapter 19 defines the difficulty function for a quantum-assisted computation. Chapter 20 proves a theorem to the effect that, if there does not exist a problem for which quantum mechanics produces any gain in efficiency, then that gain can never be more than exponential. Finally, Chapter 21 discusses a few ideas about how one might prove that quantum mechanics has the ability to enhance computational efficiency.