Quantum query complexity of state conversion

Understand

State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input.

• We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm.
• The complexity of converting between two systems of states is given by the distance between them, as measured by this norm.
• In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function.