License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.3
URN: urn:nbn:de:0030-drops-83383
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8338/
Go to the corresponding LIPIcs Volume Portal

Arunachalam, Srinivasan ; Briët, Jop ; Palazuelos, Carlos

Quantum Query Algorithms are Completely Bounded Forms

pdf-format:
LIPIcs-ITCS-2018-3.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{arunachalam_et_al:LIPIcs:2018:8338,
  author =	{Srinivasan Arunachalam and Jop Bri{\"e}t and Carlos Palazuelos},
  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 =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8338},
  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.}
}

Keywords: Quantum query algorithms, operator space theory, polynomial method, approximate degree.
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI