Quantum Computer Science: An Introduction

by N. David Mermin

• ISBN13: 9780521876582
• ISBN10: 0521876583
• eBook ISBN(s): 9781139637596
• Additional ISBN(s): 9780511339820
• Format: Hardcover
• Copyright: 2007-09-17
• Publisher: Cambridge University Press

Summary

In the 1990's it was realized that quantum physics has some spectacular applications in computer science. This book is a concise introduction to quantum computation, developing the basic elements of this new branch of computational theory without assuming any background in physics. It begins with an introduction to the quantum theory from a computer-science perspective. It illustrates the quantum-computational approach with several elementary examples of quantum speed-up, before moving to the major applications: Shor's factoring algorithm, Grover's search algorithm, and quantum error correction. The book is intended primarily for computer scientists who know nothing about quantum theory, but will also be of interest to physicists who want to learn the theory of quantum computation, and philosophers of science interested in quantum foundational issues. It evolved during six years of teaching the subject to undergraduates and graduate students in computer science, mathematics, engineering, and physics, at Cornell University.

Author Biography

N. David Mermin is Horace White Professor of Physics Emeritus at Cornell University.

Table of Contents

Preface	p. xi
A note on references	p. xv
Cbits and Qbits	p. 1
What is a quantum computer?	p. 1
Cbits and their states	p. 3
Reversible operations on Cbits	p. 8
Manipulating operations on Cbits	p. 11
Qbits and their states	p. 17
Reversible operations on Qbits	p. 19
Circuit diagrams	p. 21
Measurement gates and the Born rule	p. 23
The generalized Born rule	p. 28
Measurement gates and state preparation	p. 30
Constructing arbitrary 1- and 2-Qbit states	p. 32
Summary: Qbits versus Cbits	p. 34
General features and some simple examples	p. 36
The general computational process	p. 36
Deutsch's problem	p. 41
Why additional Qbits needn't mess things up	p. 46
The Bernstein-Vazirani problem	p. 50
Simon's problem	p. 54
Constructing Toffoli gates	p. 58
Breaking RSA encryption	p. 63
Period finding, factoring, and cryptography	p. 63
Number-theoretic preliminaries	p. 64
RSA encryption	p. 66
Quantum period finding: preliminary remarks	p. 68
The quantum Fourier transform	p. 71
Eliminating the 2-Qbit gates	p. 76
Finding the period	p. 79
Calculating the periodic function	p. 83
The unimportance of small phase errors	p. 84
Period finding and factoring	p. 86
Searching with a quantum computer	p. 88
The nature of the search	p. 88
The Grover iteration	p. 89
How to construct W	p. 94
Generalization to several special numbers	p. 96
Searching for one out of four items	p. 98
Quantum error correction	p. 99
The miracle of quantum error correction	p. 99
A simplified example	p. 100
The physics of error generation	p. 109
Diagnosing error syndromes	p. 113
The 5-Qbit error-correcting code	p. 117
The 7-Qbit error-correcting code	p. 121
Operations on 7-Qbit codewords	p. 124
A 7-Qbit encoding circuit	p. 127
A 5-Qbit encoding circuit	p. 128
Protocols that use just a few Qbits	p. 136
Bell states	p. 136
Quantum cryptography	p. 137
Bit commitment	p. 143
Quantum dense coding	p. 146
Teleportation	p. 149
The GHZ puzzle	p. 154
Appendices	p. 159
Vector spaces: basic properties and Dirac notation	p. 159
Structure of the general 1-Qbit unitary transformation	p. 168
Structure of the general 1-Qbit state	p. 173
Spooky action at a distance	p. 175
Consistency of the generalized Born rule	p. 181
Other aspects of Deutsch's problem	p. 183
The probability of success in Simon's problem	p. 187
One way to make a cNOT gate	p. 189
A little elementary group theory	p. 193
Some simple number theory	p. 195
Period finding and continued fractions	p. 197
Better estimates of success in period finding	p. 201
Factoring and period finding	p. 203
Shor's 9-Qbit error-correcting code	p. 207
A circuit-diagrammatic treatment of the 7-Qbit code	p. 210
On bit commitment	p. 216
Index	p. 218
Table of Contents provided by Ingram. All Rights Reserved.