Exploring Quasi-Quantum States & the Quasi-Quantum PCP Theorem 🧠

Miklos Santha (National University of Singapore)
https://simons.berkeley.edu/talks/miklos-santha-national-university-singapore-2025-05-30
Quantum Algorithms, Complexity, and Fault Tolerance Reunion

We introduce k-local quasi-quantum states: a superset of the regular quantum states, defined by relaxing the positivity constraint. 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 assignment over a classical k-local CSP. We show that this optimization problem is essentially classical by proving it is NP-complete. Crucially, just as ordinary quantum states, these distributions lack a simple tensor-product structure and are therefore not determined straightforwardly by their local marginals. Consequently, our classical optimization problem shares some 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 with dynamical programming (i.e., it could remain NP-hard).

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. The 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.