Spring 2021 MATH 595
Quantum, Complexity, and Topology (QCaT)

Logistics. Getting to know each other. Course overview. What is a manifold?

Recording 1.1, Meeting Notes

You can read a succinct account of some of the various foundational issues concerning manifolds in a review article by Ciprian Manolescu.

Finishing up the motivation for our focus on piecewise linear manifolds. Discussing some of the basic invariants of and problems about manifolds that we would like to solve, and associated computability issues. Justifying our extra special interest in 3-dimensional PL manifolds.

Recording 1.2, Meeting Notes

Heegaard splittings.

Recording 2.1, Meeting Notes

Normal curves and Heegaard diagrams. Definition of knot and equivalence of knots.

Recording 2.2, Meeting Notes

Combinatorializing knots via stick presentations. Diagrams. Converting braids to diagrams. Combinatorializing equivalence of knots in each of these settings.

Recording 3.1, Meeting Notes

Computability

Recording 3.2, Meeting Notes

A smattering of complexity classes, reductions, and our first NP-complete problem in knot theory

Recording 4.1, Meeting Notes

The proof in class that sub-unlink detection is NP-hard came from The unbearable hardness of unknotting, by de Mesmay, Rieck, Sedgwick, Tancer.

• The computational complexity of knot and link problems, by Hass, Lagarias, Pippinger
• A polynomial upper bound on Reidemeister moves, by Lackenby
• The unbearable hardness of unknotting, by de Mesmay, Rieck, Sedgwick, Tancer
• Knottedness is in NP, modulo GRH, by Kuperberg
• The efficient certification of knottedness and Thurston norm, by Lackenby

Recording 4.2, Meeting Notes

As a follow up, you might want to watch Marc Lackenby's recent talk about putting unknot recognition in quasi-polynomial time.

Axioms of quantum mechanics.

Recording 5.1, Meeting Notes

More on quantum states and Deutsch-Jozsa

Recording 5.2, Meeting Notes

Classical probabilistic algorithms and reversible computing

Recording 6.1, Meeting Notes

NP-complete problems for reversible circuits, ancilla bits, gate dilation, quantum circuits

See Section 2.2 of one of my paper's with Greg Kuperberg here for more info.

Recording 6.2, Meeting Notes

BQP and QMA

Recording 7.1, Meeting Notes

No meeting today.

Simon's algorithm and factoring (Shor's algorithm)

Recording 8.1, Meeting Notes

Basics of quantum error correction

Recording 8.2, Meeting Notes

Toric code I. The toric code was originally described here:

Fault tolerant quantum computation by anyons, by Kitaev

Recording 9.1, Meeting Notes

Toric code II, and the stabilizer formalism. The latter was developed by Calderbank, Rains, Shor and Sloane, and, independently, Gottesman. My preferred source among the various original papers is this one:

Quantum Error Correction Via Codes Over GF(4), by Calderbank, Rains, Shor and Sloane.

I begin a probably-too-zoomed-out overview of the historical development of ideas that begin with topological quantum field theory (TQFT) and lead to topological quantum computation (TQC). Here are some of the key papers:

