A. Yu. Kitaev, California Institute of Technology, Pasadena, CA, and A. H. Shen and M. N. Vyalyi, Independent University of Moscow, Russia
Classical and Quantum Computation
Expected publication date is July 3, 2002
Description
This book is an introduction to a new rapidly developing topic: the theory of quantum computing. It begins with the basics of classical theory of computation: Turing machines, Boolean circuits, parallel algorithms, probabilistic computation, NP-complete problems, and the idea of complexity of an algorithm. The second part of the book provides an exposition of quantum computation theory. It starts with the introduction of general quantum formalism (pure states, density matrices, and superoperators), universal gate sets and approximation theorems. Then the authors study various quantum computation algorithms: Grover's algorithm, Shor's factoring algorithm, and the Abelian hidden subgroup problem. In concluding sections, several related topics are discussed (parallel quantum computation, a quantum analog of NP-completeness, and quantum error-correcting codes).
Rapid development of quantum computing started in 1994 with a stunning suggestion by Peter Shor to use quantum computation for factoring large numbers--an extremely difficult and time-consuming problem when using a conventional computer. Shor's result spawned a burst of activity in designing new algorithms and in attempting to actually build quantum computers. Currently, the progress is much more significant in the former: A sound theoretical basis of quantum computing is under development and many algorithms have been suggested.
In this concise text, the authors provide solid foundations to the theory--in particular, a careful analysis of the quantum circuit model--and cover selected topics in depth. Some of the results have not appeared elsewhere while others improve on existing works. Included are a complete proof of the Solovay-Kitaev theorem with accurate algorithm complexity bounds, approximation of unitary operators by circuits of doubly logarithmic depth. Among other interesting topics are toric codes and their relation to the anyon approach to quantum computing.
Prerequisites are very modest and include linear algebra, elements of group theory and probability, and the notion of a formal or an intuitive algorithm. This text is suitable for a course in quantum computation for graduate students in mathematics, physics, or computer science. More than 100 problems (most of them with complete solutions) and an appendix summarizing the necessary results are a very useful addition to the book. It is available in both hardcover and softcover editions.
Contents
Introduction
Classical computation
Quantum computation
Solutions
Elementary number theory
Bibliography
Index
Details:
Series: Graduate Studies in Mathematics, Volume: 47
Publication Year: 2002
ISBN: 0-8218-3229-8
Binding: Softcover
ISBN: 0-8218-2161-X
Binding: Hardcover
Y. Eliashberg, Stanford University, CA,
and N. Mishachev, Lipetsk Technical University, Russia
Introduction to the h-Principle
Expected publication date is July 19, 2002
Description
One of the most powerful modern methods of solving partial differential equations is Gromov's h-principle. It has also been, traditionally, one of the most difficult to explain. This book is the first broadly accessible exposition of the principle and its applications.
The essence of the h-principle is the reduction of problems involving partial differential relations to problems of a purely homotopy-theoretic nature. Two famous examples of the h-principle are the Nash-Kuiper C^1-isometric embedding theory in Riemannian geometry and the Smale-Hirsch immersion theory in differential topology. Gromov transformed these examples into a powerful general method for proving the h-principle. Both of these examples and their explanations in terms of the h-principle are covered in detail in the book.
The authors cover two main embodiments of the principle: holonomic approximation and convex integration. The first is a version of the method of continuous sheaves. The reader will find that, with a few notable exceptions, most instances of the h-principle can be treated by the methods considered here. There are, naturally, many connections to symplectic and contact geometry.
The book would be an excellent text for a graduate course on modern methods for solving partial differential equations. Geometers and analysts will also find much value in this very readable exposition of an important and remarkable technique.
Contents
Intrigue
Holonomic approximation
Jets and holonomy
Thom transversality theorem
Holonomic approximation
Applications
Differential relations and Gromov's h-principle
Differential relations
Homotopy principle
Open Diff V-invariant differential relations
Applications to closed manifolds
Homotopy principle in symplectic geometry
Symplectic and contact basics
Symplectic and contact structures on open manifolds
Symplectic and contact structures on closed manifolds
Embeddings into symplectic and contact manifolds
Microflexibility and holonomic \mathcal{R}-approximation
First applications of microflexibility
Microflexible \mathfrak{U}-invariant differential relations
Further applications to symplectic geometry
Convex integration
One-dimensional convex integration
Homotopy principle for ample differential relations
Directed immersions and embeddings
First order linear differential operators
Nash-Kuiper theorem
Bibliography
Index
Details:
Series: Graduate Studies in Mathematics,Volume: 48
Publication Year: 2002
ISBN: 0-8218-3227-1
Paging: approximately 198 pp.
Binding: Hardcover
Edited by: Simon Thomas, Rutgers University, New Brunswick, NJ
Set Theory: The Hajnal Conference
Expected publication date is June 7, 2002
Description
This volume presents the proceedings from the Mid-Atlantic Mathematical Logic Seminar (MAMLS) conference held in honor of Andras Hajnal at the DIMACS Center, Rutgers University (New Brunswick, NJ). Articles include both surveys and high-level research papers written by internationally recognized experts in the field of set theory.
Many of the current active areas of set theory are represented in this volume. It includes research papers on combinatorial set theory, set theoretic topology, descriptive set theory, and set theoretic algebra. There are valuable surveys on combinatorial set theory, fragments of the proper forcing axiom, and the reflection properties of stationary sets. The book also includes an exposition of the ergodic theory of lattices in higher rank semisimple Lie groups--essential reading for anyone who wishes to understand much of the recent work on countable Borel equivalence relations.
Contents
S. Adams -- Containment does not imply Borel reducibility
J. E. Baumgartner -- Hajnal's contributions to combinatorial set theory and the partition calculus
C. Darby and J. A. Larson -- Multicolored graphs on countable ordinals of finite exponent
M. Dzamonja -- On D-spaces and discrete families of sets
I. Farah -- Analytic Hausdorff gaps
M. D. Foreman -- Stationary sets, Chang's conjecture and partition theory
I. Juhasz, L. Soukup, and Z. Szentmiklossy -- A consistent example of a hereditarily \mathfrak{c}-Lindelof first countable space of size >\mathfrak{c}
P. Komjath -- Subgraph chromatic number
S. Shelah -- Superatomic Boolean algebras: Maximal rigidity
S. Thomas -- Some applications of superrigidity to Borel equivalence relations
S. Todorcevic -- Localized reflection and fragments of PFA
B. Velickovic -- The basis problem for CCC posets
Details:
Series: DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, Volume: 58
Publication Year: 2002
ISBN: 0-8218-2786-3
Paging: 162 pp.
Binding: Hardcover
Edited by: Robert Coquereaux, Centre de Physique Theorique, Marseille, France, and Centre de International de Rencontres Mathematiques, Marseille, France, Ariel Garcia, Max-Planck-Institut fur Physik, Munchen, Germany, and Roberto Trinchero, Centro Atomico Bariloche and Instituto Balseiro, Argentina
Quantum Symmetries in Theoretical Physics and Mathematics
Expected publication date is June 16, 2002
Description
This volume presents articles from several lectures presented at the school on "Quantum Symmetries in Theoretical Physics and Mathematics" held in Bariloche, Argentina. The various lecturers provided significantly different points of view on several aspects of Hopf algebras, quantum group theory, and noncommutative differential geometry, ranging from analysis, geometry, and algebra to physical models, especially in connection with integrable systems and conformal field theories.
Primary topics discussed in the text include subgroups of quantum SU(N), quantum ADE classifications and generalized Coxeter systems, modular invariance, defects and boundaries in conformal field theory, finite dimensional Hopf algebras, Lie bialgebras and Belavin-Drinfeld triples, real forms of quantum spaces, perturbative and non-perturbative Yang-Baxter operators, braided subfactors in operator algebras and conformal field theory, and generalized (d^N) cohomologies.
Contents
N. Andruskiewitsch -- About finite dimensional Hopf algebras
M. Dubois-Violette -- Lectures on differentials, generalized differentials and on some examples related to theoretical physics
J. Bockenhauer and D. E. Evans -- Modular invariants from subfactors
A. Ocneanu -- The classification of subgroups of quantum SU(N)
O. Ogievetsky -- Uses of quantum spaces
J.-B. Zuber -- CFT, BCFT, ADE and all that
Details:
Series: Contemporary Mathematics, Volume: 294
Publication Year: 2002
ISBN: 0-8218-2655-7
Paging: 230 pp.
Binding: Softcover