skip to content

Lecture 2: Introduction to Quantum Complexity (tutorial)

Friday 6th September 2013 - 11:30 to 12:30
INI Seminar Room 1
Coauthors: David Gosset, Sandeep Narayanaswami and Sean Hallgren

In this and tomorrow's lecture, we will look at why frustrated (local Hamiltonian) and unfrustrated (quantum SAT) problems can be very hard to solve, even for the computers we don't have yet. The keywords are: universal computation, ground states, locality, qudits, promise gaps, eigenvalue gaps, history states, clocks, and translational invariance.

The goal is to build the basics so that we can focus on recent ideas about the Quantum 3-SAT problem, random Quantum SAT (its SAT/UNSAT transition), perfect verifiers (QMA_1 vs QMA), quantum walks (the difficulty of solving scattering), blind quantum computation (limited power of QMA verifiers) and QMA vs. QCMA (MQA).

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons