A quantum convolutional neural network on NISQ devices

Abstract

Quantum machine learning is one of the most promising applications of quantum computing in the noisy intermediate-scale quantum (NISQ) era. We propose a quantum convolutional neural network(QCNN) inspired by convolutional neural networks (CNN), which greatly reduces the computing complexity compared with its classical counterparts, with O((log₂M)⁶) basic gates and O(m²+e) variational parameters, where M is the input data size, m is the filter mask size, and e is the number of parameters in a Hamiltonian. Our model is robust to certain noise for image recognition tasks and the parameters are independent on the input sizes, making it friendly to near-term quantum devices. We demonstrate QCNN with two explicit examples. First, QCNN is applied to image processing, and numerical simulation of three types of spatial filtering, image smoothing, sharpening, and edge detection is performed. Secondly, we demonstrate QCNN in recognizing image, namely, the recognition of handwritten numbers. Compared with previous work, this machine learning model can provide implementable quantum circuits that accurately corresponds to a specific classical convolutional kernel. It provides an efficient avenue to transform CNN to QCNN directly and opens up the prospect of exploiting quantum power to process information in the era of big data.

Introduction

Machine learning has fundamentally transformed the way people think and behave. Convolutional neural network (CNN) is an important machine learning model which has the advantage of utilizing the correlation information of data, with many interesting applications ranging from image recognition to precision medicine.

Quantum information processing (QIP) [1, 2], which exploits quantum-mechanical phenomena such as quantum superpositions and quantum entanglement, allows one to overcome the limitations of classical computation and reaches higher computational speed for certain problems [3–5]. Quantum machine learning, as an interdisciplinary study between machine learning and quantum information, has undergone a flurry of developments in recent years [6–15]. Machine learning algorithm consists of three components: representation, evaluation and optimization, and the quantum version [16–20] usually concentrates on realizing the evaluation part, the fundamental construct in deep learning [21].

A CNN generally consists of three layers, convolution layers, pooling layers, and fully connected layers. The convolution layer calculates new pixel values $x_{\mathit{\text{ij}}}^{\left(\ell \right)}$ from a linear combination of the neighborhood pixels in the preceding map with the specific weights, $x_{i,j}^{\left(\ell \right)}=\sum _{a,b=1}^m{w}_{a,b}{x}_{i+a-2,j+b-2}^{(\ell -1)}$, where the weights w_a,b form a m×m matrix named as a convolution kernel or a filter mask. Pooling layer reduces feature map size, e.g., by taking the average value from four contiguous pixels, and is often followed by application of a nonlinear (activation) function. The fully connected layer computes the final output by a linear combination of all remaining pixels with specific weights determined by parameters in a fully connected layer. The weights in the filter mask and fully connected layer are optimized by training on large datasets.

In this article, we demonstrate the basic framework of a quantum convolutional neural network (QCNN) by sequentially realizing convolution layers, pooling layers, and fully connected layers. Firstly, we implement convolution layers based on linear combination of unitary operators (LCU) [22–24]. Secondly, we abandon some qubits in the quantum circuit to simulate the effect of the classical pooling layer. Finally, the fully connected layer is realized by measuring the expectation value of a parametrized Hamiltonian and then a nonlinear (activation) function to post-process the expectation value. We perform numerical demonstrations with two examples to show the validity of our algorithm. Finally, the computing complexity and trainability of our QCNN model are discussed followed by a summary.

Results

Framework of quantum neural networks

Quantum convolution layer

The first step for performing quantum convolution layer is to encode the image data into a quantum system. In this work, we encode the pixel positions in the computational basis states and the pixel values in the probability amplitudes, forming a pure quantum state (Fig. 1). Given a 2D image F=(F_i,j)_M×L, where F_i,j represents the pixel value at position (i,j) with $i=1,\dots ,M$ and $j=1,\dots ,L$. F is transformed as a vector $\overrightarrow{f}$ with ML elements by putting the first column of F into the first M elements of $\overrightarrow{f}$, the second column the next M elements, etc. That is,

1

$$\begin{array}{l}\overrightarrow{f}={(F_{1,1},F_{2,1},\dots ,F_{M,1},F_{1,2},\dots ,F_{i,j},\dots ,F_{M,L})}^T.\end{array}$$

Fig. 1 [Images not available. See PDF.]

Comparison of classical convolution processing and quantum convolution processing. F and G are the input and output image data, respectively. On the classical computer, a M×M image can be represented as a matrix and encoded with at least 2ⁿ bits [ n=⌈log2(M²)⌉]. The classical image transformation through the convolution layer is performed by matrix computation F∗W, which leads to $x_{i,j}^{\left(\ell \right)}=\sum _{a,b=1}^m{w}_{a,b}{x}_{i+a-2,j+b-2}^{(\ell -1)}$. The same image can be represented as a quantum state and encoded in at least n qubits on a quantum computer. The quantum image transformation is realized by the unitary evolution U on a specific quantum state

Accordingly, the image data $\overrightarrow{f}$ can be mapped onto a pure quantum state $|f⟩=\sum _{k=0}^{2^n-1}{c}_k|k⟩$ with n=⌈log2(ML)⌉ qubits, where the computational basis |k⟩ encodes the position (i,j) of each pixel, and the coefficient c_k encodes the pixel value, i.e., $c_k=F_{i,j}/{\left(\sum \underset{i,j}{\overset{2}{F}}\right)}^{1/2}$ for k<ML and c_k=0 for k≥ML. Here, ${\left(\sum \underset{i,j}{\overset{2}{F}}\right)}^{1/2}$ is a constant factor to normalizing the quantum state.

Without loss of generality, we focus on the input image with M=L=2ⁿ pixels. The convolution layer transforms an input image F=(F_i,j)_M×M into an output image G=(G_i,j)_M×M by a specific filter mask W. In the quantum context, this linear transformation, corresponding to a specific spatial filter operation, can be represented as |g⟩=U|f⟩ with the input image state |f⟩ and the output image state |g⟩. For simplicity, we take a 3×3 filter mask as an example

2

$$W=\left[\begin{array}{ccc}{w}_{11}& w_{12}& w_{13}\\ w_{21}& w_{22}& w_{23}\\ w_{31}& w_{32}& w_{33}\\ \end{array}\right].$$

The generalization to arbitrary m×m filter mask is straightforward. Convolution operation will transform the input image F=(F_i,j)_M×M into the output image as G=(G_i,j)_M×M with the pixel $G_{i,j}=\sum _{u,v=1}^3{w}_{\mathit{\text{uv}}}{F}_{i+u-2,j+v-2}$ (2≤i,j≤M−1). The corresponding quantum evolution U|f⟩ can be performed as follows. We represent input image F=(F_i,j)_M×M as an initial state

