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. (CCC’16). 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. 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.

Additional Metadata
Series arXiv.org e-Print archive
Project Networks , Quantum and classical data transmission
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/639.071.409 - Quantum and classical data transmission, This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/024.002.003 - Networks
Citation
Arunachalam, S, Briët, J, & Palazuelos, C. (2017). Quantum Query Algorithms are Completely Bounded Forms. arXiv.org e-Print archive.