Hamiltonians whose low-energy states require $Ω(n)$ T gates
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914830934343680 |
|---|---|
| author | Coble, Nolan J. Coudron, Matthew Nelson, Jon Nezhadi, Seyed Sajjad |
| author_facet | Coble, Nolan J. Coudron, Matthew Nelson, Jon Nezhadi, Seyed Sajjad |
| contents | 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 $ω(\log n)$ 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. 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. In order to accomplish this we define a "pseudo-stabilizer" property of a state with respect to each local Hamiltonian term, and prove an additive local energy lower bound for each term at which the state is pseudo-stabilizer. By proving a relationship between the number of T gates preparing a state and the number of terms at which the state is pseudo-stabilizer, we are able to give a constant energy lower bound which applies to any state with T-count less than $c \cdot n$ for some fixed positive constant $c$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_01347 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hamiltonians whose low-energy states require $Ω(n)$ T gates Coble, Nolan J. Coudron, Matthew Nelson, Jon Nezhadi, Seyed Sajjad Quantum Physics Computational Complexity 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 $ω(\log n)$ 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. 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. In order to accomplish this we define a "pseudo-stabilizer" property of a state with respect to each local Hamiltonian term, and prove an additive local energy lower bound for each term at which the state is pseudo-stabilizer. By proving a relationship between the number of T gates preparing a state and the number of terms at which the state is pseudo-stabilizer, we are able to give a constant energy lower bound which applies to any state with T-count less than $c \cdot n$ for some fixed positive constant $c$. 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. |
| title | Hamiltonians whose low-energy states require $Ω(n)$ T gates |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2310.01347 |