3

$$\begin{array}{l}|f⟩=\sum _{k=0}^{M^2-1}{c}_k|k⟩,\end{array}$$

where $c_k=F_{i,j}/{\left(\sum \underset{i,j}{\overset{2}{F}}\right)}^{1/2}$. The M²×M² linear filtering operator U can be defined as [25]:

4

$$U=\left[\begin{array}{c}E\\ V_1& V_2& V_3\\ \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \\ V_1& V_2& V_3\\ E\\ \end{array}\right],$$

where E is an M dimensional identity matrix, and V₁,V₂,V₃ are M×M matrices defined by $$\begin{array}{cc}{V}_1& ={\left(\begin{array}{c}0\\ w_{11}& w_{21}& w_{31}\\ \ddots & \ddots & \ddots \\ w_{11}& w_{21}& w_{31}\\ 0\\ \end{array}\right)}_{M\times M}\end{array}$$

5

$$\begin{array}{cc}{V}_2& ={\left(\begin{array}{c}1\\ w_{12}& w_{22}& w_{32}\\ \ddots & \ddots & \ddots \\ w_{12}& w_{22}& w_{32}\\ 1\\ \end{array}\right)}_{M\times M}\\ V_3& ={\left(\begin{array}{c}0\\ w_{13}& w_{23}& w_{33}\\ \ddots & \ddots & \ddots \\ w_{13}& w_{23}& w_{33}\\ 0\\ \end{array}\right)}_{M\times M}.\end{array}$$

Generally speaking, the linear filtering operator U is non-unitary that can not be performed directly. Actually, we can embed U in a bigger system with an ancillary system and decompose it into a linear combination of four unitary operators [26]. U=U₁+U₂+U₃+U₄, where $U_1=(U+U^{†})/2+i\sqrt{I-{(U+U^{†})}^2/4},U_2=(U+U^{†})/2-i\sqrt{I-{(U+U^{†})}^2/4},U_3=(U-U^{†})/2i+i\sqrt{I+{(U-U^{†})}^2/4}$and $U_4=(U-U^{†})/2i-i\sqrt{I+{(U-U^{†})}^2/4}$. However, the basic gates consumed to perform U_i scale exponentially in the dimensions of quantum systems, making the quantum advantage diminishing. In [25], the efficient decomposition or the gate complexity of U is an open question. However, the gate complexity is the fundamental standard for measuring algorithm efficiency. Therefore, we present a new approach to construct the filter operator to reduce the gate complexity. For convenience, we change the elements of the first row, the last row, the first column, and the last column in the matrix V₁,V₂, and V₃, which is allowable in imagining processing, to the following form

6

$$\begin{array}{cc}{V}_1^{\prime }& ={\left(\begin{array}{ccc}{w}_{21}& w_{31}& w_{11}\\ w_{11}& w_{21}& w_{31}\\ \ddots & \ddots & \ddots \\ w_{11}& w_{21}& w_{31}\\ w_{31}& w_{11}& w_{21}\\ \end{array}\right)}_{M\times M}\\ V_2^{\prime }& ={\left(\begin{array}{ccc}{w}_{22}& w_{32}& w_{12}\\ w_{12}& w_{22}& w_{32}\\ \ddots & \ddots & \ddots \\ w_{12}& w_{22}& w_{32}\\ w_{32}& w_{12}& w_{22}\\ \end{array}\right)}_{M\times M}\\ V_3^{\prime }& ={\left(\begin{array}{ccc}{w}_{23}& w_{33}& w_{13}\\ w_{13}& w_{23}& w_{33}\\ \ddots & \ddots & \ddots \\ w_{13}& w_{23}& w_{33}\\ w_{33}& w_{13}& w_{23}\\ \end{array}\right)}_{M\times M}.\end{array}$$

Defining the adjusted linear filtering operator U^′ as

7

$$U^{\prime }=\left[\begin{array}{ccc}{V}_2^{\prime }& V_3^{\prime }& V_1^{\prime }\\ V_1^{\prime }& V_2^{\prime }& V_3^{\prime }\\ \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \\ V_1^{\prime }& V_2^{\prime }& V_3^{\prime }\\ V_3^{\prime }& V_1^{\prime }& V_2^{\prime }\\ \end{array}\right],$$

Next, we decompose $V_{\mu }^{\prime }(\mu =1,2,3)$ into three unitary matrices without normalization, $V_{\mu }^{\prime }=V_{1\mu }^{\prime }+V_{2\mu }^{\prime }+V_{3\mu }^{\prime }$, where

8

$$\begin{array}{cc}{V}_{1\mu }^{\prime }& ={\left(\begin{array}{c}{w}_{1\mu }\\ w_{1\mu }\\ \ddots & \ddots & \ddots \\ w_{1\mu }\\ w_{1\mu }\\ \end{array}\right)}_{M\times M}\\ V_{2\mu }^{\prime }& ={\left(\begin{array}{c}{w}_{2\mu }\\ w_{2\mu }\\ \ddots & \ddots & \ddots \\ w_{2\mu }\\ w_{2\mu }\\ \end{array}\right)}_{M\times M}\\ V_{3\mu }^{\prime }& ={\left(\begin{array}{c}{w}_{3\mu }\\ w_{3\mu }\\ \ddots \ddots & \ddots \\ w_{3\mu }\\ w_{3\mu }\\ \end{array}\right)}_{M\times M}.\end{array}$$

Thus, the linear filtering operator U^′ can be expressed as

9

$$\begin{array}{l}{U}^{\prime }=\sum _{\mu =1}^3\sum _{v=1}^3\left(V_{\mathrm{\mu \mu }}^{\prime }/w_{\mathrm{\mu \mu }}\right)\otimes V_{\mathrm{v\mu }}^{\prime }.\end{array}$$

which can be simplified to

10

$$\begin{array}{l}{U}^{\prime }=\sum _{k=1}^9{\beta }_k{Q}_k,\end{array}$$

where $Q_k=\left(V_{\mathrm{\mu \mu }}^{\prime }/w_{\mathrm{\mu \mu }}\right)\otimes V_{\mathrm{v\mu }}^{\prime }/w_{\mathrm{v\mu }}$ is unitary, and β_k is a relabelling of the indices.

