Quantum Query Algorithms are Completely Bounded Forms

Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos

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 approximat…