COMP0157: Quantum Computation Dr. Toby Cubitt
Examinable Material Summary
Anything used or discussed in the lectures, lecture notes, or problem sheet’s that’s not
explicitly mentioned here should be considered part of the general understanding you are
expected to have obtained during the course, and is therefore examinable in that sense.
Notation and Terminology
You will be expected to understand all the standard notation and terminology defined
and used in the course.
1 Quantum Mechanics and Quantum Computation
1.1 Intro
Stern-Gerlach Experiment
Non-examinable
1.2 Classical Computation Revisited
The vector and matrix representation of classical computation is not examinable per se.
But you will be expected to understand how this mathematical formalism extends to
quantum computation, and how classical states and classical computation fit within this
formalism.
1.3 Quantum Computation and the Postulates of Quantum
Mechanics
The mathematical formalism, notation, terminology, postulates and consequences of
quantum mechanics are basic to the entire course. You will be expected to understand
and be able to apply all of this material.
1.4 Stern-Gerlach explained
You should be able to understand the quantum mechanical explanation of the Stern-
Gerlach experiment, and the notation and terminology used. But the Stern-Gerlach
experiment itself is non-examinable.
2 Reversible Computation
Toffoli gate
Examinable
Computing functions reversibly
Examinable
1
3 First Quantum Algorithms
Euclid’s algorithm and proof
Non-examinable
Exponentiation by squaring (Exercise)
Non-examinable
3.1 Deutsch-Jozsa Algorithm
Deutsch-Jozsa problem definition
Examinable
Deutsch-Jozsa algorithm
Examinable
Deutsch-Jozsa algorithm analysis and proofs
Examinable
Proof of classical worst-case exact query complexity for Deutsch-Jozsa problem
Examinable
Proof of efficient classical Deutsch-Jozsa algorithm in bounded-error setting
Non-examinable
3.2 Simon’s Algorithm
Simon’s problem definition
Examinable
Simon’s algorithm
Examinable
Simon’s algorithm analysis and proofs
Examinable
Classical lower-bound for Simon’s problem
Non-examinable
2
4 QFT and Phase Estimation
Quantum Fourier Transform definition
Examinable
Proof that QFT is unitary
Examinable
Proof of efficient QFT implementation
Examinable
Proof that small QFT rotations can be dropped
You are expected to know this result and its implications, but the proof is non-
examinable.
Phase Estimation problem definition
Examinable
Phase Estimation algorithm
Examinable
Phase Estimation algorithm analysis and proofs
Examinable
Probabilistic phase estimation variant definition and algorithm
Examinable
Probabilistic phase estimation algorithm analysis
Examinable
5 Shor’s algorithm
Non-examinable.
6 Bases, Subspaces and Projectors
This forms part of the basic mathematical formalism, terminology and notation of quantum
mechanics, and you will be expected to understand and be able to apply it.
3
7 Amplitude Amplification and Grover’s Algorithm
Amplitude Amplification problem definition
Examinable
Amplitude Amplification algorithm
Examinable
Amplitude Amplification analysis and proofs
Examinable
State decomposition with respect to a subspace and orthogonal complement
(Claim and proof)
Examinable
Unstructured search problem definition
Examinable
Classical Unstructured Search lower-bound
You should be able to formulate arguments like this for yourself. But this spe-
cific result and proof are non-examinable
Grover’s Algorithm
Examinable
Grover’s Algorithm analysis and proofs
Examinable
Quantum Unstructured Search lower-bound
Non-examinable
Proof of quadratic speedup of many quantum algorithms
Non-examinable
Grover’s algorithm for unknown number of items
Non-examinable
Exact Grover search
The 1-in-4 case is a special case of Grover’s algorithm, and therefore examinable.
The general case (covered in the final problem sheet) is non-examinable.
Oblivious and Fixed-Point amplitude amplification
Non-examinable
4
8 Hamiltonian Simulation
Non-examinable.
9 Heuristic quantum algorithms
Non-examinable
5

欢迎咨询51作业君