Now, we can perform U^′ through the linear combination of unitary operators Q_k. The number of unitary operators is equal to the size of filter mask. The quantum circuit to realize U^′ is shown in Fig. 2. The work register |f⟩ and four ancillary qubits |0000⟩_a are entangled together to form a bigger system.

Fig. 2 [Images not available. See PDF.]

Quantum circuit for realizing the QCNN. |f⟩ denotes the initial state of work system after encoded the image data, and the ancillary system is a four qubits system in the |0000⟩_a state. The squares represent unitary operations and the circles represent the state of the controlling system. Unitary operations Q₁,Q₂,⋯,Q₉, are activated only when the auxiliary system is in state |0000⟩,|0001⟩⋯,|1000⟩ respectively

Firstly, we prepare the initial state |f⟩ using amplitude encoding method or quantum random access memory (qRAM). Then, performing unitary matrix S on the ancillary registers to transform |0000⟩_a into a specific superposition state |ψ⟩_a

11

$$\begin{array}{l}S|0000{⟩}_a=|\psi {⟩}_a=\sum _{v=1}^9{\beta }_k/N|k⟩\end{array}$$

where $N_c=\sqrt{\sum _{k=1}^9{\beta }_k^2}$ and S satisfies

12

$$S_{k,1}=\left\{\begin{array}{cc}{\beta }_k/N_c& \text{if}k\le 9\\ 0& \text{if}k>9.\end{array}\right)$$

S is a parameter matrix corresponding to a specific filter mask that realizes a specific task.

Then, we implement a series of ancillary system controlled operations Q_k⊗|k⟩⟨k| on the work system |f⟩ to realize LCU. Nextly, Hadamard gates H^T=H^⊗4 are acted to uncompute the ancillary registers |ψ⟩_a. The state is transformed to

13

$$\begin{array}{l}|g^{\prime }⟩=\sum _{i=1}^{16}\frac{1}{N_c}|i⟩\sum _{k=1}^9{H}_{\left(\mathit{\text{ik}}\right)}^T{S}_{\left(k1\right)}{Q}_k|f⟩,\end{array}$$

where $H_{\left(\mathit{\text{ik}}\right)}^T$ is the ith row and kth column in matrix H^T and S_(k1) is kth row and the first column in matrix S. The first term equals to

14

$$\begin{array}{l}\frac{1}{N_c}|0⟩\sum _{k=1}^9{\beta }_k{Q}_k|f⟩,\end{array}$$

which corresponds to the filter mask W. The ith term equals to filter mask $W^i(i=2,3,\dots ,16)$, where

15

$$W^i=\left[\begin{array}{ccc}{H}_{i1}^T{w}_{11}& H_{i4}^T{w}_{12}& H_{i7}^T{w}_{13}\\ H_{i2}^T{w}_{21}& H_{i5}^T{w}_{22}& H_{i8}^T{w}_{23}\\ H_{i3}^T{w}_{31}& H_{i6}^T{w}_{32}& H_{i9}^T{w}_{33}\\ \end{array}\right].$$

Totally, 16 filter masks are realized, corresponding to ancilla qubits in 16 different state $|i⟩(i=1,2,\dots ,16)$. Therefore, the whole effect of evolution on state |f⟩ without considering the ancilla qubits, is the linear combination of the effects of 16 filter masks.

If we only need one filter mask W, measuring the ancillary register and conditioned on seeing |0000⟩. We have the state $\frac{1}{N_c}|0000⟩U^{\prime }|f⟩$, which is proportional to our expected result state |g⟩. The probability of detecting the ancillary state |0000⟩ is $P_s=\parallel \sum _{k=1}^9{\beta }_k{Q}_k|f⟩{\parallel }^2/N_c^2$.

After obtaining the final result $\frac{1}{N_c}{U}^{\prime }|f⟩$, we can multiply the constant factor N_c to compute |g^′⟩=U^′|f⟩. In conclusion, the filter operator U^′ can be decomposed into a linear combination of nine unitary operators in the case that the general filter mask is W. Only four qubits or a nine energy level ancillary system is consumed to realize the general filter operator U^′, which is independent on the dimensions of image size.

The final stage of our method is to extract useful information from the processed results |g^′⟩. Clearly, the image state |g⟩ is different from |g^′⟩. However, not all elements in |f⟩ are evaluated, the elements corresponding to the four edges of original image remain unchanged. One is only interested in the pixel values which are evaluated by W in |f⟩. These pixel values in |g^′⟩ are as same as that in |g⟩ (see details in Appendix C). So, we can obtain the information of G=(G_i,j)_M×M (2≤i,j≤M−1) by evaluating the |f⟩ under operator U^′ instead of U.

Quantum pooling layer

The function of pooling layer after the convolutional layer is to reduce the spatial size of the representation so as to reduce the amount of parameters. We adopt average pooling which calculates the average value for each patch on the feature map as pooling layers in our model. Consider a 2∗2 pixel pooling operation applied with a stride of 2 pixels. It can be directly realized by ignoring the last qubit and the mth qubit in quantum context. The input image $|g^{\prime }⟩={(g_1,g_2,g_3,g_4,\dots ,\dots ,g_{M^2})}^T$ after this operation can be expressed as the output image

16

$$\begin{array}{cc}|p⟩=& \left(\sqrt{g_1^2+g_2^2+g_{M+1}^2+g_{M+2}^2},\sqrt{g_3^2+g_4^2+g_{M+3}^2+g_{M+4}^2},\dots ,\right)\\ {\left(\sqrt{g_{M^2-M-1}^2+g_{M^2-M}^2+g_{M^2-1}^2+g_M^2}\right)}^T.\end{array}$$

Quantum fully connected layer

Fully connected layers compile the data extracted by previous layers to form the final output; it usually appears at the end of the convolutional neural networks. We define a parametrized Hamiltonian up to a seconder order correlation as the quantum fully connected layer. This Hamiltonian consists of identity operators I and Pauli operators σ_z,

17

$$\begin{array}{l}\mathcal{\mathscr{H}}=h^{0}I+\sum _i{h}^i{\sigma }_z^i+\sum _{i,j}{h}^{\mathit{\text{ij}}}{\sigma }_z^i{\sigma }_z^j\end{array}$$

where h⁰,hⁱ,h^ij are the parameters, and Roman indices i,j denote the qubit on which the operator acts, i.e., ${\sigma }_z^i$ means Pauli matrix σ_z acting on a qubit at site i. We measure the expectation value of the parametrized Hamiltonian $f\left(p\right)=⟨p\left|\mathcal{\mathscr{H}}\right|p⟩$. As shown in [27], the local cost function f(p) is more trainable than global cost function. f(p) is the final output of the whole quantum neural network. Then, we add an active function to nonlinearly map f(p) to R(f(p)).

