{"id":"arxiv/2607.14384","url":"https://arxiv.org/abs/2607.14384","tags":["quant-ph","cond-mat.dis-nn","cs.CC","math.PR"],"score":0,"title":"Circuit complexity lower bounds for quantum spin glasses","domain":"quant-ph","source":"arxiv","authors":["Omar Al-Ghattas","David Gamarnik"],"reviews":0,"subject":"quant-ph","summary":"A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}