## Classical and Quantum ComputationThis book presents a concise introduction to an emerging and increasingly important topic, the theory of quantum computing. The development of quantum computing exploded in 1994 with the discovery of its use in factoring large numbers--an extremely difficult and time-consuming problem when using a conventional computer. In less than 300 pages, the authors set forth a solid foundation to the theory, including results that have not appeared elsewhere and improvements on existing works. The book starts with the basics of classical theory of computation, including NP-complete problems and the idea of complexity of an algorithm. Then the authors introduce general principles of quantum computing and pass to the study of main 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). This is a suitable textbook for a graduate course in quantum computing. Prerequisites are very modest and include linear algebra, elements of group theory and probability, and the notion of an algorithm (on a formal or an intuitive level). The book is complete with problems, solutions, and an appendix summarizing the necessary results from number theory. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Classical Computation | 9 |

Quantum Computation | 53 |

Solutions | 177 |

Appendix A Elementary Number Theory | 237 |

Bibliography | 251 |

### Other editions - View all

Classical and Quantum Computation Alexei Yu. Kitaev,Alexander Shen,Mikhail N. Vyalyi,M. N. Vyalyi No preview available - 2002 |

Classical and Quantum Computation Alexei Yu. Kitaev,Alexander Shen,Mikhail N. Vyalyi No preview available - 2002 |

Classical and Quantum Computation Alexei Yu. Kitaev,Alexander Shen,Mikhail N. Vyalyi,M. N. Vyalyi No preview available - 2002 |

### Common terms and phrases

ancillas apply approximate arbitrary assume basis vectors binary bits Boolean circuit Boolean function classical complete basis complexity conﬁguration consider controlling qubit copies corresponding deﬁned deﬁnition denotes density matrix depth eigenvalues elements encoding equation error example exists factor ﬁeld ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed follows formula fraction function F gate graph Hamiltonian inequality input string integer Lemma length linear measuring operator mod q multiplication nonnegative nonzero norm Note NP-complete obtain operator norm oracle output P/poly pair partial trace path permutation physically realizable poly(n polynomial precision predicate prime probabilistic problem proof Prove PSPACE quantum algorithm quantum circuit quantum computation qubits random represented result reversible circuit satisﬁes sequence simulation solution space Speciﬁcally standard basis steps SU(M subgroup subspace sufﬁcient superoperator symbol symplectic tape Theorem Toffoli gate transformation Turing machine unitary operator vertex vertices Z/qZ