The parameters in Hamiltonian matrix $\mathcal{\mathscr{H}}$ are updated by gradient descent method, i.e., are calculated by $\frac{\mathrm{\partial f}\left(p\right)}{\partial h^i}=⟨p\left|{\sigma }_z^i\right|p⟩$ and $\frac{\mathrm{\partial f}\left(p\right)}{\partial h^{\mathit{\text{ij}}}}=⟨p\left|{\sigma }_z^i{\sigma }_z^j\right|p⟩$. We rewrite the cost function as

18

$$\begin{array}{cc}f\left(p\right)& =\mathit{\text{Tr}}\left(\frac{1}{N_c^2}\sum _{i=1}^{16}|i⟩\sum _{k=1}^9{H}_{\left(\mathit{\text{ik}}\right)}^T{S}_{\left(k1\right)}{Q}_k|f⟩⟨f|\sum _{i^{\prime }=1}^{16}⟨i^{\prime }|\sum _{k^{\prime }=1}^9{H}_{\left(i^{\prime }{k}^{\prime }\right)}^T{S}_{\left(k^{\prime }1\right)}{Q}_{k^{\prime }}^{†}\mathcal{\mathscr{H}}\right)\\ =\mathit{\text{Tr}}\left(\frac{1}{N_c^2}\sum _{i=1}^{16}\sum _{k=1}^9{H}_{\left(\mathit{\text{ik}}\right)}^T{S}_{\left(k1\right)}{Q}_k{\rho }_i\sum _{k^{\prime }=1}^9{H}_{\left(i{k}^{\prime }\right)}^T{S}_{\left(k^{\prime }1\right)}{Q}_{k^{\prime }}^{†}\mathcal{\mathscr{H}}\right),\end{array}$$

here ρ_i=|f⟩|i⟩⟨i|⟨f|. From Eq.(18), the cost function partial derivative with respect to w_k is $$\begin{array}{c}\frac{\mathrm{\partial f}\left(p\right)}{\partial w_k}=\frac{1}{N_c^2}\mathit{\text{Tr}}\left(\sum _{i=1}^{16}\sum _{k^{\prime }=1}^9{H}_{\left(\mathit{\text{ik}}\right)}^T{H}_{\left(i{k}^{\prime }\right)}^T{S}_{\left(k^{\prime }1\right)}\left(Q_{k^{\prime }}^{†}\mathcal{\mathscr{H}}{Q}_k+Q_k^{†}\mathcal{\mathscr{H}}{Q}_{k^{\prime }}\right){\rho }_i\right).\end{array}$$

Therefore, the parameters can be updated by measuring the expectation values of specific operators.

Now, we have constructed the framework of quantum neural networks. We demonstrate the performance of our method in image processing and handwritten number recognition in the next section.

Numerical simulations

Image processing: edge detection, image smoothing, and sharpening

In addition to constructing QCNN, the quantum convolutional layer can also be used to spatial filtering which is a technique for image processing [25, 28–30], such as image smoothing, sharpening, edge detection, and edge enhancement. To show the quantum convolutional layer can handle various image processing tasks, we demonstrate three types of image processing, edge detection, image smoothing, and sharpening with fixed filter mask W_de,W_sm and W_sh respectively

19

$$\begin{array}{cc}{W}_{\mathit{\text{de}}}& =\left(\begin{array}{ccc}-1& -1& -1\\ -1& 8& -1\\ -1& -1& -1\\ \end{array}\right),W_{\mathit{\text{sm}}}=\frac{1}{13}\left(\begin{array}{ccc}1& 1& 1\\ 1& 5& 1\\ 1& 1& 1\\ \end{array}\right),\\ W_{\mathit{\text{sh}}}& =\frac{1}{16}\left(\begin{array}{ccc}-2& -2& -2\\ -2& 32& -2\\ -2& -2& -2\\ \end{array}\right).\end{array}$$

In a spatial image processing task, we only need one specific filter mask. Therefore, after performing the above quantum convolutional layer mentioned, we measure the ancillary register. If we obtain |0⟩, our algorithm succeeds and the spatial filtering task is completed. The numerical simulation proves that the output images transformed by a classical and quantum convolutional layer are exactly the same, as shown in Fig. 3.

Fig. 3 [Images not available. See PDF.]

Three types of image processing, edge detection, image smoothing, and sharpening, are implemented on an image by classical method and quantum method respectively

Handwritten number recognition

Here, we demonstrate a type of image recognition task on a real-world dataset, called MNIST, a handwritten character dataset. In this case, we simulate a complete quantum convolutional neural network model, including a convolutional layer, a pooling layer, and a full-connected layer, as shown in Fig. 2. We consider the two-class image recognition task(recognizing handwritten characters ^′1^′ and ^′8^′) and ten-class image recognition task(recognizing handwritten characters ^′0^′- ^′9^′). Meanwhile, considering the noise on NISQ quantum system, we respectively simulate two circumstances that are the quantum gate Q_k is a perfect gate or a gate with certain noise. The noise is simulated by randomly acting a single qubit Pauli gate in [I,X,Y,Z] with a probability of 0.01 on the quantum circuit after an operation implemented. In detail, the handwritten character image of MNIST has 28×28 pixels. For convenience, we expand 0 at the edge of the initial image until 32×32 pixels. Thus, the work register of QCNN consists of 10 qubits, and the ancillary register needs 4 qubits. The convolutional layer is characterized by 9 learnable parameters in matrix W that is the same for QCNN and CNN. In QCNN, by abandoning the 4-th and 9-th qubit of the work register, we perform the pooling layer on quantum circuit. In CNN, we perform average pooling layer directly. Through measuring the expected values of different Hamiltonians on the remaining work qubits, we can obtain the measurement values. After putting them in an activation function, we get the final classification result. In CNN, we perform a two-layer fully connected neural network and an activation function. In the two-classification problem, the QCNN’s parametrized Hamiltonian has 37 learnable parameters, and the CNN’s fully-connected layer has 256 learnable parameters. The classification result that is close to 0 are classified as handwritten character ^′1^′, and the result that is close to 1 are classified as handwritten character ^′8^′. In the ten-classification problem, the parametrized Hamiltonian has 10×37 learnable parameters and the CNN’s fully-connected layer has 10×256 learnable parameters. The result is a 10-dimension vector. The classification results are classified as the index of the max element of the vector. Details of parameters, accuracy, and gate complexity are listed in Table 1.

