Journal Club Winter 2012

This quarter we will be focusing on Hamiltonian Complexity.

People

Organizer(1): Isaac Crosson

Organizer(2): Kamil Michnicki (kpm3@u.washington.edu)

Faculty Advisor: Aram Harrow

Place

Friday 1:30pm in Computer Science, CSE 503.

Schedule

Subject	Speaker	Date
Introduction and Review		Jan 7

Papers

Recent Survey

June 2011: Hamiltonian Complexity - Tobias Osbourne
"In recent years we've seen the birth of a new field known as hamiltonian complexity lying at the crossroads between computer science and theoretical physics. Hamiltonian complexity is directly concerned with the question: how hard is it to simulate a physical system?"
http://arxiv.org/abs/1106.5875

Quantum Cook-Levin Theorem

Oct 2002: Quantum NP - A Survey - Dorit Aharonov, Tomer Naveh
"We describe Kitaev's result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3-SAT, namely local Hamiltonians, is QMA complete. "
http://arxiv.org/abs/quant-ph/0210077

May 2007: The power of quantum systems on a line - Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe
"...with some additional technical effort and 12 states per particle, we show that the problem of approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete..."
http://arxiv.org/abs//0705.4077

Organization

Possible Topics

• Quantum Information (Mark Wilde http://arxiv.org/abs/1106.1445) (2 votes)

  * Pro/Con: field has stabilized, stuck on solving additivity problem
  * Con: unrealistic models, not as applicable
  * Pro: Using asymptotic bounds on entropy can give classical algorithm for approximating separable states. (Brandao, Christandl, Yard)
  * Pro: connection to quantum error-correcting codes

• Self-Correcting Quantum Memories (5 votes)

 * Pro: hot/active research area right now, possibility of making contribution, not many people working on
   * Major breakthrough by Haah http://arxiv.org/abs/1101.1962
 * Pro: best way theory can help build a quantum computer
 * Pro: nice connections to statistical physics (topological order)

• Matt Hastings / Sergei Bravyi / Alexei Kitaev (Greatest Hits, Vol. 1) (0 votes)

  * Hastings: area laws, Lieb-Robinson bounds, additivity, classical algorithms for simulating quantum systems, hamiltonian complexity, self-correcting quantum memory, topological order
  * Bravyi: stoquastic hamiltonians, topological codes, Majorana fermions, stability results for topological order
  * Kitaev: awesome
  * Possibly invite for physics colloquium

• Oded Regev: quantum algorithms, communication complexity, lattice-based crypto (1 vote)
• Following one particular person:

  * Pro: can jump around various topics, get good breadth
  * Con: might not ever understand anything

• Hamiltonian Complexity (3 votes)

  * Pro: has great obscure acronyms, in the intersection of physics and CS (Lieb-Robinson, area laws, etc.), good guide / survey by Tobias Osborne (http://arxiv.org/abs/1106.5875)
  * Con: hard! (e.g. quantum PCP)

• Quantum Money / Knots
• Stephen Bartlett