In Quantum Illumination (QI), a signal beam initially entangled with an idler beam held at the receiver interrogates a target region bathed in thermal background light. The returned beam is measured jointly with the idler in order to determine whether a weakly reflecting target is present. Using tools from quantum information theory, we derive lower bounds on the average error probability of detecting both specular and fading targets and on the mean squared error of estimating the reflectance of a detected target, which are obeyed by any QI transmitter satisfying a signal energy constraint. For bright thermal backgrounds, we show that the QI system using multiple copies of low-brightness two-mode squeezed vacuum states is nearly optimal. More generally, our results place limits on the best possible performance achievable using QI systems at all wavelengths, and at all signal and background noise levels.