Open Access

ARTICLE

# 3-Qubit Circular Quantum Convolution Computation Using the Fourier Transform with Illustrative Examples

1 Department of Electrical and Computer Engineering, The University of Texas at San Antonio, San Antonio, USA

2 Computer Science Department, The College of Staten Island, New York, USA

* Corresponding Author: Artyom M. Grigoryan. Email:

*Journal of Quantum Computing* **2024**, *6*, 1-14. https://doi.org/10.32604/jqc.2023.026981

**Received** 16 October 2023; **Accepted** 14 December 2023; **Issue published** 30 January 2024

## Abstract

In this work, we describe a method of calculation of the 1-D circular quantum convolution of signals represented by 3-qubit superpositions in the computational basis states. The examples of the ideal low pass and high pass filters are described and quantum schemes for the 3-qubit circular convolution are presented. In the proposed method, the 3-qubit Fourier transform is used and one addition qubit, to prepare the quantum superposition for the inverse quantum Fourier transform. It is considered that the discrete Fourier transform of one of the signals is known and calculated in advance and only the quantum Fourier transform of another signal is calculated. The frequency characteristics of many linear time-invariant systems and filters are well known. Therefore, the described method of convolution can be used for these systems in quantum computation.## Keywords

The fast Fourier transform-based convolution is widely used in signal/image processing, data-driven learning, big data vitalization, and deep convolutional neural networks numerous applications [1–5]. Building an efficient quantum convolution algorithm for science and engineering needs is challenging. One solution here might be to use the convolution property, which states that the Fourier transform of a convolution of two signals is the pointwise product of their Fourier transforms under suitable conditions. In quantum computation, the

In this paper, we propose a method of quantum convolution which is described in detail using examples with 3 qubits. Note here that the convolution of length

Quantum computing promises fast solutions to many problems in several areas, including quantum signal/image processing and quantum machine learning [14–16]. In recent decades, many papers have been published with the main goal of extending traditional signal and image processing tasks and operations within quantum computing [17,18]. It is well known that efficient quantum algorithms exist and perform significantly faster than classical computers [19]. The basic concept in the quantum computation is the qubit described by the superposition of states

All computation operations over qubits, or multiqubit superposition of states, are described by unitary matrices. This is a major hurdle in the construction of quantum circuits for many of the traditional operations that are widely used in signal and image processing. They include the convolution and gradient operators. In medical image processing, the method of quantum edge detection was described in [20]. Later, the model of image representation known as the novel enhanced quantum representation (NEQR) has proven to be very suitable for extracting edges with Sobel gradients [21]. We also mention the quantum algorithm for the Kirsch and Prewitt operator-based edge extractions [22,23]. The computation of linear and circular convolution in quantum computation is still the open problem. If the traditional fast method of convoluting two signals is based on the DFT and is reduced to the pointwise multiplication of these transforms, then such multiplication in quantum computing must be performed or at least approximated by unitary transforms. Thus, the circuits for the QFT exist, but cannot be directly applied to calculate the convolution. Our inability to work with the QFT in the traditional way should lead us to develop additional methods and circuits that could solve this difficult problem. We believe that sooner or later this problem will be solved for many cases of the convolution.

In this section, we describe the quantum scheme for the convolution of a signal

Here,

The quantum Fourier transform is described by the following 3-qubit superposition:

Here,

The quantum algorithms for the Fourier transform are known, and the circuit unit element for the 3-qubit QFT can be represented as shown in Fig. 1. Here, for the permutation

We take the amplitudes of the transform in the order

The values of the frequency characteristic

Now, we consider the scheme given in Fig. 2. This scheme is for the state-wise multiplication of two qubits in matrix form,

by using the operation

After normalizing the superposition of qubits, this operation can be written in matrix form as

where the normalized coefficient for this new qubit is

The diagonal matrix

for an angle

The following four matrices are defined:

It is assumed that all numbers

In quantum computation, the matrices on one-qubit operators are unitary. Therefore, we consider the case when the signal

The numbers

by the angles

The scheme of multiplication of the transform

The same diagram as the quantum circuit is shown in Fig. 5. The first two qubits are the control qubits. A bullet in the line indicates that the control qubit is in state

The 3-qubit superposition that corresponds to the multiplication of the Fourier transform by the phase coefficients can be written as

4 Multiplication of the Fourier Transforms

We consider an example of multiplication of 3-qubit Fourier transforms.

Example 1: If the impulse response is

The values of phases are

To get the values

This operation is described by the diagonal matrix

For the above example, the diagonal matrix is

If the frequency characteristic has zeros, then we can consider adding a constant,

The same control bits cannot be used for the multiplication by magnitudes

is the identity transformation. It does not change the qubit, since the amplitudes of the basis states should be normalized. In other words,

We denote the amplitudes of this superposition by

