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 9-11.


Tentative schedule:

Week commencingMonday 9-11Wednesday 9-11
25 JanComputational complexity
The quantum circuit model
Grover's algorithm
1 FebThe QFT and periodicity
Shor's algorithm
Shor's algorithm (ctd) (Thu 10-12)
Approximate periodicity
8 FebPhase estimation
Hamiltonian simulation
Quantum walks
Quantum walk algorithms
15 FebDecoherence
Quantum error-correction
No lecture
22 FebNo lectureThe stabilizer formalism (Fri 9-11, CDT student office)
Measurement and tomography
29 FebMeasurement-based 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 plagiarism-detection software. The essay will be assessed using the School of Physics 21-point 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. quant-ph/0302112, quant-ph/0406151
  • Efficient quantum phase estimation. quant-ph/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, quant-ph/0505030
  • Hardness of classical simulation of simple quantum computers. arXiv:1011.3245, arXiv:1504.07999
  • Simulating restricted classes of quantum circuits classically. quant-ph/0511069, arXiv:0804.4050
  • Verification of quantum computations. arXiv:1509.09180, arxiv:1203.5217
  • Quantum fault-tolerance thresholds. quant-ph/0404104, quant-ph/9906129
  • Quantum versus classical proofs. quant-ph/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 low-energy trivial states and the quantum PCP conjecture. arXiv:1309.7495, arXiv:1510.02082
  • Grover search and speculative physical theories. arXiv:1511.00657, quant-ph/9801041
  • Undecidability of problems in quantum information. arXiv:1502.04573, arXiv:1111.5425
  • Quantum communication complexity. arXiv:0907.3584, quant-ph/0611209
  • Lower bounds on quantum query complexity. quant-ph/0509153, quant-ph/9802049
  • Optimal tomography of quantum states. arXiv:1508.01797, arXiv:1508.01907
  • Testing properties of quantum states. arXiv:1310.2035, arXiv:1501.05028