Quantum query algorithms are completely bounded forms

We prove a characterization of t-query quantum algorithms in terms of the unit ball of a space of degree-(2t) 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.

• View at Publisher

Full Text ( Author Manuscript , 331kb )

See Also
inProceedings Quantum query algorithms are completely bounded forms S. Arunachalam (Srinivasan), J. Briët (Jop) and C. Palazuelos (Carlos)
techReport Quantum Query Algorithms are Completely Bounded Forms S. Arunachalam (Srinivasan), J. Briët (Jop) and C. Palazuelos (Carlos)