We denote by

This operator can be viewed as the process of preparing the next quantum superposition from

The normalized coefficient is

Thus, D is an operator of transition from one 3-qubit superposition to another. The amplitudes

In quantum computing, this step relates to measurement. In other words, the operator D is the Hermitian operator specifying the measurement in a 3-qubit system in the computational basis,

The superposition

The above circuit of multiplication of the transforms with the measurements in Fig. 8 will be considered as a circuit element shown in Fig. 9.

The complete quantum scheme for calculating the 3-qubit convolution is shown in Fig. 10.

5 Ideal Low-Pass Filter in Example

It should be noted that the operation

and

It is important to note that the operator D is not unitary. It could be added to the set of unitary operators of quantum computing to use the D operator in quantum circuits. The example below shows that it is possible to implement this operator without measurement and therefore solve the problem of quantum convolution at least for simple filters. Such filters are the low-pass, high-pass, and band-pass ideal filters.

Example 2: Consider the following ideal low-pass filter

The impulse response

The discrete Fourier transform of the convolution

Thus, the input of the inverse 3-qubit QFT is the 3-qubit superposition

with the normalized coefficient

and the permutation

The only difficulty is understanding how to implement the quantum gates for the superposition in Eq. (28) after computing the 3-qubit QFT of the signal

with the matrix representation

Let us see how the diagonal operator D can be included in a non-abstract quantum scheme using this example. We add one qubit, qubit number 4, as the zero qubit. In other words, we consider the 4-qubit register, wherein the second part is filled by zeros. This superposition is

Now, we consider a permutation that removes unnecessary information from the first part of the register for further processing. For instance, the permutation

There are many permutations that result in the 16-dimensional vector with the first part equal

One more step is required to perform the 3-qubit quantum Fourier transform on the first part of the 4-qubit register/superposition. For that, the first qubit can be used as the control qubit. The 3-qubit QFT is performed when the first qubit is in the state 0. As a result, we obtain the circuit with the 4-qubit input, to calculate the 3-qubit convolution. This simplified circuit is shown in Fig. 14. The 3-qubit direct QFT and inverse QFT (IQFT) work in this circuit when the first qubit is in the state |0⟩.

If use the 3-qubit inverse QFT (IQFT) when the first qubit is in the state |1⟩, the result will be convolution of the signal with the high-pass filter

We can simplify the circuit for this high-pass filter, as shown in Fig. 15. There is no need to use the phase operator

6 General Case of Convolution with Ideal Filters

We assume that such examples of filtering or quantum convolution over

The 2-qubit convolution scheme can be described by the operations similar to the

In this circuit, the permutation is

Implementing the circular convolution in quantum computers is difficult, but examples of convolution can be found. In this work, the convolution of a 3-qubit signal with another one is considered. The second signal is the impulse response of a linear time-invariant system, whose discrete Fourier transform is known or given. The abstract quantum scheme for the 3-qubit circular convolution is proposed. The examples with the low-pass and high-pass filters are described. The most interesting case is when the impulse response of the system is real. The only difficulty in implementing this algorithm in the general case is the implementation of

Acknowledgement: None.

Funding Statement: The authors received no specific funding for this study.

Author Contributions: The authors confirm contribution to the paper as follows: study conception and design: A. Grigoryan; methodology and data collection: A. Grigoryan; analysis and interpretation of results: A. Grigoryan, S. Agaian; draft manuscript preparation and structuring: A. Grigoryan, S. Agaian. All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials: All data generated or analyzed during this study are included in this published article.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

## References

1. K. Beer et al., “Training deep quantum neural networks,” Nat. Commun., 2020. doi: https://doi.org/10.1038/s41467-020-14454-2. [Google Scholar] [PubMed] [CrossRef]

2. S. Sahoo, A. K. Mandal1, P. K. Samanta, I. Basu, and P. Roy, “A critical overview on quantum computing,” J. Quantum. Comput., vol. 2, no. 4, pp. 181–192, 2020. [Google Scholar]

3. Y. Li, R. Zhou, Q. Xu, and J. Luo, “A quantum deep convolutional neural network for image recognition,” Quantum Sci. Technol., vol. 5, no. 4, 2020. doi: https://doi.org/10.1088/2058-9565/ab9f93. [Google Scholar] [CrossRef]

4. M. Altaisky, N. Kaputkina, and V. Krylov, “Quantum neural networks: Current status and prospects for development,” Phys. Part. Nuclei., vol. 45, pp. 1013–1032, 2014. [Google Scholar]

5. A. M. Grigoryan and S. S. Agaian, “Quaternion quantum image representation: New models,” in Proc. SPIE 11399, Mobile Multimedia/Image Processing, Security, and Applications 2020, 2020, vol. 11399, pp. 6. [Google Scholar]

