3 Search Results for "Palazuelos, Carlos"


Document
On Converses to the Polynomial Method

Authors: Jop Briët and Francisco Escudero Gutiérrez

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)


Abstract
A surprising "converse to the polynomial method" of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the famous Grothendieck constant. A natural question posed there asks if bounded quartic polynomials can be approximated by 2-query quantum algorithms. Arunachalam, Palazuelos and the first author showed that there is no direct analogue of the result of Aaronson et al. in this case. We improve on this result in the following ways: First, we point out and fix a small error in the construction that has to do with a translation from cubic to quartic polynomials. Second, we give a completely explicit example based on techniques from additive combinatorics. Third, we show that the result still holds when we allow for a small additive error. For this, we apply an SDP characterization of Gribling and Laurent (QIP'19) for the completely-bounded approximate degree.

Cite as

Jop Briët and Francisco Escudero Gutiérrez. On Converses to the Polynomial Method. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.TQC.2022.6,
  author =	{Bri\"{e}t, Jop and Escudero Guti\'{e}rrez, Francisco},
  title =	{{On Converses to the Polynomial Method}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{6:1--6:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.6},
  URN =		{urn:nbn:de:0030-drops-165139},
  doi =		{10.4230/LIPIcs.TQC.2022.6},
  annote =	{Keywords: Quantum query complexity, polynomial method, completely bounded polynomials}
}
Document
Quantum Query Algorithms are Completely Bounded Forms

Authors: Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos

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


Abstract
We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Using this characterization, we show that many polynomials of degree at least 4 are far from those coming from quantum query algorithms. Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.

Cite as

Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum Query Algorithms are Completely Bounded Forms. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2018.3,
  author =	{Arunachalam, Srinivasan and Bri\"{e}t, Jop and Palazuelos, Carlos},
  title =	{{Quantum Query Algorithms are Completely Bounded Forms}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{3:1--3:21},
  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.3},
  URN =		{urn:nbn:de:0030-drops-83383},
  doi =		{10.4230/LIPIcs.ITCS.2018.3},
  annote =	{Keywords: Quantum query algorithms, operator space theory, polynomial method, approximate degree.}
}
Document
How Many Quantum Correlations Are Not Local?

Authors: Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva

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


Abstract
We study how generic is the property of nonlocality among the set of quantum correlations for bipartite dichotomic measurements. To do so, we consider the characterization of these quantum correlations as those of the form gamma = ( < u_i , v_j > )_{i,j=1}^n , where the vectors u_i and v_j are in the unit sphere of a real Hilbert space. The important parameters in this description are the number of vectors n and the dimension of the Hilbert space m. Thus, it is natural to study the probability of a quantum correlation being nonlocal as a function of alpha = m/n , where the previous vectors are independent and uniformly distributed in the unit sphere of R^m. In this situation, our main result shows the existence of two completely different regimes: There exists an alpha_0 > 0 such that if alpha leq alpha_0, then gamma is nonlocal with probability tending to 1 as n rightarrow infty. On the other hand, if alpha geq 2 then gamma is local with probability tending to 1 as n rightarrow infty.

Cite as

Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva. How Many Quantum Correlations Are Not Local?. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 39-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{gonzalezguillen_et_al:LIPIcs.TQC.2015.39,
  author =	{Gonz\'{a}lez-Guill\'{e}n, Carlos E. and Jim\'{e}nez, C. Hugo and Palazuelos, Carlos and Villanueva, Ignacio},
  title =	{{How Many Quantum Correlations Are Not Local?}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{39--47},
  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.39},
  URN =		{urn:nbn:de:0030-drops-55475},
  doi =		{10.4230/LIPIcs.TQC.2015.39},
  annote =	{Keywords: nonlocality, quantum correlations, Bell inequalities, random matrices}
}
  • Refine by Author
  • 2 Briët, Jop
  • 2 Palazuelos, Carlos
  • 1 Arunachalam, Srinivasan
  • 1 Escudero Gutiérrez, Francisco
  • 1 González-Guillén, Carlos E.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Functional analysis
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 2 polynomial method
  • 1 Bell inequalities
  • 1 Quantum query algorithms
  • 1 Quantum query complexity
  • 1 approximate degree.
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2015
  • 1 2018
  • 1 2022

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