{"id":"arxiv/2606.23967","url":"https://arxiv.org/abs/2606.23967","tags":["quant-ph"],"score":0,"title":"Polynomial-time exact diagonalization via sparse guided eigenwalks","domain":"quant-ph","source":"arxiv","authors":["Zachary E. Chin","Mario Motta","Javier Robledo Moreno","Antonio Mezzacapo","Isaac L. Chuang","William Kirby"],"reviews":0,"subject":"quant-ph","summary":"Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-22","reactions":{}}