|
|
| Line 27: |
Line 27: |
| | | | |
| | ==Papers== | | ==Papers== |
| − | Note:Papers will change soon.
| + | Coming soon. |
| − | ===Recent Survey===
| |
| − | '''June 2011:''' Hamiltonian Complexity - Tobias Osbourne<br/>
| |
| − | ''"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?"''<br/>
| |
| − | http://arxiv.org/abs/1106.5875
| |
| − | | |
| − | ===Quantum Cook-Levin Theorem===
| |
| − | <p>'''Oct 2002:''' Quantum NP - A Survey - Dorit Aharonov, Tomer Naveh<br/>
| |
| − | ''"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. "''<br/>
| |
| − | http://arxiv.org/abs/quant-ph/0210077 </p>
| |
| − | <p>'''May 2007:''' The power of quantum systems on a line - Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe<br/>
| |
| − | ''"...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..."''<br/>
| |
| − | http://arxiv.org/abs//0705.4077</p>
| |
| − | | |
| − | ===Bounds on Entanglement Entropy===
| |
| − | <p>'''May 2007''' An Area Law for One Dimensional Quantum Systems - Hastings<br/>
| |
| − | ''"We prove an area law for the entanglement entropy in gapped one dimensional quantum systems."''<br/>
| |
| − | http://arxiv.org/abs/0705.2024</p>
| |
| − | | |
| − | <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/>
| |
| − | http://arxiv.org/abs/0808.3773</p>
| |
| − | | |
| − | <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/>
| |
| − | 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/0806.1746</p>
| |
| − | | |
| − | ===Quantum PCP Conjecture===
| |
| − | <p>'''Nov 2008''' The Detectability Lemma and Quantum Gap Amplification - Aharonov, Arad, Landau, Vazirani<br/>
| |
| − | ''"...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."''<br/>
| |
| − | http://arxiv.org/abs/0811.3412</p>
| |
| − | | |
| − | <p>'''Feb 2011''' On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems - Aharonov, Eldar<br/>
| |
| − | ''"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."''<br/>
| |
| − | http://arxiv.org/abs/1102.0770</p>
| |
This quarter we will be focusing on Quantum Expanders and Randomized Constructions.
