Internal:Quantum Edge Detection

Quantum Hadamard Edge Detection (QHED)

A recent quantum edge detection algorithm called Quantum Hadamard Edge Detection[2] (QHED) provides a promising means of quantum image processing and experimentation. This is done by providing full boundary gradient across a 1D mapping of a 2D image. Due to fidelity issues on NISQ era hardware, we are required to divide our images into sub images (domain decomposition) for proper edge detection[1]. When doing this, we find a boundary error issue with the algorithm. In addition, we utilize a series of optimization techniques found in Ref. [6] to overcome the resultant hardware noise. The hardware limitations and the few issues with the QHED algorithm itself are reduced in order to produce simulated NISQ hardware results on large images.

The overall goal of this project is to produce high quality results via the QHED circuit on large medical images via REAL NISQ era hardware. Classically, we can use space filling curves or pixel buffers to improve results upon the decomposed image. As far as real hardware is concerned, areas of interest to achieve quality results are by implementing major improvements upon the decrement gate which seems to be the failure point. We can tackle this by a combination of efficient mathematics[7], NISQ error mitigation techniques[6], and VQC techniques. The combination of all of these applied to the three major sections of the circuit (ignoring the measurement phase) could very well result in accurate edge detection results on real quantum hardware. Without access to larger number of qubits (>7 qubits) we need to use the topology taken from noisy simulated hardware. The principles of CX error, single gate error, fidelity, and coherence normally found in real hardware are applicable to noisy simulations. Thus, this remains as a quality means of data analysis prior to execution on real hardware.

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. Ref. [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 Ref. [3] (or through Qiskit's StatePreparation), 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:

To the best of our abilities, we find that references to the QHED method provide very little (if any) detail as to the architecture of the decrement gate. Refs. [4] and presumably [5] use a qiskit unitary class function to convert a numpy matrix into a circuit. Although quite useful for simulations, this type of construction fails on real hardware. We can find a far more reasonable design of the gate in Ref. [7] which is shown below.

Multi controlled NOT gates perform the decrement operation. q_0 being the least significant qubit.

Although it is known that multi qubit gates are highly error prone, we achieve reasonable results when we compare the two methodologies. We begin with a 4 qubit circuit initialized to the state |0000> = (1...0) which is to be decremented to state |1111> = (0...1). Shown below are the results of the more careful multi controlled qubit construction and the unitary class function executed on the real quantum device, ibmq_lima.

Although the results are far from perfect, we can clearly see the state 1111> has been formed from the state 0000>.

The results of our gate are lost in the noise of the output using the unitary class function.

We can improve upon the Decrement gate by using 2n total qubits by altering the increment gates in Ref. [??]. More simply, using open controls (bit flip in the case of the qubit being in the state |0>) alters the increment permutation to a decrement.

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. An overview of the QHED algorithm can be visualized as having the following effect on the input of an image state:

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).

Example of 1024x1024 Medical image decomposed into 64x64 sub images. In the domain decomposed images (bottom row) a different space filling curve is used for mapping. A laplacian (far left column) edge detection stenciling is used as a classical analog for comparisons.

QHED in 3 Dimensions

We can apply the same principles to 3D. The main difference is that instead of performing a vertical and horizontal detection we need to add in a third in order to achieve a full boundary about each pixel. We consider a "scan" about the x, y, and z planes.

Example of 3D Medical image to be edge detected.

3D Medical image passed through the QHED algorithm (simulated) 3 times (x,y,z plane). The entire image was passed through each plane.

3D Medical image with decomposed domains. Each sub domain (3D block) passed through the QHED algorithm (simulated) 3 times (x,y,z plane). Each block was mapped using RCMO, edge detected, and pieced back together.

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.

[4] Team, T. Q. (2022, July 6). Quantum Edge Detection - qhed algorithm on small and large images. Quantum Edge Detection - QHED Algorithm on Small and Large Images. Retrieved October 28, 2022, from https://qiskit.org/textbook/ch-applications/quantum-edge-detection.html

[5] Anand, A., Lyu, M., Baweja, P. S., & Patil, V. (2022). Quantum Image Processing. https://doi.org/https://arxiv.org/pdf/2203.01831.pdf

[6] Ferris, K. J., Ramusson, A. J., Bronn, N. T., & Lanes, O. (2022). Quantum Simulation on Noisy Superconducting Quantum Computers. https://doi.org/https://doi.org/10.48550/arXiv.2209.02795

[7] LI, X. I. A. O. Y. U., YANG, G. U. O. W. U., TORRES, C. A. R. L. O. S. M. A. N. U. E. L., ZHENG, D. E. S. H. E. N. G., & WANG, K. A. N. G. L. (2013). A class of efficient quantum incrementer gates for quantum circuit synthesis. International Journal of Modern Physics B, 28(01), 1350191. https://doi.org/10.1142/s0217979213501919

[8] . Gidney, Constructing large increment gates. URL https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html