DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.41

Krenn-Gu Conjecture for Sparse Graphs

Authors: L. Sunil Chandran, Rishikesh Gajjala, and Abraham M. Illickan

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

Greenberger–Horne–Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. Krenn, Gu and Zeilinger discovered a correspondence between a large class of quantum optical experiments which produce GHZ states and edge-weighted edge-coloured multi-graphs with some special properties called the GHZ graphs. On such GHZ graphs, a graph parameter called dimension can be defined, which is the same as the dimension of the GHZ state produced by the corresponding experiment. Krenn and Gu conjectured that the dimension of any GHZ graph with more than 4 vertices is at most 2. An affirmative resolution of the Krenn-Gu conjecture has implications for quantum resource theory. Moreover, this would save huge computational resources used for finding experiments which lead to higher dimensional GHZ states. On the other hand, the construction of a GHZ graph on a large number of vertices with a high dimension would lead to breakthrough results. In this paper, we study the existence of GHZ graphs from the perspective of the Krenn-Gu conjecture and show that the conjecture is true for graphs of vertex connectivity at most 2 and for cubic graphs. We also show that the minimal counterexample to the conjecture should be 4-connected. Such information could be of great help in the search for GHZ graphs using existing tools like PyTheus. While the impact of the work is in quantum physics, the techniques in this paper are purely combinatorial, and no background in quantum physics is required to understand them.

Cite as

L. Sunil Chandran, Rishikesh Gajjala, and Abraham M. Illickan. Krenn-Gu Conjecture for Sparse Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.MFCS.2024.41,
  author =	{Chandran, L. Sunil and Gajjala, Rishikesh and Illickan, Abraham M.},
  title =	{{Krenn-Gu Conjecture for Sparse Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.41},
  URN =		{urn:nbn:de:0030-drops-205978},
  doi =		{10.4230/LIPIcs.MFCS.2024.41},
  annote =	{Keywords: Graph colourings, Perfect matchings, Quantum Physics}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.8

Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings

Authors: Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal, and Sandeep Sen

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract

In this paper, we study the problem of designing prefix-free encoding schemes having minimum average code length that can be decoded efficiently under a decode cost model that captures memory hierarchy induced cost functions. We also study a special case of this problem that is closely related to the length limited Huffman coding (LLHC) problem; we call this the soft-length limited Huffman coding problem. In this version, there is a penalty associated with each of the n characters of the alphabet whose encodings exceed a specified bound D(≤ n) where the penalty increases linearly with the length of the encoding beyond D. The goal of the problem is to find a prefix-free encoding having minimum average code length and total penalty within a pre-specified bound P. This generalizes the LLHC problem. We present an algorithm to solve this problem that runs in time O(nD). We study a further generalization in which the penalty function and the objective function can both be arbitrary monotonically non-decreasing functions of the codeword length. We provide dynamic programming based exact and PTAS algorithms for this setting.

Cite as

Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal, and Sandeep Sen. Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{banchhor_et_al:LIPIcs.FSTTCS.2021.8,
  author =	{Banchhor, Shashwat and Gajjala, Rishikesh and Sabharwal, Yogish and Sen, Sandeep},
  title =	{{Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.8},
  URN =		{urn:nbn:de:0030-drops-155193},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.8},
  annote =	{Keywords: Approximation algorithms, Hierarchical memory, Prefix free codes}
}

Search Results

Documents authored by Gajjala, Rishikesh

Krenn-Gu Conjecture for Sparse Graphs

Abstract

Cite as

Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings

Abstract

Cite as

Thanks for your feedback!

Could not send message