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

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].

1 aCoble, Nolan, J.1 aCoudron, Matthew1 aNelson, Jon1 aNezhadi, Seyed, Sajjad uhttps://arxiv.org/abs/2310.0134701454nas a2200145 4500008004100000245006000041210005900101260001400160520101200174100002101186700002101207700001601228700002701244856003701271 2023 eng d00aLocal Hamiltonians with no low-energy stabilizer states0 aLocal Hamiltonians with no lowenergy stabilizer states c2/28/20233 a

The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.

1 aCoble, Nolan, J.1 aCoudron, Matthew1 aNelson, Jon1 aNezhadi, Seyed, Sajjad uhttps://arxiv.org/abs/2302.1475502079nas a2200133 4500008004100000245007300041210006900114260001400183520164800197100002001845700002701865700001601892856003701908 2021 eng d00aNonlocal Games, Compression Theorems, and the Arithmetical Hierarchy0 aNonlocal Games Compression Theorems and the Arithmetical Hierarc c10/9/20213 a

We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 12 is complete for the class Σ1 (i.e., RE). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE). We prove that deciding whether the quantum value of a two-player nonlocal game is exactly equal to 1 is complete for Π2; this class is in the second level of the arithmetical hierarchy and corresponds to formulas of the form "∀x∃yϕ(x,y)". This shows that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value (either exactly or approximately). We explain how results about the complexity of nonlocal games all follow in a unified manner from a technique known as compression. At the core of our Π2-completeness result is a new "gapless" compression theorem that holds for both quantum and commuting operator strategies. Our compression theorem yields as a byproduct an alternative proof of Slofstra's result that the set of quantum correlations is not closed. We also show how a "gap-preserving" compression theorem for commuting operator strategies would imply that approximating the commuting operator value is complete for Π1.

1 aMousavi, Hamoon1 aNezhadi, Seyed, Sajjad1 aYuen, Henry uhttps://arxiv.org/abs/2110.0465101359nas a2200157 4500008004100000245003200041210003200073260001400105520093200119100002001051700002001071700002701091700002201118700002401140856003701164 2021 eng d00aSynchronous Values of Games0 aSynchronous Values of Games c9/29/20213 a

We study synchronous values of games, especially synchronous games. It is known that a synchronous game has a perfect strategy if and only if it has a perfect synchronous strategy. However, we give examples of synchronous games, in particular graph colouring games, with synchronous value that is strictly smaller than their ordinary value. Thus, the optimal strategy for a synchronous game need not be synchronous. We derive a formula for the synchronous value of an XOR game as an optimization problem over a spectrahedron involving a matrix related to the cost matrix. We give an example of a game such that the synchronous value of repeated products of the game is strictly increasing. We show that the synchronous quantum bias of the XOR of two XOR games is not multiplicative. Finally, we derive geometric and algebraic conditions that a set of projections that yields the synchronous value of a game must satisfy.

1 aHelton, William1 aMousavi, Hamoon1 aNezhadi, Seyed, Sajjad1 aPaulsen, Vern, I.1 aRussell, Travis, B. uhttps://arxiv.org/abs/2109.14741