Difference between revisions of "Journal Club Spring 2012"
(Created page with "This quarter we will be focusing on Hamiltonian Complexity. ==People== '''Organizer(1):''' Isaac Crosson '''Organizer(2):''' Kamil Michnicki (kpm3uw@gmail.com...") |
|||
Line 20: | Line 20: | ||
|Isaac | |Isaac | ||
|Jan 7 | |Jan 7 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|} | |} | ||
Revision as of 21:32, 22 March 2012
This quarter we will be focusing on Hamiltonian Complexity.
Contents
People
Organizer(1): Isaac Crosson
Organizer(2): Kamil Michnicki (kpm3uw@gmail.com)
Faculty Advisor: Aram Harrow
Place
Friday 1:30pm in Computer Science, CSE 503.
Schedule
Subject | Speaker | Date |
---|---|---|
Introduction and Review , arXiv:1106.5875 , Slides | Isaac | 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
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."
http://arxiv.org/abs/0705.2024
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..."
http://arxiv.org/abs/0808.3773
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..."
http://arxiv.org/abs/1011.3445
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..."
http://arxiv.org/abs/quant-ph/0606140
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..."
http://arxiv.org/abs/0806.1746
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."
http://arxiv.org/abs/0811.3412
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."
http://arxiv.org/abs/1102.0770