6. A. M. Grigoryan and S. S. Agaian, “Paired quantum Fourier transform with log2N Hadamard gates,” Quantum Inf. Process., vol. 18, no. 217, pp. 26, 2019. [Google Scholar]

7. H. S. Li, P. Fan, H. Xia, S. Song, and X. He, “The quantum Fourier transform based on quantum vision representation,” Quantum Inf. Process., vol. 17, no. 333, pp. 25, 2018. [Google Scholar]

8. R. Cleve and J. Watrous, “Fast parallel circuits for the quantum Fourier transform,” in Proc. IEEE 41st Annual Symp. on Found. of Comput., Redondo Beach, CA, USA, 2000, pp. 526–536. [Google Scholar]

9. L. R. Perez and J. C. Garcia-Escartin, “Quantum arithmetic with the quantum Fourier transform,” Quantum Inf. Process, vol. 16, pp. 14, 2017. [Google Scholar]

10. A. M. Grigoryan and S. S. Agaian, “1-D convolution circuits in quantum computation,” Int. J. Sci. Eng. Res., vol. 11, no. 8, pp. 5, 2020. [Google Scholar]

11. S. Caraiman and V. I. Manta, “Quantum image filtering in the frequency domain,” Adv. Electr. Comp. Eng., vol. 13, no. 3, pp. 77–84, 2013. [Google Scholar]

12. C. Lomont, “Quantum convolution and quantum correlation are physically impossible,” arXiv: quant-ph/:0309070, 2003. [Google Scholar]

13. A. M. Grigoryan, “Resolution map in quantum computing: Signal representation by periodic patterns,” Quantum Inf. Process, vol. 19, no. 177, pp. 21, 2020. [Google Scholar]

14. S. K. Jeswal1 and S. Chakraverty, “Recent developments and applications in quantum neural network: A review,” Arch. Comput. Methods Eng., vol. 26, no. 3, pp. 15, 2018. [Google Scholar]

15. M. Schuld, I. Sinayskiy, and F. Petruccione, “An introduction to quantum machine learning,” Contemp. Phys., vol. 56, no. 2, pp. 172–185, 2015. [Google Scholar]

16. J. Biamonte et al., “Quantum machine learning,” Nature, vol. 549, no. 7671, pp. 195–202, 2017. doi: https://doi.org/10.1038/nature23474. [Google Scholar] [PubMed] [CrossRef]

17. A. M. Grigoryan and S. S. Agaian, “New look on quantum representation of images: Fourier transform representation,” Quantum Inf. Process, vol. 19, no. 148, pp. 26, 2020. [Google Scholar]

18. F. Yan, A. M. Iliyasu, and S. E. Venegas-Andraca, “A survey of quantum image representations,” Quantum Inf Process, vol. 12, no. 1, pp. 1–35, 2015. [Google Scholar]

19. M. A. Nielsen and I. L. Chuang, “Introduction and overview,” in Quantum Computation and Quantum Information, 10th ed. New York, USA: Cambridge University Press, 2010, pp. 36–42. [Google Scholar]

20. X. Fu, M. Ding, Y. Sun, and S. Chen, “A new quantum edge detection algorithm for medical images,” in Proc. SPIE 7497, MIPPR 2009: Medical Imaging, Parallel Processing of Images, and Optimization Techniques, 2009, vol. 7497, pp. 7. [Google Scholar]

21. R. Chetia, S. M. B. Boruah, and P. P. Sahu, “Quantum image edge detection using improved Sobel mask based on NEQR,” Quantum Inf. Process, vol. 20, no. 21, 2021. [Google Scholar]

22. P. Xu, Z. He, T. Qiu, and H. Ma, “Quantum image processing algorithm using edge extraction based on Kirsch operator,” Opt. Express, vol. 28, no. 9, pp. 12508–12517, 2020. [Google Scholar] [PubMed]

23. R. G. Zhou, H. Yu, Y. Cheng, and F. X. Li, “Quantum image edge extraction based on improved Prewitt operator,” Quantum Inf. Process, vol. 18, no. 9, pp. 261, 2019. [Google Scholar]

24. A. Barenco and, “Elementary gates for quantum computation,” arXiv:quant-ph/9503016v1, 1995. [Google Scholar]

25. J. Kim, J. S. Lee, and S. Lee, “A general method to implement an arbitrary unitary operator in quantum computation,” arXiv:quant-ph/9908052, 2000. [Google Scholar]

## Cite This Article

**APA Style**

*Journal of Quantum Computing*,

*6*

*(1)*, 1-14. https://doi.org/10.32604/jqc.2023.026981

**Vancouver Style**

**IEEE Style**

*J. Quantum Comput.*, vol. 6, no. 1, pp. 1-14. 2024. https://doi.org/10.32604/jqc.2023.026981

This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.