2026-06-29T07:27:34Zhttps://docta.ucm.es/rest/oai/request

oai:docta.ucm.es:20.500.14352/959832025-09-18T15:55:22Zcom_20.500.14352_14col_20.500.14352_15

Quantum Query Algorithms Are Completely Bounded Forms Srinivasan Arunachalam Jop Briët Palazuelos Cabezón, Carlos Quantum algorithms Query complexity Polynomial method Multilinear forms Operator space theory Análisis matemático 12 Matemáticas We prove a characterization of query quantum algorithms in terms of the unit ball of a space of degree polynomials. 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. [``Polynomials, Quantum Query Complexity, and Grothendieck's Inequality,” in Proceedings of the 31st Conference on Computational Complexity, CCC 2016, Schloss Dagstuh, 2016, pp. 25:1--25:19]. Our proof is based on a fundamental result of Christensen and Sinclair [J. Funct. Anal., 72 (1987), pp. 151-181] that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. 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. Depto. de Análisis Matemático y Matemática Aplicada Fac. de Ciencias Matemáticas TRUE pub 2024-01-29T12:06:32Z 2024-01-29T12:06:32Z 2019 journal article https://hdl.handle.net/20.500.14352/95983 0097-5397 10.1137/18m117563x eng Arunachalam, S.; Briët, J.; Palazuelos, C. Quantum Query Algorithms Are Completely Bounded Forms. SIAM Journal on Computing 2019, 48(3), 903–925. doi:10.1137/18M117563X. open access application/pdf Society for Industrial and Applied Mathematics