Quantum Computing

for

Computer Scientists

Noson S. Yanofsky

and

Mirco A. Mannucci

Table of Contents

Preface

Introduction

1 Complex Numbers

1.1 Basic Definitions

1.2 The Algebra of Complex Numbers

1.3 The Geometry of Complex Numbers

2 Complex Vector Spaces

2.1 Cⁿ as the Primary Example

2.2 Definitions, Properties, and Examples

2.3 Basis and Dimension

2.4 Inner Products and Hilbert Spaces

2.5 Eigenvalues and Eigenvectors

2.6 Hermitian and Unitary Matrices

2.7 Tensor Product of Vector Spaces

3 The Leap From Classical to Quantum

3.1 Classical Systems

3.2 Probabilistic Systems

3.3 Quantum Systems

3.4 Combining Systems

4 Basic Quantum Theory

4.1 Quantum States

4.2 Observables

4.3 Measuring

4.4 Dynamics

4.5 Assembling Quantum Systems

5 Architecture

5.1 Bits and Qubits

5.2 Classical Gates

5.3 Reversible Gates

5.4 Quantum Gates

6 Algorithms

6.1 Deutsch’s Algorithm

6.2 The Deutsch-Jozsa Algorithm

6.3 Simon’s Periodicity Algorithm

6.4 Grover’s Search Algorithm

6.5 Shor’s Factoring Algorithm

7 Programming Languages

7.1 Programming in the Quantum World

7.2 Manipulating Qubits: Quantum Assembly Programming

7.3 Towards Higher-Level Quantum Programming

7.4 Quantum Emulators

8 Theory

8.1 Deterministic and Nondeterministic Turing Machines

8.2 Probabilistic Turing Machines

8.3 Quantum Turing Machines

8.4 Complexity Results

9 Cryptography

9.1 Classical Cryptography

9.2 Quantum Key Distribution Protocol I: BB84

9.3 Quantum Key Distribution Protocol II: B92

9.4 Quantum Key Distribution Protocol III: EPR

9.5 Quantum Teleportation

10 Information Theory

10.1 Classical Information and Shannon’s Entropy

10.2 Quantum Information and Von Neumann Entropy

10.3 Classical and Quantum Data Compression

11 Hardware

11.1 Quantum Hardware: goals and challenges

11.2 Ion Traps

11.3 Linear Optics

11.4 The Future of Quantum Hardware

Appendix A) An Historical Bibliography for Quantum Computing

by Jill Cirasella

Appendix B) Answers to Selected Exercises

Appendix C) Quantum Computing Experiments with MATLAB

Appendix D) Keeping Abreast of Quantum News: Quantum

Computing in the Literature and on the Web

Appendix E) Selected Topics for Student Presentations

Bibliography

Index