Advanced Quantum Information Theory
Ashley Montanaro
This unit is a graduate course for the Centre for Doctoral Training in Quantum Engineering, running in Spring 2016. The unit will cover advanced and recent developments in the theory of quantum information processing, with a particular focus on quantum computation.
The lectures and examples classes will be held in the ground floor seminar
room in the Nanoscience and Quantum Information (NSQI) building, usually on Mondays
and Wednesdays from 911.
Materials
Tentative schedule:
Week commencing  Monday 911  Wednesday 911 
25 Jan  Computational complexity The quantum circuit model  Grover's algorithm 
1 Feb  The QFT and periodicity Shor's
algorithm  Shor's algorithm (ctd) (Thu 1012) Approximate periodicity 
8 Feb  Phase estimation Hamiltonian simulation  Quantum walks Quantum walk algorithms 
15 Feb  Decoherence Quantum errorcorrection  No lecture 
22 Feb  No lecture  The stabilizer formalism (Fri
911, CDT student office) Measurement and tomography 
29 Feb  Measurementbased QC (Damian Markham)  Essay surgery 
Assessment: The assessment for this unit is an essay of 3,500
words. This should summarise and synthesise technical research from one or
more research papers in the field of quantum information theory, including a
brief description of how the topic fits into the broader context. Any content
over 3,500 words must be placed in a clearly marked appendix and will not
count towards the final mark.
The deadline for the essay is Thursday 24 March. The essay should be
submitted to Blackboard in PDF format and will be run through the standard
Turnitin plagiarismdetection software. The essay will be assessed using the
School of Physics 21point scale (also on Blackboard). Some more specific
guidance:
 The assignment aims to test your understanding of the material on a
technical level. Therefore, to obtain a high mark it is not sufficient to
simply state and compare the claims of one or more papers verbatim; instead,
the essay should show that you have understood the key ideas behind the
material.
 Given the constraints of the word limit, it will be important to write
concisely and clearly while not omitting any important technical details.
 A good essay would:
 Contain a substantial amount of technical content (e.g. proofs, precise
statements of theorems, definitions etc.) demonstrating clear understanding
of said content;
 Compare and/or synthesise the content of more than one paper, or otherwise
demonstrate understanding of how the paper fits into the overall field.
 An excellent essay would demonstrate a level of understanding and/or
creativity beyond what is in the paper(s) surveyed.
 For example, this could include finding bugs or fixing incorrect claims;
synthesising content in a way that leads to a new understanding; or original
research.
 The essay for this unit forms a significant fraction of your overall mark
for the year, and you need to pass it just like any other unit. The pass
mark is 50%.
A list of suggested topics for essays is given below. Other ideas  and
modifications of the ideas below  are very welcome, but you may not choose a
topic which was previously undertaken by a student
from last
year's unit. Each topic may only be chosen by at most one student. If
you have any concerns about potential overlap, please ask.
For each topic, two references are given, all to the arXiv. These could form a
starting point for your essay, but you should also read around the area (for
example, looking at papers in the bibliography of the references below, as
well as papers that cite them).
Quantum algorithms:
 Solving linear equations with a quantum computer. arXiv:0811.3171,
arXiv:1010.4458
 Hidden shifts and the dihedral hidden subgroup problem. quantph/0302112,
quantph/0406151
 Efficient quantum phase estimation. quantph/0609160, arXiv:1304.0741
 Quantum query complexity separations beating Grover's
algorithm. arXiv:1511.01937, arXiv:1506.04719
 Quantum walks and electrical circuits. arXiv:1302.3143, arXiv:1509.02374
 Optimal quantum query complexity separations. arXiv:1411.5729,
arXiv:1005.0523
Quantum circuits and complexity:
 Efficient compilation of quantum gates. arXiv:1510.03888, quantph/0505030
 Hardness of classical simulation of simple quantum
computers. arXiv:1011.3245, arXiv:1504.07999
 Simulating restricted classes of quantum circuits
classically. quantph/0511069, arXiv:0804.4050
 Verification of quantum computations. arXiv:1509.09180, arxiv:1203.5217
 Quantum faulttolerance thresholds. quantph/0404104, quantph/9906129
 Quantum versus classical proofs. quantph/0604056, arXiv:1510.06750
Connections to physics and foundations:
 Efficient quantum simulation of strongly correlated models and
superconductivity. arXiv:1506.05135, arXiv:1510.03859
 Local Hamiltonians with no lowenergy trivial states and the quantum PCP
conjecture. arXiv:1309.7495, arXiv:1510.02082
 Grover search and speculative physical theories. arXiv:1511.00657,
quantph/9801041
 Undecidability of problems in quantum information. arXiv:1502.04573,
arXiv:1111.5425
Other:
 Quantum communication complexity. arXiv:0907.3584, quantph/0611209
 Lower bounds on quantum query complexity. quantph/0509153,
quantph/9802049
 Optimal tomography of quantum states. arXiv:1508.01797, arXiv:1508.01907
 Testing properties of quantum states. arXiv:1310.2035, arXiv:1501.05028
