Hamiltonian complexity

Hamiltonian complexity or Quantum hamiltonian complexity is a field 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 . The constraint satisfaction problems in quantum hamiltonian complexity have lead to the quantum version of the Cook–Levin theorem. Quantum hamiltonian complexity has helped physicists understand the difficulty of simulating physical systems.

Local Hamiltonian problem

Main article: QMA § The_local_Hamiltonian_problem

Given a hermitian matrix $H$ and non-negative reals $a$, $b$ with $b\geq a+1$, If $\lambda _{0}(H)\leq a$, output Yes. If $\lambda _{0}(H)>=b$, output No; where $\lambda _{0}$ is the ground state energy. The k-Local Hamiltonian problem is similarly except the hamiltonians have $k$ local interactions. This problem has been shown to be QMA-complete for $k\geq 2$.

Area law

Main article: Entropy_of_entanglement § Area_law_of_bipartite_entanglement_entropy

The Area law explains the structure of entanglement present in ground states of physical relevant systems. . It states that the entropy of a reduced density matrix of a quantum system in it's ground state is proportional to the boundary length of the area. The Area law has been useful in finding efficient ways in simulating entangled quantum systems.

Quantum analog of the PCP theorem

Main article: PCP_theorem § 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. Proof of the Quantum analog of the PCP theorem is an open problem.

See also

• Hamiltonian simulation
• Density Matrix Renormalization Group
• Matrix product state