Table 1. The important parameters of models

Models	Problems	Data set	Parameters
			Learnable parameters	Average accuracy	Gate complexity
Noisy QCNN	′1′ or ′8′	Training set	46	0.948	O((log2M)6)
		Test set		0.960
	′0′∼′9′	Training set	379	0.742
		Test set		0.740
Noise-free QCNN	′1′ or ′8′	Training set	46	0.954
		Test set		0.963
	′0′∼′9′	Training set	379	0.756
		Test set		0.743
CNN	′1′ or ′8′	Training set	265	0.962	O(M2)
		Test set		0.972
	′0′∼′9′	Training set	2569	0.802
		Test set		0.804

For the 2 class classification problem, the training set and test set have a total of 5000 images and 2100 images, respectively. For the 10 class classification problem, the training set and test set have a total of 60000 images and 10000 images, respectively. Because in a training process, 100 images are randomly chosen in one epoch, and 50 epochs in total, the accuracy of the training set and the test set will fluctuate. So, we repeatedly execute noisy QCNN, noise-free, and CNN 100 times, under the same construction. In this way, we obtain the average accuracy and the field of accuracy, as shown in Fig. 4. We can conclude that from the numerical simulation result, QCNN and CNN provide similar performance. QCNN involves fewer parameters and has a smaller fluctuation range.

Fig. 4 [Images not available. See PDF.]

The performance of QCNN based on MNIST. The blue, red, and green curves denote the average accuracy of the noisy QCNN, noise-free QCNN, and CNN, respectively. The shadow areas of the corresponding color denote the accuracy fluctuation range in the 100 times simulation results. The insets are the typical images from MNIST set. a, b The curves representing the result from the training set and the test set for the 2 class classification problem respectively. c, d The result from the training set and the test set for the 10 class classification problem respectively

Algorithm complexity and trainability analysis

