# 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 o

# 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 ©{

# 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.

# Advanced Quantum Information Theory course

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-2: Whistle-stop introduction to complexity theory
- Lectures 3-4: Local Hamiltonians
- Lectures 5-7: Kitaev's Theorem
- Lecture 8: Local clock construction

### Section 2: Lieb-Robinson techniques

- Lecture 9: Many-body quantum physics introduction
- Lecture 10-12: Lieb-Robinson bounds
- Lectures 13-15: Exponential decay of correlations

## Problem sheets

- Examples sheet 1: Complexity theory; Hamiltonian complexity
- Examples sheet 2: Kitaev's theorem; Many-body physics; Lieb-Robinson bounds

# 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

# 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

**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

# 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.

# 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 bitter and twist