We introduce k-local quasi-quantum states: a superset of the regular quantum states, defined by relaxing the positivity constraint of quantum states. We show that a k-local quasi-quantum state on n qubits can be 1-1 mapped to a *distribution of assignments* over n variables with an alphabet of size 4, which is subject to non-linear constraints over its k-local marginals. Therefore, solving the k-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignments over a classical k-local constraint satisfaction problem.  

We show that this optimization problem is essentially classical, by proving it to be NP-complete. Crucially, as in a quantum state, the optimal distribution is *not* determined straightforwardly by its local marginals. Consequently, our classical optimization problem shares several unique aspects of Hamiltonian complexity: it lacks an easy search-to-decision reduction and it is not clear that its 1D version can be solved efficiently.

Our main result is a PCP theorem for the k-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result. Our proof suggests the existence of a subtle promise-gap amplification procedure in a model that shares many similarities with the quantum local Hamiltonian problem, thereby providing insights on the quantum PCP conjecture.

Joint work with Miklos Santha, arXiv:2410.13549