Quantum circuit design of approximate median filtering with noise tolerance threshold

Quantum median filtering is an important step for many quantum signal processing algorithms. Current quantum median filtering designs show limitations in either computational complexity or incomplete noise detection. We propose a design of quantum median filtering, which uses approximate median filtering with noise tolerance threshold to remove salt-and-pepper noise. Instead of calculating the median, we search an approximate median by sorting four times, which reduces the computational complexity from \(O\left( {21{q^2} + 63q} \right) \) to \(O\left( {12{q^2} + 36q} \right) \). Here, q is the qubit used to represent the gray value. Furthermore, we adopt a two-level threshold to detect the noise points as much as possible. Finally, we design a complete quantum circuit to implement the approximate median filtering. The computational complexity of our proposed circuit is \(O\left( {10{n^2} + 14{q^2}} \right) \) for a NEQR quantum image with a size of \({2^n} \times {2^n}\). The complexity analysis shows that our proposed method significantly speeds up the filtering process compared with the classical filtering methods and the existing quantum filtering methods. In addition, the simulation results prove the proposed approximate median filtering is feasible.