  We study approximation of embeddings between finite dimensional L_p spaces in
the quantum model of computation. For the quantum query complexity of this
problem matching (up to logarithmic factors) upper and lower bounds are
obtained. The results show that for certain regions of the parameter domain
quantum computation can essentially improve the rate of convergence of
classical deterministic or randomized approximation, while there are other
regions where the best possible rates coincide for all three settings. These
results serve as a crucial building block for analyzing approximation in
function spaces in a subsequent paper.
