Journal Club Winter 2012

From Quantum Computing Theory Group
Jump to: navigation, search

This quarter we will be focusing on Hamiltonian Complexity.


Organizer(1): Isaac Crosson

Organizer(2): Kamil Michnicki (

Faculty Advisor: Aram Harrow


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


Subject Speaker Date
Introduction and Review , arXiv:1106.5875 , Slides Isaac Jan 7
Local Hamiltonians and QMA, arXiv:quant-ph/0210077v1, Slides David Jan 13
QMA-Complete in 1D, arXiv:0705.4077 Isaac Jan 20
detectability lemma and area laws, arXiv:1011.344 Kamil Jan 27
detectability lemma and area laws, arXiv:1011.344 Kamil Feb 3
Stoquastic Hamiltonians, arXiv:quant-ph/0606140 Isaac Feb 24
Quantum PCP, arXiv:0811.3412 Group Mar 2
Quantum PCP, arXiv:0811.3412 Group Mar 9


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?"

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. "

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..."

Bounds on Entanglement Entropy

May 2007 An Area Law for One Dimensional Quantum Systems - Hastings
"We prove an area law for the entanglement entropy in gapped one dimensional quantum systems."

Aug 2008 Area laws for the entanglement entropy - a review - Eisert, Cramer, Plenio
"A significant proportion of the article is devoted to the quantitative connection between the entanglement content of states and the possibility of their efficient simulation..."

Nov 2010 Quantum Hamiltonian complexity and the detectability lemma - Aharonov, Arad, Landau, Vazirani
"We use [the detectability lemma] to provide a simplified and more combinatorial proof of Hastings' 1D area law..."

Stoquastic Hamiltonians

Jun 2006 The Complexity of Stoquastic Local Hamiltonian Problems - Bravyi, DiVincenzo, Oliveira, Terhal
"We prove that the Local Hamiltonian Problem for stoquastic Hamiltonians belongs to the complexity class AM..."

Jun 2008 Complexity of stoquastic frustration-free Hamiltonians - Bravyi, Terhal
"...we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer..."

Quantum PCP Conjecture

Nov 2008 The Detectability Lemma and Quantum Gap Amplification - Aharonov, Arad, Landau, Vazirani
"...proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof."

Feb 2011 On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems - Aharonov, Eldar
"The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons."