Quantum Computer Science: qq.JPG

ABSTRACT
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.
KEYWORDS
Quantum Computing, Quantum Algorithms, Quantum Information, Computer Science,
Grover’s Algorithm, Shor’s Algorithm, Quantum Fourier Transform, Circuit
Complexity, Computational Geometry, Computer Graphics, The Hidden Sub-Group
Problem, Cryptoanalysis.

Contents
Synthesis Lectures on Quantum Computing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .iii
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xiii
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 The Algorithmic Structure of Quantum Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Understanding Quantum Algorithmics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
1.1.1 Quantum Computing Property #1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Quantum Computing Property #2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Quantum Computing Property #3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Quantum Computing Property #4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.5 Quantum Computing Property #5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.6 Quantum Computing Property #6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.7 Quantum Computing Property #7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.8 Quantum Computing Property #8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Advantages and Limitations of Quantum Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
2.1 Quantum Computability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Classical and Quantum Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Advantages and Disadvantages of the Quantum Computational Model . . . . . . . . 25
2.4 Hybrid Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 The QRAM Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28
2.5.1 Algorithmic Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
x CONTENTS
2.5.2 Quantum Algorithm Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6 Quantum Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Amplitude Amplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35
3.1 Quantum Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36
3.1.1 Quantum Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Searching Data in a Quantum Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.3 Grover’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39
3.1.4 Generalized Quantum Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Grover’s Algorithm with Multiple Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49
3.3 Further Applications of Amplitude Amplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 Case Study: Computational Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1 General Spatial Search Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 QMOS for Object-Object Intersection Identification . . . . . . . . . . . . . . . . . . 59
4.1.2 QMOS for Batch Intersection Identification . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Quantum Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2.1 Z-Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62
4.2.2 Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63
4.2.3 Radiosity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.4 Level of Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5 The Quantum Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.1 The Classical Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73
5.2 The Quantum Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74
5.3 Matrix Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
5.4 Circuit Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.6 Algorithmic Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
CONTENTS xi
5.6.1 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6.2 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6.3 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6 Case Study: The Hidden Subgroup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1 Phase Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Period Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3 The Hidden Subgroup Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.4 Quantum Cryptoanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7 Circuit Complexity Analysis of Quantum Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
7.1 Quantum Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
7.2 Algorithmic Equity Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
7.3 Classical and Quantum Circuit Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.4 Comparing Classical and Quantum Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .97
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103
Biographies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108

thank you fo r the book,it is useful to me

好书啊！！！！！！！！！！！！！！！！！！！！！！

是好书就下载下来拜读拜读，谢谢斑竹啦。。。。。

:11bb :27bb :29bb ：9de

:11bb :11bb :11bb :11bb

谢谢，收藏了。。。。。。。。。。。。。

感谢楼主分享
:11bb :11bb :11bb :11bb