Principles of Quantum Computation and Information: A Comprehensive Textbook

Description

Quantum computation and information is a rapidly developing interdisciplinary field. It is not easy to understand its fundamental concepts and central results without facing numerous technical details. This book provides the reader with a useful guide. In particular, the initial chapters offer a simple and self-contained introduction; no previous knowledge of quantum mechanics or classical computation is required. Various important aspects of quantum computation and information are covered in depth, starting from the foundations (the basic concepts of computational complexity, energy, entropy, and information, quantum superposition and entanglement, elementary quantum gates, the main quantum algorithms, quantum teleportation, and quantum cryptography) up to advanced topics (like entanglement measures, quantum discord, quantum noise, quantum channels, quantum error correction, quantum simulators and tensor networks). It can be used as a broad range textbook for a course in quantum information and computation, both for upper-level undergraduate students and for graduate students. It contains a large number of solved exercises, which are an essential complement to the text, as they will help the student to become familiar with the subject. The book may also be useful as general education for readers who want to know the fundamental principles of quantum information and computation and who have the basic background acquired from their undergraduate course in physics, mathematics, or computer science, as well as for researchers interested in some of the latest spin-off of the field, including the use of quantum information in the theories of many-body systems. Readership: Upper-level undergraduates and graduate students in physics, mathematics and computer science. Contents About the Cover Preface Introduction 1. Introduction to classical computation 1.1 The Turing machine 1.1.1 Addition on a Turing machine 1.1.2 The Church{Turing thesis 1.1.3 The universal Turing machine 1.1.4 The probabilistic Turing machine 1.1.5 * The halting problem 1.2 The circuit model of computation 1.2.1 Binary arithmetics 1.2.2 Elementary logic gates 1.2.3 Universal classical computation 1.3 Computational complexity 1.3.1 Tractable vs. intractable problems 1.3.1.1 * Optimization problems 1.3.1.2 * Decision problems 1.3.2 Complexity classes 1.3.3 * The Chernoff bound 1.4 * Computing dynamical systems 1.4.1 * Deterministic chaos 1.4.2 * Algorithmic complexity 1.5 Energy and information 1.5.1 Maxwell's demon 1.5.2 Landauer's principle 1.5.3 Extracting work from information 1.6 Reversible computation 1.6.1 Toffoli and Fredkin gates 1.6.2 * The billiard-ball computer 1.7 * Energy dissipation in computation 1.7.1 * Experimental realization of a Maxwell's demon 1.7.2 * Experimental verification of Landauer's principle 1.7.3 * Energy dissipation in real classical computer 1.7.4 * Experimental realization of reversible computers 1.7.5 * Neuromorc computing 1.8 A guide to the bibliography 2. Introduction to quantum mechanics 2.1 The Stern{Gerlach experiment 2.2 Young's double-slit experiment 2.3 The postulates of quantum mechanics 2.3.1 Dynamical evolution 2.3.2 Outcomes of a measurement 2.3.3 The post-measurement state 2.3.4 Heisenberg's uncertainty principle 2.4 The EPR paradox 2.5 Bell's inequalities 2.6 The density matrix 2.6.1 Composite systems 2.7 The Schmidt decomposition 2.8 Purification 2.9 Generalized measurements 2.9.1 POVM measurements 2.10 A guide to the bibliography 3. Quantum computation 3.1 The qubit 3.1.1 Pure qubit states: The Bloch sphere 3.1.2 Mixed qubit states: The Bloch ball 3.2 Measuring the state of a qubit 3.2.1 Pure qubit states 3.2.2 Mixed qubit states 3.3 The circuit model of quantum computation 3.4 Single-qubit gates 3.4.1 Rotations of the Bloch sphere 3.5 Controlled gates and entanglement generation 3.5.1 The Bell basis 3.6 Hamiltonian model for one- and two-qubit gates 3.7 Universal quantum gates 3.7.1 * Preparation of the initial state 3.8 Unitary errors 3.9 Function evaluation 3.10 * The quantum adder 3.11 Adiabatic theorem 3.11.1 Adiabatic condition 3.11.2 Berry phase 3.12 * Non-Abelian geometric phase 3.13 Adiabatic quantum computation 3.14 * Maximum speed of quantum gates 3.14.1 * Speed limit of an autonomous time evolution 3.14.2 * Speed limit of single-qubit gates 3.15 * Holonomic quantum computation 3.16 A guide to the bibliography 4. Quantum algorithms 4.1 Deutsch's algorithm 4.1.1 The Deutsch{Jozsa problem 4.1.2 * An extension of Deutsch's algorithm 4.2 Quantum search 4.2.1 Searching one item out of four 4.2.2 Searching one item out of N 4.2.3 Geometric visualization 4.2.4 Searching by adiabatic quantum evolution 4.3 The quantum Fourier transform 4.4 Quantum phase estimation 4.5 ? Finding eigenvalues and eigenvectors 4.6 Period finding and Shor's algorithm 4.7 Quantum computation of dynamical systems 4.7.1 Quantum simulation of the SchrŁodinger equation 4.7.2 * The quantum baker's map 4.7.3 * The quantum sawtooth map 4.7.4 Information extraction for dynamical quantum systems 4.8 Universal quantum simulation 4.9 A guide to the bibliography 5. Quantum communication 5.1 Classical cryptography 5.1.1 The Vernam cypher 5.1.2 The public-key cryptosystem 5.1.3 The RSA protocol 5.2 The no-cloning theorem 5.2.1 Faster-than-light transmission of information? 5.2.2 * The no-signalling condition 5.2.3 * Universal quantum cloning 5.2.4 * The universal-NOT gate 5.3 Quantum cryptography 5.3.1 The BB84 protocol 5.3.2 The E91 protocol 5.4 Dense coding 5.5 Quantum teleportation 5.5.1 * Conclusive teleportation 5.6 Quantum mechanics with continuous variables 5.6.1 * General framework for Gaussian states 5.7 Quantum cryptography with continuous variables 5.8 A guide to the bibliography 6. Entanglement and non-classical correlations 6.1 Definition of entanglement 6.1.1 Basic properties 6.2 Bipartite separability criteria 6.2.1 The Peres separability criterion 6.2.2 Positive maps 6.2.3 Entanglement witnesses 6.2.4 Positive maps and witnesses 6.3 The Shannon entropy 6.3.1 Mutual information 6.4 The von Neumann entropy 6.4.1 Example 1: source of orthogonal pure states 6.4.2 Example 2: source of non-orthogonal pure states 6.5 Entanglement concentration 6.5.1 * Entanglement of a random state 6.6 Requirements for bipartite entanglement measures 6.7 Other entanglement measures 6.7.1 * Concurrence 6.7.2 * Negativity 6.8 * Multipartite entanglement 6.8.1 * Monogamy of entanglement and tangle measures 6.9 Quantum discord 6.9.1 Definition 6.9.2 Basic properties 6.9.3 Examples 6.9.4 * Other measures of quantum correlations 6.10 * Quantum discord in continuous systems 6.10.1 * Entropy of a Gaussian state 6.10.2 * Discord of a Gaussian state 6.11 * Entropies in physics 6.11.1 * Thermodynamic entropy 6.11.2 * Statistical entropy 6.11.3 * Dynamical Kolmogorov{Sinai entropy 6.12 A guide to the bibliography 7. Decoherence 7.1 The Kraus representation 7.2 Decoherence models for a single qubit 7.2.1 The quantum black box 7.2.2 Measuring a quantum operation acting on a qubit 7.2.3 Quantum circuits simulating noise channels 7.2.4 The bit-flip channel 7.2.5 The phase-flip channel 7.2.6 The bit-phase-flip channel 7.2.7 The depolarizing channel 7.2.8 Amplitude damping 7.2.9 Phase damping 7.2.10 De-entanglement 7.3 * The Bloch-Fano representation 7.3.1 * Bloch-Fano representation of a state 7.3.2 * Bloch-Fano representation of a quantum operation 7.4 The master equation 7.4.1 * Derivation of the master equation 7.4.1.1 Damping of an harmonic oscillator 7.4.1.2 Damping of a qubit 7.4.2 The master equation and quantum operations 7.4.3 The master equation for a single qubit 7.5 * Non-Markovian quantum dynamics 7.6 Quantum to classical transition 7.6.1 SchrŁodinger's cat 7.6.2 Decoherence and destruction of cat states 7.7 Decoherence and quantum measurements 7.7.1 * Weak measurements 7.7.2 * Decoherence and quantum trajectories 7.8 A guide to the bibliography 8. Quantum information theory 8.1 Classical data compression 8.1.1 Shannon's noiseless coding theorem 8.1.2 Examples of data compression 8.1.3 Capacity of classical channels 8.2 Quantum data compression 8.2.1 Schumacher's quantum noiseless coding theorem 8.2.2 Compression of an n-qubit message 8.2.3 Example 1: two-qubit messages 8.2.4 Example 2: three-qubit messages 8.3 Accessible information 8.3.1 The Holevo bound 8.3.2 Example 1: two non-orthogonal pure states 8.3.3 * Example 2: three non-orthogonal pure states 8.4 Capacities of quantum channels 8.4.1 Classical capacity 8.4.2 Quantum capacity 8.5 * Quantum memory channels 8.6 A guide to the bibliography 9. Quantum error correction 9.1 The three-qubit bit-flip code 9.2 The three-qubit phase-flip code 9.3 The nine-qubit Shor code 9.4 General properties of quantum error correction 9.4.1 The quantum Hamming bound 9.5 Stabilizer coding 9.5.1 The nine-qubit Shor code revisited 9.5.2 * General formalism for stabilizer codes 9.5.3 * Logical operators for stabilizer codes 9.6 * The five-qubit code 9.7 Decoherence-free subspaces 9.7.1 * Conditions for decoherence-free dynamics 9.7.2 * The spin-boson model 9.8 * Dynamical decoupling 9.8.1 * Explicit form of control Hamiltonian 9.9 * The Zeno effect 9.10 Fault-tolerant quantum computation 9.10.1 Avoidance of error propagation 9.10.2 Fault-tolerant quantum gates 9.10.3 The noise threshold for quantum computation 9.11 A guide to the bibliography 10. Principles of experimental implementations of quantum protocols 10.1 Cavity quantum electrodynamics 10.1.1 Interaction of a two-level atom with a classical field 10.1.2 The Jaynes{Cummings model 10.1.3 Rabi oscillations 10.1.4 Entanglement generation 10.2 The ion-trap quantum computer 10.2.1 The Paul trap 10.2.2 Laser pulses 10.3 Solid-state qubits 10.3.1 Spins in semiconductors 10.3.2 Quantum dots 10.3.3 Superconducting qubit circuits 10.4 Quantum communication with photons 10.4.1 Linear optics 10.4.2 Non-linear optics and probabilistic gates 10.4.3 Experimental quantum-key distribution 10.5 Problems and prospects 10.6 A guide to the bibliography 11. Quantum information in many-body systems 11.1 Quantum simulators 11.1.1 Ultracold atoms 11.1.2 Arrays of coupled QED cavities 11.2 Emergence of quantum correlations 11.2.1 The Hubbard model 11.3 The spin-1=2 quantum Ising chain 11.3.1 Jordan{Wigner transformation 11.3.2 Diagonalization of the Ising chain 11.3.3 Two-spin concurrence 11.3.4 Entanglement block entropy 11.3.5 The Ising model revisited: Kitaev chain 11.4 Area-law scaling of the entanglement 11.5 Matrix product states 11.5.1 Examples of MPS wave functions 11.6 Graphical representation of matrix product states 11.6.1 Expectation values of observables 11.6.2 * Scaling of correlation functions with the distance 11.6.3 Gauge freedom 11.6.4 Schmidt decomposition of a MPS 11.7 Ground-state search in the Hilbert space corner 11.7.1 Density-matrix renormalization group 11.7.2 * DMRG as a variational optimization over the MPS class 11.8 Time evolution of matrix product states 11.8.1 Finite-temperature calculations 11.8.2 Mixed-state time evolution 11.9 * General tensor-network structures 11.9.1 * Projected entangled pair states 11.9.2 * Hierarchical tensor networks 11.10 A guide to the bibliography Conclusions and prospects Appendix A Elements of linear algebra A.1 Finite-dimensional vector spaces A.1.1 Basic properties of vector spaces A.1.2 Inner product and norm of a vector A.1.3 Linear independence and the notion of basis A.1.4 Linear operators A.1.5 Tensor product A.1.6 Matrix decompositions A.1.6.1 Diagonalization and spectral decomposition A.1.6.2 Singular value decomposition A.1.6.3 Polar decomposition A.1.6.4 Cholesky decomposition A.1.6.5 QR decomposition A.1.7 Symplectic decompositions A.1.7.1 Euler's decomposition A.1.7.2 Williamson's theorem A.2 Infinite-dimensional vector spaces A.2.1 Discrete and continuous bases A.2.2 The Dirac delta function A.2.3 Orthonormality and completeness relations A.2.4 Position and momentum representations A.2.5 Position and momentum operators Appendix B Solutions to the exercises B.1 Chapter 1 B.2 Chapter 2 B.3 Chapter 3 B.4 Chapter 4 B.5 Chapter 5 B.6 Chapter 6 B.7 Chapter 7 B.8 Chapter 8 B.9 Chapter 9 B.10 Chapter 10 B.11 Chapter 11 B.12 Appendix A Bibliography Index