Internal:Quantum Edge Detection

Quantum Hadamard Edge Detection (QHED)

The Quantum Hadamard Edge Detection (QHED) algorithm presented by [2] is a method of providing full boundary gradient across a 1D mapping of a 2D image. The presented means of achieving this image processing would require a circuit of exponential depth in regards to the number of qubits used for the data encoding portion. This leads to quantum decoherence leaving our output data indistinguishable from noise. Reference [1] describes the D-NISQ model which could be a means to practically apply the QHED algorithm. When decomposing a large image to a series of more manageable sub images we receive errors across the boarders of the sub images. These errors stem from the classically computed preprocessing method (2D to 1D mapping) shown in [2].

QHED Circuit

Figure 1 Generalized qHED Circuit with input vector f and output vector g.

State Prep

Figure 2 Row (left) and Column (right) major ordered mapping.

The image is first mapped as a 2D array to a 1D vector. Reference [2] uses methodology known as row and column major ordering (RCMO). Each pixel is then normalized such that the sum of their squares is equal to 1, a necessary quality of quantum states. Using a module presented by reference [3], we can calculate a quantum circuit which achieves what is known as amplitude encoding. The normalized pixel values of the input vector will be returned as the probability amplitudes of computational basis states. Those computational basis states act as the indexing of the original vector. I.e. if we had a length 64 vector, the 7th element is represented as c_7|000111>. The resultant normalized image state can be written as:

The Hadamard gate in the state prep acts on the Least Significant Bit (LSB) initialized to state |0> which outputs the |+> state. Application of the H-Gate on the LSB has the following tensor product on the input image state:

Decrement

The decrement portion of the quantum algorithm can be represented by the matrix unitary:

With application of that unitary gate to the state prepared vector yields the decrement state:

Permutation

This is the portion of the circuit where the actual edge detection occurs. It can be thought of as a series of identity gates tensored together with an H-Gate in the LSB tensored last. The resultant unitary matrix can be written as:

With application of the resultant decrement vector as:

This is the final output state. Note that if the LSB is in the state |1> we retrieve all of the odd indexed states i.e. |...001> (1), |...011> (3), |...111> (5), ect. These states provide the boundary gradient across the 1D input image.

Domain Decomposition

Consider a 1024x1024 medical image. This comes out to 1,048,576 pixels requiring 20 (2^20) qubits plus 1 ancillary qubit for the QHED algorithm. Additionally, the amplitude encoding process expands exponentially with regards to qubit number. We can divide the image into separate sub images and solve either iteratively or in parallel (multithreading). Each sub image is now considered to be a sub input of the overall problem.

Example of 1024x1024 Medical image decomposed into 256x256 sub images.

Errors begin to occur with the 2D to 1D mapping of subdomains. Consider the row major ordering in figure 1. Elements c_3 and c_4 will provide gradient detection for the output pixel at location 3. This is because the RCMO mappings do not preserve locality at the boarders of multi dimensional arrays. In a full image pass of the algorithm this would hardly be noticeable and leave little error on the output image. It becomes readily apparent in decomposed domains, however:

RCMO 2D to 1D mapping applied prior to the output of QHED (simulated) shown above. RCMO mapping does not preserve locality and thus non neighboring pixels are calculated to have edges between them where no such edges exist.

Space Filling Curves

One way to solve this issue without the addition of extra qubits is to use space filling curves as a means of 2D to 1D mapping. Space filling curves preserve locality in that the final output of the algorithm will provide boundary detection across exclusively neighboring pixels (with the exception of one pixel per domain in certain cases).

References

[1] Acampora, Giovanni, et al. “D-NISQ: A Reference Model for Distributed Noisy Intermediate-Scale Quantum Computers.” Information Fusion, vol. 89, 2023, pp. 16–28., https://doi.org/10.1016/j.inffus.2022.08.003.

[2] .-W. Yao, H. Wang, Z. Liao, M.-C. Chen, J. Pan, J. Li, K. Zhang, X. Lin, Z. Wang, Z. Luo, et al., Quantum image processing and its application to edge detection: Theory and experiment, Physical Review X 7 (3) (2017). doi:10.1103/physrevx.7.031041.

[3]I. F. Araujo, D. K. Park, F. Petruccione, A. J. da Silva, A divide-and-conquer algo- rithm for quantum state preparation, Scientific Reports 11 (1) (2021). doi:10.1038/ s41598-021-85474-1.