Introduction to Quantum Computing [Mīkstie vāki]

Preface		x
Acknowledgements		xi
Introduction and Background		1	(20)
Overview		1	(1)
Computers and the Strong Church--Turing Thesis		2	(4)
The Circuit Model of Computation		6	(2)
A Linear Algebra Formulation of the Circuit Model		8	(4)
Reversible Computation		12	(3)
A Preview of Quantum Physics		15	(4)
Quantum Physics and Computation		19	(2)
Linear Algebra and the Dirac Notation		21	(17)
The Dirac Notation and Hilbert Spaces		21	(2)
Dual Vectors		23	(4)
Operators		27	(3)
The Spectral Theorem		30	(2)
Functions of Operators		32	(1)
Tensor Products		33	(2)
The Schmidt Decomposition Theorem		35	(2)
Some Comments on the Dirac Notation		37	(1)
Qubits and the Framework of Quantum Mechanics		38	(23)
The State of a Quantum System		38	(5)
Time-Evolution of a Closed System		43	(2)
Composite Systems		45	(3)
Measurement		48	(5)
Mixed States and General Quantum Operations		53	(8)
Mixed States		53	(3)
Partial Trace		56	(3)
General Quantum Operations		59	(2)
A Quantum Model of Computation		61	(17)
The Quantum Circuit Model		61	(2)
Quantum Gates		63	(5)
1-Qubit Gates		63	(3)
Controlled-U Gates		66	(2)
Universal Sets of Quantum Gates		68	(3)
Efficiency of Approximating Unitary Transformations		71	(2)
Implementing Measurements with Quantum Circuits		73	(5)
Superdense Coding and Quantum Teleportation		78	(8)
Superdense Coding		79	(1)
Quantum Teleportation		80	(2)
An Application of Quantum Teleportation		82	(4)
Introductory Quantum Algorithms		86	(24)
Probabilistic Versus Quantum Algorithms		86	(5)
Phase Kick-Back		91	(3)
The Deutsch Algorithm		94	(5)
The Deutsch--Jozsa Algorithm		99	(4)
Simon's Algorithm		103	(7)
Algorithms with Superpolynomial Speed-Up		110	(42)
Quantum Phase Estimation and the Quantum Fourier Transform		110	(15)
Error Analysis for Estimating Arbitrary Phases		117	(3)
Periodic States		120	(4)
GCD, LCM, the Extended Euclidean Algorithm		124	(1)
Eigenvalue Estimation		125	(5)
Finding-Orders		130	(12)
The Order-Finding Problem		130	(1)
Some Mathematical Preliminaries		131	(3)
The Eigenvalue Estimation Approach to Order Finding		134	(5)
Shor's Approach to Order Finding		139	(3)
Finding Discrete Logarithms		142	(4)
Hidden Subgroups		146	(5)
More on Quantum Fourier Transforms		147	(2)
Algorithm for the Finite Abelian Hidden Subgroup Problem		149	(2)
Related Algorithms and Techniques		151	(1)
Algorithms Based on Amplitude Amplification		152	(27)
Grover's Quantum Search Algorithm		152	(11)
Amplitude Amplification		163	(7)
Quantum Amplitude Estimation and Quantum Counting		170	(5)
Searching Without Knowing the Success Probability		175	(3)
Related Algorithms and Techniques		178	(1)
Quantum Computational Complexity Theory and Lower Bounds		179	(25)
Computational Complexity		180	(5)
Language Recognition Problems and Complexity Classes		181	(4)
The Black-Box Model		185	(3)
State Distinguishability		187	(1)
Lower Bounds for Searching in the Black-Box Model: Hybrid Method		188	(3)
General Black-Box Lower Bounds		191	(2)
Polynomial Method		193	(4)
Applications to Lower Bounds		194	(2)
Examples of Polynomial Method Lower Bounds		196	(1)
Block Sensitivity		197	(1)
Examples of Block Sensitivity Lower Bounds		197	(1)
Adversary Methods		198	(6)
Examples of Adversary Lower Bounds		200	(3)
Generalizations		203	(1)
Quantum Error Correction		204	(37)
Classical Error Correction		204	(3)
The Error Model		205	(1)
Encoding		206	(1)
Error Recovery		207	(1)
The Classical Three-Bit Code		207	(4)
Fault Tolerance		211	(1)
Quantum Error Correction		212	(11)
Error Models for Quantum Computing		213	(3)
Encoding		216	(1)
Error Recovery		217	(6)
Three- and Nine-Qubit Quantum Codes		223	(11)
The Three-Qubit Code for Bit-Flip Errors		223	(2)
The Three-Qubit Code for Phase-Flip Errors		225	(1)
Quantum Error Correction Without Decoding		226	(4)
The Nine-Qubit Shor Code		230	(4)
Fault-Tolerant Quantum Computation		234	(7)
Concatenation of Codes and the Threshold Theorem		237	(4)
APPENDIX A		241	(19)
Tools for Analysing Probabilistic Algorithms		241	(2)
Solving the Discrete Logarithm Problem When the Order of a Is Composite		243	(2)
How Many Random Samples Are Needed to Generate a Group?		245	(2)
Finding r Given k/r for Random k		247	(1)
Adversary Method Lemma		248	(2)
Black-Boxes for Group Computations		250	(3)
Computing Schmidt Decompositions		253	(2)
General Measurements		255	(3)
Optimal Distinguishing of Two States		258	(2)
A Simple Procedure		258	(1)
Optimality of This Simple Procedure		258	(2)
Bibliography		260	(10)
Index		270

Phillip Ronald Kaye was born in Toronto, and raised in Waterloo, Ontario, Canada. In 1995 Phil was accepted to the Faculty of Engineering at the University of Waterloo with an entrance scholarship. He completed his undergraduate degree in Systems Design Engineering in 2000 and was awarded the George Dufault Medal for Excellence in Communication at his convocation. During the Summer months following his undergraduate convocation, Phil worked as an encryption software developer at Research in Motion (RIM), where he continued to work on a part-time basis during his graduate studies. Phil did his Master's degree in the department of Combinatorics and Optimization at Waterloo. His Master's thesis was entitled 'Quantum Networks for Concentrating Entanglement, and a Logical Characterization of the Computational Complexity Class BPP.' Phil is currently a PhD student at the School of Computer Science at the University of Waterloo.

Raymond Laflamme completed his undergraduate studies in Physics at Université Laval. He then moved to Cambridge, UK, where he took Part III of the Mathematical Tripos before doing a PhD in the Department of Applied Mathematics and Theoretical Physics (DAMTP) under the direction of Professor Stephen Hawking. Following posts at UBC, Cambridge and Los Alamos National Laboratory, Raymond moved to the University of Waterloo in 2001 as a Canada Research Chair in Quantum Information. Raymond is a recipient of Ontario's Premier Research Award and a Director of the Quantum Information program of the Canadian Institute for Advanced Research. He was named the Ivey Foundation Fellow of the Canadian Institute for Advanced Research (CIAR) in September of 2005.

Michele Mosca obtained a DPhil in quantum computer algorithms in 1999 at the University of Oxford. Since then he has been a faculty member in Mathematics at St. Jerome's University and in the Combinatorics and Optimization department of the Faculty of Mathematics, University of Waterloo, and a member of the Centre for Applied Cryptographic Research. He holds a Premier's Research Excellence Award (2000-2005), is the Canada Research Chair in Quantum Computation (since January 2002), and is a CIAR scholar (since September 2003). He is a co-founder and the Deputy Director of the Institute for Quantum Computing, and a founding member of the Perimeter Institute for Theoretical Physics.