Hamiltonian complexity
Hamiltonian complexity or quantum Hamiltonian complexity is a topic which deals with problems in quantum complexity theory and condensed matter physics. It mostly studies constraint satisfaction problems related to ground states of local Hamiltonians; that is, Hermitian matrices that act locally on a system of interest.[1] The constraint satisfaction problems in quantum Hamiltonian complexity have led to the quantum version of the Cook–Levin theorem. Quantum Hamiltonian complexity has helped physicists understand the difficulty of simulating physical systems.[1]
Local Hamiltonian problem
Given a Hermitian matrix [math]\displaystyle{ H }[/math], let [math]\displaystyle{ \lambda_0 }[/math] denote the ground state energy of the Hamiltonian [math]\displaystyle{ H }[/math], and let [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] be non-negative real numbers with [math]\displaystyle{ b \geq a + 1 }[/math]. If [math]\displaystyle{ \lambda_0 \leq a }[/math], output Yes. If [math]\displaystyle{ \lambda_0 \geq b }[/math], output No. The k-local Hamiltonian problem is similar except the Hamiltonians have [math]\displaystyle{ k }[/math]-local interactions. This problem has been shown to be QMA-complete for [math]\displaystyle{ k \geq 2 }[/math].
Area law
The area law explains the structure of entanglement present in ground states of physically relevant systems.[2] It states that the entropy of a reduced density matrix of a quantum system in its ground state is proportional to the boundary length of the area.[3]
The area law has been useful in finding efficient ways to simulate entangled quantum systems.[1]
Quantum analog of the PCP theorem
The classical PCP theorem states that simulating the ground states of classical systems is hard. The quantum analog of the PCP theorem concerns simulations of quantum systems. Proving the quantum analog of the PCP theorem is an open problem.[2]
See also
References
- ↑ 1.0 1.1 1.2 Osborne, Tobias J. (2011). "Hamiltonian complexity". Reports on Progress in Physics 75 (2): 022001. doi:10.1088/0034-4885/75/2/022001. PMID 22790342.
- ↑ 2.0 2.1 Gharibian, Sevag; Huang, Yichen; Landau, Zeph; Shin, Seung Woo (2014). "Hamiltonian complexity". Reports on Progress in Physics 75 (2): 022001. doi:10.1088/0034-4885/75/2/022001. PMID 22790342.
- ↑ Zeng, Bei; Xie, Chen; Zhou, Duan-Lu; Wen, Xiao-Gang (2019). Quantum Information Meets Quantum Matter. New York: Springer-Verlag. doi:10.1007/978-1-4939-9084-9. ISBN 978-1-4939-9082-5.
 |  |