We analyze the computing resources in gate complexity and qubit consumption. (1) Gate complexity. At the convolutional layer stage, we could prepare an initial state in O(poly(log₂(M²)) steps. In the case of preparing a particular input |f⟩, we employ the amplitude encoding method in [31–33]. It was shown that if the amplitude c_k and $P_k=\sum _k|c_k{|}^2$ can be efficiently calculated by a classical algorithm, constructing the log₂(M²)-qubit X state takes O(poly(log₂(M²)) steps. Alternatively, we can resort to quantum random access memory [34–36]. Quantum random access memory (qRAM) is an efficient method to do state preparation, whose complexity is O(log₂(M²)) after the quantum memory cell established. Moreover, the controlled operations Q_k can be decomposed into O((log₂M)⁶) basic gates (see details in Appendix A). In summary, our algorithm uses O((log₂M)⁶) basic steps to realize the filter progress in the convolutional layer. For CNN, the complexity of implementing a classical convolutional layer is O(M²). Thus, this algorithm achieves an exponential speedup over classical algorithms in gate complexity. The measurement complexity in fully connected layers is O(e), where e is the number of parameters in the Hamiltonian.

(2) Memory consumption. The ancillary qubits in the whole algorithm are O(log₂(m²)), where m is the dimension of the filter mask, and the work qubits are O(log₂(M²)). Thus, the total qubits resource needed is O(log₂(m²)+O(log₂(M²).

According to [27, 37–39], we can analyze the trainability of the parameters in our QCNN model by studying the scaling of the variance

20

$$\mathit{\text{Var}}\left[\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right]=⟨{\left(\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right)}_S^2⟩-{⟨\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}⟩}_S^2,$$

where the expectation value ⟨⋯ ⟩ is taken over the parameters in S [39, 40]. The cost will exhibit a barren plateau in the case the variance is exponentially small, and hence leads to the circuit untrainable. In contrast, large variances (polynomial small) indicate the absence of barren plateaus and that the trainability of the parameters can be guaranteed.

The variance in our model is (see details in Appendix C)

21

$$\begin{array}{lcr}\mathit{\text{Var}}\left[\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right]& =& ⟨{\left(\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right)}_S^2⟩-{⟨\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}⟩}_S^2\\ & =& \frac{1}{N_c^4}\left(\frac{1}{17}\left(2{\alpha }_0^2+\sum _i{\alpha }_i^2+\sum _{\mathit{\text{ij}}}{\alpha }_{\mathit{\text{ij}}}^2\right)-{\alpha }_0^2\right)\end{array}$$

If $\frac{\left(2{\alpha }_0^2+\sum _i{\alpha }_i^2+\sum _{\mathit{\text{ij}}}{\alpha }_{\mathit{\text{ij}}}^2\right)-{\alpha }_0^2}{N_c^4}\in O\left(\mathit{\text{poly}}\right(\mathit{\text{log}}\left(n\right))$, then Var$\left[\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right]\propto O(1/\mathit{\text{poly}}(\mathit{\text{log}}\left(n\right)).$ This assumption is reasonable and easy to be satisfied, because parameters $N_c^4$ in a convolutional kernel which is usually a 3×3 or 5×5 matrix are independent on input image size. This implies that the cost function landscape does not present a barren plateau,and hence that this QCNN architecture is trainable under a convolutional kernel.

Discussion

In summary, we designed a quantum neural network which provides exponential speed-ups over their classical counterparts in gate complexity. With fewer parameters, our model achieves similar performance compared with classical algorithm in handwritten number recognition tasks. Therefore, this algorithm has significant advantages over the classical algorithms for large data. We present two interesting and practical applications, image processing and handwritten number recognition, to demonstrate the validity of our method. The mapping relations between a specific classical convolutional kernel to a quantum circuit is given that provides a bridge between QCNN to CNN. We analyze the trainability and the existence of barren plateaus in our QCNN model. It is a general algorithm and can be implemented on any programmable quantum computer, such as superconducting, trapped ions, and photonic quantum computer. In the big data era, this algorithm has great potential to outperform its classical counterpart, and works as an efficient solution.

Appendix A: Adjusted operator U^′ can provide enough information to remap the output imagine

Proof.- The different elements of image matrix after implementing operator U^′ compared with U are in the edges of image matrix. We prove that the evolution under operator U^′ can provide enough information to remap the output image. The different elements between U^′ and U are included in

22

$$\begin{array}{c}{U}_{k,n}^{\prime }\ne U_{k,n}\left\{\begin{array}{l}(1\le k\le M;1\le n\le 2M,M^2-M\le n\le M^2)\\ (M^2-M\le k\le M^2;1\le n\le M,M^2-3M\le n\le M^2-M)\\ (k=\mathit{\text{sM}}+1;n=1+(s-1)M,2+(s-1)M,\mathit{\text{sM}},\mathit{\text{sM}}\\ +1,\mathit{\text{sM}}+2,(s+1)M,(s+1)M+1,(s+1)M+2,(s+2)M)\\ (k=(s+1)M;n=1,\mathit{\text{sM}}-1,\mathit{\text{sM}},\mathit{\text{sM}}+1,(s+1)M-2,\\ (s+1)M-1,(s+1)M+1,(s+2)M-2,(s+2)M-1)\end{array}\right)\end{array}$$

where 1≤s≤M−2.

After performing U^′ and U on quantum state |f⟩ respectively, the difference exits in the elements $|g_k^{\prime }⟩\ne |g_k⟩(k=1,2,\cdots ,M,\mathit{\text{sM}}+1,(s+1)M,M^2-M+1,\cdots ,M^2)$, where 1≤s≤M−2. Since |g^′⟩ can be remapped to G^′,U^′ will give the output image $G^{\prime }={\left(G_{i,j}^{\prime }\right)}_{M\times M}$. The elements in U^′ which is different from U only affect the pixel i,j∉2,⋯,M−1. Thus, only and if only i,j∉2,⋯,M−1, the matrix elements satisfy $G_{i,j}\ne G_{i,j}^{\prime }$. Namely, the output imagine $G_{i,j}^{\prime }=G_{i,j}$(2≤i,j≤M−1).

Appendix B: Decomposing operator Q into basic gates

Considering the nine operators Q₁,Q₂,⋯,Q₉ consist of filter operator U^′. Q_k is the tensor product of two of the following three operators

23

$$\begin{array}{ccc}{E}_1& ={\left(\begin{array}{l}1\\ 1\\ \ddots & \ddots & \ddots \\ 1\\ 1\\ \end{array}\right)}_{M\times M}{E}_2& ={\left(\begin{array}{l}1\\ 1\\ \ddots & \ddots & \ddots \\ 1\\ 1\\ \end{array}\right)}_{M\times M}\\ E_3& ={\left(\begin{array}{l}1\\ 1\\ \ddots \ddots & \ddots \\ 1\\ 1\\ \end{array}\right)}_{M\times M}.\end{array}$$

E₂ is a M×M identity matrix not need to be further decomposed. For convenient, consider a n-qubits operator E₁ with dimension M×M, where n=log₂(M²). It can be expressed by the combination of O(n³) CNOT gates and Pauli X gates as shown in Fig. 5. Consequently, E₃ can be decomposed into the inverse of combinations of basic gate as shown in Fig. 5, because of the fact $E_3=E_1^{†}$. Thus, Q_k can be implemented by no more than O(n⁶) basic gates. Totally, the controlled Q_k operation can be implemented by no more than O(n⁶)=O((log₂M)⁶)(ignoring constant number).

Fig. 5 [Images not available. See PDF.]

Decomposition of operator E₁ in the form of basic gates

Appendix C: Trainable analysis of the QCNN model

Firstly, we recall the definition of a t-design. Consider a finite set S={S_y}_y∈Y contains |Y| number d-dimensional unitaries S_y. And P_t,t(S) is a polynomial function with degree at most t in the matrix elements of S and at most of degree t in those of S^†. Then, we say that this finite set is a t-design if

24

$$\frac{1}{\left|Y\right|}\sum _{y\in Y}{P}_{t,t}\left(S_y\right)=\int \mathrm{d\mu }\left(S\right)P_{t,t}\left(S\right),$$

where the integral is over U(d) with respect to the Haar distribution. In our QCNN model, S forms a 2-design and for any function F(S), and for any unitary matrix A

25

$$\begin{array}{ll}\int F\left(\mathit{\text{AS}}\right)\mathrm{d\mu }\left(S\right)=& \int F\left(S\right)\mathrm{d\mu }\left(S\right).\end{array}$$

The average of the partial derivative of the cost function is $$\begin{array}{c}{⟨\frac{\mathrm{\partial f}\left(p\right)}{\partial w_k}⟩}_S=\frac{1}{N_c^2}\mathit{\text{Tr}}\left(\sum _{k^{\prime }=1}^9{H}_{\left(\mathit{\text{ik}}\right)}^T{H}_{\left(i{k}^{\prime }\right)}^T{S}_{\left(k^{\prime }1\right)}\left(Q_{k^{\prime }}^{†}\mathcal{\mathscr{H}}{Q}_k+Q_k^{†}\mathcal{\mathscr{H}}{Q}_{k^{\prime }}\right)\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\end{array}$$ and Tr(|f⟩⟨f|)=1. Consider the fact that $\mathcal{\mathscr{H}}$ maintains the property that being constructed by Pauli product matrices under the transformation of Q_k,i.e., $\sum _{k^{\prime }=1}^9{H}_{\left(\mathit{\text{ik}}\right)}^T{H}_{\left(i{k}^{\prime }\right)}^T{S}_{\left(k^{\prime }1\right)}(Q_{k^{\prime }}^{†}\mathcal{\mathscr{H}}{Q}_k+Q_k^{†}\mathcal{\mathscr{H}}{Q}_k)={\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}$, where ${\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}={\alpha }_{0}I+\sum _i{\alpha }_i{\sigma }_z^i+\sum _{i,j}\left({\alpha }_{\mathit{\text{ij}}}\right){\sigma }_z^i{\sigma }_z^j$. Then, we have $\mathit{\text{Tr}}\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)={\alpha }_0$, and $$⟨\frac{\mathrm{\partial f}\left(p\right)}{\partial w_k}⟩=\frac{{\alpha }_0}{N_c^4}.$$

The expectation value of the squares of gradients is $$\begin{array}{cc}{⟨{\left(\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right)}^2⟩}_S=& \int \mathrm{d\mu }\left(S\right)\frac{1}{\underset{c}{\overset{4}{N}}}\mathit{\text{Tr}}\left(\sum _{i=1}^{16}\sum _{k^{\prime }=1}^9\underset{\left(\mathit{\text{ik}}\right)}{\overset{T}{H}}\underset{\left(i{k}^{\prime }\right)}{\overset{T}{H}}{S}_{\left(k^{\prime }1\right)}\left(\underset{k^{\prime }}{\overset{†}{Q}}\mathcal{\mathscr{H}}{Q}_k\right)\right)\\ {\left(\left(+Q_k^{†}\mathcal{\mathscr{H}}{Q}_{k^{\prime }}\right){\rho }_i\right)}^2\\ =& \frac{1}{N_c^4}\frac{1}{16^2-1}\left(\mathit{\text{Tr}}\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\mathit{\text{Tr}}\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\right)\\ \left(+\mathit{\text{Tr}}\left({\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)}^2\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\right)\\ -\frac{1}{N_c^4}\frac{1}{16(16^2-1)}\left(\mathit{\text{Tr}}\left({\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)}^2\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\right)\\ \left(+\mathit{\text{Tr}}\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)\mathit{\text{Tr}}\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)\mathit{\text{Tr}}\left(\right|f⟩⟨f\left|\right)\right)\\ =& \frac{1}{N_c^4}\left(\frac{1}{16^2-1}({\alpha }_0^2+\mathit{\text{Tr}}({\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)}^2\left)\right)-\frac{1}{16(16^2-1)}\right)\\ \left(({\alpha }_0^2+\mathit{\text{Tr}}({\left({\mathcal{\mathscr{H}}}^{\mathit{\text{new}}}\right)}^2\left)\right)\right)\\ =& \frac{1}{N_c^4}\left(\frac{1}{17}(2{\alpha }_0^2+\sum _i{\alpha }_i^2+\sum _{\mathit{\text{ij}}}{\alpha }_{\mathit{\text{ij}}}^2)\right)\end{array}$$

Therefore, the variance is

26

$$\begin{array}{lcr}\mathit{\text{Var}}\left[\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right]& =& ⟨{\left(\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}\right)}_S^2⟩-{⟨\frac{\mathrm{\partial f}\left(p\right)}{\mathrm{\partial w}}⟩}_S^2\\ & =& \frac{1}{N_c^4}\left(\frac{1}{17}(2{\alpha }_0^2+\sum _i{\alpha }_i^2+\sum _{\mathit{\text{ij}}}{\alpha }_{\mathit{\text{ij}}}^2)-{\alpha }_0^2\right)\end{array}$$

