Quantum Circuit Simulation (eBook)

George Viamontes has a Ph.D. in Computer Science and Enginering from the University of Michigan where his research was focused on quantum circuit simulation.  Through a Department of Energy fellowship for high-performance computer science, he completed a portion of his graduate research at Los Alamos National Laboratory.  Upon graduation, Dr. Viamontes spent a year at Lockheed Martin Advanced Technology Laboratories where he continued to work on quantum circuit simulation.  Currently he develops and implements algorithms for high-frequency automated trading and continues to consult for Lockheed Martin on quantum computing projects.Igor L. Markov is an associate professor of Electrical Engineering and Computer Science at the University of Michigan. He received his Ph.D. in Computer Science from UCLA. Currently he is a member of the Executive Board of ACM SIGDA, Editorial Board member of Communications of ACM, ACM TODAES, IEEE Transactions on Computers, IEEE Transactions on CAD, as well as IEEE Design & Test. Prof. Markov researches computers that make computers. He has co-authored two books and more than 160 refereed publications, some of which were honored by the best-paper awards at the Design Automation and Test in Europe Conference (DATE), the Int'l Symposium on Physical Design (ISPD) and IEEE Trans. on Computer-Aided Design. Prof. Markov is the recipient of a DAC Fellowship, an ACM SIGDA Outstanding New Faculty award, an NSF CAREER award, an IBM Partnership Award, and a Microsoft A. Richard Newton Breakthrough Research Award. John P. Hayes received the B.E. degree from the National University of Ireland, Dublin, and the M.S. and Ph.D. degrees from the University of Illinois, Urbana-Champaign, all in electrical engineering. While at the University of Illinois, he participated in the design of the ILLIAC III computer. In 1970 he joined the Operations Research Group at the Shell Benelux Computing Center in The Hague, where he worked on mathematical programming and software development. From 1972 to 1982 he was a faculty member of the Departments of Electrical Engineering–Systems and Computer Science of the University of Southern California, Los Angeles. Since 1982 he has been with the Electrical Engineering and Computer Science Department of the University of Michigan, Ann Arbor, where he holds the Claude E. Shannon Endowed Chair in Engineering Science.

Preface 4
Contents 7
1 Introduction 9
1.1 Quantum Circuits 9
1.2 Quantum Simulation 11
1.3 Book Outline 12
Acknowledgments 13
2 Gate Modeling and Circuit Simulation 14
2.1 Classical Digital Circuits 14
2.2 Simulation with Binary Decision Diagrams 18
2.3 Sequential Circuits and Synchronization 24
2.4 Summary 25
3 Linear Algebra and Quantum Mechanics 26
3.1 Linear Algebra 26
3.2 Quantum Mechanics 31
3.3 Summary 39
4 Quantum Information Processing 40
4.1 Quantum Gates 40
4.2 Quantum Circuits 45
4.3 Synchronization of Quantum Circuits 49
4.4 Sample Algorithms 50
4.5 Summary 53
5 Special Case: Simulating Stabilizer Circuits 54
5.1 Basics of a Quantum Circuit Simulator 54
5.2 Stabilizer States, Gates and Circuits 56
5.3 Data Structures 58
5.4 Algorithms 59
5.5 Summary 62
6 Generic Circuit Simulation Techniques 65
6.1 Qubit-wise Multiplication 65
6.2 P-blocked Simulation 67
6.3 Tensor Networks 69
6.4 Slightly-entangled Simulation 72
6.5 Summary 76
7 State-Vector Simulation with Decision Diagrams 77
7.1 Quantum Information Decision Diagrams 77
7.2 Scalability of QuIDD-based Simulation 86
7.3 Empirical Validation 94
7.4 Related Decision Diagrams 98
7.5 Summary 106
8 Density-Matrix Simulation with QuIDDs 108
8.1 QuIDD Properties and Density Matrices 108
8.2 QuIDD-based Outer Product 110
8.3 QuIDD-based Partial Trace 111
8.4 Empirical Validation 114
8.5 Summary 119
9 Checking Equivalence of States and Circuits 120
9.1 Quantum Equivalence Checking 120
9.2 Global-Phase Equivalence 122
9.3 Relative-Phase Equivalence 127
9.4 Empirical Validation 131
9.5 Summary 133
10 Improving QuIDD-based Simulation 137
10.1 Gate Algorithms 137
10.2 Dynamic Tensor Products and Partial Tracing 143
10.3 Empirical Validation 149
10.4 Summary 154
11 Closing Remarks 157
Appendix A QuIDDPro Simulator 159
A.1 Running the Simulator 159
A.2 Functions and Code in Multiple Files 162
A.3 Language Reference 164
Appendix B QuIDDPro Examples 180
B.1 Well-known Quantum States 180
B.2 Grover’s Search Algorithm 181
B.3 Shor’s Integer Factoring Algorithm 182
References 184
Index 190