MATH 595 - Quantum Complexity and Topology
MATH 595 - Quantum Complexity and Topology
-
I give lightening overview of what is known about the computational complexity of TQFT invariants like the Jones polynomial.
Meeting 14.1: Computational complexity of TQFT…
From Eric Samperton
94 plays 0 -
Justin talks about the computational complexity of approximating Cheeger constants of graphs, and the relation of this problem to quantum algorithms for persistent…
Meeting 15.1: Students talks
From Eric Samperton
16 plays 0 -
We spell out the precise relation between 3-manifold/knot invariants and the model of topological quantum computing discussed in the previous several meetings.
Meeting 13.2: Topological quantum computing and…
From Eric Samperton
43 plays 0 -
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…
Meeting 12.2: Topological quantum computing IV
From Eric Samperton
29 plays 0 -
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…
Meeting 11.2: Topological quantum computing III
From Eric Samperton
31 plays 0 -
We mostly say more about (2+1)-dimensional unitary TQFTs. In particular, we define the quantum representations of mapping class groups of surfaces determined by a TQFT.…
Meeting 11.1: Topological quantum computing II
From Eric Samperton
36 plays 0 -
Continuing to follow Kitaev, we consider the toric code as the ground state space of a Hamiltonian constructed from the vertex and plaquette operators. The other…
Meeting 10.2: Topological quantum computing I
From Eric Samperton
93 plays 0 -
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…
Meeting 10.1: From TQFT to TQC, Part 1
From Eric Samperton
54 plays 0 -
I finish up calculating the distance of the toric code. I then introduce the stabilizer formalism, which provides a method to construct quantum error correcting codes…
Meeting 9.2: Toric code II and stabilizer…
From Eric Samperton
61 plays 0 -
We construct Kitaev's toric code in full gory detail. Here's his paper.
Meeting 9.1: Toric code I
From Eric Samperton
194 plays 0 -
BQP is generally expect to be the correct abstraction of "quantum polynomial time," but two practical issues will need to be overcome in order to build quantum…
Meeting 8.2: Quantum error correction
From Eric Samperton
30 plays 0 -
Simon's problem is a somewhat contrived oracle problem that provides an oracle separation of BQP and BPP, which should be interpreted as evidence (but not proof)…
Meeting 8.1: Simon's problem and factoring
From Eric Samperton
28 plays 0 -
I define BQP ("bounded error quantum polynomial time") and pay lip service to the Solovay-Kitaev theorem (hopefully a student will prove it in a talk at the…
Meeting 7.1: BQP and QMA
From Eric Samperton
29 plays 0 -
I follow up more thoroughly on RSAT, an NP-complete satisfiability problem for Boolean reversible circuits. It actually has several variants, of which we discuss 2. …
Meeting 6.2: More on reversible circuits, and…
From Eric Samperton
13 plays 0 -
We discuss (classical) probabilistic algorithms and reversible circuits.
Meeting 6.1: Classical warm-ups to quantum…
From Eric Samperton
16 plays 0 -
We dig into quantum states in more detail, but still somewhat informally. (We won't do any formal "quantum information" in this class, choosing instead…
Meeting 5.2: Digging into quantum states
From Eric Samperton
24 plays 0 -
I discuss the four axioms of quantum mechanics, and do some very simple examples of time evolution and measurements of qubits.
Meeting 5.1: Axioms of quantum mechanics
From Eric Samperton
43 plays 0 -
I discuss what's known about the computational complexity of unknot recognition. You might want to watch Marc Lackenby's recent talk after watching this.
Meeting 4.2: The complexity of unknot recognition
From Eric Samperton
34 plays 0 -
I continue to review some of the usual suspects in complexity: P, NP, PSPACE, EXP and such. I then introduce two basic notions of reduction: polynomial-time many-one…
Meeting 4.1: Complexity
From Eric Samperton
31 plays 0 -
I discuss the definition of computability via Turing machines, and a couple of examples and non-examples of computable problems in geometric topology.
Meeting 3.2: Computability
From Eric Samperton
38 plays 0 -
We combinatorialize tame knots using stick presentations, then form knot diagrams by taking regular projections onto a plane. I explain two ways to convert a word in…
Meeting 3.1: More on knots, and building knot…
From Eric Samperton
41 plays 0 -
We continue the discussion of Heegaard diagrams from last time. I give some examples, calculate the homology of a lens space, and introduce normal curves. We then…
Meeting 2.2: More on Heegaard diagrams, knots and…
From Eric Samperton
57 plays 0 -
I sketch the proof that every (orientable, closed, PL) 3-manifold has a Heegaard splitting.
Meeting 2.1: Heegaard splittings of 3-manifolds
From Eric Samperton
66 plays 0 -
We discuss triangulations of manifolds, and then I justify my hot take that the best dimension is three.
Meeting 1.2: The best dimension is 3
From Eric Samperton
76 plays 0 -
I begin with a very brief overview of the main themes we will explore this semester: interactions between (low-dimensional) topology, computational complexity and…
Meeting 1.1: Course overview, and what is a…
From Eric Samperton
205 plays 0
Search for ""