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