Complexity of pixel detection in quantum images

In this paper Identification of Desired Pixels in an Image Using Grover's Quantum Search Algorithm it is stated in the abstract that "[...]As has been observed in complexity analysis, Grover's unstructured search has the $$O(2^n)$$ while as for classical schemes $$O(2^{2n+2m})$$, where $$m$$ and $$n$$ denote the dimensions of the image."

Their goal is to apply Grover's algorithm in order to find the desired pixel (darkest ones below certain threshold). This could be useful for detecting data hiding in steganography.They use NEQR for image encoding.

What I don't undestand is the complexity $$O$$ for the classical scheme. Why is it $$2^{2n+2m}$$ against $$2^{n}$$ in the quantum case?

Any suggestions?

EDIT Here is the circuit for the following list of elements (it is not the implementation of a grayscale image, is just a reduced example): according to NEQR notation, the first two qubits represent the index of four elements, i.e. 00, 01, 10 and 11, whilst the others the encoding of the value, in this case 1,2,5 and 7 {00001,01010,10101,11111}. The threshold is all numbers less than 5, that is the oracle marks the numbers 00001 and 01010. The diffuser is the standard one that can be found anywhere on the web. Of course in the case of four pixel of a grayscale images we would need 8 (for intensity) + 2 (for position) qubits.

I don't understand how to read Quirk measurements, if I run the circuit on Qiskit I get the following results: {'11': 20, '00': 468, '10': 487, '01': 25} over 1000 shots, that is '00' and '10' are the position of the elements below my threshold, so I think it's working.

Their claim that the processing time is $$2^n$$ instead of $$2^{2n} \times 2^{2m}$$ for an $$n \times m$$ image is simply wrong. (A red flag is how it isn't justified or cited, just stated with an appeal to "as has been observed in complexity analysis".)

The correct numbers would be $$O(\sqrt{nm})$$ quantum pixel queries vs $$O(nm)$$ classical pixel queries. Also, keep in mind that if the image starts as classical data, then the quantum cost includes $$O(nm)$$ classical pixel queries to prepare the representation.

Also, I'm pretty sure you can't just apply Grover's algorithm to the "NEQR" representation they describe and have it do the right thing. I'm very skeptical of the results they show for that, but I can't tell you for sure because they don't actually specify exactly the circuit they are running or provide source code.

In my experience, this kind of sloppiness is typical of papers with "quantum image processing" in the title. I've just stopped reading them; they're consistently a waste of time. There is a similar thing that happens in cryptography: "image encryption" isn't fundamentally different from just encryption, so a paper focusing on "image encryption" is strong signal that it's bad.

For actually cool image processing results, you go to places that focus on image/video processing such as SIGGRAPH. Actually, SIGGRAPH is the only place where I saw a quantum image processing paper I liked: "Quantum Supersampling" by Eric R. Johnston. In their talk they even demonstrate a clear understanding of how costly this would be, placing it in far-future quantum-computers-are-cheap land.

• Thank you for your answer, Craig! I had some doubts too about the complexity being wrong. As for the application of Grover's algorithm, I think it can be possible to apply it to the NEQR representation, as the image is just being encoded in $n$ qubits of the circuit, thus applying the oracle and the diffuse on those states can give you the answer one is looking for. I will have a look at the paper you linked! Feb 29 at 14:55
• @aghin00 Grover's algorithm requires your initial state to match the diffusion step that you are doing. A NEQR state would require a NEQR diffuser, which would be more complex than the usual one in a way that would likely defeat the speedup. The paper never talks abut this, which is the source of my suspicion. Feb 29 at 17:26
• I've tried their implementation, by putting all qubits needed for the representation of the image in superposition (NEQR required only the index qubits to be in superposition), like they did in their last figure, and then applied the oracle and the general diffuser on all qubits. Actually, the results I've got seems pretty good: I used only 5 qubits for the sake of example, and I wanted to get two states that were below a certain threshold implemented by the oracle. Over all 4 possible states, I get the desired two with equal and high probability with respect to the others. I don't know Feb 29 at 17:41
• @aghin00 Can you put your circuit into quirk algassert.com/quirk and link it in your question? I want to see it working. Feb 29 at 20:06
• I edited the question with the quirk circuit. As I mention there, I don't know to use quirk so it was just for a bettere explanation. I actually use Qiskit and I get the results I mentioned. I'm waiting for you to come back at it! Feb 29 at 20:40