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.

Code

Download the Decrement and image encoding notebooks here [1]

Paper

Find the current version of paper here[2]

Quantum Fidelity

For most of this research project we have been using a fidelity metric from Ref. [3]. This metric is a simple function dependent on the number of single qubit gates, CNOT gates, and their respective average error rates for some particular circuit on a pre specified backend. This is, in my opinion, analogous to a performance metric from the standpoint of an engineer (say miles per gallon on a car). The calculation itself yields a somewhat confusing unit of measurement (MPG is a cross sectional unit of area!). The metric of MPG still gives you insight into efficiency and performance. However, the results of MPG will depend entirely on the driver and the conditions that the vehicle is subject to. I believe that IBM did do a good job with this as it gives (seemingly) a predictable insight into the efficiency and performance of a circuit on some given hardware. If we want the real observed fidelity through sampling the circuit we are required to "drive" and test our circuit.

Fidelity in itself is not a strict metric. Rather, it is an abstract computation which can be used to predict the probability that one quantum state can pass as another [4]. Allegedly, Jozsa points out in the publication found here [5] that an overlap of pure quantum states on the geometry of hilbert space can easily be defined as:

|<ψ|χ>|

Which will be 1 where |χ> = |ψ> and 0 if they are perfectly orthogonal. This can be visualized as a simple overlap of two quantum states and the result is exactly how much they overlap. Since the QHED circuit produces pure quantum states we consider this as a fidelity option to calculate. Noisy circuits will yield (at the time of each individual measurement) a pure quantum state. However, the sum of those pure states will produce a density matrix which is most probably not pure. With that being said, Jozsa had produced a fidelity metric for one pure state (ideal) and one mixed state (noisy). Given two density operators where one is pure and the other mixed:

F(ρ,σ) = (tr √ (√ρ σ √ρ))²

There are other definitions for fidelity in the case of mixed states developed by Jozsa[6], Nielsen[7], and several others [8]. A more robust technique is called Quantum Tomography [9]. This, I believe, falls out of the scope of QHED. QHED relies only on the output state of the circuit in the computational (Z) basis, therefore I believe that Josza's trace definition should suffice.

In short, the Qiskit definition of fidelity in their paper is not wrong, but rather incomplete in my opinion. There is no strict definition for fidelity. Rather, fidelity is used to give insight to the closeness between states in quantum information theory. The IBM paper predicts the "overlap" while Josza's metric requires sampling to determine fidelity through experimentation. I think that redefining this metric for ourselves within the scope of Jozsa's definition allows for a more robust representation of what we have actually accomplished with these optimizations since we are comparing the ideal output directly to the actual result.

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. Based on the results, we know that we must design our own decrement gates and cannot rely on any arbitrary unitary transformation algorithim.

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. [8]. 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.

Looking at the CX counts and fidelity estimates for QHED circuits show promising results. The upcoming section "Methods of Optimization" will describe the optimizations themselves as they are labeled in the charts below.

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:

Methods of Optimization

The improved decrement gate was already discussed in the previous section so we will leave it there.

We then utilize Qiskit's transpiler. The optimal SWAP mapping is an NP-Hard problem which yields ambiguous results. "The choice of initial layout can mean the difference between getting a result, and getting nothing but noise." To compute the best low noise layout, we use an open source module called mapomatic. Mapomatic finds the best low noise sub-graph for some given hardware backend(s). The end result is that the module returns the best set of qubits and their appropriate ordering to execute your circuit with minimal noise. This qubit layout is sent to the transpiler. A heuristic fidelity estimate is taken from Ref. [6].

We now turn to a means of error reduction in the measurement output of the circuit. Researchers are able to perform a variety of experiments to measure a qubit's state preparation and measurement (SPAM) errors forming a relationship of noisy probabilities to ideal probabilities in the form of a matrix transformation. The correction matrix can be measured by using a variety of circuits with known outcomes and finding the noisy outcome of every possible bit-string for a particular piece of hardware. From this, it is possible to reconstruct our desired output.

There are obvious scaling issues when it comes to building 2^n x 2^n matricies. There are alternatives to this which do not require such scaling or computational overhead. We make use of such a module called mthree. An excellent demonstration of this can be found in the Qiskit Textbook.

In the case of large images, we must perform domain decomposition to preserve fidelity and reduce noise. However, we find that when applying the suggested RMO and CMO indexed 2D to 1D mapping on decomposed sub images there is a non negligible quality reduction to the output edge detected image. This is due to the fact that this use of mapping does not preserve locality. It can be seen from Fig. [2] how these methods of indexing will provide errors across the boundaries of the image/sub images. Consider the output state |g>. It can be seen how non adjacent pixels of the original image will be compared with each other e.g. c_{3} - c_{4} in the Fig. [2] RMO mapping or c_{12} - c_{1} in the CMO mapping. This may lead to detected edges where there are none. To avoid these discrepancies we apply buffer cells to our decomposed images. We choose to do a row by row decomposition for the horizontal scan as shown below. This leaves 2 redundant pixels per sub image, no matter the decomposition size.

Buffer pixels of value 0 are applied to the boundary of the overall image.

Further decomposition is then possible by adding neighboring pixels to be used as a buffer due to QHED error. The red cells are ultimately disposed in the final output.

With the decrement gate optimization, the more NISQ-era friendly QHED circuit takes the form shown below.

QHED circuit with expanded, noise mitigated, decrement gate

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