Acknowledgements

We thank X. Yao and X. Peng for inspiration and fruitful discussions.

Authors’ contributions

S.W. formulated the theory. Y.C. and Z.Z. performed the calculation. All work was carried out under the supervision of G.L. All authors contributed to writing the manuscript. The authors read and approved the final manuscript.

Funding

This research was supported by National Basic Research Program of China. S.W. acknowledge the China Postdoctoral Science Foundation 2020M670172 and the National Natural Science Foundation of China under Grants No. 12005015. We gratefully acknowledge support from the National Natural Science Foundation of China under Grants No. 11974205 and No. 11774197, The National Key Research and Development Program of China (2017YFA0303700), The Key Research and Development Program of Guangdong province (2018B030325002), and Beijing Advanced Innovation Center for Future Chip (ICFC).

Availability of data and materials

The code used to generate the quantum circuit and implement the experiment is available on reasonable request.

Declarations

Ethics approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Competing interests

The authors declare that they have no competing interests.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1 Benioff, P. The computer as a physical system: a microscopic quantum mechanical hamiltonian model of computers as represented by turing machines. J. Stat. Phys.; 1980; 22, 5 pp. 563-591.1980JSP..22.563BMathSciNet ID: 574722[DOI: https://dx.doi.org/10.1007/BF01011339]

2 Feynman, R. P. Simulating physics with computers. Int. J. Theor. Phys.; 1982; 21, 6 pp. 467-488.MathSciNet ID: 658311[DOI: https://dx.doi.org/10.1007/BF02650179]

3 Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev.; 1999; 41, 2 pp. 303-332.1999SIAMR.41.303SMathSciNet ID: 1684546[DOI: https://dx.doi.org/10.1137/S0036144598347011]

4 Grover, L. K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett.; 1997; 79, 2 325.1997PhRvL.79.325G[DOI: https://dx.doi.org/10.1103/PhysRevLett.79.325]

5 Long, G. L. Grover algorithm with zero theoretical failure rate. Phys. Rev. A; 2001; 022307, 64.

6 Biamonte, J.; Wittek, P.; Pancotti, N.; Rebentrost, P.; Wiebe, N.; Lloyd, S. Quantum machine learning. Nature; 2017; 549, 7671 pp. 195-202.2017Natur.549.195B[DOI: https://dx.doi.org/10.1038/nature23474]

7 Dunjko, V.; Taylor, J. M.; Briegel, H. J. Quantum-enhanced machine learning. Phys. Rev. Lett.; 2016; 117, 13 130501.2016PhRvL.117m0501DMathSciNet ID: 3636529[DOI: https://dx.doi.org/10.1103/PhysRevLett.117.130501]

8 Killoran, N.; Bromley, T. R.; Arrazola, J. M.; Schuld, M.; Quesada, N.; Lloyd, S. Continuous-variable quantum neural networks. Phys. Rev. Res.; 2019; 1, 3 033063. [DOI: https://dx.doi.org/10.1103/PhysRevResearch.1.033063]

9 J. Liu, K. H. Lim, K. L. Wood, W. Huang, C. Guo, H. -L. Huang, Hybrid quantum-classical convolutional neural networks. arXiv preprint arXiv:1911.02998 (2019).

10 Hu, F.; Wang, B. -N.; Wang, N.; Wang, C. Quantum machine learning with d-wave quantum computer. Quantum Eng.; 2019; 1, 2 e12.

11 Farhi, E.; Neven, H. Classification with quantum neural networks on near term processors. Quantum Rev. Lett.; 2020; 1, 2 pp. 10-37686.

12 Huggins, W.; Patil, P.; Mitchell, B.; Whaley, K. B.; Stoudenmire, E. M. Towards quantum machine learning with tensor networks. Quantum Sci. Technol.; 2019; 4, 2 024001.2019QS&T..4b4001H[DOI: https://dx.doi.org/10.1088/2058-9565/aaea94]

13 Yuan, X.; Sun, J.; Liu, J.; Zhao, Q.; Zhou, Y. Quantum simulation with hybrid tensor networks. Phys. Rev. Lett.; 2021; 127, 4 040501.2021PhRvL.127d0501Y[DOI: https://dx.doi.org/10.1103/PhysRevLett.127.040501]

14 Zhang, Y.; Ni, Q. Recent advances in quantum machine learning. Quantum Eng.; 2020; 2, 1 e34.

15 Liu, J. -G.; Mao, L.; Zhang, P.; Wang, L. Solving quantum statistical mechanics with variational autoregressive networks and quantum circuits. Mach. Learn. Sci. Technol.; 2021; 2, 2 025011. [DOI: https://dx.doi.org/10.1088/2632-2153/aba19d]

16 E. Farhi, H. Neven, Classification with quantum neural networks on near term processors. arXiv preprint arXiv:1802.06002 (2018).

17 Cong, I.; Choi, S.; Lukin, M. D. Quantum convolutional neural networks. Nat. Phys.; 2019; 15, 12 pp. 1273-1278. [DOI: https://dx.doi.org/10.1038/s41567-019-0648-8]

18 Britt, B. C. Modeling viral diffusion using quantum computational network simulation. Quantum Eng.; 2020; 2, 1 e29. [DOI: https://dx.doi.org/10.1002/que2.29]

19 Schuld, M.; Killoran, N. Quantum machine learning in feature hilbert spaces. Phys. Rev. Lett.; 2019; 122, 4 040504.2019PhRvL.122d0504S[DOI: https://dx.doi.org/10.1103/PhysRevLett.122.040504]

20 Li, Y.; Zhou, R. -G.; Xu, R.; Luo, J.; Hu, W. A quantum deep convolutional neural network for image recognition. Quantum Sci. Technol.; 2020; 5, 4 044003.2020QS&T..5d4003L[DOI: https://dx.doi.org/10.1088/2058-9565/ab9f93]

21 Goodfellow, I.; Bengio, Y.; Courville, A.; Bengio, Y. Deep learning, volume 1; 2016; Cambridge, MIT press:zbMath ID: 1373.68009

22 Gui-Lu, L. General quantum interference principle and duality computer. Commun. Theor. Phys.; 2006; 45, 5 825.2006CoTPh.45.825LMathSciNet ID: 2286814[DOI: https://dx.doi.org/10.1088/0253-6102/45/5/013]

23 Gudder, S. Mathematical theory of duality quantum computers. Quantum Inf. Process.; 2007; 6, 1 pp. 37-48.MathSciNet ID: 2297228[DOI: https://dx.doi.org/10.1007/s11128-006-0040-3]

24 Wei, S. -J.; Long, G. -L. Duality quantum computer and the efficient quantum simulations. Quantum Inf. Process.; 2016; 15, 3 pp. 1189-1212.2016QuIP..15.1189WMathSciNet ID: 3475789[DOI: https://dx.doi.org/10.1007/s11128-016-1263-6]

25 Yao, X. -W; Wang, H; Liao, Z; Chen, M. -C; Pan, J; Li, J; Zhang, K; Lin, X; Wang, Z; Luo, Z et al. Quantum image processing and its application to edge detection: theory and experiment. Phys. Rev. X; 2017; 7, 3 031041.

26 Xin, T; Wei, S; Cui, J; Xiao, J; Arrazola, I; Lamata, L; Kong, X; Lu, D; Solano, E; Long, G. Quantum algorithm for solving linear differential equations: theory and experiment. Phys. Rev. A; 2020; 101, 3 032307.2020PhRvA.101c2307XMathSciNet ID: 4086394[DOI: https://dx.doi.org/10.1103/PhysRevA.101.032307]

27 Cerezo, M.; Sone, A.; Volkoff, T.; Cincio, L.; Coles, P. J. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nat. Comput.; 2021; 12, 1 pp. 1-12.

28 Yan, F.; Iliyasu, A. M.; Venegas-Andraca, S. E. A survey of quantum image representations. Quantum Inf. Process.; 2016; 15, 1 pp. 1-35.2016QuIP..15..1YMathSciNet ID: 3441389[DOI: https://dx.doi.org/10.1007/s11128-015-1195-6]

29 S. E. Venegas-Andraca, S. Bose, Storing, processing, and retrieving an image using quantum mechanics. Inf. Comput. (2003).

30 Le, P. Q.; Dong, F.; Hirota, K. A flexible representation of quantum images for polynomial preparation, image compression, and processing operations. Quantum Inf. Process.; 2011; 10, 1 pp. 63-84.MathSciNet ID: 2765303[DOI: https://dx.doi.org/10.1007/s11128-010-0177-y]

31 Long, G. -L.; Sun, Y. Efficient scheme for initializing a quantum register with an arbitrary superposed state. Phys. Rev. A; 2001; 64, 1 014303.2001PhRvA.64a4303L[DOI: https://dx.doi.org/10.1103/PhysRevA.64.014303]

32 L. Grover, T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/0208112 (2002).

33 Soklakov, A. N.; Schack, R. Efficient state preparation for a register of quantum bits. Phys. Rev. A; 2006; 73, 1 012307.2006PhRvA.73a2307S[DOI: https://dx.doi.org/10.1103/PhysRevA.73.012307]

34 Giovannetti, V; Lloyd, S; Maccone, L. Quantum random access memory. Phys. Rev. Lett.; 2008; 100, 16 160501.2008PhRvL.100p0501GMathSciNet ID: 2403262[DOI: https://dx.doi.org/10.1103/PhysRevLett.100.160501]

35 Giovannetti, V; Lloyd, S; Maccone, L. Architectures for a quantum random access memory. Phys. Rev. A; 2008; 78, 5 052310.2008PhRvA.78e2310G[DOI: https://dx.doi.org/10.1103/PhysRevA.78.052310]

36 Arunachalam, S; Gheorghiu, V; Jochym-O’Connor, T; Mosca, M; Srinivasan, P. V. On the robustness of bucket brigade quantum ram. New J. Phys.; 2015; 17, 12 123010.2015NJPh..17l3010A[DOI: https://dx.doi.org/10.1088/1367-2630/17/12/123010]

37 McClean, J. R.; Boixo, S.; Smelyanskiy, V. N.; Babbush, R.; Neven, H. Barren plateaus in quantum neural network training landscapes. Nat. Commun.; 2018; 9, 1 pp. 1-6.2018NatCo..9..1M[DOI: https://dx.doi.org/10.1038/s41467-018-07090-4]

38 K. Sharma, M. Cerezo, L. Cincio, P. J. Coles, Trainability of dissipative perceptron-based quantum neural networks. arXiv preprint arXiv:2005.12458 (2020).

39 Pesah, A.; Cerezo, M.; Wang, S.; Volkoff, T.; Sornborger, A. T.; Coles, P. J. Absence of barren plateaus in quantum convolutional neural networks. Phys. Rev. X; 2021; 11, 4 041011.

40 Collins, B.; Śniady, P. Integration with respect to the haar measure on unitary, orthogonal and symplectic group. Commun. Math. Phys.; 2006; 264, 3 pp. 773-795.2006CMaPh.264.773CMathSciNet ID: 2217291[DOI: https://dx.doi.org/10.1007/s00220-006-1554-3]