## Quantum Computer ScienceIn this text we present a technical overview of the emerging field of quantum computation along with new research results by the authors. What distinguishes our presentation from that of others is our focus on the relationship between quantum computation and computer science. Specifically, our emphasis is on the computational model of quantum computing rather than on the engineering issues associated with its physical implementation. We adopt this approach for the same reason that a book on computer programming doesn't cover the theory and physical realization of semiconductors. Another distinguishing feature of this text is our detailed discussion of the circuit complexity of quantum algorithms. To the extent possible we have presented the material in a form that is accessible to the computer scientist, but in many cases we retain the conventional physics notation so that the reader will also be able to consult the relevant quantum computing literature. Although we expect the reader to have a solid understanding of linear algebra, we do not assume a background in physics. This text is based on lectures given as short courses and invited presentations around the world, and it has been used as the primary text for a graduate course at George Mason University. In all these cases our challenge has been the same: how to present to a general audience a concise introduction to the algorithmic structure and applications of quantum computing on an extremely short period of time. The feedback from these courses and presentations has greatly aided in making our exposition of challenging concepts more accessible to a general audience. Table of Contents: Introduction / The Algorithmic Structure of Quantum Computing / Advantages and Limitations of Quantum Computing / Amplitude Amplification / Case Study: Computational Geometry / The Quantum Fourier Transform / Case Study: The Hidden Subgroup / Circuit Complexity Analysis of Quantum Algorithms / Conclusions / Bibliography |

### What people are saying - Write a review

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

### Contents

3 | |

4 | |

8 | |

10 | |

11 | |

12 | |

116 QUANTUM COMPUTING PROPERTY 6 | 16 |

117 QUANTUM COMPUTING PROPERTY 7 | 17 |

411 QMOS FOR OBJECTOBJECT INTERSECTION IDENTIFICATION | 59 |

412 QMOS FOR BATCH INTERSECTION IDENTIFICATION | 61 |

42 QUANTUM RENDERING | 62 |

422 RAYTRACING | 63 |

423 RADIOSITY | 68 |

424 LEVEL OF DETAIL | 70 |

43 SUMMARY | 71 |

The Quantum Fourier Transform | 73 |

118 QUANTUM COMPUTING PROPERTY 8 | 19 |

12 SUMMARY | 21 |

Advantages and Limitations of Quantum Computing | 23 |

22 CLASSICAL AND QUANTUM COMPLEXITY CLASSES | 24 |

23 ADVANTAGES AND DISADVANTAGES OF THE QUANTUM COMPUTATIONAL MODEL | 25 |

24 HYBRID COMPUTING | 28 |

251 ALGORITHMIC CONSIDERATIONS | 29 |

252 QUANTUM ALGORITHM DESIGN | 31 |

26 QUANTUM BUILDING BLOCKS | 32 |

27 SUMMARY | 33 |

Amplitude Amplification | 35 |

31 QUANTUM SEARCH | 36 |

312 SEARCHING DATA IN A QUANTUM REGISTER | 38 |

313 GROVERS ALGORITHM | 39 |

314 GENERALIZED QUANTUM SEARCH | 48 |

32 GROVERS ALGORITHM WITH MULTIPLE SOLUTIONS | 49 |

33 FURTHER APPLICATIONS OF AMPLITUDE AMPLIFICATION | 52 |

Case Study Computational Geometry | 53 |

41 GENERAL SPATIAL SEARCH PROBLEMS | 55 |

52 THE QUANTUM FOURIER TRANSFORM | 74 |

53 MATRIX REPRESENTATION | 75 |

54 CIRCUIT REPRESENTATION | 76 |

55 COMPUTATIONAL COMPLEXITY | 80 |

561 NORMALIZATION | 81 |

57 SUMMARY | 82 |

Case StudyThe Hidden Subgroup | 83 |

62 PERIOD FINDING | 86 |

63 THE HIDDEN SUBGROUP PROBLEM | 88 |

64 QUANTUM CRYPTOANALYSIS | 89 |

65 SUMMARY | 92 |

Circuit Complexity Analysis of Quantum Algorithms | 95 |

73 CLASSICAL AND QUANTUM CIRCUIT COMPLEXITY ANALYSIS | 96 |

74 COMPARING CLASSICAL AND QUANTUM ALGORITHMS | 97 |

75 SUMMARY | 99 |

Conclusions | 101 |

103 | |

Biographies | 108 |

### Other editions - View all

### Common terms and phrases

algorithm design amplitude ampliﬁcation analysis applied arbitrary architecture best known classical box queries CC algorithms chapter ciphers circuit complexity classical algorithm classical alternative classical bit classical computer CNOT computational basis computational complexity Computational Geometry computational steps convex hull database dataset deﬁned determine difﬁcult efﬁciently elements example exploit exponentially faster exponentially large extra qubits factor ﬁnd ﬁnding ﬁrst Grover iteration Grover’s algorithm hardware Hidden Subgroup Problem identiﬁcation implementation important to note initial integer linear matrix measurement n-bit n-qubit no-cloning theorem number of gates optimal output overall complexity perform pixel polygon possible probability QMOS quan quantum algorithms quantum circuit quantum computing model Quantum Fourier Transform quantum information quantum model quantum oracle quantum parallelism quantum processor quantum register quantum search quantum solution quantum superposition qubit radiosity ray tracing reﬂected representation represents require result scene search problem simulation space speciﬁc sublinear uniform superposition unitary operator vector Z-Buffering