Quantum Lower Bounds by Entropy Numbers
arXiv:quant-ph/0611294
Abstract
We use entropy numbers in combination with the polynomial method to derive a new general lower bound for the n-th minimal error in the quantum setting of information-based complexity. As an application, we improve some lower bounds on quantum approximation of embeddings between finite dimensional L_p spaces and of Sobolev embeddings.
Submitted to J. Complexity