Summary: Based on the NEQR representation of quantum grayscale images and binary images, the optimal LSBs-based quantum watermarking scheme is investigated in this paper, which embeds several binary images (watermark images) into a grayscale image (cover image). The size of the cover image and secret image are both assumed to be \(2^n \times 2^n\). Compared to quantum simple LSBs substitution method generating one stego-pixel, our presented quantum optimal LSBs-based method can generate three stego-pixel simultaneously first. Then one of them with lowest visual distortion is chosen as the final stego-pixel. To this end, first of all, the quantum circuits for a few basic quantum modules (i.e. Quantum Comparator, Parallel CNOT, Parallel Swap, ADDER MOD, Subtracter (SUB.ER) MOD and Absolute Value) are predefined. Following that, based on these simple modules, two composite quantum modules (i.e. the ADDER and SUB.ER MOD \(2^q\) module and Choose final stego-pixel module) are further constructed. With the help of the basic and composite quantum modules, the integrated quantum circuit implementation of the optimal LSBs-based quantum watermark images embedding/extracting procedures are illustrated. Then, the experiment result are simulated under the classical computer software MATLAB 2014(b), which illustrates our presented optimal LSBs-based quantum watermarking methods are superior to the simple LSBs scheme in terms of PSNR and histogram graphs on the basis of visual effect, and the circuit’s complexity analysis also demonstrates our investigated scheme with a very low computational complexity. Finally, we analyze the security of quantum cryptography system, which verifies the quantum watermarking data can be securely transmitted to other legal normal users.