DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.15

Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians

Authors: Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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) [Alexei Y. Kitaev et al., 2002] 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 [Dinur, 2007]. 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 [Fernando G. S. L. Brandão and Aram Wettroth Harrow, 2013].

Cite as

Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang. Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bergamaschi_et_al:LIPIcs.CCC.2026.15,
  author =	{Bergamaschi, Thiago and Metger, Tony and Vidick, Thomas and Zhang, Tina},
  title =	{{Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.15},
  URN =		{urn:nbn:de:0030-drops-270572},
  doi =		{10.4230/LIPIcs.CCC.2026.15},
  annote =	{Keywords: quantum PCP conjecture, gap amplification, local Hamiltonians, tensor product amplification, expander random walks, quantum de Finetti theorems}
}

Search Results

Documents authored by Zhang, Tina

Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians

Abstract

Cite as

Thanks for your feedback!

Could not send message