  For a given set of input-output pairs of quantum states or observables, we
ask the question whether there exists a physically implementable transformation
that maps each of the inputs to the corresponding output. The physical maps on
quantum states are trace-preserving completely positive maps, but we also
consider variants of these requirements. We generalize the definition of
complete positivity to linear maps defined on arbitrary subspaces, then
formulate this notion as a semidefinite program, and relate it by duality to
approximative extensions of this map. This gives a characterization of the maps
which can be approximated arbitrarily well as the restriction of a map that is
completely positive on the whole algebra, also yielding the familiar extension
theorems on operator spaces. For quantum channel extensions and extensions by
probabilistic operations we obtain semidefinite characterizations, and we also
elucidate the special case of Abelian in- or outputs. Finally, revisiting a
theorem by Alberti and Uhlmann, we provide simpler and more widely applicable
conditions for certain extension problems on qubits, and by using a
semidefinite programming formulation we exhibit counterexamples to seemingly
reasonable but false generalizations of the Alberti-Uhlmann theorem.
