



01577nas a2200145   4500008004100000245006900041210006300110260001400173520112200187100002101309700002101330700001601351700002701367856003701394       2023                        eng d00aHamiltonians whose low-energy states require $\Omega(n)$ T gates0 aHamiltonians whose lowenergy states require Omegan T gates  c10/2/20233 a<p>The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Even with NLTS now solved, there remain many independent and unresolved prerequisites to the QPCP Conjecture, such as the NLSS Conjecture of [GL22]. In this work we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose low-energy states all require ω(logn) T gates to prepare. In fact, we prove a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require Ω(n) T gates. Following a previous work [CCNN23], we further show that our procedure can be applied to the NLTS Hamiltonians of [ABN22] to yield local Hamiltonians whose low-energy states require both Ω(logn)-depth and Ω(n) T gates to prepare. Our results utilize a connection between T-count and stabilizer groups, which was recently applied in the context of learning low T-count states [GIKL23a, GIKL23b, GIKL23c].</p>1 aCoble, Nolan, J.1 aCoudron, Matthew1 aNelson, Jon1 aNezhadi, Seyed, Sajjad  uhttps://arxiv.org/abs/2310.01347