Search Results

Documents authored by Piovesan, Teresa

Document
DOI: 10.4230/LIPIcs.TQC.2015.127
On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings

Authors: Sabine Burgdorf, Monique Laurent, and Teresa Piovesan

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We investigate structural properties of the completely positive semidefinite cone CS^n_+, consisting of all the n x n symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of bipartite quantum correlations, as projection of an affine section of it. We have two main results concerning the structure of the completely positive semidefinite cone, namely about its interior and about its closure. On the one hand we construct a hierarchy of polyhedral cones which covers the interior of CS^n_+, which we use for computing some variants of the quantum chromatic number by way of a linear program. On the other hand we give an explicit description of the closure of the completely positive semidefinite cone, by showing that it consists of all matrices admitting a Gram representation in the tracial ultraproduct of matrix algebras.
Cite as

Sabine Burgdorf, Monique Laurent, and Teresa Piovesan. On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 127-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{burgdorf_et_al:LIPIcs.TQC.2015.127,
  author =	{Burgdorf, Sabine and Laurent, Monique and Piovesan, Teresa},
  title =	{{On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{127--146},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.127},
  URN =		{urn:nbn:de:0030-drops-55537},
  doi =		{10.4230/LIPIcs.TQC.2015.127},
  annote =	{Keywords: Quantum graph parameters, Trace nonnegative polynomials, Copositive cone, Chromatic number, Quantum Entanglement, Nonlocal games, Von Neumann algebra}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.206
Round Elimination in Exact Communication Complexity

Authors: Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we consider two types of communication problems that we call promise equality and list problems. For both of these, it was already known that the one-round classical and one-round quantum complexities are characterized by the chromatic number and orthogonal rank of a certain graph, respectively. In a promise equality problem, Alice and Bob must decide if their inputs are equal or not. We prove that classical protocols for such problems can always be reduced to one-round protocols with no extra communication. In contrast, we give an explicit instance of a promise problem that exhibits an exponential gap between the one- and two-round exact quantum communication complexities. Whereas the chromatic number thus captures the complete complexity of promise equality problems, the hierarchy of "quantum chromatic numbers" (starting with the orthogonal rank) giving the quantum communication complexity for every fixed number of communication rounds thus turns out to enjoy a much richer structure. In a list problem, Bob gets a subset of some finite universe, Alice gets an element from Bob's subset, and their goal is for Bob to learn which element Alice was given. The best general lower bound (due to Orlitsky) and upper bound (due to Naor, Orlitsky, and Shor) on the classical communication complexity of such problems differ only by a constant factor. We exhibit an example showing that, somewhat surprisingly, the four-round protocol used in the bound of Naor et al. can in fact be optimal. Finally, we pose a conjecture on the orthogonality rank of a certain graph whose truth would imply an intriguing impossibility of round elimination in quantum protocols for list problems, something that works trivially in the classical case.
Cite as

Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman. Round Elimination in Exact Communication Complexity. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 206-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.TQC.2015.206,
  author =	{Bri\"{e}t, Jop and Buhrman, Harry and Leung, Debbie and Piovesan, Teresa and Speelman, Florian},
  title =	{{Round Elimination in Exact Communication Complexity}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{206--225},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.206},
  URN =		{urn:nbn:de:0030-drops-55588},
  doi =		{10.4230/LIPIcs.TQC.2015.206},
  annote =	{Keywords: communication complexity, round elimination, quantum communication, protocols, chromatic numbers}
}
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 About DROPS Imprint Privacy Contact