Document Open Access Logo

From Holant to Quantum Entanglement and Back

Authors Jin-Yi Cai, Zhiguo Fu, Shuai Shao

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.22.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Jin-Yi Cai
  • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA
Zhiguo Fu
  • School of Information Science and Technology and KLAS, Northeast Normal University, Changchun, China
Shuai Shao
  • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA

Funding

  • Cai, Jin-Yi: Jin-Yi Cai is supported by NSF CCF-1714275.
  • Fu, Zhiguo: Zhiguo Fu is supported by NSFC-61872076.
  • Shao, Shuai: Shuai Shao is supported by NSF CCF-1714275.

Acknowledgements

We want to thank anonymous reviewers for their helpful comments.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ICALP.2020.22

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Holant problem
  • Quantum entanglement
  • SLOCC equivalence
  • Bell property

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miriam Backens. The inductive entanglement classification yields ten rather than eight classes of four-qubit entangled states. Physical Review A, 97:022329, 2017. Google Scholar
  2. Miriam Backens. A new holant dichotomy inspired by quantum computation. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, pages 16:1-16:14, 2017. Google Scholar
  3. Miriam Backens. A complete dichotomy for complex-valued holant^c. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, pages 12:1-12:14, 2018. Google Scholar
  4. Rodney J Baxter. Eight-vertex model in lattice statistics. Physical Review Letters, 26(14):832, 1971. Google Scholar
  5. Rodney J Baxter. The six and eight-vertex models revisited. Journal of statistical physics, 116(1-4):43-66, 2004. Google Scholar
  6. Charles H Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K Wootters. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Physical review letters, 70(13):1895, 1993. Google Scholar
  7. Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #csp. Journal of Computer and System Sciences, 78(2):681-688, 2012. Google Scholar
  8. Andrei Bulatov and Martin Grohe. The complexity of partition functions. Theoretical Computer Science, 348(2-3):148-186, 2005. Google Scholar
  9. Andrei A Bulatov. The complexity of the counting constraint satisfaction problem. Journal of the ACM (JACM), 60(5):1-41, 2013. Google Scholar
  10. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain. Cambridge University Press, 2017. Google Scholar
  11. Jin-Yi Cai and Xi Chen. Complexity of counting csp with complex weights. Journal of the ACM (JACM), 64(3):1-39, 2017. Google Scholar
  12. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. SIAM Journal on Computing, 42(3):924-1029, 2013. Google Scholar
  13. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted# csp: An effective complexity dichotomy. SIAM Journal on Computing, 45(6):2177-2198, 2016. Google Scholar
  14. Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. arXiv preprint, 2017. URL: http://arxiv.org/abs/1702.07938.
  15. Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. Complexity of counting weighted eulerian orientations with ars. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.02362.
  16. Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation, 259:130-141, 2018. Google Scholar
  17. Jin-Yi Cai and Artem Govorov. Perfect matchings, rank of connection tensors and graph homomorphisms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 476-495. SIAM, 2019. Google Scholar
  18. Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. SIAM Journal on Computing, 45(5):1671-1728, 2016. Google Scholar
  19. Jin-Yi Cai, Heng Guo, and Tyson Williams. Clifford gates in the holant framework. Theoretical Computer Science, 745:163-171, 2018. Google Scholar
  20. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for holant* problems of boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714-1728. SIAM, 2011. Google Scholar
  21. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted boolean #csp. Journal of Computer and System Sciences, 80(1):217-236, 2014. Google Scholar
  22. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for real holant^c problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1802-1821. SIAM, 2018. Google Scholar
  23. Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear and quadratic operations over gf (2). Physical Review A, 68(4):042318, 2003. Google Scholar
  24. Wolfgang Dür, Guifre Vidal, and J Ignacio Cirac. Three qubits can be entangled in two inequivalent ways. Physical Review A, 62(6):062314, 2000. Google Scholar
  25. Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3-4):260-289, 2000. Google Scholar
  26. Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245-1274, 2013. Google Scholar
  27. Artur K Ekert. Quantum cryptography based on bell’s theorem. Physical review letters, 67(6):661, 1991. Google Scholar
  28. Michael Freedman, László Lovász, and Alexander Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20(1):37-51, 2007. Google Scholar
  29. Mariami Gachechiladze and Otfried Gühne. Completing the proof of “generic quantum nonlocality”. Physics Letters A, 381(15):1281-1285, 2017. Google Scholar
  30. Masoud Gharahi Ghahi and Stefano Mancini. Comment on “inductive entanglement classification of four qubits under stochastic local operations and classical communication”. Physical Review A, 98(6):066301, 2018. Google Scholar
  31. Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing, 39(7):3336-3402, 2010. Google Scholar
  32. Daniel Gottesman. The heisenberg representation of quantum computers, talk at. In International Conference on Group Theoretic Methods in Physics. Citeseer, 1998. Google Scholar
  33. Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of modern physics, 81(2):865, 2009. Google Scholar
  34. Richard Jozsa and Noah Linden. On the role of entanglement in quantum-computational speed-up. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 459(2036):2011-2032, 2003. Google Scholar
  35. Lucas Lamata, Juan León, D Salgado, and E Solano. Inductive entanglement classification of four qubits under stochastic local operations and classical communication. Physical Review A, 75(2):022318, 2007. Google Scholar
  36. Lucas Lamata, Juan León, D Salgado, and Enrique Solano. Inductive classification of multipartite entanglement under stochastic local operations and classical communication. Physical Review A, 74(5):052336, 2006. Google Scholar
  37. Jiabao Lin and Hanpin Wang. The complexity of boolean holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798-828, 2018. Google Scholar
  38. Milena Mihail and Peter Winkler. On the number of eulerian orientations of a graph. Algorithmica, 16(4-5):402-414, 1996. Google Scholar
  39. Akimasa Miyake and Frank Verstraete. Multipartite entanglement in 2×2×n quantum systems. Physical Review A, 69(1):012101, 2004. Google Scholar
  40. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  41. Linus Pauling. The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. Journal of the American Chemical Society, 57(12):2680-2684, 1935. Google Scholar
  42. Sandu Popescu and Daniel Rohrlich. Generic quantum nonlocality. Physics Letters A, 166(5-6):293-297, 1992. Google Scholar
  43. Leslie G Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410-421, 1979. Google Scholar
  44. Leslie G Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229-1254, 2002. Google Scholar
  45. Leslie G Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565-1594, 2008. Google Scholar
  46. Frank Verstraete, Jeroen Dehaene, Bart De Moor, and Henri Verschelde. Four qubits can be entangled in nine different ways. Physical Review A, 65(5):052112, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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