Difference between revisions of "Journal Club Winter 2012"
(→Papers) |
(→Papers) |
||
| Line 47: | Line 47: | ||
<p>'''Aug 2008''' Area laws for the entanglement entropy - a review - Eisert, Cramer, Plenio<br/> | <p>'''Aug 2008''' Area laws for the entanglement entropy - a review - Eisert, Cramer, Plenio<br/> | ||
| − | ''"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"''<br/> | + | ''"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..."''<br/> |
http://arxiv.org/abs/0808.3773</p> | http://arxiv.org/abs/0808.3773</p> | ||
<p>'''Nov 2010''' Quantum Hamiltonian complexity and the detectability lemma - Aharonov, Arad, Landau, Vazirani<br/> | <p>'''Nov 2010''' Quantum Hamiltonian complexity and the detectability lemma - Aharonov, Arad, Landau, Vazirani<br/> | ||
| − | ''"We use [the detectability lemma] to provide a simplified and more combinatorial proof of Hastings' 1D area law"''<br/> | + | ''"We use [the detectability lemma] to provide a simplified and more combinatorial proof of Hastings' 1D area law..."''<br/> |
http://arxiv.org/abs/1011.3445</p> | http://arxiv.org/abs/1011.3445</p> | ||
| + | |||
| + | ===Stoquastic Hamiltonians=== | ||
| + | <p>'''Jun 2006''' The Complexity of Stoquastic Local Hamiltonian Problems - Bravyi, DiVincenzo, Oliveira, Terhal<br/> | ||
| + | ''"We prove that the Local Hamiltonian Problem for stoquastic Hamiltonians belongs to the complexity class AM..."''<br/> | ||
| + | http://arxiv.org/abs/quant-ph/0606140</p> | ||
| + | |||
| + | <p>'''Jun 2008''' Complexity of stoquastic frustration-free Hamiltonians - Bravyi, Terhal<br/> | ||
| + | ''"...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..."''<br/> | ||
| + | http://arxiv.org/abs/quant-ph/0606140</p> | ||
==Organization== | ==Organization== | ||
Revision as of 18:00, 30 December 2011
This quarter we will be focusing on Hamiltonian Complexity.
Contents
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
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/quant-ph/0606140
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
