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.

, , ,
doi.org/10.4230/LIPIcs.ITCS.2018.3
Leibniz International Proceedings in Informatics, LIPIcs
Quantum and classical data transmission
Innovations in Theoretical Computer Science Conference (ITCS)
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Arunachalam, S., Briët, J., & Palazuelos, C. (2018). Quantum query algorithms are completely bounded forms. In Innovations in Theoretical Computer Science Conference (pp. 3:1–3:21). doi:10.4230/LIPIcs.ITCS.2018.3