# Science posts

Blog posts which assume some prior mathematical knowledge are tagged @school, @undergrad or @PhD, to give you a rough idea of what level of expertise is needed to follow the post.

This is just a very rough guideline, to help you restrict the list of blog posts to those that are of most interest to you. Don't let the tag names put you off! If you're at school and keen to read about quantum information or other mathematical topics, by all means go ahead and read a post tagged @PhD. You'll probably understand it better than I would have after my PhD.

# Truths about proofs and groups

Truths about proofs and groups 9 February 2018

A while back, a PhD student in our group asked me whether the sum over all elements of a stabilizer is a projector. If you know what this means, you're probably (a) a quantum information theorist (in which case, stop reading here) and (b) already know the answer and how to prove it (unlike me, who'd forgotten both).

The answer is no doubt well-known to anyone who works on quantum stabilizer codes, and we could have just googled for the result. It seemed like a nice, self-contained mathematical question, though. So rather than googling, we tried to figure it out for ourselves at the blackboard.

If you just want to see the simple final answer, skip to the end. But then you'll miss all the fun and the main point of this post. The way we came up with the solution makes for a nice toy example of the convoluted, messy and inelegant process by which mathematical results are really proven. Before they get polished up into the simple, elegant, pristine proofs "from The Book" that are all you ever get to see in textbooks and research papers. The unspoken (or at least unpublished) reality is that elegant proofs invariably emerge after following numerous blind alleys, unjustified intuitive leaps, and inelegant, round-the-houses arguments. All of which get simplified away in time for publication. (Or maybe that's just my proofs!)

Instead of just explaining the elegant final answer, I'm going to explain the inelegant process we went

# Advanced Quantum Information Theory course

Advanced Quantum Information Theory course 23 June 2017 Lectured from 2017 as an optional advanced theory course for the UCL quantum CDT.

Based on a course I originally designed and 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

## Problem sheets

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

## Course description

Quantum information theory is neither wholly physics (though it's mostly about quantum mechanics), nor wholly mathematics (though it mostly proves rigorous mathematical results), nor wholly computer science (though it's mostly about storing, processing, or transmitting information). Over the last two decades, it has developed into a rich mathematical theory of information in quantum mechanical systems, that draws on all three of these disciplines. More recently, this has been turned on its head: quantum information is beginning to be used to attack deep problems in physics, computer science, and mathematics.

The aim of this course is to select one or two advanced topics in quantum information theory, close to the cutting edge of research, and cover them in some depth and rigour.

This time around, I will focus on quantum information in many-body systems. What do these two topics have to do with each other? Quantum computation aims to engineer complex many-body systems to process information in ways that would not be possible classically. Many-body physics aims to understand the complex behaviour of nat

# Quantum Computation and Complexity course

Quantum Computation and Complexity course 15 July 2016 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

The Arora-Barak book gives an excellent, modern treatment of the theory of computation and complexity, going far beyond what's covered in this short course. The proof of Kitaev's theorem closely follows the original from the Kitaev-Schen-Vyalyi book. The other references are review papers on Hamiltonian complexity, which may also be of interest.

• Arora and Barak, "Complexity Theory: A Modern Approach, Cambridge University Press
• Kitaev, A., Shen, A., and Vyalyi M. "Classical and Quantum Computation", American Mathematical Society
• Aharonov, D. and Naveh, T. "Quantum NP - a Survey"
• Gharibian, S., Huang, Y. and Landau, Z. "Hamiltonian Complexity"

The following is a selective and incomplete list of links to the arXiv versions of papers that proved key results in Hamiltonian Complexity post-Kitaev. (These are the papers I mentioned in the brief survey at the very end of the lecture course.)

### QMA-completeness with stronger locality conditions, and related results

• J. Kempe and O. Regev, "3-local Hamiltonian is QMA-complete" (2003)

Proves QMA-completeness of the k-local Hamiltonian problem for $$k=3$$.

• J. Kempe, A. Kitaev and O. Regev, "The Complexity of the Local Hamiltonian Problem" (2004)

Proves QMA-completeness of the k-local Hamiltonian problem for $$k=2$$. Introduces the perturbation gadget technique.

• R. Oliveira, B. Terhal, "The complexity of quantum spin systems on a two-dimensional square lattice" (2007)

Proves QMA-completeness of the k-local Hamiltonian problem for nearest-neighbo

# Matrix Product States and PEPS

Matrix Product States and PEPS 14 July 2016 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)

# Decoupling Method in Quantum Shannon Theory

Decoupling Method in Quantum Shannon Theory 19 October 2015 Originally lectured in 2015 as part of the quantum information theory masters course for the UCL quantum CDT.

## Lecture Notes

• Decoupling Method

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.

# Quantum Mechanics for Mathematicians course

Quantum Mechanics for Mathematicians course 4 November 2011 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)

## Recommended books

I have closely followed Chapter 2 of Nielsen and Chuang (which is by now the standard textbook on quantum information theory), with some additional mathematical content, and a more careful proof of the CHSH inequality.

The other books listed below may also be of interest:

