Derandomised tensor product gap amplification for quantum Hamiltonians
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918152923774976 |
|---|---|
| author | Bergamaschi, Thiago Metger, Tony Vidick, Thomas Zhang, Tina |
| author_facet | Bergamaschi, Thiago Metger, Tony Vidick, Thomas Zhang, Tina |
| contents | The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between "high" and "low" energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur's proof of the classical PCP theorem. In this work, following Dinur's model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01333 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Derandomised tensor product gap amplification for quantum Hamiltonians Bergamaschi, Thiago Metger, Tony Vidick, Thomas Zhang, Tina Quantum Physics Computational Complexity The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between "high" and "low" energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur's proof of the classical PCP theorem. In this work, following Dinur's model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture. |
| title | Derandomised tensor product gap amplification for quantum Hamiltonians |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2510.01333 |