MAT 4930: Quantum Algorithms & Complexity

Vectors in the Dirac Notation

Module One

Objectives

a) The students will know how to write vectors in the Dirac notation.

b) The students will know how to perform inner products in the Dirac notation.

c) The students will know how to decompose a vector as a linear combination or orthonormal vectors using inner products.

d) The students will know how to compute an orthonormal basis from an a given basis of a subspace of  Cn

Lecture Notes PDF

Linear Operators

Module Two

Objectives

a) The students will know how to perform matrix arithmetic operations and matrix-vector multiplication.

b) The students will know how to perform outer products and express arbitrary matrices as linear combination of outer products of the canonical basis.

c) The students will know how to write projection operators on a subspace from an orthonormal basis of the space.

d) The students will know how to compute adjoints, inverses, and identify unitary matrices.

Lecture Notes PDF

Qubits

Module Three

Objectives

a) The students will know how to express states of qubits on the computational basis.

b) The students will know how to model measurements on qubits.

c) The students will know how to represent the state of a qubit on the Bloch sphere.

Lecture Notes PDF

Tensor Products and Multi-Qubit Systems

Module Four

Objectives

a) The students will know how to perform tensor products of vectors and matrices.

b) The students will know how to model independent systems with product states.

c) The students will be able to prove that a state is not a product state (i.e. is an entangled state).

d) The students will be able to perform inner products of tensor products of vectors.

e) The students will know how to perform partial measurements on multi-qubit systems.

Lecture Notes PDF

Quantum Circuits and Complexity

Module Five

Objectives

a) The students will know how to model the evolution of the state of a closed system via unitary matrices.

b) The students will know how to measure the cost of a quantum circuit.

c) The students will know how to invert a quantum circuit.

d) The students will know how to compute the unitary matrix representing the evolution of a given circuit.

Lecture Notes PDF

Reversible Circuits

Module Six

Objectives

a) The students will know why quantum circuits need to be reversible.

b) The students will know how to turn a non-reversible classical circuit into a reversible one using ancilla qubits.

c) The students will know the quantum circuits implementing certain classical gates.

Lecture Notes PDF

The Deutsch-Jozsa Algorithm

Module Seven

Objectives

a) The students will know how to compute the action of the n-qubit Hadamard gate.

b) The students will know how to build the Deutsch-Jozsa circuit from an oracle subroutine.

c) The students will know how to analyze the state of the system step after step in the Deutsch-Jozsa circuit.

Lecture Notes PDF

Amplitude Amplification Algorithms

Module Eight

Objectives

a) The students will know how describe the circuit for Grover's algorithm.

b) The students will know how to analyse the cost of Grover's algorithm.

c) The students will know how to bound the probability of success of Grover's algorithm.

d) The students will be able to generalize the above tasks to all amplitude amplification methods.

Lecture Notes PDF

Quantum Phase Estimation

Module Nine

Objectives

a) The students will know how describe the circuit for the quantum phase estimation algorithm.

b) The students will know how to compute the success probability of the quantum phase estimation algorithm.

c) The students will know how the relationship between the Quantum Fourier Transform and the resolution of the quantum phase estimation algorithm.

Lecture Notes PDF

Elementary Number Theory

Module Ten

Objectives

a) The students will know how to perform essential modular arithmetic operations (additions, multiplication, fast exponentiation).

b) The students will know the definition of the Euler phi function and how to compute it.

c) The students will know how how to compute the probability that factoring a number N reduces to computing the order of an element modulo N.

d) The students will know how to compute the continued fraction expansion of a real number.

Lecture Notes PDF

Order Finding Algorithms

Module Eleven

Objectives

a) The students will know how to describe the circuit of a quantum algorithm for computing the order of  a modulo N when  φ (N)is known.

b) The students will know how to calculate the probability of success of the order finding algorithm when  φ (N)is known.

c) The students will know how to adapt the above strategy when  φ (N)is not known, and derive the corresponding probability of success.

Lecture Notes PDF
University of South Florida