Quantum Computation

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Contents
Preface
Acknowledgements
Symbols
I: Mathematical Foundations for Quantum Computation
1. Mathematical preliminaries
1.1. Objectives
1.2. Definitions and notation
1.3. Venn diagrams
1.4. Laws of set algebra
1.5. Boolean algebra
1.5.1. The exclusive-or operator (xor)
1.6. Groups
1.7. Cartesian product
1.8. Number bases
1.9. Modular arithmetic
1.10. Relations, equivalence relations and equivalence classes
1.10.1. Equivalence relations
1.11. Combinatorics-permutations and combinations
1.12. End-of-chapter exercises
2. Functions and their application to digital gates
2.1. Objectives
2.2. Introductory definitions and terminology
2.3. Some more functions f : R→R
2.3.1. The relative growth of functions
2.4. The Boolean functions f : B→B
2.5. Functions defined on Cartesian products
2.5.1. The Boolean functions f : Bx B→B
2.5.2. The Boolean functions f : B2→B2
2.5.3. Further Boolean functions
2.6. Further composition of functions
2.7. The Cartesian product of functions
2.8. Permuting (swapping) binary digits and binary strings
2.8.1. A classical digital circuit for swapping binary digits
2.8.2. Swapping binary digits using the Feynman cnot gate
2.8.3. Swapping strings of binary digits-vectorising the swap operator
2.9. Copying binary digits and binary strings
2.9.1. Fan-out
2.9.2. A dupe gate
2.9.3. The cnot gate
2.9.4. The Feynman double gate
2.9.5. The ccnot (Toffoli) gate
2.9.6. Fan-out copying of binary strings
2.9.7. Digital string copying with the non-reversible copy and reversible swap gates
2.9.8. Digital string copying using only reversible (the cnot and swap) gates
2.9.9. Digital string copying using only the cnot gate
2.10. Periodic functions
2.10.1. Real-valued periodic functions
2.10.2. Periodic Boolean functions
2.11. End-of-chapter exercises
3. Complex numbers
3.1. Objectives
3.2. Introduction to complex numbers and the imaginary number i
3.3. The arithmetic of complex numbers
3.4. The set of all complex numbers as a field
3.5. The Argand diagram and polar form of a complex number
3.6. The exponential form of a complex number
3.7. The Fourier transform: an application of the exponential form of a complex number
3.8. End-of-chapter exercises
4. Vectors
4.1. Objectives
4.2. Vectors: preliminary definitions
4.3. Graphical representation of two- and three-dimensional vectors
4.4. Vector arithmetic: addition, subtraction and scalar multiplication
4.5. Qubits represented as vectors
4.5.1. Combining kets and functions f : B→B
4.6. The inner product (scalar product, dot product)
4.6.1. The inner product in R2 and R3
4.6.2. The inner product on Cn: Definition 1
4.6.3. The inner product on Cn: Definition 2
4.7. End-of-chapter exercises
5. Matrices
5.1. Objectives
5.2. Matrices: preliminary definitions
5.3. Matrix arithmetic: addition, subtraction and scalar multiplication
5.4. The product of two matrices
5.5. Block multiplication of matrices
5.6. Matrices, inner products and ket notation
5.7. The determinant of a square matrix
5.8. The inverse of a square matrix
5.8.1. The inverse of an n x n matrix
5.9. Similar matrices and diagonalisation
5.10. Orthogonal matrices
5.11. Unitary matrices
5.12. Matrices and the solution of linear simultaneous equations
5.12.1. Gaussian elimination
5.13. Matrix transformations
5.14. Projections
5.15. End-of-chapter exercises
6. Vector spaces
6.1. Objectives
6.2. Definition of a vector space
6.3. Inner product spaces
6.4. Subspaces
6.5. Linear combinations, span and LinSpan
6.6. Linear independence
6.7. Basis of a vector space
6.8. Change of basis matrices
6.9. Orthogonal projections onto subspaces
6.10. Construction of an orthogonal basis - the Gram-Schmidt process
6.11. The Cartesian product of vector spaces
6.12. Equivalence classes defined on vector spaces
6.13. The sum of a vector and a subspace
6.14. The quotient space
6.15. End-of-chapter exercises
7. Eigenvalues and eigenvectors of a matrix
7.1. Objectives
7.2. Preliminary definitions
7.3. Calculation of eigenvalues
7.4. Calculation of eigenvectors
7.5. Real symmetric matrices and their eigenvalues and eigenvectors
7.6. Diagonalisation of real symmetric matrices
7.7. The spectral theorem for symmetric matrices
7.8. Self-adjoint matrices and their eigenvalues and eigenvectors
7.9. End-of-chapter exercises
8. Group theory
8.1. Objectives
8.2. Preliminary definitions and the axioms for a group
8.3. Permutation groups and symmetric groups
8.4. Unitary groups
8.5. Cosets, partitions and equivalence classes
8.6. Quotient groups
8.7. End-of-chapter exercises
9. Linear transformations
9.1. Objectives
9.2. Preliminary information
9.3. The kernel and image of a linear transformation
9.4. Linear functionals
9.5. Matrix representations of linear transformations
9.6. Bilinear maps
9.7. End-of-chapter exercises
10. Tensor product spaces
10.1. Objectives
10.2. Preliminary discussion
10.3. Calculation of tensor products
10.4. Inner products and norms on the tensor product space C2 x C2
10.5. Formal construction of the tensor product space
10.5.1. The free vector space generated by U x V
10.5.2. An equivalence relation on LinSpan(U x V)
10.5.3. Definition of the tensor product space
10.6. End-of-chapter exercises
11. Linear operators and their matrix representations
11.1. Objectives
11.2. Linear operators
11.3. The matrix representation of a linear operator
11.4. The matrix representation of a linear operator when the underlying basis is orthonormal
11.5. Eigenvalues and eigenvectors of linear operators
11.6. The adjoint and self-adjoint linear operators
11.7. Unitary operators
11.8. Linear operators on tensor product spaces
11.9. End-of-chapter exercises
II: Foundations of quantum-gate computation
12. Introduction to Part II
12.1. Objectives
12.2. Computation and physics
12.3. Physical systems
12.4. An overview of digital computation
12.4.1. Digital computer states
12.4.2. Digital computer dynamics
12.4.3. Digital computer `measurement'
12.5. The emergence of quantum computation
12.6. Observables and measurement
12.6.1. Observables
12.6.2. Measurement
12.7. The Stern-Gerlach quantum experiment
13. Axioms for quantum computation
13.1. Objectives
13.2. Quantum state spaces for computation
13.2.1. The 2-dimensional vector space representation of 'spin' and quantum bits
13.2.2. The case for quantum bit (qubit) representation in C2
13.2.3. Quantum bits - or qubits
13.2.4. Global phase
13.2.5. Projective spaces and the Bloch sphere
13.2.6. Multi-qubit state spaces
13.3. Quantum observables and measurement for computation
13.4. Quantum dynamics for computation
13.5. Orthogonal projection in a complex inner product space
13.6. A summary of the axioms for quantum computation
13.7. Special cases of the measurement axiom
13.8. A formal comparison with digital computation
13.9. Gates
14. Quantum measurement 1
14.1. Objectives
14.2. Measurement using Axiom 3.2
14.2.1. Measurement of non-superimposed states in C2
14.2.2. Measurement of non-superimposed states in C2 x C2
14.2.3. Measurement of non-superimposed states in C2 x C2 x C2
15. Quantum information processing 1: the quantum emulation of familiar invertible digital gates
15.1. Objectives
15.2. On the graphical representation of quantum gates
15.3. A 1-bit/qubit gate
15.3.1. The digital not gate
15.3.2. The quantum not gate, notQ, on BC2 = {|x : x 2 B}
15.4. 2-bit/qubit gates
15.4.1. The non-invertible digital cnot, or xor, gate
15.4.2. The invertible digital cnot, or Feynman FD, gate
15.4.3. The quantum cnot, or Feynman FQ, gate on Bx2 C2 = {|x|yr : x, y 2 B}
15.5. 3-bit/qubit gates
15.5.1. The digital Toffoli (or ccnot) gate
15.5.2. The quantum Toffoli (or ccnot) gate on Bxr3C2 = {|x|y|z : x,y, z 2 B}
15.5.3. The digital Peres (invertible half-adder) gate
15.5.4. The quantum Peres gate on Bx3C2 = {|x|y|z : x, y,z B}
16. Unitary extensions of the gates notQ; FQ; TQ and PQ: more general quantum inputs
16.1. Objectives
16.2. A lemma on unitary operators
16.3. The notQ gate on C2
16.4. The Feynman FQ gate on x2C2
16.5. The quantum To oli gate on x3C2
16.6. The quantum Peres gate on x3C2
16.7. Summation expressions for the unitary extensions
16.7.1. On C2
16.7.2. On C2 x C2
16.7.3. On C2 x C2 x C2
16.7.4. Notation and closing observations
17. Quantum information processing 2: the quantum emulation of arbitrary Boolean functions
17.1. Objectives
17.2. Notation
17.3. Quantum emulation of arbitrary invertible Boolean functions
17.3.1. The quantum emulation of the invertible subset of F(B,B)
17.3.2. The quantum emulation of the invertible subset of F(B2,B2)
17.3.3. Explicit forms of the emulations of Section 17.3.2
17.3.4. The invertible subset of F(Bn,Bn); n > 3
17.4. Quantum emulation of arbitrary non-invertible Boolean functions
17.4.1. A fundamental lemma
17.4.2. The non-invertible subset of F(B,B)
17.4.3. The non-invertible functions F(B2,B)
17.4.4. The non-invertible subset of F(Bn,Bn)
17.4.5. The general functions F(Bn, Bm)
17.5. Black-box representations of Boolean functions and their quantum emulations
18. Invertible digital circuits and their quantum emulations
18.1. Objectives
18.2. Invertible digital circuits
18.3. Junk removal
18.4. Quantum emulation
19. Quantum measurement 2: general pure states, Bell states
19.1. Objectives
19.2. The measurement of super-imposed quantum states
19.3. Measuring the EPR-Bell state ½ (|0|0 + |1|1)
19.4. More general measurements of 2-qubit states in the computational basis
19.5. Measuring 2-qubit states in the Bell basis
19.5.1. Measuring the observables S2 3 and S21
20. Quantum information processing 3
20.1. Objectives
20.2. Quantum parallelism
20.3. Qubit swapping
20.4. Quantum copying - the no-cloning theorem
20.5. Quantum teleportation 1, computational-basis measurement
20.6. Quantum teleportation 2, Bell-basis measurement
21. More on quantum gates and circuits: those without digital equivalents
21.1. Objectives
21.2. General 1-qubit quantum gates
21.3. The Pauli and the not 1-qubit gates
21.4. Further 1-qubit gates: phase-shift and Hadamard
21.5. Universal 1-qubit circuits
21.6. Some 2-qubit quantum gates
21.6.1. Tensor product gates
21.6.2. The Hadamard-cnot circuit
21.7. The Hadamard gate on n-qubit registers
22. Quantum algorithms 1
22.1. Objectives
22.2. Preliminary lemmas
22.3. Diagrammatic representation of the measurement process
22.4. An introduction to computational complexity
22.5. Oracle-based complexity estimation
22.6. Deutsch's algorithm
22.7. The Deutsch-Jozsa algorithm
22.8. The Bernstein-Vazirani algorithm
23. Quantum algorithms 2: Simon's algorithm
23.1. Objectives
23.2. Periodicity, groups, subgroups and cosets
23.2.1. Real-valued functions
23.2.2. A summary of the real-valued case
23.3. Boolean functions
23.3.1. The subgroups of group (B3,)
23.3.2. The cosets B3=Ks
23.4. The hidden subgroup problem
23.5. Simon's problem
23.6. The complexity of digital solutions
23.7. Simon's quantum algorithm
A. Probability
A.1. Definition of probability
A.2. Discrete random variables and probability distributions
B. Trigonometric ratios and identities
C. Coordinate systems
D. Field axioms
E. Solutions to selected exercises
References
Index