Our implementation of FRQI for \(4 \times 4\)  images follows the implementation of [1]}, which uses three qubits more than theoretically possible according to [2]}, but is easier to implement. Note, that we do not implement the quantum image compression enhancement proposed along with the FRQI algorithm by [2]}, since it would introduce more computational complexity on the classical side.
For our NEQR implementation we keep the number of qubits closer to that of FRQI, so no ancilla qubits were introduced, which makes the following decomposition significantly harder. We used the mcx gate provided by Qiskit ([4]}) as our \(2n\) -CNOT gates. They have a complexity of \(\mathcal {O}(2^{2n+1})\) , resulting in the total number of gates in the circuit scaling with \(\mathcal {O}(2^{4n})\) . For a specific application of the NEQR encoding, the number of gates in the circuit also depends heavily on the input – a property, which is not immediately obvious from the formula in Sec. REF  alone. E.g., if \(C_{01}^{0}=0\) , i.e. the pixel in position \((0,1)\)  has a value smaller than 128, then \(|C_{01}^{0}\rangle \)  is an identity gate and can therefore be omitted in the circuit. On the other hand, if we encode an image that has pixel value 255 everywhere, which results in the maximum number of gates used and call this worst case gate number \(W(n)\)  as in the following formula, we see that NEQR uses a much larger amount of gates than either of the other two algorithms, but asymptotically scales similarly to FRQI. Explicitly in this case, NEQR requires \(2n\)  Hadamard gates for the positional qubits, \(n2^n\)  NOT gates to construct and deconstruct all on-off combinations of the positional qubits and finally for every pixel eight times \(||\text{X}_{2n}\rangle |\) , which denotes the number of gates needed to form one \(2n\) -CNOT gate.
\(W(n) &= 2n + n2^n + 2^{2n} \cdot 8 ||\text{X}_{2n}\rangle | = 2n + n2^n + 2^{2n} \cdot 8 (3\cdot 2^{2n+1} -5)\\&= 48\cdot 2^{4n} - 40\cdot 2^{2n} + n\cdot 2^{2n+1}\) 
