# Advanced Quantum Information Theory course

Lectured from 2017 as an optional advanced theory course for the UCL quantum CDT.

Based on a course I originally lectured from 2013 to 2015 as a Part III Mathematics course at the University of Cambridge.

## Lecture notes

- Notation and terminology
- Bibliography

### Section 1: Hamiltonian Complexity

- Lecture 1: Whistle-stop introduction to computability and complexity theory
- Lectures 2: Local Hamiltonians
- Lectures 3: Kitaev's Theorem
- Lecture 4: Local clock construction

### Section 2: Lieb-Robinson techniques

- Lecture 5: Many-body quantum physics introduction
- Lecture 6: Lieb-Robinson bounds
- Lectures 7-8: Exponential decay of correlations

# LaTeX: Cleveref package

The Cleveref package (also available from CTAN) does clever things with cross-references:

- automatic formatting of cross-references based on the type of object referred to (chapter, section, equation, theorem, etc.);
- full control and customisation of the reference format;
- cross-references and page references to multiple items;
- automatic (optional) sorting and compression of multiple cross-references or page references;
- optional output of a sed script that can strip out Cleveref commands and replace them with standard LaTeX, allowing Cleveref to be used e.g. in articles sent to journals or collaborators that don't (yet!) support Cleveref.

# Dear Diane

[Letter sent to my local MP, Diane Abbott. Do the same! Keep up the pressure on MPs to represent your views.]

Dear Diane,

When I first moved to Hackney, I was proud to tell people I had you as my MP. As one of the few voices on the Labour backbenches consistently voting according to conscience, defying the party whip when it was at odds with your principles and your constituents' interests, you stood out from the crowd of political apparatchiks toting the party line. On issues ranging from the Iraq war, to defending the NHS from privatisation, to resisting the incoming tide

# Quantum Computation and Complexity course

Lectured at the 2016 Autrans summer school on Stochastic Methods in Quantum Mechanics. The notes are adapted from the first half my Advanced Quantum Information Theory course, with additional material on the basics of computation and complexity theory.

## Lecture notes

- Lectures 1-2: Computation and Complexity
- Lecture 3: Local Hamiltonians
- Lectures 3-4: Kitaev's Theorem
- Lecture 4: Local clock construction

## Recommended reading

The Arora-Barak book gives an excellent, modern treatment of the theory of computation and complexity, going far beyond what's covered i

# Matrix Product States and PEPS

Notes from David Perez-Garcia's lecture course on Matrix Product States and PEPS at the 2016 Autrans summer school on Stochastic Methods in Quantum Mechanics.

The slides are courtesy of David. The lecture notes are my handwritten notes from the whiteboard section of David's lectures. All content by David; all mistakes by me!

## Lecture notes

- MPS motivation (slides)
- MPS lecture notes (handwritten)
- PEPS and topological order (slides)