• Topological quantum field theories, by Atiyah. Gives the rigorous mathematical definition of a TQFT.
• Quantum field theory and the Jones polynomial, by Witten. Argues (not completely rigorously) that the Jones polynomial/Kauffman bracket can be juiced up to a (2+1)-dimensional TQFT when q is a root of unity.
• Invariants of 3-manifolds via link polynomials and quantum groups, by Reshetikhin and Turaev. Gives a rigorous mathematical construction of Witten's TQFTs, using somewhat different but mathematically rigorous ideas, namely, the representation theory of certain ribbon Hopf algebras. The small quantum group U_q sl_2 yields the Jones-Kauffman theory.
• Modular categories and 3-manifold invariants, by Turaev. Abstracts out the properties of the representation categories used in the previous paper, and arrives at the definition of modular tensor category.
• State sum invariants of 3-manifolds and quantum 6j-symbols, by Turaev and Viro. Builds a fully-extended (2+1)-d TQFT from every modular tensor category.
• Invariants of piecewise-linear 3-manifolds, by Barrett and Westbury. Defines spherical tensor categories and shows that the Turaev-Viro construction works on them more generally.
• Fault-tolerant quantum computation by anyons, by Kitaev. Introduces the toric code, and more generally surface codes associated to any finite group, and shows how to process quantum information by braiding anyons around surfaces.
• P/NP, and the quantum field computer, by Freedman. Proposes that (topological) quantum field theories could be used to build a kind of quantum computer, and maybe solve #P-complete problems in polynomial time.
• Simulation of topological field theories by quantum computers, by Freedman, Kitaev and Wang. Shows that TQFTs can be "simulated" on a quantum computer (that is, inside the usual quantum circuit model). They don't say this, but their work shows one should not expect a TQFT-based computer to be able to solve #P-complete problems in polynomial time.
• A modular functor which is universal for quantum computation, by Freedman, Larsen and Wang. Shows that when q is a principal root of unity whose order is not 1, 2, 3, 4 or 6, then the U_q sl_2 Witten-Reshetikhin-Turaev TQFT can be used to simulate arbitrary quantum circuits. In other words, the Jones polynomial can be used for universal quantum computation. This is the theoretical "proof-of-concept" for topological quantum computation. Combined with the previous paper, topological quantum computation with a "sufficiently powerful TQFT" is equivalent to the standard quantum circuit model.
• String-net condensation: A physical mechanism for topological phases, by Levin and Wen. Generalizes the toric code to any unitary fusion category. Unitary fusion categories are always spherical, so the Levin-Wen construction is essentially concocting "physically realistic" (but, as of 2021, still theoretical!) Hamiltonian models of the Turaev-Viro-Barrett-Westbury fully-extended TQFTs. Levin and Wen's motivation is to construct many interesting examples of distinct topological phases of matter. My understanding of the topological condensed matter literature is that topological phases of matter in 2 spatial dimensions are expected to be "classified" by once-extended (2+1)-dimensional unitary TQFTs, hence (by the next paper) unitary modular tensor categories.
• Modular categories as representations of the 3-dimensional bordism 2-category, by Bartlett, Douglas, Schommer-Pries, and Vicary. Shows that every once-extended (2+1)-dimensional TQFT is determined by a modular tensor category, and a choice of square root of its global dimension. Thus, Turaev's definition of modular tensor category is precisely the correct one.

Recording 10.1, Meeting Notes

Topological quantum computing I

Recording 10.2, Meeting Notes

Topological quantum computing II. We define quantum representations of mapping class groups of (closed) surfaces determined by TQFTs, and begin to show one can build quantum circuits inside (2+1)-dimensional unitary TQFTs. More on this next time.

Recording 11.1, Meeting Notes

Topological quantum computing III. We discuss extended (2+1)-dimensional TQFTs, and show how the structure of an extended TQFT allows us to localize the state spaces of surfaces by cutting them up into subsurfaces.

Recording 11.2, Meeting Notes

Topological quantum computing IV. We show that if an extended unitary TQFT supports a quantum representation of a braid group with image that is dense inside of the unitary group of an appropriate state space, then the TQFT can be used to simulate quantum circuits.

Recording 12.2, Meeting Notes

No meeting (recovering from Pfizer dose #2). Students watched one of the following recordings of talks by Eric:

• Computational complexity and three manifolds and zombies
• Khovanov homology: what it is and how(?) to compute it

Topological quantum computing and 3-manifold invariants

Recording 13.2, Meeting Notes

Computational complexity of TQFT invariants

Recording 14.1, Meeting Notes

Patrick and Ryan talk about the Solovay-Kitaev theorem

No recording, Notes from Patrick's talk

Justin talks about the computational complexity of approximating Cheeger constants of graphs, and the relation of this problem to quantum algorithms for persistent homology. Hans gives an overview of the structure of 3-manifolds.

Recording 15.1, no meeting notes

The semester is over. Have a nice summer! If you're interested in more algorithms and topology, you might consider taking Nathan Dunfield's class next semester.