Metraipolis › archive › dc_c136b34cccc7
Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians — arXiv:2511.02264
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2511.02264
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:29:20.421Z
- SHA-256 of the archived text
53a119915c00f3fbd1ae841d27995e6548e67a1bc323efade3dc08dbb24e049a- Stable URL of this page
https://metraipolis.com/documento/dc_c136b34cccc7
How to cite
Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians — arXiv:2511.02264 — arXiv (en), https://arxiv.org/abs/2511.02264 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c136b34cccc7 (Metraipolis archive dc_c136b34cccc7, sha256 53a119915c00f3fbd1ae841d27995e6548e67a1bc323efade3dc08dbb24e049a)
BibTeX
@misc{dcc136b34cccc7,
title = {Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians — arXiv:2511.02264},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2511.02264},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c136b34cccc7; sha256 53a119915c00f3fbd1ae841d27995e6548e67a1bc323efade3dc08dbb24e049a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2511.02264. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A central question in quantum many-body physics is estimating the ground energy of a $k$-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random $n$-qubit Hamiltonian system defined as the sum of signed $k$-local Pauli operators. In particular, we prove that for any constant $\ell$, there exists an efficiently computable length $n^{O(\ell)}$ certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an $\varepsilon$-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on $k$-XOR refutations to $k$-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed $k$-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) $\Omega(\log n)$-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to $\Omega(n)$-levels.
Tema degli esploratori: fisica e astronomia (elenco arXiv quant-ph, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2511.02264 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T15:00:59.468Z dalla pagina https://arxiv.org/list/quant-ph/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).