(The slides are copyright © 2016 David Perez-Garcia, with all rights reserved. The handwritten notes are copyright ©{

# Paternity leave: statistics

## Lies, damn lies, and…

A couple of months ago, the statistic that only 1% of men had taken up shared parental leave was splashed all over the British media. (Shared Parental Leave was introduced in the UK in 2015, and essentially allows parents to share 12 months of leave however they like. Taking it consecutively, simultaneously, alternating blocks of leave between both parents, or a mixture of the above are all permitted.)

My Family Care, the company that carried out the survey on which this statistic was based, apparetly asked Human Resources directors at 200 business

# Paternity leave: reactions

~~ ~~ full time. The reactions I've had from people when they discover I'm on paternity leave for half a year have been entirely positive. But some of the comments I've had in response have been interesting. I've collected the ones that stuck in my mind, together with my thoughts on them.

(If you know me personally, and think you recognise something you've said, you don't! These aren't direct quotes. I've paraphrased things that have been said to me multiple times by many different people.)

## "I wish I could have taken paternity leave, but I can't really do that in my job."

# Decoupling Method in Quantum Shannon Theory

Originally lectured in 2015 as part of the quantum information theory masters course for the UCL quantum CDT.

## Lecture Notes

- Decoupling Method

## Recommended reading

Much of the material covered here (and more!) was originally proven in the Mother of All Protocols paper by Abeyesinghe, Devetak, Hayden and Winter.

These notes largely follow Section 10.9 of Preskill's wonderful lecture notes, with a (very) few modifications and additions.

# LaTeX: Quantum package

The Quantum package defines a number of commands and short-hands useful when writing about quantum mechanics, and quantum information theory in particular.

There is no separate documentation; read the package source to find out what commands it provides.

- Quantum package

# LaTeX: Authord package

Gives a complete solution to the problem of precedence in scientific pubication, in a way that Don Knuth would surely approve of.

- Authord package
- Authord documentation

# Quantum Mechanics for Mathematicians course

Lectured in 2011 as the first section of a "Mathematics for Quantum Information" masters course given in the mathematics faculty of the Universidad Complutense de Madrid.

## Lecture Notes

- Section 0: Dirac notation;

Section 1: The postulates of quantum mechanics

(lecture 1) - Section 2: Combining quantum systems: tensor products

(lecture 2) - Section 3: Non-locality and Bell inequalities

(lecture 3) - Section 4: Ensembles and density operators;

Section 5: Taking quantum systems apart: reduced states and the partial trace;

Section 6: A brief introduction to entropy

(lecture 4)

# Quantum Mechanics course

Lectured from 2007 to 2010 as the second part of the 3rd year mathematics undergraduate "Quantum Mechanics" course at the University of Bristol.

## Lecture Notes

- Section 1: Angular Momentum and Spin

(lectures 1 and 2) - Section 2: Representations of Angular Momentum

(lectures 3 to 5) - Section 3: Orbital Anglular Momentum

(bonus lecture) - Section 4: Measurement

(lecture 6) - Section 5: Multiple Particles and Tensor Products

(lectures 7 and 8) - Section 6: Non-Locality and Bell Inequalities

(lectures 9 and 1

# Why I use TMDA

Mine is a sad and familiar story. I was drowning in a deluge of spam (a.k.a. junk email), and it had become such a problem that email was fast becoming useless for me. Having to sort through and delete hundreds of spam emails per day was bad enough. Worse was the increasing frequency with which I was accidentally deleting legitimate email along with the spam.

There are various ways to fight this deluge of spam. The most common is to use a filter that tries to recognise and delete the spam (or, more usually, move it to a spam box for later perusal). This is quite effective. A

# Classical mechanics and electrodynamics

I have left up some of the material I prepared for classical mechanics and electrodynamics courses taught by Prof. Weise at the TUM (many, many years ago!) in case it's of use to someone.

## Question Sheet Solutions

Given that the question sheets are substantially re-used in subsequent semesters, I've removed the worked solutions that were available here, to help you avoid the temptation to…ahem…short-cut the valuable learning process that struggling to solve the questions provides. (Believe it or not, the question sheets are not some obscure form of torture dreamed up by

# Emacs: Auto-Overlays package

The Auto-Overlays package allows you to define overlays that are created (and updated and destroyed) automatically when text in a buffer matches a regular expression.

Various classes of automatic overlay are provided, to make it easy to define matches for different text regions: words, lines, regions enclosed by start and end tags, or regions enclosed by delimiters. You can also define your own custom classes.

The overlays are updated just before any buffer modification. The built in overlay classes only update as much as is necessary to ensure that overlays covering the point are consistent

# Emacs: Completion User Interface package

The Completion User Interface package is a library that implements user-interfaces for in-buffer completion.

Typically, in packages providing some kind of text completion, a large amount of code deals with providing the user interface rather than finding good completions. The goal of Completion-UI is to be the swiss-army knife of in-buffer completion user-interfaces; a library which any completion package can use to provide an in-buffer completion user-interface, thereby freeing completion package writers to concentrate on the task of finding the completions in the first place.

In fact, Comp

# Emacs: data structure packages

These packages provide basic (and not so basic) data structures. They are all relatively stable, though bug-fixes and new features are added occasionally. (Latest update: February 2013).

In recent versions of Emacs (>=24.1), you can install all the non-obsolete packages from within Emacs itself, via GNU ELPA. Use `M-x list-packages`

and take it from there. This is the preferred installation method. (Occasionally, the ELPA version might lag slightly behind the latest version available here.)

- Git repository:
`http://www.dr-qubit.org/git/predictive.git`

- heap.el (version 0.4)
- queue.el (version 0.1.1)

# Emacs: miscelaneous packages

These packages provide miscelaneous features I needed at some point. So I coded them. Currently, they're all to do with displaying useful information in the mode line.

`show-point-mode`

displays the current value of the point in the mode line. I primarily find it useful when debugging Elisp code that uses overlays and markers.

`wc-mode`

displays output similar to the Unix `wc`

command in the mode line, i.e. the character count, word count and line count for the current buffer. (I primarily find this Useful when writing grant applications with character or word limits. Though I'm sure it's us

# Emailing me

## Email address

I can be reached by email at toby@dr-qubit.org, associated with this PGP key:

4096R/0xA96F4A674DC39B79 BB74 FB42 4C64 4CB7 3571 39AA A96F 4A67 4DC3 9B79

As of 2 August 2013, I transitioned from an old 1024-bit DSA key to this new 4096-bit RSA key. I will be signing all software releases with the new key. Please also use the new key for all correspondence. See the transition statement to certify the transition, and for more details.

Note that I use FLOSS spam-reduction software called TMDA to protect my addresses from junk-mail.

If you've nev

# Matlab code

I've collected here various functions, routines, and other bits of Matlab, Octave and Mathematica code organized by topic, that might save someone, somewhere, from re-inventing the wheel. Some of them are so simple it would probably be quicker to re-code them than find this page, but since you're here anyway…

Comments within the code should be enough to figure out what they do and how to use them (try `help <function>`

from within Matlab or Octave). No guarantee they work as advertised, but I use them myself so I do correct bugs when I come across them. The Matlab code *should* run under bo

# Emacs: Predictive Completion package

The Emacs Predictive Completion package adds a new minor-mode to the GNU Emacs editor. When enabled, predictive mode exploits the redundancy inherent in languages in order to complete words you are typing before you've finished typing them (somewhat like the IntelliSense feature in some IDEs). It is highly customisable, and works happily alongside other Emacs major modes. See the documentation for more details.

Predictive mode only works under GNU Emacs, not under XEmacs. It may be possible to get it to work under XEmacs with a modicum of work. (At the very least, the overlay compatibility pa

# Publications

You can also find all of my papers on the arXiv (which is sometimes more up-to-date than this list).

## Published Papers

**Fundamental limitations in the purifications of tensor networks***G. De las Cuevas, T. S. Cubitt, J. I. Cirac, M. M. Wolf and D. Perez-Garcia*J. Math. Phys. 57, 071902 (2016) [8 pages] arXiv:1512.05709[quant-ph]**The Complexity of Divisibility***Johannes Bausch and Toby S. Cubitt*J. Linear Alg.**504**, p64–107 (2016) [50 pages] arXiv:1411.7380[math.PR]**Complexity Classification of Local Hamiltonian Problems***Toby Cubitt and Ashley Montanaro*SIAM J. on Computing,**45**:2, p268–316 (2016) [50 pages] arXiv:1311.3161[quant-ph]**Simple Universal Models Capture all Classical Spin Physics***Gemma de las Cuevas and Toby S. Cubitt*Science,**351**:6278, p1180-1183 (2016) [47 pages] arXiv:1406.5955[cond-mat.stat-mech]**Area law for fixed points of rapidly mixing dissipative quantum systems***F. G. S. L. Brandao, T. S. Cubitt, A. Lucia, S. Michalakis and D. Perez-Garcia*J. Math. Phys.**56**, 102202 (2015) [17 pages] arXiv:1505.02776[quant-ph]**Undecidability of the Spectral Gap***Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf*Nature,**528**, p207–211, (2015) arXiv:1502.04135[quant-ph] (short version) arXiv:1502.04573[quant-ph] (full version, 143 pages)**Quantum reverse hypercontractivity***T. Cubitt, M. Kastoryano, A. Montanaro and K. Temme*J. Math. Phys.**56**, 102204 (2015) [14 pages] arXiv:1504.06143[quant-ph]**Rapid Mixing and Stability of Quantum Dissipative Systems***Toby S. Cubitt, Angelo Lucia, Spyridon Michalakis, and David Perez-Garcia*Phys. Rev. A**91**, 040302 (2015) arXiv:1409.7809[quant-ph]**Unbounded Number of Channel Uses may be Required to Detect Quantum Capacity***D. Elkouss, S. Strelchuck, W. Matthews, M. Ozols, D. Perez-Garcia and T. S. Cubitt*Nature Communications**6**, 7739 (2015) [11 pages] arXiv:1408.5115[quant-ph]**Complexity Classification of Local Hamiltonian Problems***Toby Cubitt and Ashley Montanaro*IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), p120–129 (2014) arXiv:1311.3161[quant-ph]**Bounds on Entanglement Assisted Source-Channel Coding via the Lovász Theta Number and its Variants***Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke and Andreas Winter*IEEE Trans. Inform. Theory**60**, 7330 (2014) [15 pages] arXiv:1310.7120[quant-ph]**Stability of local quantum dissipative systems***Toby S. Cubitt, Angelo Lucia, Spyridon Michalakis, and David Perez-Garcia*Commun. Math. Phys.**337**, 1275 (2015) [38 pages] arXiv:1303.4744[quant-ph]**Preparing Topological PEPS on a Quantum Computer***M. Schwarz, K. Temme, F. Verstraete, D. Perez-Garcia and T. S. Cubitt*Phys. Rev. A,**88**, 032321 (2013)*(Editors' suggestion)*arXiv:1211.4050[quant-ph]**Entanglement can Completely Defeat Quantum Noise***Jianxin Chen, Toby S. Cubitt, Aram W. Harrow and Graeme Smith*Phys. Rev. Lett.**107**, 250504 (2011)*(Editor's suggestion)*arXiv:1109.0540[quant-ph] (highlighted in APS*Physics*article)**Extracting Dynamical Equations from Experimental Data is NP-Hard***Toby S. Cubitt, Jens Eisert and Michael M. Wolf*Phys. Rev. Lett.**108**, 120503 (2012)*(Editor's suggestion)*arXiv:1005.0005[quant-ph] (highlighted in*Science*NOW article and in APS*Physics*article)**Zero-Error Channel Capacity and Simulation Assisted by Non-Local Correlations***T. S. Cubitt, D. Leung, W. Matthews and A. Winter*IEEE Trans. Inform. Theory**57**:8, 5509–5523 (2011) [15 pages] arXiv:1003.3195[quant-ph]**Super-duper-activation of the zero-error quantum capacity***Jianxin Chen, Toby S. Cubitt, Aram W. Harrow and Graeme Smith*IEEE International Symposium on Information Theory (ISIT), p2695–2697 (2010)**An Extreme Form of Superactivation for Quantum Zero-Error Capacities***Toby S. Cubitt and Graeme Smith*IEEE Trans. Inform. Theory**58**:3, 1953–1961 (2012) [9 pages] arXiv:0912.2737[quant-ph]**Improving Zero-Error Classical Communication with Entanglement***T. S. Cubitt, D. Leung, W. Matthews and A. Winter*Phys. Rev. Lett.**104**, 230503 (2010) arXiv:0911.5300[quant-ph]**The Complexity of Relating Quantum Channels to Master Equations***Toby S. Cubitt, Jens Eisert and Michael M. Wolf*Commun. Math. Phys.**310**, 383–417 (2012) [35 pages] arXiv:0908.2128[quant-ph]**Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel***Toby S. Cubitt, Jianxin Chen and Aram W. Harrow*IEEE Trans. Inform. Theory**57**:12, 8114–8126 (2011) [8 pages] arXiv:0906.2547[quant-ph]**Non-Secret Correlations can be Used to Distribute Secrecy***Joonwoo Bae, Toby S. Cubitt and Antonio Acín*Phys. Rev. A**79**, 032304 (2009) arXiv:0806.1606[quant-ph]**The Structure of Degradable Quantum Channels***Toby S. Cubitt, Mary Beth Ruskai and Graeme Smith*J. Math. Phys.**49**, 102104 (2008) [27 pages] arXiv:0802.1460[quant-ph]**Counterexamples to Additivity of Minimum Output \(p\)-Rényi Entropy for \(p\) close to 0***Toby S. Cubitt, Aram W. Harrow, Debbie Leung, Ashley Montanaro and Andreas Winter*Commun. Math. Phys.**284**, 281–290 (2008) [9 pages] arXiv:0712.3628[quant-ph]**Assessing non-Markovian Dynamics***M. M. Wolf, J. Eisert, T. S. Cubitt and J.I. Cirac*Phys. Rev. Lett.**101**, 150402 (2008) arXiv:0711.3172[quant-ph]**On the Dimension of Subspaces with Bounded Schmidt Rank***Toby S. Cubitt, Ashley Montanaro and Andreas Winter*J. Math. Phys.**49**, 022107 (2008) arXiv:0706.0705[quant-ph]**Engineering Correlation and Entanglement Dynamics in Spin Systems***T. S. Cubitt and J.I. Cirac*Phys. Rev. Lett.**100**, 180406 (2008) arXiv:quant-ph/0701053**Entanglement Flow in Multipartite Systems***T. S. Cubitt, F. Verstraete and J.I. Cirac*Phys. Rev. A**71**, 052308 (2005) [12 pages] arXiv:quant-ph/0404179**Separable States can be Used to Distribute Entanglement***T. S. Cubitt, F. Verstraete, W. Dür, J.I. Cirac*Phys. Rev. Lett.**91**, 037902 (2003) arXiv:quant-ph/0302168 (highlighted in*Science*NOW article)

## Preprints

**Universal Quantum Hamiltonians***Toby Cubitt, Ashley Montanaro and Stephen Piddock*arXiv:1701.05182[quant-ph]**The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension***Johannes Bausch, Toby Cubitt and Maris Ozols*arXiv:1605.01718[quant-ph]**Comment on "On the uncomputability of the spectral gap"***Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf*arXiv:1603.00825[quant-ph]**Universal Refocusing of Systematic Quantum Noise***Imdad S. B. Sardharwalla, Toby S. Cubitt, Aram W. Harrow and Noah Linden*arXiv:1602.07963[quant-ph]**Size-Driven Quantum Phase Transitions***Johannes Bausch, Toby S. Cubitt, Angelo Lucia, David Perez-Garcia and Michael M. Wolf*arXiv:1512.05687[quant-ph]**Undecidability of the Spectral Gap**(full version)*Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf*arXiv:1502.04573[quant-ph]**An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma***M. Schwarz, T. S. Cubitt and Frank Verstraete*arXiv:1311.6474[quant-ph]**Are Problems in Quantum Information Theory (Un)decidable?***Michael M. Wolf, Toby S. Cubitt and David Perez-Garcia*arXiv:1111.5425[quant-ph]**Entanglement in the Stabilizer Formalism***David Fattal, Toby S. Cubitt, Yoshihisa Yamamoto, Sergey Bravyi and Isaac L. Chuang*arXiv:quant-ph/0406168

# Toby 'qubit' Cubitt

## Who am I? (a brief Curriculum Vitae)

I'm a nationality-confused European, born and raised in Luxembourg but technically British.

I went to the European school in Luxembourg, graduating with the European Baccalaureate in 1998. From there, I hopped across the Channel to Churchill College, Cambridge, studying physics under the Natural Sciences Tripos at the University of Cambridge.

After graduating in 2002, I decided to see what the other end of Europe was like, and moved to the Max Planck Institute for Quantum Optics just outside Munich, Germany to do a PhD in quantum information theory und

# Research interests

## General interests

- CP maps (a.k.a. quantum channels)
- Quantum information theory
- Many-body physics
- Complexity theory
- Hamiltonian complexity
- Entanglement theory
- Probability theory
- Algebraic geometry
- Learning any other interesting new maths I come across…

That'll do for now.

## Publications

You can find a (possibly not-quite-up-to-date) list of my publications on this web site, including copies of the papers, as well as the slides from some of my talks. For a more up-to-date list, try the arXiv.

# Emacs: Undo Tree package

Emacs has a powerful undo system. Unlike the standard undo/redo system in most software, it allows you to recover *any* past state of a buffer (whereas the standard undo/redo system can lose past states as soon as you redo). However, this power comes at a price: many people find Emacs' undo system confusing and difficult to use, spawning a number of packages that replace it with the less powerful but more intuitive undo/redo system. (See the Emacs Wiki.)

Both the loss of data with standard undo/redo, and the confusion of Emacs' undo, stem from trying to treat undo history as a linear sequence of