DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.75

Product-State Approximation Algorithms for the Transverse Field Ising Model

Authors: Vincenzo Lipardi, David Mestel, and Georgios Stamoulis

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We study classical polynomial-time approximation algorithms for the transverse field Ising model (TFIM), allowing a mixture of ferromagnetic and antiferromagnetic interactions between pairs of qubits, alongside transverse field terms with arbitrary non-negative weights. In this work, we first prove a second-order conic inequality based on the anticommutation property of the two competing terms (Ising Z_i Z_j vs. field X_i terms), and we use this inequality to strengthen the basic SDP relaxation of the problem. By producing two competing rounded product state solutions and taking the better of the two we achieve an approximation ratio γ≈ 0.7860. A further improvement by non-uniform interpolation achieves a ratio γ ≈ 0.82197. Finally, we give an explicit purely antiferromagnetic TFIM instance on three qubits for which every product state achieves at most 169/180≈ 0.9389 of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely antiferromagnetic case.

Cite as

Vincenzo Lipardi, David Mestel, and Georgios Stamoulis. Product-State Approximation Algorithms for the Transverse Field Ising Model. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lipardi_et_al:LIPIcs.MFCS.2026.75,
  author =	{Lipardi, Vincenzo and Mestel, David and Stamoulis, Georgios},
  title =	{{Product-State Approximation Algorithms for the Transverse Field Ising Model}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.75},
  URN =		{urn:nbn:de:0030-drops-274574},
  doi =		{10.4230/LIPIcs.MFCS.2026.75},
  annote =	{Keywords: Ising model, Hamiltonian Complexity, Approximation Algorithms, Semidefinite Programming}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2019.49

Widths of Regular and Context-Free Languages

Authors: David Mestel

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract

Given a partially-ordered finite alphabet Sigma and a language L subseteq Sigma^*, how large can an antichain in L be (where L is given the lexicographic ordering)? More precisely, since L will in general be infinite, we should ask about the rate of growth of maximum antichains consisting of words of length n. This fundamental property of partial orders is known as the width, and in a companion work [Mestel, 2019] we show that the problem of computing the information leakage permitted by a deterministic interactive system modeled as a finite-state transducer can be reduced to the problem of computing the width of a certain regular language. In this paper, we show that if L is regular then there is a dichotomy between polynomial and exponential antichain growth. We give a polynomial-time algorithm to distinguish the two cases, and to compute the order of polynomial growth, with the language specified as an NFA. For context-free languages we show that there is a similar dichotomy, but now the problem of distinguishing the two cases is undecidable. Finally, we generalise the lexicographic order to tree languages, and show that for regular tree languages there is a trichotomy between polynomial, exponential and doubly exponential antichain growth.

Cite as

David Mestel. Widths of Regular and Context-Free Languages. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mestel:LIPIcs.FSTTCS.2019.49,
  author =	{Mestel, David},
  title =	{{Widths of Regular and Context-Free Languages}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.49},
  URN =		{urn:nbn:de:0030-drops-116111},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.49},
  annote =	{Keywords: Formal languages, combinatorics on words, information flow}
}

Search Results

Documents authored by Mestel, David

Product-State Approximation Algorithms for the Transverse Field Ising Model

Abstract

Cite as

Widths of Regular and Context-Free Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message