DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.22

From Holant to Quantum Entanglement and Back

Authors: Jin-Yi Cai, Zhiguo Fu, and Shuai Shao

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

Holant problems are intimately connected with quantum theory as tensor networks. We first use techniques from Holant theory to derive new and improved results for quantum entanglement theory. We discover two particular entangled states |Ψ₆⟩ of 6 qubits and |Ψ₈⟩ of 8 qubits respectively, that have extraordinary closure properties in terms of the Bell property. Then we use entanglement properties of constraint functions to derive a new complexity dichotomy for all real-valued Holant problems containing a signature of odd arity. The signatures need not be symmetric, and no auxiliary signatures are assumed.

Cite as

Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to Quantum Entanglement and Back. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ICALP.2020.22,
  author =	{Cai, Jin-Yi and Fu, Zhiguo and Shao, Shuai},
  title =	{{From Holant to Quantum Entanglement and Back}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.22},
  URN =		{urn:nbn:de:0030-drops-124298},
  doi =		{10.4230/LIPIcs.ICALP.2020.22},
  annote =	{Keywords: Holant problem, Quantum entanglement, SLOCC equivalence, Bell property}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2018.2

A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

Authors: Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, and Michael Kowalczyk

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract

Suppose \varphi and \psi are two angles satisfying \tan(\varphi) = 2 \tan(\psi) > 0. We prove that under this condition \varphi and \psi cannot be both rational multiples of \pi. We use this number theoretic result to prove a classification of the computational complexity of spin systems on k-regular graphs with general (not necessarily symmetric) real valued edge weights. We establish explicit criteria, according to which the partition functions of all such systems are classified into three classes: (1) Polynomial time computable, (2) \#P-hard in general but polynomial time computable on planar graphs, and (3) \#P-hard on planar graphs. In particular problems in (2) are precisely those that can be transformed to a form solvable by the Fisher-Kasteleyn-Temperley algorithm by a holographic reduction.

Cite as

Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, and Michael Kowalczyk. A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ITCS.2018.2,
  author =	{Cai, Jin-Yi and Fu, Zhiguo and Girstmair, Kurt and Kowalczyk, Michael},
  title =	{{A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.2},
  URN =		{urn:nbn:de:0030-drops-83251},
  doi =		{10.4230/LIPIcs.ITCS.2018.2},
  annote =	{Keywords: Spin Systems, Holant Problems, Number Theory, Characters, Cyclotomic Fields}
}

Search Results

Documents authored by Fu, Zhiguo

From Holant to Quantum Entanglement and Back

Abstract

Cite as

A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

Abstract

Cite as

Thanks for your feedback!

Could not send message