Quantum Information and Computation

The local Hamiltonian problem on a line with eight states is QMA-complete

HallgrenSean, NagajDaniel, NarayanaswamiSandeep

Published Sep 1, 2013• 0 citations

Publisher

Abstract

DOI: 10.5555/2535680.2535681

Related papers

The Local Hamiltonian problem on a line with eight states is QMA-complete

Sean Hallgren, Daniel Nagaj, S. Narayanaswami

The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

arXiv:1312.1469Dec 5, 201313 citations

The local Hamiltonian problem on a line with eight staes is QMA-complete

Sean Hallgren, Daniel Nagaj, S. Narayanaswami

Quantum Information and ComputationSep 1, 201339 citations

3-Local Hamiltonian is QMA-complete

Julia Kempe, Oded Regev

It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.

arXiv:quant-ph/0302079Quantum Information and ComputationMay 1, 2003112 citations

Product-state approximations to quantum ground states

Fernando G. S. L. Brandão, Aram W. Harrow

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean ground-state energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. A key feature that distinguishes quantum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error.

arXiv:1310.0017ACM Symposium on Theory of Computing (STOC)May 28, 201331 citations

3-local Hamitonian is QMA-complete

KempeJulia, RegevOded

It has been shown by Kitaev that the 5-LOCAL HAMILTONIAN problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-LOCAL HAMILTONIAN is already QMA-complete.

Quantum Information and ComputationMay 1, 20037 citations

The complexity of the separable hamiltonian problem

André Chailloux, Or Sattath

In this paper, we study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.

Jan 1, 201214 citations