2026-08-17T08:56:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8338 2024-03-06T10:42:02Z ddc:004 open_access

Quantum Query Algorithms are Completely Bounded Forms Arunachalam, Srinivasan Briët, Jop Palazuelos, Carlos Quantum query algorithms operator space theory polynomial method approximate degree. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Srinivasan Arunachalam and Jop Briët and Carlos Palazuelos 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.3 urn:nbn:de:0030-drops-83383 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode