Search Results

Documents authored by Bergamaschi, Thiago

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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.16
On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement

Authors: Thiago Bergamaschi and Yunchao Liu

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Preparing encoded logical states is the first step in a fault-tolerant quantum computation. Standard approaches based on concatenation or repeated measurement incur a significant time overhead. The Raussendorf-Bravyi-Harrington cluster state [Raussendorf et al., 2005] offers an alternative: a single-shot preparation of encoded states of the surface code, by means of a constant depth quantum circuit, followed by a single round of measurement and classical feedforward [Bravyi et al., 2020]. In this work we generalize this approach and prove that single-shot logical state preparation can be achieved for arbitrary quantum LDPC codes. Our proof relies on a minimum-weight decoder and is based on a generalization of Gottesman’s clustering-of-errors argument [Gottesman, 2014]. As an application, we also prove single-shot preparation of the encoded GHZ state in arbitrary quantum LDPC codes. This shows that adaptive noisy constant depth quantum circuits are capable of generating generic robust long-range entanglement.
Cite as

Thiago Bergamaschi and Yunchao Liu. On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 16:1-16:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergamaschi_et_al:LIPIcs.ITCS.2025.16,
  author =	{Bergamaschi, Thiago and Liu, Yunchao},
  title =	{{On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{16:1--16:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.16},
  URN =		{urn:nbn:de:0030-drops-226444},
  doi =		{10.4230/LIPIcs.ITCS.2025.16},
  annote =	{Keywords: Quantum error correction, fault tolerance, single-shot error correction, logical state preparation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.20
Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians

Authors: Thiago Bergamaschi

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum k-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of weak Szemerédi regularity lemmas for k-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop constant time sampling algorithms, and to characterize the "vertex sample complexity" of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.
Cite as

Thiago Bergamaschi. Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergamaschi:LIPIcs.ICALP.2023.20,
  author =	{Bergamaschi, Thiago},
  title =	{{Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.20},
  URN =		{urn:nbn:de:0030-drops-180722},
  doi =		{10.4230/LIPIcs.ICALP.2023.20},
  annote =	{Keywords: Approximation Algorithms, Quantum Information}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact