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

# Quantum Computation and Algorithms course

Quantum Computation and Algorithms course

Quantum computing is the flagship quantum technology. Peter Shor's 1994 quantum factoring algorithm kicked off a wave of interest and excitment about quantum computing, and is in large part responsible for the field of quantum information going mainstream. A second wave of even more excitment has been kicked off recently by the near-term prospect of NISQ hardware (noisy, intermediate-scale quantum computers) – i.e. quantum computing hardware that is not obviously useful for anything… but no longer obviously useless either!

However, there is also currently a lot of hype and many unrealistic expectations. The aim of this course is to show you where all the excitment derives from, rigorously and in detail; and to innoculate you against the over-hype.

# Toby's ten commandments of being scooped

Toby's ten commandments of being scooped

[To be read in alongside Luc's ten commandments of authorship.]

- Rule 1
- Never consult a list of rules regarding being scooped.
- Rule 2
- Be happy: it implies \(\geq 1\) other person is interested in the problem you solved.
- Rule 3
- You hear about the other author's paper before it's posted on the arXiv, and are on friendly terms with them. Politely ask if they'd be willing to post to the arXiv simultaneously. This is a win-win: both papers will look more important and get more attention. If they don't agree, go to Rule 6. In either case, cite the other paper and be generous in crediting them.
- Rule 4
- You agree to post simultaneously, but then they ask for more time. Be generous and give them plenty of extra time. You will feel good. When you post yours, cite the other paper and be generous in crediting them.
- Rule 5
- You agree to post simultaneously, but then you need more time. Go home, have a beer, tell them you're not going to make the agreed date and let them post first. When you post yours, cite the other paper and be generous in crediting them.
- Rule 6
- The other results appear on the arXiv before yours, but you can post your results soon enough that it's clearly independent work. Go ahead and post them. You'll still get credit for the work. Cite the other paper and be generous in crediting them.
- Rule 7
- You're not ready to post soon without stressing about it, but the differences in your results are interesting and you're motivated to work on them. Work on those, post your paper when you have interesting new results. Be happy, smile. You've advanced science a few more steps. Cite the other paper and be generous in crediting them.
- Rule 8
- Your results are very similar, and the differences aren't interesting enough to you. Get your mind off it—crying, sex, indulging, smoking, hallucinating, and swimming in the North Sea may help. After doing \(\geq 1\) of those activities, look at the differences with fresh eyes. If they look interesting now, go back to Rule 7. If not, let this one go. There are infinitely many new and interesting problems to work on: go and work on one of those.
- Rule 9
- It happens - do not get stressed about it.

# Complexity and Computability in Physics course

Complexity and Computability in Physics course Lecture course on quantum complexity theory, encompassing (a brief intro to) computability and complexity theory, complexity theory in quantum physics, and computability theory in physics. Lectured at the 2018 Boulder quantum information summer school.

## Lecture videos and notes

- Lecture 1, Computation and Complexity video and lecture notes
- Lecture 2: Complexity in Physics video and lecture notes
- Lecture 3: Computability in Physics video and lecture notes

# Advanced Quantum Information Theory course

Advanced Quantum Information Theory course

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 naturally-occurring many-body systems. In a sense, they are two sides of the same coin. Quantum information theory is now used both to prove important results in many-body physics, and to construct many-body models that exhibit very unusual physics, providing counterexamples to long-standing beliefs in condensed matter theory. This is now one of the fastest-developing areas of the field.

# Truths about proofs and groups

Truths about proofs and groups

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 through to reach it.

# Quantum Computation and Complexity course

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.

## Lecture notes

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

# Matrix Product States and PEPS

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 © 2016 Toby Cubitt, and are licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.)

# Decoupling Method in Quantum Shannon Theory

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

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

# Quantum Mechanics for Mathematicians course

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

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 10)

# Classical mechanics and electrodynamics

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

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

# Publications

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

## Papers

**Complete Toy Models of Holographic Duality**

*Tamara Kohler, Toby Cubitt*
arXiv:1810.08992[hep-th] [62 pages]

**History-state Hamiltonians are critical**

*Carlos E. González-Guillén, Toby S. Cubitt*
arXiv:1810.06528[quant-ph] [35 pages]

**Undecidability of the Spectral Gap in One Dimension**

*Johannes Bausch, Toby Cubitt, Angelo Lucia, David Perez-Garcia*
arxiv:1810.01858[quant-ph] [54 pages]

**The Unsolvable Problem**

*Toby Cubitt, David Perez-Garcia, Michael Wolf*
Scientific American, Volume 319, Issue 4, October 2018
(Cover article; selected for 2018 "Scientific American Articles of the Year" special issue.)

**Translationally invariant universal classical Hamiltonians**

*Tamara Kohler and Toby Cubitt*
arxiv:1807.01715[cond-mat.stat-mech] [44 pages]

**Universal Quantum Hamiltonians**

*Toby Cubitt, Ashley Montanaro and Stephen Piddock*
Proc. Natl. Acad. Sci. (2018)
arXiv:1701.05182[quant-ph] [82 pages]

**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*
Proc. Natl. Acad. Sci. **115**:1, p19–23 (2018) [18 pages]
arXiv:1512.05687[quant-ph]

**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]
(Winner of 2018 AHP-Birkhauser Prize for "most remarkable paper published in Annales Henri Poincaré".)

**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** (full version)

*Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf*
arXiv:1502.04573[quant-ph] (full version, 127 pages)

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

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

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

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

**Are Problems in Quantum Information Theory (Un)decidable?**

*Michael M. Wolf, Toby S. Cubitt and David Perez-Garcia*
arXiv:1111.5425[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 in the Stabilizer Formalism**

*David Fattal, Toby S. Cubitt, Yoshihisa Yamamoto, Sergey Bravyi and Isaac L. Chuang*
arXiv:quant-ph/0406168

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