RT Journal Article
T1 Quantum Query Algorithms Are Completely Bounded Forms
A1 Srinivasan Arunachalam, 
A1 Jop Briët, 
A1 Palazuelos Cabezón, Carlos
AB 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.
PB Society for Industrial and Applied Mathematics
SN 0097-5397
SN 1095-7111
YR 2019
FD 2019-01
LK https://hdl.handle.net/20.500.14352/95983
UL https://hdl.handle.net/20.500.14352/95983
LA eng
NO 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.
DS Docta Complutense
RD 7 abr 2025