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.1475502278nas a2200121 4500008004100000245012000041210006900161260001500230520183200245100002102077700002102098856003702119 2020 eng d00aQuasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits0 aQuasipolynomial Time Approximation of Output Probabilities of Co c12/10/20203 a

We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit C, and any bit string x∈{0,1}n, can compute the quantity |<x|C|0⊗n>|2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P-hard to compute this same quantity to within 2−n2 additive error [Mov20]. The previous best known algorithm for this problem used O(2n1/3poly(1/ε)) time to compute probabilities to within additive error ε [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit "pieces" produced this way.

1 aCoble, Nolan, J.1 aCoudron, Matthew uhttps://arxiv.org/abs/2012.0546002321nas a2200121 4500008004100000245011300041210006900154260001500223520188200238100002102120700002102141856003702162 2020 eng d00aQuasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits0 aQuasipolynomial time approximation of output probabilities of ge c12/10/20203 a

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit C acting on n qubits, and any bit string x∈{0,1}n, can compute the quantity |<x|C|0⊗n>|2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P-hard to compute this same quantity to within 2−n2 additive error [Mov20, KMM21]. The previous best known algorithm for this problem used O(2n1/3poly(1/ϵ)) time to compute probabilities to within additive error ϵ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for this estimation task restricted to 2D circuits, which makes a novel use of 1D Matrix Product States (MPS) carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach.
Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted combination of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit ``pieces" produced this way.

1 aCoble, Nolan, J.1 aCoudron, Matthew uhttps://arxiv.org/abs/2012.05460