  We show that a certain tensor norm, the completely bounded norm, can be
expressed by a semidefinite program. This tensor norm recently attracted
attention in the field of quantum computing, where it was used by Arunachalam,
Bri\"{e}t and Palazuelos for characterizing the quantum query complexity of
Boolean functions. Combined with their results, we obtain a new
characterization of the quantum query complexity through semidefinite
programming. Using the duality theory of semidefinite programming we obtain a
new type of certificates for large query complexity. We show that our class of
certificates encompasses the linear programming certificates corresponding to
the approximate degree of a Boolean function.
