Abstract
Quantum Image Processing has exploded in recent years with dozens of papers trying to take advantage of quantum parallelism in order to offer a better alternative to how current computers are dealing with digital images. The vast majority of these papers define or make use of quantum representations based on very large superposition states spanning as many terms as there are pixels in the image they try to represent. While such a representation may apparently offer an advantage in terms of space (number of qubits used) and speed of processing (due to quantum parallelism), it also harbors a fundamental flaw: only one pixel can be recovered from the quantum representation of the entire image, and even that one is obtained non-deterministically through a measurement operation applied on the superposition state. We investigate in detail this measurement bottleneck problem by looking at the number of copies of the quantum representation that are necessary in order to recover various fractions of the original image. The results clearly show that any potential advantage a quantum representation might bring with respect to a classical one is paid for dearly with the huge amount of resources (space and time) required by a quantum approach to image processing.