The $k$-$\mathsf{XOR}$ problem is one of the most well-studied problems in classical complexity. We study a natural quantum analogue of $k$-$\mathsf{XOR}$, the problem of computing the ground energy of a certain subclass of structured local Hamiltonians, signed sums of $k$-local Pauli operators, which we refer to as $k$-$\mathsf{XOR}$ Hamiltonians. As an exhibition of the connection between this model and classical $k$-$\mathsf{XOR}$, we extend results on refuting $k$-$\mathsf{XOR}$ instances to the Hamiltonian setting by crafting a quantum variant of the Kikuchi matrix for CSP refutation, instead capturing ground energy optimization. As our main result, we show an $n^{O(\ell)}$-time classical spectral algorithm certifying ground energy at most $\frac{1}{2} + \varepsilon$ in (1) semirandom Hamiltonian $k$-$\mathsf{XOR}$ instances or (2) sums of Gaussian-signed $k$-local Paulis both with $O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2-1} \log n /\varepsilon^4$ local terms, a tradeoff known as the refutation threshold. Additionally, we give evidence this tradeoff is tight in the semirandom regime via non-commutative Sum-of-Squares lower bounds embedding classical $k$-$\mathsf{XOR}$ instances as entirely classical Hamiltonians.

翻译：$k$-$\mathsf{XOR}$ 问题是经典复杂性理论中研究最深入的问题之一。我们研究 $k$-$\mathsf{XOR}$ 的一个自然量子类比，即计算一类特定结构化局域哈密顿量的基态能量，这类哈密顿量是 $k$-局域泡利算符的带符号和，我们称之为 $k$-$\mathsf{XOR}$ 哈密顿量。为了展示该模型与经典 $k$-$\mathsf{XOR}$ 之间的联系，我们将关于反驳 $k$-$\mathsf{XOR}$ 实例的结果扩展到哈密顿量场景，通过构造用于 CSP 反驳的 Kikuchi 矩阵的量子变体，转而捕捉基态能量优化。作为主要结果，我们展示了一个 $n^{O(\ell)}$ 时间经典谱算法，该算法能够在以下两种情况下证明基态能量至多为 $\frac{1}{2} + \varepsilon$：(1) 半随机哈密顿量 $k$-$\mathsf{XOR}$ 实例，或 (2) 具有 $O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2-1} \log n /\varepsilon^4$ 个局域项的高斯符号 $k$-局域泡利算符之和，这一权衡被称为反驳阈值。此外，我们通过非交换平方和下界，将经典 $k$-$\mathsf{XOR}$ 实例嵌入为完全经典的哈密顿量，从而证明该权衡在半随机区域是紧的。