• "Quantum Computation and Quantum Information", Nielsen & Chuang Chapter 2 gives a concise but excellent introduction to quantum mechanics, more suitable for quantum information theory than most quantum mechanics textbooks. I have closely followed this chapter, but I have given additional mathematical results and proofs when desirable. Bell inequalities are also covered in this chapter, but this is not the focus of the book and the proof they give obscures some of the subtleties.
• "An Introduction to Quantum Theory", Hannabuss A nice and more mathematically oriented quantum mechanics textbook, but still contains a lot more physics than covered in this course.
• "Quantum Theory: Concepts and Methods", Asher Peres A delightful text book that contains a good treatement of the Bell experiment and much more.
• "Bell Inequalities and Entanglement", Werner and Wolf arXiv:quant-ph/0107093 This review article gives a careful and rigorous discussion of Bell inequalities.
• "Speakable and Unspeakable in Quantum Mechanics", John Bell A collection of insightful essays and papers by John Bell (of Bell inequality fame).
• "Feynman Lectures vol. 3", Feynman, Leighton, Sands

# Quantum Mechanics course

Quantum Mechanics course 11 May 2010 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 10)

## Problem Sheets

Problem sheets 7 and 8 correspond to my section of the course. I have removed the solution sheets, as the same problems may be used by future lecturers. If you want a copy of the solutions for purposes other than avoiding having a good go at the problems yourself, email me.

• Problem Sheet 7
• Problem Sheet 8

## Recommended books

### Angular momentum (lectures 1 to 5)

The main text book for this part of the course is the book by Hannabuss. But any good text book on quantum mechanics will cover this material. A sample of ones I like is listed below, but if you find one that presents the material in a way that you find easier, you should by all means make use of it.

• "An Introduction to Quantum Theory", Hannabuss.
The angular momentum section of the course closely follows chapter 8.
• "Modern Quantum Mechanics", Sakurai
• "Quantum Mechanics",Cohen-Tannoudji
• "Group Theory in Physics", Cornwell.
Chapter 12, Volume 2. For interest only; well beyond the level of the course.
• "Feynman Lectures vol. 3", Feynman, Leighton, Sands.
As an accompaniement to the other books, volume 3 of Feynman's famous lecture series contains a presentation of quantum mechanics with a different and somewhat less mathematical flavour, which some may find helpful or interesting.

# Classical mechanics and electrodynamics

Classical mechanics and electrodynamics 14 May 2004 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 twisted physics professors).

If anyone involved in teaching the courses is interested in obtaining the solutions, drop me an email. I have scanned copies for about half the mechanics question sheets and all the electrodynamics question sheets.

## Extra information sheets

• Summation convention and $$\delta$$-functions

## Recommended books

These books complement those recommended in the lectures, rather than replacing them. I recommend them as alternative references written in a less formal style, for when you're confused by the more formal approach (or just want to read more):

• Feynman Lectures vols. 1 and 2
Feynman, Leighton, Sands
• Mathematical Methods for Physics and Engineering
Riley, Hobson, Bence

## Vocabulary

I started making a list of physical and mathematical vocabulary in both English and German:

• English/German mathematical vocabulary

If you have corrections or words you would like to see added, please email me.

# Publications

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

## Published Papers

1. Size-Driven Quantum Phase Transitions Johannes Bausch, Toby S. Cubitt, Angelo Lucia, David Perez-Garcia and Michael M. Wolf Proc. Natl. Acad. Sci. 115:1, p19–23 (2018) [18 pages] arXiv:1512.05687[quant-ph]
2. The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension Johannes Bausch, Toby Cubitt and Maris Ozols Annales Henri Poincaré, 18:11, p3449–3513 (2017) [63 pages] arXiv:1605.01718[quant-ph]
3. 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]
4. The Complexity of Divisibility Johannes Bausch and Toby S. Cubitt J. Linear Alg. 504, p64–107 (2016) [50 pages] arXiv:1411.7380[math.PR]
5. 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]
6. 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]
7. 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]
8. 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)
9. 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]
10. 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]
11. 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]
12. 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]
13. 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]
14. 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]
15. 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]
16. 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)
17. 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)
18. 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]
19. 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)
20. 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]
21. 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]
22. 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]
23. 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]
24. 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]
25. 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]
26. 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]
27. 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]
28. 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]
29. 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
30. 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
31. 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

1. Universal Quantum Hamiltonians Toby Cubitt, Ashley Montanaro and Stephen Piddock arXiv:1701.05182[quant-ph]
2. Comment on "On the uncomputability of the spectral gap" Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf arXiv:1603.00825[quant-ph]
3. Universal Refocusing of Systematic Quantum Noise Imdad S. B. Sardharwalla, Toby S. Cubitt, Aram W. Harrow and Noah Linden arXiv:1602.07963[quant-ph]
4. Undecidability of the Spectral Gap (full version) Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf arXiv:1502.04573[quant-ph]
5. 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]
6. Are Problems in Quantum Information Theory (Un)decidable? Michael M. Wolf, Toby S. Cubitt and David Perez-Garcia arXiv:1111.5425[quant-ph]
7. 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

• Quantum information theory
• Many-body physics
• Complexity theory
• Hamiltonian complexity
• Hamiltonian simulation
• CP maps (a.k.a. quantum channels)
• 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 with links to the papers, as well as the slides from some of my talks. For a more up-to-date list, try the arXiv.