Hamiltonians whose low-energy states require Ω(n) T gates

CS/Math Seminar - Nolan Coble - University of Maryland, College Park

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 talk 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 ω(log n) T gates to prepare. In fact, we will show a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require Ω(n) T gates. 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 Ω(log n)-depth and Ω(n) T gates to prepare. This result represents a significant improvement over [CCNN23] where we used a different technique to give an energy bound which only distinguishes between stabilizer states and states which require a non-zero number of T gates.

Join Zoom Meeting

https://uwaterloo.zoom.us/j/94853577366?pwd=Ty9YZUViVVlteDg0R2lEZkdnUVBKdz09

Meeting ID: 948 5357 7366

Passcode: 176439