Quantum Computer Science

Front Cover
Morgan & Claypool Publishers, 2009 - Computers - 108 pages
In 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

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
Bibliography
103
Biographies
108
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information