MATH 595 - Quantum Complexity and Topology
MATH 595 - Quantum Complexity and Topology
-
From Eric Samperton
73 plays 0I give lightening overview of what is known about the computational complexity of TQFT invariants like the Jones polynomial. -
From Eric Samperton
14 plays 0Justin talks about the computational complexity of approximating Cheeger constants of graphs, and the relation of this problem to quantum algorithms for persistent… -
From Eric Samperton
30 plays 0We spell out the precise relation between 3-manifold/knot invariants and the model of topological quantum computing discussed in the previous several meetings. -
From Eric Samperton
17 plays 0We 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… -
From Eric Samperton
25 plays 0We 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… -
From Eric Samperton
32 plays 0We 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.… -
From Eric Samperton
74 plays 0Continuing 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… -
From Eric Samperton
42 plays 0I 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… -
From Eric Samperton
51 plays 0I 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… -
From Eric Samperton
172 plays 0We construct Kitaev's toric code in full gory detail. Here's his paper. -
From Eric Samperton
23 plays 0BQP 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… -
From Eric Samperton
26 plays 0Simon'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)… -
From Eric Samperton
25 plays 0I 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… -
From Eric Samperton
10 plays 0I 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. … -
From Eric Samperton
13 plays 0We discuss (classical) probabilistic algorithms and reversible circuits. -
From Eric Samperton
19 plays 0We dig into quantum states in more detail, but still somewhat informally. (We won't do any formal "quantum information" in this class, choosing instead… -
From Eric Samperton
30 plays 0I discuss the four axioms of quantum mechanics, and do some very simple examples of time evolution and measurements of qubits. -
From Eric Samperton
30 plays 0I discuss what's known about the computational complexity of unknot recognition. You might want to watch Marc Lackenby's recent talk after watching this. -
From Eric Samperton
22 plays 0I 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… -
From Eric Samperton
26 plays 0I discuss the definition of computability via Turing machines, and a couple of examples and non-examples of computable problems in geometric topology. -
From Eric Samperton
32 plays 0We 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… -
From Eric Samperton
37 plays 0We 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… -
From Eric Samperton
40 plays 0I sketch the proof that every (orientable, closed, PL) 3-manifold has a Heegaard splitting. -
From Eric Samperton
59 plays 0We discuss triangulations of manifolds, and then I justify my hot take that the best dimension is three. -
From Eric Samperton
169 plays 0I begin with a very brief overview of the main themes we will explore this semester: interactions between (low-dimensional) topology, computational complexity and…