Quantum Algorithms for Deep Convolutional Neural Networks
Authors: Iordanis Kerenidis
Jonas Landman
Anupam Prakash
Venue:  (2020)
Keywords: quantum computing
quantum machine learning
convolutional neural network
theory
algorithm

Abstract: Quantum computing is a powerful computational paradigm with applications in several fields, including machine learning. In the last decade, deep learning, and in particular Convolutional Neural Networks (CNN), have become essential for applications in signal processing and image recognition. Quantum deep learning, however, remains a challenging problem, as it is difficult to implement non linearities with quantum unitaries. In this paper we propose a quantum algorithm for evaluating and training deep convolutional neural networks with potential speedups over classical CNNs for both the forward and backward passes. The quantum CNN (QCNN) reproduces completely the outputs of the classical CNN and allows for non linearities and pooling operations. The QCNN is in particular interesting for deep networks and could allow new frontiers in the image recognition domain, by allowing for many more convolution kernels, larger kernels, high dimensional inputs and high depth input channels. We also present numerical simulations for the classification of the MNIST dataset to provide practical evidence for the efficiency of the QCNN.

Published as a conference paper at ICLR 2020
QUANTUM ALGORITHMS FOR DEEP CONVOLUTIONAL NEURAL NETWORK
Iordanis Kerenidis, Jonas Landman & Anupam Prakash Institut de Recherche en Informatique Fondamentale (IRIF) Université de Paris, CNRS
Paris, France landman comman@irifff
ABSTRACT
Quantum computing is a powerful computational paradigm with applications in several fields, including machine learning. In the last decade, deep learning, and in particular Convolutional Neural Networks (CNN), have become essential for applications in signal processing and image recognition. Quantum deep learning, however, remains a challenging problem, as it is difficult to implement non lin- earities with quantum unitaries (Schuld et al. (2014). In this paper we propose a quantum algorithm for evaluating and training deep convolutional neural networks with potential speedups over classical CNNs for both the forward and backward passes. The quantum CNN (QCNN) reproduces completely the outputs of the classical CNN and allows for non linearities and pooling operations. The QCNN is in particular interesting for deep networks and could allow new frontiers in the image recognition domain, by allowing for many more convolution kernels, larger kernels, high dimensional inputs and high depth input channels. We also present numerical simulations for the classification of the MNIST dataset provide prac- tical evidence for the efficiency of the QCNN.
INTRODUCTION
The growing importance of deep learning in research, in industry and in our society will require extreme computational power as the dataset sizes and the complexity of these algorithms is expected to increase. Quantum computers are good candidate to answer this challenge. The recent progress in the physical realization of quantum processors and the advances in quantum algorithms increases the importance of understanding their capabilities and limitations. In particular, the field of quantum machine learning has witnessed many innovative algorithms that offer speedups over their classical ( (2013 2014); Kerenidis & Prakash (201bb) 7b); Wiebel
counterparts Kerenidis et al. (2019) Lloyd et al.
al. 201
Quantum deep learning refers to the problem of creating quantum circuits that mimic and enhance the operations of neural networks. It has been studied in several works works/Allcock et al.) (2018): Reben- trost et al. (0118); Wiebe et al. (2014b) but remains challenging as it is difficult to implement non linearities with quantum unitaries Schuld al. (2014). In this work we propose quantum algorithm for convolutional neural networks (CNN), a type of deep learning designed for visual recognition, signal processing and time series. We also provide results of numerical simulations to evaluate the running time and accuracy of the quantum convolutional neural network (QCNN). Note that our algorithm is theoretical and could compiled on any type of quantum computers (trapped ions, superconducting qubits, cold atoms, photons, etc.)
The CNN was originally developed by LeCun et al. 1998) in the 1980's. They have achieved great practical success over the last decade Krizhevsky et al. (2012) and have been used in cutting-edge domains like autonomous cars Bojarski et al. (2016) and gravitational wave detection George & Huertal (2018). Despite these successes, CNNs suffer from computational bottlenecks due to the size of the optimization space and the complexity of the inner operations, these bottlenecks make deep CNNs resource expensive.

---

Published as a conference paper at ICLR 2020
The growing interest in quantum machine learning has led researchers to develop different variants of Quantum Neural Networks (QNN). The quest for designing quantum analogs of neural networks is challenging due to the modular layer architecture of the neural networks and the presence of non linearities, pooling, and other non unitary operations, as explained in [Schuld et al. (2014). Several strategies have been tried in order to implement some features of neural networks Alleock et al. 22118: Wiebe et al. (2014b); Beer et al. (2019) in the quantum setting.
Variational quantum circuits provide another path the design of QNNs, this approach has been developed in Farhi & Neven (2018); Henderson et al. (2019); Killoran et al. (2018). A quantum con- volutional neural network architecture using variational circuits was recently proposed [ong et al. (2188). However further work is required to provide evidence that such techniques can outperform classical neural networks in machine learning settings.
2
PRELIMINARIES
2.1 CONVOLUTION PRODUCT AS MATRIX MULTIPLICATION
We briefly introduce the formalism and notation concerning classical convolution product and its
equivalence with matrix multiplication. More details can be found in Appendix (Section C). A
single layer l of the classical CNN does the following operations: from an input image X E HH''xx>> seen as a 3D tensor, and kernel Kt E x DD
seen 4D tensor, it
performs convolution product and outputs X = X K with X E B x xD
This convolution operation equivalent to the matrix multiplication A pt y where A p and y are suitably vectorized versions of X K and X x-1 respectively. The output of the layer of the CNN is f(x++) ++1) where ff a non linear function.
2.2 QUANTUM COMPUTING
For detailed introduction to quantum computing and its applications to machine learning in the context of this work, we invite the reader to look at Appendix F We also refer to Nielsen & Chuang 2002b) for
complete overview of quantum computing.
In this part we will discuss only briefly the core notions of quantum computing. Like a classical bit, quantum bit (qubit) can be (0). (1), but can also be in superposition state a (0) [1) with amplitudes (a, 3) E C such that |a|2 + 1 = 1. With n qubits it is then possible to construct superposition of the 2n binary combinations possible, each with specific amplitude. We will note the jth combination (c.g. 101... 110)) as (i). A vector v E Rd can be encoded in quantum quantum superposition, where the components (e1,". ... 1 (da) of v are used as the amplitudes of the d binary combinations. We note this state (0) = |+ll Eie( Us (i), where (i) is a register representing the ith vector in the standard basis.
state made of [log(d)] qubits. This encoding
Quantum computation proceeds by applying quantum gates which are defined to be unitary matrices acting on 1 or 2 qubits, for example the Hadamard gate that maps (0) + } (10) + [1)) and [1) + V2
/2 (10) - (1)). The output of the computation is a quantum state that can be measured to obtain classical information. The measurement of a qubit [0) + [1) yields either or 1, with probability equal to the square of the respective amplitude. A detailed discussion of the results from quantum machine learning and linear algebra used in this work can be found in Appendix (Section
3 MAIN RESULTS
In this paper, we design a quantum convolutional neural network (QCNN) algorithm with a modular architecture that allows for any number of layers, any number and size of kernels, and that can support a large variety of non linearity and pooling methods. Our main technical contributions include new notion of quantum convolution product, the development of quantum sampling technique well suited for information recovery in the context of CNNs and a proposal for a quantum backpropagation algorithm for efficient training of the QCNN.
2

---

Published as a conference paper at ICLR 2020
The QCNN can be directly compared to the classical CNN it has the same inputs and outputs. We show that it offers a speedup compared to certain cases of classical CNN for both the forward pass and for training using backpropagation. For each layer, the forward pass (Algorithm [ the speedup is exponential in the size of the layer (number of kernels) and almost quadratic on the spatial dimension of the input. We next state informally the speedup for the forward pass, the formal version appears as Theorem D.I
Result 1 (Quantum Convolution Layer)
Let X be the input and K' be the kernel for layer i of convolutional neural network, and f [0, C| with C be a non linear function so that f (X++1)= == f(x * K*) is the output for layer &. Given X and Kt stored in QRAM (Quantum Random Access Memory), there is quantum
algorithm that, for precision parameters
0 and 1j > 0, creates quantum state If(X }) such S 2E and retrieves classical tensor xe+1 such that for each pixel j.
f+1
that [(xx*t)) 2+
f(x+11)
xc
| 1(x x =0
S 2e is J(X
2
(I)
if J(X;
<1
The running time of the algorithm is Ō age value, Ô hides factors poly-logarithmic in the size of X and K2 and the parameter M maxp.1 |Apll | F is the maximum product of norms from subregions of X and Kt.
MVC VELI(X!T)
where E(-) represents the aver-
eqp
We that the number of elements in the input and the kernels appear only with poly-logarithmic contribution in the running time. This is one of the main advantages of our algorithm and allows us use for larger and even exponentially deeper kernels. For the number of elements in the input, their number is hidden in the precision parameter 17 in the running time. Indeed, a sufficiently large fraction of pixels must be sampled from the output of the quantum convolution to retrieve the meaningful information. In the Numerical Simulations (Section 6 we provide empirical estimates for 1). For details about the QRAM, see Appendix F22
Following the forward pass, loss function C is computed for the output of a classical CNN. The backpropagation algorithm then used to calculate, layer by layer, the gradient of this loss with respect to the elements of the kernels K in order to update them through gradient descent. We state our quantum backpropagation algorithm next, the formal version of this result appears as Theorem
E
Result 2 (Quantum Backpropagation for Quantum CNN)
Given the forward pass quantum algorithm in Result 7 and given the kernel matrix F*, input matrices A and Yf, stored in the QRAM for each layer t, and a loss function L. there is a quantum within additive BC l, and updates Fe according to a gradient descent update rule. The running time of single layer E for quantum backpropagation is given by
backpropagation algorithu that estimates each element of the gradient tensor Df
OFT
error 8
DFT
o (((u(A))+
Oc 16
OC OF
OC (O + U(F2) x<
Oc (yre)
log 1/8
TY
(2)
82
where for a matrix V E Raxn, R(V) is the condition number and μ(V) S vn is matrix dependent parameter defined in Equation (
For the quantum back propppropagation algorithm, we introduce a quantum tomography algorithm with to norm guarantees, that could be independent interest. is exponentially faster than tomog- raphy with le norm guarantees and is given as Theorem G. in Section G Numerical simulations on classifying the MNIST dataset show that our quantum CNN achieves a similar classification accuracy as the classical CNN.
4 FORWARD PASS FOR QCNN
The forward pass algorithm for the QCNN implements the quantum analog of single quantum convolutional layer. It includes convolution product between input and kernel, followed by
3

---

Published as a conference paper at ICLR 2020
the application of non linear function and pooling operations to prepare the next layer's input. We provide an overview of the main ideas of the algorithm here, the complete technical details are given in the Appendix (Section
Algorithm QCNN Layer
Require: Matrix A representing input to layer and kernel matrix F stored in QRAM. Precision parameters and 77, boolean circuit for non linear function f R [0, Cj.
Ensure: Outputs the data matrix A for the next layer which is the result the convolution between the input and the kernel, followed by non linearity and pooling.
1: Step 1: Quantum Convolution
1.1: Inner product estimation
Perform the following mapping, using QRAM queries on rows AG. and columns F fol- lowed by quantum inner product estimation (Theorems F22 and to implement the mapping
R Ep.g (p) ()) + x Ep. (p) lq) (Ppg) 19p4)
Where P'g is e-close to P'g- L+AAEE)) == = De+1 is normalisation factor
and (pp/ some garbage quantum state that can be ignored.
1.2: Non linearity
Use an arithmetic circuit and two QRAM queries to obtain y*+1 an e-approximation of the convolution output Y = (Ag. Ft) and apply the non linear function f as boolean circuit to obtain T2 Ep (p) lq) ( )} (pp))-
2: Step 2: Quantum Sampling
f0 ++
Use Conditional Rotation and Amplitude Amplification to encode the values a'y
into the amplitudes to obtain K Epn "by (p) (4) ( pq }} 19pa)- Perform fo tomography from Theorem G.1 with precision 17, and obtain classically all positions and values (p, q, ((((+)) ") such that, with high probability, values above v are known exactly, while others are set to
3: Step 3: QRAM Update and Pooling
Update the QRAM for the next layer A while sampling. The implementation of pooling (Max, Average, etc.) can be done by specific update to the QRAM data structure described in Section D.2.2
In this algorithm, we propose the first quantum algorithm for performing the convolution product. Our algorithm is based on the observation that the convolution product can be regarded as ma- trix product between reshaped matrices. The reshaped input's rows 46, and the reshaped kernel's columns F 9 are loaded as quantum states, in superposition. Then the entries of the convolution FAg are estimated using a simple quantum circuit for inner product estimation and stored in an auxiliary register in Step 1.1 of Algorithm
One of the difficulties in the design of quantum neural networks is that non linear functions are hard implement unitary operations. We get around this difficulty by applying the non-linear function f as a boolean circuit to the output of the quantum inner product estimation circuit in Step 1.2 of Algorithm[] T Most of the non linear functions in the machine learning literature can be implemented using small sized boolean circuits, our algorithm thus allows for many possible choices of the non- linear function f (see Appendix F.I for details on non linear boolean circuits in quantum circuits).
Step 2 of Algorithm I develops a quantum importance sampling procedure wherein the pixels with high values of (V pq are read out with higher probability. This is done by encoding these values into the amplitudes of the quantum state using the well known Amplitude Amplification algorithm Brassard et al.] (2002). This kind of importance sampling is a task that can be performed easily in the quantum setting and has no direct classical analog. Although it does not lead to asymptotic improvements for the algorithms running time, it could lead to improvements that are significant in practice.
More precisely, during the measurement of a quantum register in superposition, only one of its values appears, with probability corresponding the the square of its amplitude. It implies that the
4

---

With the modified values of ay use quantum linear algebra algorithm (Theorem F.7 to aL perform the matrix-matris multiplications (At)T оY and ac F4 (F+)T, allowing to Published as a conference paper at ICLR 2020
output's pixels measured with more probability the ones with the highest value f(Y,.'') Once measured, we read directly from the registers the position p, and the value itself. Thus we claim that we measure only a fraction of the quantum convolution product output, and that the set of pixels measured collect most of the meaningful information for the CNN, the other pixels being set to O.
p.g
After being measured, each pixel's value and position stored in QRAM to be used quantum state for next layer's 8 input. During this phase, it is possible to discard or aggregate some values to perform pooling operations as described in Step 3 of Algorithm The forward pass for the QCNN thus includes the the convolution product, the non linearity f and pooling operation, in time poly- logarithmic in the kernel's dimensions. In comparison, the classical CNN layer in linear in both kernel and input dimensions.
Note finally that quantum importance sampling in Step 2 implies that the non linear function be bounded by a parameter C > 1. In our experiments we use the capReL. function, which is modified ReLu function that becomes constant above C.
QUANTUM BACKPROPAGATION ALGORITHM
The second algorithm required for the QCNN the quantum backpropagation algorithm given as Algorithm Like the classical backpropagation algorithm, it updates all kernels weights according to the derivatives of a given loss function C. In this sectiion, we explain the main ideas and compare it to the classical backpropagation algorithm, the complete details given in Appendix (Section
Algorithm Quantum Backpropagation
Require: Precision parameter Data matrices A and kernel matrices pe stored QRAM for each layer f.
Ensure: Outputs gradient matrices ac and aFe
оy for each layer
1: Calculate the gradient for the last layer L using the outputs and the true labels: ac BY
2: for = L -1,- ..... 0 do
3: Step 1 Modify the gradient
With 9C FFT stored in QRAM, set to some of its values to take into account pooling, tomog- raphy and non linearity that occurred in the forward pass of layer f. These values correspond to positions that haven't been sampled nor pooled, since they have no impact on the final loss.
4: Step 2 Matrix-matris multiplications
#C obtain quantum states corresponding OF7 and ac BY7.
5: Step lo tomography
Measure the previous outputs, in Algorithm This allows to estimate each entry of ac
dc
oF
and ac
BY with errors 8 || aFe and bl respectively, using for tomography from Theorem Bc
ac
G.1 Store all elements of SFT in QRAM.
6: Step 4 Gradient descent
From the previous tomography, perform the gradient descent to update the values of p in
QRAM: Fd
Fe
25
2.g
3F
OF
7: end for
We describe briefly detail the implementation of quantum backpropagation at layer &. The algorithm assumes that ac サy known. First, the backpropagation of the quantum convolution product equivalent to the classical one, and we use the matrix-matrix multiplication formulation to obtain the derivatives Dpt and ayz. The first one is the result wanted and the second one is needed for layer f f- 1. This matrix-matrin multiplication can be implemented as quantum circuit, by decomposing into several matrix-vecti multiplications, known to be efficient, with a running time depending on the ranks and Frobenius norm of the matrices. We obtain quantum state corresponding
dc
8L
5

---

Published as a conference paper at ICLR 2020
superposition of all derivatives. We again the lxc, tomography to retrieve each derivative with precision 5 > O such that, for all kernel's weight 5.g we have approximated it's loss derivative with ac 8F with an error bounded by descent rule is perturbed by 20
Oc
BC
S 26
This implies that the gradient ac
aF?
8F
OF
ac 8F
|| at most, see Appendix (Section E.4)
We also take into account the effects of quantum non linearity, quantum measurement and pooling, The quantum pooling operation is equivalent the classical one, where pixels that were not selected during pooling see their derivative set to O. Quantum measurement is similar, since pixels that haven't been measured don't t contribute to the gradient. For the non linearity, in the classical case, pixels with negative values were set to zero, hence should have no contribution to the gradient. Additionally, because we used the capReLu function, pixels bigger than the threshold C must also have null derivatives. This two rules can be implemented by combining them with measurement rules compared to classical backpropagation, see Appendix (Section E.2.2 for details.
NUMERICAL SIMULATIONS
As described above, the adaptation of the CNNs to the quantum setting implies some modifications that could alter the efficiency of the learning or classifying phases. We now present some experi- ments to show that such modified CNNs can converge correctly, as the original ones.
The experiment, using the PyTorch library developed by Paszke et al. (2017), consists of training classically a small convolutional neural network for which we have added a "quantum" sampling after each convolution. Instead of parametrising it with the precision 7/, we have choosed to use the sampling ratio a that represents the fraction of pixels drawn during tomography. This two definitions equivalent, as shown in Appendix (Section D.1.5). but the second one is more intuitive regarding the running time and the simulations.
We also add a noise simulating the amplitude estimation (parameter c), followed by capReLu instead of the usual ReLu (parameter C`), and a noise during the backpropagation (parameter 8). In observe that our quantum CNN is able to learn and classify visual data
the following results, from the widely used MNIST dataset. This dataset is made of 60.000 training images and 10.000 testing images of handwritten digits. Each image is 28x28 grayscale pixels between 0 and 255 (8 bits encoding), before normalization.
Let's first observe the "quantum" effects on image of the dataset. In particular, the effect of the capped non linearity, the introduction of noise and the quantum sampling.
We now present the full simulation of our quantum CNN. In the following, we a simple network made of 2 convolution layers, and compare our quantum CNN to the classical one. The first and second layers are respectively made of 5 and 10 kernels, both of size 7x7. A three-layer fully connected network is applied at the end and softmax activation function is applied on the last layer to detect the predicted outcome over 10 classes (the ten possible digits). Note that we didn't t introduce pooling, being equivalent between quantum and classical algorithms and not improving the results on our CNN. The objective of the learning phase is to minimize the loss function, defined by the negative log likelihood of the classification the training set. The optimizer used was built-in Stochastic Gradient Descent.
Using PyTorch we have been able implement the following quantum effects (the first three points are shown in Figure D:
The addition of noise, to simulate the approximation of amplitude estimation during the forward quantum convolution layer, by adding gaussian noise centered on 0 and with standard deviation 2Mc, with M max,.9 || [|F,
A modification of the non linearity: a ReLu function which is constant above the value T (the cap).
A sampling procedure apply on tensor with probability distribution proportional to the tensor itself, reproducing the quantum sampling with ratio o.
The addition of noise during the gradient descent, to simulate the quantum backpropagation, by adding a gaussian noise centered on with standard deviation 6, multiplied by the norm of the gradient, as given by Equation (28).

---

Published as a conference paper at ICLR 2020
5
5
5
5
100
24
5
6
6
6
19
x
Figure I: Effects of the QCNN on a 28x28 input image. From left to right: original image, image after applying capReLu activation function with cap C 2.0, introduction of strong noise during amplitude estimation with highest values in priority. The useful information tends to be conserved in this example. The side gray scale indicates the value of each pixel. Note that during the QCNN layer. a convolution is supposed happen before the last image but we chose not to perform it for visualisation matter.
0.5, quantum sampling with ratio a = 0.4 that samples the
The CNN used for this simulation may seem "small" compared to the standards AlexNet developed by Krizhevsky et al. (2012) or 16 by Simonyan & Zisserman (2014), or those used in industry. already very computationally
However simulating this small QCNN intensive and time consuming, due to the""quntumr sampling task, apparently not optimized for classical implementation in PyTorch. Every single training curve showed in Figure 9 could last for 4 to 8 hours. Hence adding more convolutional layers wasn't t convenient. Similarly, we didn't 't compute the loss on the whole testing set (10.000 images) during the training to plot the testing curve. However we have computed the test losses and accuracies once the model trained (see Table 4), in order to detect potential overfitting cases.
a elassical computer
We now present the result of the training phase for a quantum version of this CNN, where partial quantum sampling is applied, for different sampling ratio (number samples taken from the result- ing convolution). Since the quantum sampling gives more probability to observe high value pixels, we expect to be able to learn correctly even with small ratio (o S 0.5). We compare these training curve the classical one. The learning has been done two epochs, meaning that the whole dataset used twice. The following plots show the evolution the loss L during the iterations on batches. This is the standard indicator of the good convergence of a neural network learning phase. We can compare the evolution of the loss between a classical CNN and our QCNN for different parameters. Most results are presented in Appendix (Section
Our simulations show that the QCNN is able to learn despite the introduction of noise, tensor sam- pling and other modifications. In particular shows that only a fraction of the information mean- ingful for the neural network, and that the quantum algorithm captures this information in priority. This learning can be more or less efficient depending on the choice of the key parameters. For de- cent values of these parameters, the QCNN is able to converge during the training phase. It can then classify correctly on both training and testing set, indicating neither overfitting nor underfitting.
We notice that the learning curves sometimes present a late start before the convergence initializes, in particular for small sampling ratio. This late start can due to the random initialization of the where the quantum sampling of the
kernel weights, that performs meaningless convolution, output is of no interest. However it is very interesting to see that despite this late start, the kernel start converging once they have found good combination.
Overall, it is possible that the QCNN presents some behaviors that have no classical equivalence. Understanding their potential effects, positive negative, is open question, all the more as the effects the classical CNN's hyperparameters are already a topic active research, see the work of Samek et al. (2017) for details. Note also that the neural network used in this simulation is
7

---

Published as a conference paper at ICLR 2020
Training curves e.0.11, C 10.0, 6 0.01
QUNN: 5-05
QCNS: g=0.1
1.5
QCKN: m-003
QCNN- m=02
QCNN: o-01
0.5
20000 40000
00000
80000
100000
120000
Iterasions
Figure 2: Training curves comparison between the classical CNN and the Quantum CNN (QCNN) for 0.01, C = 10, 5 = 0.01 and the sampling ratio from 0.1 to 0.5. We can observe learning phase similar to the classical one, even for weak sampling of 20% or 30% of each convolution output, which tends to show that the meaningful information is distributed only at certain location of the images, coherently with the purpose of the convolution layer. Even for a very low sampling ratio of 10%, we observe convergence despite late start.
rather small. A following experiment would be to simulate a quantum version standard deeper CNN (AlexNet VGG-16), eventually on more complex dataset, such CIFAR- 1- developed by Krizhevsky & Hinton 2009) or Fashion MNIST by Xíao et al. (2017).
7 CONCLUSIONS
We have presented quantum algorithm for evaluating and training convolutional neural networks (CNN). At the core of this algorithm, we have developed novel quantum algorithm for computing a convolution product between two tensors, with a substantial speed up. This technique could be reused in other signal processing tasks that could benefit from an enhancement by a quantum com- puter. Layer by layer, convolutional neural networks process and extract meaningful information. Following this idea of learning foremost important features, we have proposed a new approach of quantum tomography where the most meaningful information is sampled with higher probability, hence reducing the complexity of our algorithm.
Our QCNN is complete in the sense that almost all classical architectures can be implemented in quantum fashion: any (non negative and upper bounded) non linearity, pooling, number of layers and size of kernels are available. Our circuit is shallow and could be run relatively small quantum computers. One could repeat the main loop many times on the same shallow circuit, since perform- ing the convolution product is simple, and is similar for all layer. The pooling and non linearity included in the loop. Our building block approach, layer by layer, allows high modularity, and can be combined with work on quantum feedforward neural network developed by Allcock al. (208))
The running time presents a speedup compared to the classical algorithm, due to fast linear alge- bra when computing the convolution product, and by only sampling the important values from the resulting quantum state. This speedup can be highly significant in cases where the number of chan- nels De in the input tensor is high (high dimensional time series, videos sequences, games play) or when the number of kernels D is big, allowing deep architectures for CNN, which was the case in the recent breakthrough of DeepMind AlphaGo algorithm (iilvrr al. 2016). The Quantum CNN also allows larger kernels, that could be used for larger input images, since the size the kernels must be contant fraction of the input in order to recognize patterns. However, despite our new techniques to reduce the complexity, applying non linearity and reusing the result of layer for the next layer make register encoding and state tomography mandatory, hence preventing from having exponential speedup on the number of input parameters.
Finally we have presented a backpropagation algorithm that can also be implemented as a quantum circuit. The numerical simulations sampling. the QCNN can efficiently learn to classify visual data from the MNIST dataset, perform- ing similar accuracy than the classical CNN.
small CNN show that despite the introduction of noise and
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Jonathan Allcock, Chang-Yo Yu Hsich, Iordanis Kerenidis, and Shengyu Zhang. Quantum algorithms for feedforward neural networks. arXiv preprint 1exxiv::/12.00151 2018.
Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J Osborne, Robert Salzmann, and Ramona Wolf. Efficient learning for deep quantum neural networks. arXiv preprint arXiv:1902.10445 2019.
Mariusz Bojarski, Anna Choromanska, Krzysztof Choromanski, Bernhard Firner, Larry Jackel, Urs Muller, and Karol Zieba. Visualbackprop: efficient visualization of cnns. arXiv preprint arXiv:1611.05415 2016.
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power block-encoded ma- trix powers: improved regression techniques via faster Hamiltonian simulation. arXiv preprint arXiv: 1804.00973 2018.
Iris Cong, Soonwon Choi. and Mikhail D Lukin. Quantum convolutional neural networks. arXiv preprint arXiv:1810.03760 2018.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term pro- cessors. arXiv preprint 100.vv/802.00000 2018
Daniel George and EA Huerta, Deep learning for real-time gravitational wave detection and param- eter estimation: Results with advanced ligo data. Physics Letters B, 778:64-70, 70, 2018.
Maxwell Henderson, Samriddhi Shakya, Shashindra Pradhan, and Tristan Cook. Quanvolu- tional neural networks: Powering image recognition with quantum circuits. arXiv preprint arXiv:1904.04767, 2019.
Tordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017a.
Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. 1704.0/7044049990 2017b.
Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. (1f1::1808.092666, 2018
Tordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. Neural Information Processing systems (NeurIPS), 2019.
Nathan Killoran, Thomas Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd. Continuous-variable quantum neural networks. arXiv preprint I 888610687,, 2018.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, L Bottou, Yoshua Bengio, and P Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv, 130700411:1-11, 7 2013. ARLattp:/// /ttp:://rxii.....////// http///xxvvvorr///////////. org/ abs/1300 0411

---

Published as a conference paper at ICLR 2020
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis.
Nature Physics, 10(9);631, 2014.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002a.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002b.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Patrick Rebentrost, Thomas R Bromley, Christian Weedbrook, and Seth Lloyd. Quantum hopfield neural network. Physical Review A, 98(4):442308 2018.
Wojciech Samek, Thomas Wiegand, and Klaus-Robert Müller. Explainable artificial intelli- gence: Understanding, visualizing and interpreting deep learning models. arXiv:1708.08296, 2017.
arXiv preprint
Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. The quest for quantum neural network. Quantum Information Processing, 131155225772 2014.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: /409. 1556, 2014.
Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum Algorithms for Nearest-Neightt Methods for Supervised and Unsupervised Learning. 4rXh:1140.211222,, 2014a. URL https:
//arziv.org/pdf/
http://pd..1111.21........
Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum deep learning. arXiv preprint
arXiv:1412.3489 2014b.
J Wu. Introduction to convolutional neural networks, https::/paffs..emntii.coo 10t:///6001111111111166622222223
2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmark- ing machine learning algorithms, arXiv preprint 17Xiv:1708.07747, 2017.
10

---

Published as a conference paper at ICLR 2020
APPENDIX A VARIABLE SUMMARY
We recall the most important variables for layer e. They represent tensors, their approximations, and their reshaped versions.
Data
Variable
Dimensions
Indices (i', d"
X
H' x W D
Input
Y
(H"W") X D
A
(H W " X (HWD")
(p,r)
K
H x W x D' x D
(i, d. d')
Kernel
F
(HWD') x D
(8,
Table I: Summary of input variables for the eth layer, along with their meaning, dimensions and corresponding notations. These variables are common for both quantum and classical algorithms. We have omitted indices for Y which don't It appear in our work.
Data
Variable
Dimensions
Indices
f(X
[H x De+1
(p.g) g)
Output of Quantum Convolution
1(x"11)
H x We+1 x De+1
(i++1 _ett det1)
Output of Quantum Tomography
Xe+1
H x We+t x D
(i jeti det1)
Output of Quantum Pooling
pe+1
H X P
W DC+1
[8+1,Jet) dct1)
Table 2: Summary of variables describing outputs of the layer E, with the quantum algorithm.
Data
Variable f(Y (g++WE++ D
Dimensions
Indices
(p.9)
Output of Classical Convolution
f(X+F))
H W
D
(i d
Output of Classical Pooling
X H
W
x D
(1++1
s0+ db+1)
p
P
Table 3: Summary of variables describing outputs of the layer E, with the classical algorithm.
Classical and quantum algorithms can be compared with these two diagrams:
Quantum convolution layer: X - (x(t1) - (((x(t)) - xe+1 - pet1 Classical convolution layer: X X + f(x+1) + X
(3)
We finally provide some remarks that could clarify some notations ambiguity:
Formally, the output of the quantum algorithm is g It is used as input for the next layer E + 1.
But we consider that all variables' names are reset when starting a new layer: X + x++1
For simplicity, we have sometimes replaced the indices (if+1, jit1 dl+1) by n index the ele- ments of the output.
In Section D.2.2 the input for layer é is stored as e for which the elements indexed by (p',r').
APPENDIX B PRELIMINARIES IN QUANTUM INFORMATION
We introduce a basic and arodd-audience quantum information background necessary for this work. For more detailed introduction recommend Nielsen & Chuang (20)2a).
11

---

Published as a conference paper at ICLR 2020
B.1 QUANTUM INFORMATION
Quantum Bits and Quantum Registers: 'he bit the most basic unit of classical information. can be either in state 0 or 1. Similarly a quantum bit or qubit, is a quantum system that can be is state (0), [1) (the braker notation 1-) is a reminder that the bit considered is a quantum system) in superposition of both states a [0] + 3 [1) with coefficients a, 8 E C such that |a + 18|² = 1. The amplitdes a and are linked the probabilities of observing either or I when measuring the qubit, since P(O) = |a|2 and P(1) [8|2.
Before the measurement, any superposition possible, which gives quantum information special abilities in terms of computation. With n qubits. the 2" possible binary combinations can exist simultaneously, each with a specific amplitude. For instance we can consider an uniform distribution vn Ei (i) where (i) represents the jth binary combination (e.g. |01 -... [01-.-10011 1001)). Multiple qubits together are often called a quantum register.
In its most general formulation, quantum state with n qubits can be seen as vector in a complex Hilbert space of dimension 2". This vector must be normalized under Ez-norm, to guarantee that the squared amplitudes sum to I.
To process qubits and therefore quantum registers, we use quantum gates. These gates are unitary operators in the Hilbert space as they should map unit-norm vectors to unit-norm vectors, Formally, we can see quantum gate acting on n qubits as a matrix U E C² such that Uut UTU I, where Ut is the conjugate transpose of U. Some basic single qubit
Quantum Computation:
gates includes the NOT gate (0 1
[ 0) that inverts (0) and [1), or the Hadamard gate V2 (1 -
that maps 10) + 1 (10) + 1)) and [1) + +/2 (10) - (1)), creating the quantum superposition.
Finally, multiple qubits gates exist, such as the Controlled-NOT that applies a NOT gate on target qubit conditioned on the state of a control qubit.
The main advantage of quantum gates is their ability to be applied to superposition of inputs. Indeed, given gate such that U (x) + If(x)), we can apply it to all possible combinations at once U Σn (z)) + è If()).
We now state some primitive quantum circuits, which we will use in our algorithm: For two integers
1i) (5) [ j(}. For two real value numbers a > 0 and > O, we can compare them using (a) 8) 10) + for real value numbers are basically a reversible version of the classical ones and are linear the number of qubits used to encode the input values.
i and can check their equality with the mapping (t) (5) [0] +
- a) (6) aa 8]}. Finally, O, we can obtain its square (a) 10) (a) la?). Note that these circuits
Any classical boolean function can be implemented in a quantum unitary, even though this seems at first contradictory with the requirements of unitaries (reversibility, linearity). Let a R - IR be classical function, we define U, the unitary that acts as U, (z) (0) + (x) (x()). Using second quantum register to encode the result of the function, the properties of quantum unitaries are respected.
B.2 QUANTUM SUBROUTINES FOR DATA ENCODING
Knowing some basic principles of quantum information, the next step is understand how data can be efficiently encoded using quantum states. While several approaches could exist, we present the most common one called amplitude encoding, which leads to interesting and efficient applications.
Let x E Rd be a vector with components (-),-.- ,.a). Using only [log(d)] qubits, we can form lz). the quantum state encoding z. given by (x) | x, lb). We see that the jth component xy becomes the amplitude of Ij),, the jth binary combination (or equivalently the 7th vector in the standard basis). Each amplitude must be divided by ||>||| to preserve the unit norm of (z).
Similarly, for a matrix A E Rdd or equivalently for n vectors A, for i E [r2], we can express each
row of A as (A,) | Ei Aug lj).
12

---

Published as a conference paper at ICLR 2020
We can explain important definition, the ability to have quantum access to matrix. This will be a requirements for many algorithms.
Definition [Quantum Access to Data]
We say that we have quantum access matrix A Tgaxd if there exist a procedure to perform the following mapping, for i E [n], in time T:
<2) 10) + (8> |A,)
00) - - Σ, |x
By using appropriate data structures the first mapping can be reduced to the ability to perform
mapping of the form [t) ( (0)
+ (t) (5) [Ay). The second requirement can be replaced by the
ability of performing ()) (0) + [ [|ll)) or just have the knowledge of each norm. Therefore,
using matrices such that all rows A; have the same norm makes it simpler to obtain the quantum access.
The time or complexity T necessary for the quantum access can be reduced to polylogarithmic dependence in n and d if we consider the access to a Quantum Memory or QRAM. The QRAM Kerenidis & Prakash] (2017a) is specific data structure from which quantum circuit can allow quantum access to data in time Ollog (nd)).
Theorem B.1 (QRAM data structure, see Kerenidis & Prakash (017aa) Let E Raxd x there is data structure to store the rows of A such that,
1. The time insert, update delete single entry Aig is (log((n))
2. A quanium algorithm with access to the data structure can perform the following unitaries in time T Olog' n)).
(a) [2) 0) (2) [At)) for E [m].
(b) 00) Eie |4 It).
We now state important methods for processing the quantum information. Their goal is to store some information alternatively the quantum state's amplitude or the quantum register as a bitstring.
Theorem B.2 [Amplitude Amplification and Estimation Brassard et al. (2002)) Given a unitary operator U such that U 10) + // 3) [0) + 11-ply- in time T, where >> 0 is the probability of measuring "0", it is possible obtain the state ly) 0) using O vp queries U, or estimate p with relative error ê using ( ovp) queries to U.
Theorem B.3 /Conditional Rotation] Given the quantum state (a), with [-1, it is possible to perform (a) [0} + |a) (a (0) + VI-a (1)) with complexity ((1).
Using Theorem F3 followed by Theorem F2 then possible transform the state va Ez= (xy)
into
[ Σド= Tz [zz).
In addition to amplitude estimation, we will make use tool developed in Wiebe et al. boost the probability of getting good estimate for the inner product required for the quantum convolution algorithm. In high level, we take multiple copies of the estimator from the amplitude estimation procedure, compute the median, and reverse the circuit get rid of the garbage. Here provide a theorem with respect to time and not query complexity.
(011aa)
Theorem B.4 (Median Evaluation, see Wiebe et al. 2014a)) Let U be a unitary operation that maps
u (0 Valx, /1- a
for some 1/2 < 5 in time T. Then there exists quantumn algorithm that, for any A 0 and for any 1/2 an S a, produces state (V) such that [V] (0@nL) (ar) || S 22A for some integer
13

---

Published as a conference paper at ICLR 2020
L, in time
In(1/A)
27
2 (laol )
B.3 QUANTUM SUBROUTINES FOR LINEAR ALGEBRA
In the recent years, as the field of quantum machine learning grew, its "toolkit" for linear alge- bra algorithms has become important enough allow the development of many quantum machine learning algorithms, We introduce here the important subroutines for this work, without detailing the circuits or the algorithms.
Definition For a matrix A. the parameter p(A) is defined by p(A) minpe(o.1]
FI
. $ 22p (1))2(1-p))))))) (AP) where sp(A) (IAA
The next theorems allow to compute the distance between vectors encoded as quantum states, and use this idea to perform the k-means algorithm.
Theorem B.5 [Quantum Distance Estimation Wiebe et al. (2014b); Kerenidis et al.) (2019) Given quantum access in time T to two matrices U and V with rows and vj of dimen- sion d, there is a quantum algorithm that, for any pair (i,J), performs the following mapping (t) (5) (0) + [i) (,) [ds(, Uz)), estimating the euclidean distance between and vj with precision ld ("; 01) d' dlu,; U;)1 ffr any O. The algorithm has running time given by OTTn/c), where 1) = maxij [[ [[),]]), assuming that min; min;([[u;]) = minx([]e]]]
Theorem B.6 [Quantum k-means clustering Kerenidis el al. (2019g
Given quantum access in time T to dataset V E <Raxa, there a quantum algorithm that oulputs with high probability k centroids -1. .ck that are consistent with the output of the k-means algo- VV) rithm with noise 8 >> O, time Ö(T x (Vd x(V)((VV) + k =)()) k22 k2n(V x(V))(V))) per iteration.
82
Definition 3 For matrix V. E Raxd its parameter v(V) is defined max; ?) m|lx// assuming min, (ainn((lee ([[w/]) 1.
In theorem F.6 the other parameters in running time can be interpreted as follows is the precision in the estimation of the distances, but also in the estimation of the position of the centroids. x(V) is the condition number of and μ(V) is defined above (Definition 5). Finally, in the case of well clusterable datasets, which should be the
when will apply k-means during spectral clustering, the running simplifies to Ö(T x (k2 (=())²
2..5 (()) )) 8
89
Note that the dependence in is hidden in the time T to load the data. This dependence becomes polylogarithmic in n if we assume access to QRAM.
Theorem B.7 (Quantum Matrix Operations, Chakraborty et al. 2018 ) Let M E RRdxd and E Rdd. Let 81, 82 O. If M is stored in appropriate QRAM data structures and the time to prepare (x) is Tz, then there exist quantum algorithms that with probability at least 1 - 1/poly(d) return
1. A state [z) such that [||=) - |M < 8, in time (((K(M))(MM) +T (+(K))))(((())+++))))))))))))))) log(//1)). Note that this also implies [||>) - Mx) 6,
2. Norm estimate
z E (1 + 62) ||Maly with relative error 8z. in time Ö(T, x(M))((M) log(1/)))).
82
The linear algebra procedures above also be applied any rectangular matrix V paxd by considering instead the symmetric matrix V = yT
0
V
0
14

---

Published as a conference paper at ICLR 2020
APPENDIX C CLASSICAL CONVOLUTIONAL NEURAL NETWORK (CNN)
CNN is specific type of neural network, designed in particular for image processing or time series. uses the Convolution Product as main procedure for each layer. We will focus on image pro- cessing with tensor framework for all elements of the network. Our goal is to explicitly describe CNN procedures in a form that can be translated the context of quantum algorithms.
As regular neural network, CNN should learn how to classify any input, in our case images. The training consists of optimizing a series of parameters, learned on the inputs and their corresponding labels.
C.I TENSOR REPRESENTATION
Images, more generally layers of the network, can be seen tensors. tensor is generalization of a matrix to higher dimensions. For instance an image of height H and width W can be seen as matrix in I HWW where every pixel is greyscale value between 0 ans 255 (8 bit). However the three channels of color (RGB: Red Green Blue) must be taken into account, by stacking three times the matrix for each color. The whole image is then seen as a dimensional tensor # where D is the number of channels. We will see that the Convolution Product in the CNN can be expressed between 3-tensors (input) and 4-tensors (convolution filters or kernels), the output being a 3.3 3-tensor of different dimensions (spatial size and number of channels).
81
88
23
13
44
20
Mile
0
2
0
77
19
21
20
17
12
11
12
33
21
27
38
65
Figure 3: RGB decomposition, colored image is a 3-tensor.
C.2 ARCHITECTURE
CNN is composed of main procedures, compiled and repeated in any order Convolution layers, most often followed by an Activation Function, Pooling Layers and some Fully Connected layers at the end. We will note the current layer.
Convolution Layer: The gth layer convolved by set filters called kernels. The output of this operation is the (e + 1)th layer. A convolution by single kernel can be seen as a feature detector, that will screen over all regions of the input. the feature represented by the kernel, for instance vertical edge, is present in some part of the input, there will be a high value at the corresponding position of the output. The output is commonly called the feature map of this convolution.
Activation Function As regular neural network, we insert some non linearities also called activation functions. These mandatory for neural network to be able to learn any function. In the case of a CNN, each convolution is often followed by Rectified Linear Unit function, or ReLu. This is simple function that puts all negative values of the output to zero, and lets the positive values as they are.
Pooling Layer: This downsampling technique reduces the dimensionality of the layer, in order to improve the computation. Moreover, it gives to the CNN the ability to learn representation invariant to small translations. Most of the time, we apply a Maximum Pooling or an Average Pooling. The first consists of replacing subregion of P x & elements only by the one with the
15

---

Published as a conference paper at ICLR 2020
maximum value. The second does the same by averaging all values. Recall that the value of pixel corresponds to how much a particular feature was present in the previous convolution layer.
Fully Connected Layer: After certain number of convolution layers, the input has been suf- ficiently processed so that we can apply fully connected network. Weights connect each input to each output, where inputs are all element of the previous layer. The last layer should have one node per possible label. Each node value can interpreted as the probability of the initial image to belong to the corresponding class.
C.3 CONVOLUTION PRODUCT AS A TENSOR OPERATION
Most of the following mathematical formulations have been very well detailed by Wu At layer L, we consider the convolution of a multiple channels image, seen as a 3-tensor X E x XD" Let's consider a single kernel in R#xWxD Note that its third dimension must match the number of channels of the input, as in Figure 4 The kernel passes over all possible re- gions of the input and outputs value for each region, stored in the corresponding element of the output. Therefore the output is dimensional, in IR fr xW
(007
H
H
H
DE
Wl+
D
W
We
Figure 4: Convolution of a 3-tensor input (Left) by one 3-tensor kernel (Center). The ouput (Right) matrix for which each entry is inner product between the kernel and the corresponding over- lapping region of the input.
In CNN, the most general case is to apply several convolution products to the input, each one with a different 3-tensor kernel. Let's consider an input convolved by D kernels, We can globally see this process as a whole, represented by one 4-tensor kernel Kt E D'xDD As D convolutions are applied, there are D outputs of dimensions, equivalent to 3-tensor X g+1 1 x w x
x++1
We can Figure 5 that the output's dimensions modified given the following rule:
H H - H +1 w - W +1
(4)
We omit to detail the use of Padding and Stride, two parameters that control how the kernel moves through the input, but these easily be incorporated in the algorithms.
An element of X is determined by indices (f while an element of the kernel K is determined by 4 indices (i, d, d'). For element of X use indices (if+1, je+l ++1). We can express the value of each element of the output x with the relation
D
E+1
ΣΣΣ
Kf
(5)
16

---

Published as a conference paper at ICLR 2020
!
l
X (+
X
K
7
P+1
D
H (t
H
D
Wet
H
W l
De
Figure 5: Convolutions of the 3-tensor input X (Left) by one 4-tensor kernel Kt (Center). Each channel of the output x (Right) corresponds to the output matrix of the convolution with one of the 3-tensor kernel.
C.4 MATRIX EXPRESSION
X
A
y
X
KL l
Fe
Figure 6: A convolution product is equivalent to matrix matrix multiplication.
It is possible reformulate Equation (5) as matrix product. For this we have to reshape objects. We expand the input X into matrix A (///+///1))x(//////
Each row of A' is vectorized version of a subregion of X This subregion is volume of the same size as a single kernel volume H W D Hence each of the H x w rows of A used for creating one value in X Given such subregion of X the rule for creating the row of A is to stack, channel by channel, a column first vectorized form of each matrix. Then, we reshape the kernel tensor Kt into matrix Fe RHH D*) such that each column of pd is column first vectorized version of one of the 1 kernels.
The convolution operation X * k = x++1 is equivalent to the following matrix multiplication
A =
17

---

Published as a conference paper at ICLR 2020
where each column of Y (
is column first vectorized form of one of the D channels of X Note that an element Y is the inner product between the pt row of A and the 9th column of FL. is then simple to convert y into X The indices relation between the elements Y and X (441 ,0++1 is given by:
d ②
jet1 T
P
(7)
ie+1
H
summary of all variables along with their meaning and dimensions is given in Section
APPENDIX D QUANTUM CONVOLUTIONAL NEURAL NETWORK
In this section we will design quantum procedures for the usual operations in a CNN layer. We start by deseribing the main ideas before providing the details. Steps are gathered in Algorithm
First, to perform a convolution product between an input and kernel, we will use the mapping be- tween convolution of tensors and matrix multiplication from Section CS that can further be reduced to inner product estimation between vectors, in order to use quantum linear algebra procedures to perform these computations faster. The output will be a quantum state representing the result of the convolution product, from which we can sample to retrieve classical information to feed the next layer. This is stated by the following Theorem:
Theorem D.I (Quantum Convolution Layer)
Given 3D tensor input X It xD' and 4D tensor kernel K' E "X* stored in QRAM, there is a quantum algorithm that computes a quantum states A-close to [f(x(t) with arbitrary small parameter A > O. |f(x'+)) is close to the result of the convolution product X X x Kt followed by any non linear function f : R + Rt, with an error bounded by |(X f f((+t))
I 2M for any precision e > 0, where M is the maximun norm of product between one of the D kernels, and one of the regions of X of size HWD The time complexity of this procedure is given by Ô (1/e), where Ô hides factors poly-logaritmmic in A and in the size of X and K'.
In a second step, we efficiently retrieve classical information from the output. Recall that a convo- lution can be seen as a pattern detection on the input image, where the pattern is the kernel. The output values correspond to "how much" the pattern was present in the corresponding region of the input. Low value pixels in the output indicate the absence of the pattern the input at the corre- sponding regions. Therefore, by sampling according to these output values, where the high value pixels are sampled with more probability, we could retrieve less but only meaningful information for the neural network to learn. While sampling, we update the QRAM data structure with the new information (see Section D.2p. We also perform the Pooling operation during this phase (see Section D.2.2.. It is interesting use case where amplitudes of quantum state proportional to the importance of the information they carry, giving a new utility to the probabilistic nature of quantum sampling. Numerical simulations are presented in Section 6 to have an empirical estimation of how many samples from the output state are necessary.
D.1 SINGLE QUANTUM CONVOLUTION LAYER
In order develop quantum algorithm perform the convolution as described above, will make use of quantum linear algebra procedures, We will use quantum states proportional to the rows of A noted Ap), and the columns of F noted [F,)) (we omit the l exponent in the quantum states
to simplify the notation). These states are given by (Ap) T4,
Apr Ir) and (&A))
F. - D Fay (s). We suppose we can load these vectors in quantum states by performing the following queries:
{ (p) 10) + (p) IAp) (q) (0) + (q) (E
(8)
18

---

Published as a conference paper at ICLR 2020
Such queries, in time poly-logarithmic in the dimension of the vector, can be implemented with a Quantum Random Access Memory (QRAM). See Section D.2 for more details on the QRAM update rules and its integration layer by layer.
D.1.1 INNER PRODUCT ESTIMATION
The following method estimates inner product is derived from previous work by Kerenidis et al. 2019). With the initial state (p) lq) v (10) + [1)) (0) we apply the queries detailed above in a con- trolled fashion, followed simply by a Hadamard gate extract the inner product (AplFg) in an amplitude. +22 (Ip) (a) (0) [0) + p) lq) (1) (0)) + V2 (Ip) (q) (0) Ap) + (p) (q) 11) (F))). By apply-
ing a Hadamard gate on the third register obtain the following state. 1 1p) 14) (10) (14p) + (
(1) (14p) (144))1F1)))) The probability of measuring 0 on the third register is given by Ppg (A.1F))))
2
Thus we can rewrite the previous state as (p) |q) (VPpg I0, Upg) + vI- Ppy [1, Bpg)) where
(ypg) and Ws are some garbage states. We can perform the previous circuit in superposi- tion. Since A has H4+1w++1 rows, and F has D columns, we obtain the state: lu)
WH+ D Ep E. (p) l4) (VPpn [0, Upa) + /1-1111 Ppo [1, (1u)))))))) Therefore the probability of measuring the triplet (p. q, 0) in the first three registers is given by Po(p.q) = H Her-wiiIDe
I+(A,) F2) 2H DeFI Now we can relate to the Convolution product. Indeed, the triplets (p.q.0) that are the most probable to be measured are the ones for which the value (Ap)Fi,) is the highest. Recall that each element of y is given by y = (Ap, Fz),, where "(:,-)" denotes the inner product. We see here that we will sample most probably the positions (p.q) for the highest values of y that
corresponds to the most important points of x by the Equation 77). Note that the the values of y can be either positive of negative, which is not an issue thanks to the positiveness of Po(p, q).
A first approach could be to measure indices (p. q) and rely on the fact that pixels with high values, hence a high amplitude, would have higher probability to be measured. However we have not exactly the final result, since (AplFg) & (Ap. F,)) = || [I (A). Most importantly we then want to apply a non linearity f(ypt1) to each pixel, for instance the ReLu function, which seems not possible with unitary quantum gates if the data is encoded in the amplitudes only. Morever, due to normalization of the quantum amplitudes and the high dimension of the Hilbert space of the input, the probability of measuring each pixel is roughly the same, making the sampling inefficient. Given these facts, we have added steps to the circuit, in order to measure (p. 9, I (Yx++))) )), therefore know the value of a pixel when measuring it, while still measuring the most important points in priority.
D.1.2 ENCODING THE AMPLITUDE IN A REGISTER
Let 4 be the unitary that map 10) to |u): (u) V De+T
Ep.o lp) (a) (VPpa 10, Upg) +
[1, )/mm)) The amplitude /Ppy can be encoded in an ancillary register by using Ampli- tude Estimation (Theorem F.2) followed by a Median Evaluation (Theorem F.4). For any A > 0 and 6 0, we can have state A-close to |u'
VeeFWerrDer DeFT Ep. (p) lq) 10) IP pq) lppq) with probability at least 1 2A, where IPMb P Pmpl S < and (9m²) is garbage state. This requires
0 (1(1/A queries U. In the following we discard the third register (0) for simplicity.
The benefit of having Pyy in a register is to be able to perform operations on it (arithmetic or even non linear). Therefore we can simply obtain state corresponding the exact value of the the convolution product. Since we' ve built a circuit such that Ppy = 2
1+(Ap1Fa) with
two QRAM calls, we can retrieve the norm of the vectors by applying the following unitary (p) lg) P
pm)) 19pp) (0) [0) + 1p) (4) Ppg) (gpg) |||A,||> ||| l). On the fourth register, we can then write y - 14, || (AplFg) using some arithmetic circuits (addition, multiplication by a scalar, multiplication between registers). We then apply boolean circuit that implements the ReLu function on the same register, in order to obtain an estimate of f f(y in the fourth register. We finish by inverting the previous computations and obtain the final state:
19

---

Published as a conference paper at ICLR 2020
If(r 1
1p) (q) |f(P)T
}> (9pa)
D
pq
P.q
Because of the precision on | p our estimation
x pq
= (2P pq
1) 11pl1l is obtained
with error such that IY f+ pq Y + - 2e
| ||
In superposition, we can bound this error by y Y - 2Mc where we define
M max
|| FF
(10)
P.0
M is the maximum product between norms of one of the DC+1 kernels, and one of the regions of X of size HWD'. Finally, since the previous enror estimation is valid for all pairs (p. q). the overall
error committed on the convolution product can be bounded by | y I 2Mc, where
Il-Il-o denotes the lo norm. Recall that y is just a reshaped version of X Since the non linearity adds approximation, we conclude the final error committed for a layer of QCNN
- -(X(()) 2M
(11)
At this point, we have established Theorem D.I as we have created the quantum state (.. with given precision guarantees, in time poly-logarithmic in A and in the size of X and Kº
We know aim to retrieve classical information from this quantum state. Note that [Y is rep- resenting a scalar encoded in as many qubits as needed for the precision, whereas IAp) was repre- senting vector a quantum state in superposition, where each element Ap.- is encoded in one amplitude (See Section F). The next step can be seen as way to retrieve both encoding at the same time, that will allow an efficient tomography focus on the values of high magnitude.
D.1.3 CONDITIONAL ROTATION
In the following sections, we omit the f+1 1 exponent for simplicity. Garbage states are removed as they will not perturb the final measurement. We now aim to modify the amplitudes, such that the highest values of If(Y) are measured with higher probability. A way to do so consists in applying conditional rotation on an ancillary qubit, proportionally to (())). We will detail the calculation since in the general case f(Y pq) can be greater than 1. To simplify the notation, note f(Y pq) This step consists in applying the following rotation
ancillary qubit: (x) [0) + (x) max (0) + 3 [1))), where max maxp.q f(Y and [ /I- mus
Note that in practice is possible have access mmax from the state (9). but will present a method to know a priori this value or an upper bound in section D.1.6 Let's note
1(Fpg) maN.. (F(V The ouput of this conditional rotation in superposition on state (9) is Opg
then
HWWD Eno 1p) (a) ( p2)) (Apg (0) + V - az 11)).
1.1.4 AMPLITUDE AMPLIFICATION
In order to measure (p, q. fY pn)) with higher probability where f(Y,.) pq) has high value, we could post select on the measurement of 10) on the last register. Otherwise, we can per- form an amplitude amplification on this ancillary qubit. Let's rewrite the previous state as
VHWD Eps O' (p) lq) ( pn)) (0) /1-a2, l9/na> [1), where lbppg) is another garbage state. The overall probability of measuring (0) on the last register P(O) HWD Σ 1ap The 1
number of queries required to amplify the state 10) is O
P(O)) )) as shown by Brassard et al. J(Y..)
/P(O)
2002
Since [( mm) E R+, we have oZ
Therefore the number of
max o D.))
20

---

setting them to 0. Pixels with higher values f(x+1) 2 will be sample with high probability, also Published as a conference paper at ICLR 2020
=0 -0(-
( Vmxxx..u (f(l vel)
queries is O V maxp.a ((( pq))
where the nota-
V nnn Ep.o 1(F
VEpialff (x))
tion pp.g(f( pg represents the average value the matrix f(Y). can also be written E(f(X)
as in Result E P. (f(( pp)) HWD Ep [(ppg). At the end of these iterations, we have modi-
fied with high probability the state to the following:
((()) VHWD D
Σd (o) (a) 15((pa))
(12)
P-g
Where, to respect the normalization of the quantum state, 4pg
Eventually, the
Epio
wwb
probability of measuring (p, J(Y pq)) is given by p(p, 4. JY pq))
(aing)
1(T pq)
Note
HWD
Ep 5(Y p4)
that we have used the same type of name (f({)) for both state and state state name will refer only to the latter (12)
12
For now on, this
D.1.5 &o TOMOGRAPHY AND PROBABILISTIC SAMPLING
We can rewrite the final quantum state obtained in as
(
Σ P-q
Eyst s(D lp) la) (5( pa
(13)
Ep.
E
S( pq
We see here that f(Y the amplitude. We will use this property to extract efficiently the exact values of high magnitude
f(Y(+)) ) the values of each pixel, are encoded in both the last register and in
pixels. For simplicity, we will use instead the notation s(xx+t) (+1] to denote a pixel's value, with [H&++ Det1). Recall that y and X are reshaped version the same object.
The pixels with high values will have more probability of being sampled. Specifically, we perform a tomography with Loo guarantce and precision parameter 7) > 0. See Theorem G.1 and Section G for details. The foo guarantee allows to obtain each pixel with error at most and require ((1v²²) f+
samples from the state (13). Pixels with low values f(x=x) < 1) will probably be sampled due to their low amplitude. Therefore the error committed will be significative and we adopt the rule of
n and only one appearance is enough to get the exact register value f(x(+)) of the pixel, written in the last register.
To conclude, let's note Xf+1 the resulting pixel values after the tomography, and compare it the real classical outputs f f(x+11). Recall that the measured values f fxx are approximated with error at most 2M with M = maxp.g ||Apll [l The algorithm described above implements the following rules:
|x xe+1
f(Xx+)) 2Mc if f(x 2 n
(14)
if s(X
Concerning the running time, one could ask what values of are sufficient to obtain enough mean- ingful pixels. Obviously this highly depends on the output's size H++l Dé+1 and on the out- put's content itself. But we can view this question from other perspective, by considering that we sample a constant fraction pixels given by a ( W D where o E |0, 1] is a sampling ratio. Because of the particular amplitudes of state (13 the high value pixels will be measured and
known with higher probability. The points that are not sampled are being set to 0. We see that this approach is equivalent to the foc tomography, therefore have
H 11+11111pm D
21

---

Published as a conference paper at ICLR 2020
We will use this analogy in the numerical simulations (Section 6 to estimate, for a particular QCNN architecture and a particular dataset of images, which values of a are enough to allow the neural network to learn.
D.1.6 REGULARIZATION OF THE NON LINEARITY
In the previous steps, several appearances of the parameter max conditional rotation preprocessing, we need to know this value or an upper bound. Then for the running time, would like to bound this parameter. Both problems usual ReLu non linearity by particular activation function, that we note capReLa. This function simply parametrized ReLu function with an upper threshold, the cap C, after which the function remain constant. The choice of C' will be tuned for each particular QCNN, as tradeoff between accuracy and speed. Otherwise, the only other requirement of the QCNN activation function would be not to allow negative values. This is already often the case for most of the classical CNN. In practice, we expect the capReL.u be as good as a usual ReLu, for convenient values of the cap C (s 10). We performed numerical simulations to compare the learning curve of the same CNN with several values C. See the numerical experiments presented in Section 6 for more details.
( (f(Y )). First for the
E+
be solved by replacing the
6
Figure 7: Activation functions: ReLu (Left) and capReLu (Right) with cap C at 5.
D.2 QRAM UPDATE
We wish to detail the use of the QRAM between each quantum convolution layer, and present how the pooling operation can happen during this phase. General results about the QRAM is given as Theorem F.I. Implementation details be found in the work of Kerenidis & Prakash (2017a). In this section, we will show how to store samples from the output the layer é, to create the input of layer& 1.
D.2.1 STORING THE OUTPUT VALUES DURING THE SAMPLING
At the beginning of layer {+1, 1, the QRAM must store f matrix where each elements is indexed by (p',r), and perform Ip') (0) + Ip') ( The data is stored in the QRAM as tree structure described by Kerenidis & Prakash 2017b). Each row A g+1 is stored in such tree T Each leaf
/rr correspond to a value sampled from the previous quantum state ( }), output of the layer ( in the tree r++11
l. The question is to know where to store sample from
When point is sampled from the final state of the quantum convolution, at layer e, as described in Section D.I.4 we obtain a triplet corresponding to the two positions and the value of a point in the
matrix
We can know where this point belong in the input of layer & f 1, the tensor X by Equation since Y a reshaped version of X
The position in X noted (if+1 , d ). is then matched to several positions (7/,') in 4++1 For each p', we write in the tree T the sampled value at leaf r' and update its parent nodes, as required in the work Kereniisss & Prakash (2017b). Note that leaves that weren' 't updated will be considered as zeros, corresponding to pixels with too low values, or not selected during pooling (see next section).
22

---

Published as a conference paper at ICLR 2020
Having stored pixels in this way, we then query Ip') 10) + 'p') (4 using the quan- tum circuit developed by Kerenidis Prakash (2017b) where we correctly have |4 = Σ,' A Ir'). Note that each tree has logarithmic depth the number leaves, hence the running time of writing the output of the quantum convolution layer in the QRAM gives marginal multiplicatiie increase, poly-logarithmic in the number of points sampled from (f )), namely
(llg(L1/n2))
D.2.2 QUANTUM POOLING
As for the classical CNN, a QCNN should be able to perform pooling operations. We first detail the notations for classical pooling. the end of layer L, we wish to apply a pooling operation of size P on the output f(X++1). We note X the tensor after the pooling operation. For a point in f(x++1) at position (i jet], dd we know to which pooling region it belongs, corresponding position (itt1, jett d in 8et1.
de+1 de
jet1 =
++
(15)
jet1 1
f f(Xet1
X e+1
Figure 8: A 2 tensor pooling. A point in f(X+11 (left) given by its position (it+1, jetz (441,000 dd+1).. point in x (right) given by its position (f+11, de+1). Different pooling regions in f(X++1) have separate colours, and each one corresponds to a unique point in X
We now show how any kind of pooling can be efficiently integrated our QCNN structure. In- deed the pooling operation will occur during the QRAM update described above, at the end of convolution layer. At this moment we will store sampled values according to the pooling rules.
In the quantum setting, the output of layer é after tomography is noted x++1 After pooling, we will describe it by get11 which has dimensions Hº12 w p Dé+1, ge+1 will be effectively used as input for layer ++1 and its values should be stored in the QRAM to form the trees 7 related to the matrix expansion A++1
However x is not known before the tomography is over. Therefore we have to modify the update rule of the QRAM to implement the pooling in online fashion, each time sample from [((x(t))) is drawn. Since several sampled values of (((x(=)) can correspond to the same leaf A+11 (points in the same pooling region), we need an overwrite rule, that will depend the type of pooling. In the case of Maximum Pooling, we simply update the leaf and the parent nodes if the new sampled value higher that the one already written. In the case of Average Polling, we replace the actual value by the new averaged value.
In the end, any pooling can included in the already existing QRAM update. In the worst case, the running time is increased by Ö(P/7²), an overhead corresponding to the number of times we need overwrite existing leaves, with P being small constant in most cases.
23

---

Published as a conference paper at ICLR 2020
the final positions (p, 7) that were sampled from |/(x*+)) and selected after pooling must be stored for further use during the backpropagation phase.
As we will see in Section F
D.3 RUNNING TIME
We will now summarise the running time for one forward pass of convolution layer L. With Ô we hide the polylogaryhtmic factors. We first write the running time of the classical CNN layer, which given by O H W D&+1 HWD') For the QCNN, the previous steps prove Result and
can be implemented in time δ (E((X*+)))
MVC
Note that, as explain in Section D.1.5 the
quantum running time can also be written [HH Det1
MvC EVEUX
with or E [0, 1]
being the fraction of sampled elements among H W of them.
is interesting to notice that the one quantum convolution layer can also include the Rel.u operation and the Pooling operation in the same circuit, for no significant increase in the running time, whereas in the classical CNN each operation must be done on the whole data again.
APPENDIX E QUANTUM BACKPROGATION
The entire QCNN is made of multiple layers. For the last layer's output, we expect only one possible outcome, or a few in the case of a classification task, which means that the dimension the quantum output is very small. A full tomography can be performed on the last layer's output in order to calculate the outcome. The loss then calculated, as a measure of correctness of the predictions compared to the ground truth. As the classical CNN, our QCNN should be able to perform the optimization of weights (elements of the kernels) to minimize the loss by an iterative method.
Theorem E.1 (Quantum Backpropagation for Quantum CNN)
Given the forward pass quantum algorithm in Algorithm 7 the input matrix A and the kernel matrix Fe stored in the QRAM for each layer f, and loss function L, there is a quantum backpropugation ac and update each element
algorithm that estimates, for any precision 8 0, the gradient tensor SFt
to perform gradient descent such that v(8, OF.. OF S
25
Dr l1
Let Dc be the gradi-
"Y
ent with respect to the eth layer. The running time of a single layer E for quantum backpropagation is given by
OC o ((MLAA)) + ml
OC ((
(ML (ML
Oc +
Oc OY?
log 1/8
(YY+T)
xi
(16)
82
where for a matrix V, x(V) is the condition number and p(V) is defined in Equation (5)
E CLASSICAL BACKPROPAGATION
After each forward pass, the outcome is compared to the true labels and define loss. We can update our weights by gradient descent to minimize this loss, and iterate. The main idea behind the backpropagation is to compute the derivatives of the loss L, layer by layer, starting from the last one.
At layer L, the derivatives needed to perform the gradient descent are aF represents the gradient of the final loss L with respect to each kernel element, matrix of values that we will use to update the kernel weights F The second one is the gradient of L with respect to 8c the layer itself and is only needed to calculate the gradient T at layer L 1.
ac and AC The first one øyz.
E.1.1 CONVOLUTION PRODUCT
We first consider classical convolution layer without non linearity pooling. Thus the output of layer is the same tensor as the input of layer + 1, namely X or equivalently y Assuming dC
76 know FF or equivalently σyт-r, both corresponding the derivatives of the (e (1+1)th layer's
24

---

Published as a conference paper at ICLR 2020
imput, will show how calculate öFC, the matrix of derivatives with respect the elements of the previous kernel matrix f This is the main goal in order optimize the kernel's weights.
dc
The details of the following calculations can be found in the work of Wu (0177) We will use the notation vec(X) to represents the vectorized form of any tensor X.
Recall that A is the matrix expansion of the tensor X whereas Y is a matrix reshaping of X dc ( Qvec[Xr+1y Ovec(Frr"" we can obtain:
By applying the chain rule Fvec(Fry
ac
ac (A
OL
(17)
OF
0y
See calculations details in the work of Wu (2117). Equation (17) shows that, to obtain the desired gradient, we can just perform a matrix- matrix multiplication between the transposed layer itself (A*) and the gradient with respect to the previous layer (ayt+)).
Equation 17p explains also why will need to caleulate ac in order backpropagate through 8Y
ac Quent x layer f To calculate it, we use the chain rule again for _vee(X²TT Suee( 1177 Qveet Xeyr
ac
Recall that point in A', indexed by the pair (p,r), correspond to several triplets (i', j d') in X We will use the notation (p, r) + (i', j"' (f, d to express formally this relation. One can show that 7F (Fe)T" a matrix same shape as A and that the chain rule leads to simple relation
to calculate 82 8Y?
OC 0x
Σ
0ye+I (FEjT
Oc
(18)
(p.))e
p.r
We have shown how to obtain the gradients with respect to the kernels F and to the layer itself y (or equivalently X²).
1.2 NON LINEARITY
The activation function has also an impact on the gradient. In the case of the ReLu, we should only cancel gradient for points with negative values. For points with positive value, the derivatives remain the same since the function is the identity. A formal relation can be given by
ac
8C
if X+1
E+1
2et 20
stt jett
(19)
ax++1
(et1jt-1.0 1,
otherwise
1.3 POOLING
If we take into account the pooling operation, we must change some of the gradients. Indeed, pixel that hasn't 't been selected during pooling has no impact on the final loss, thus should have gradient equal to O. We will focus on the case of Max Pooling (Average Pooling relies on similar idea). To state a formal relation, we will use the notations of Section D.2.2 an element the output of the layer, the tensor f(X is located by the triplet (it+1, _jtt] d The tensor after pooling is noted {++1 and its points are located by the triplet (ze+1, 15et1 T01)). During backpropagation, after the calculation of ac #x some of the derivatives of f(xe+1) should be set to zero with the
following rule:
dC 0f(x++1)
8C
if (gt+1,10 jet1 det1) was selected during pooling
ox
1
otherwise
(20)
25

---

Published as a conference paper at ICLR 2020
E.2 QUANTUM ALGORITHM FOR BACKPROPAGATION
In this section, want give quantum algorithm to perform backrpopagation layer l, and detail the impact on the derivatives, given by the following diagram:
ac
Oc
ac 0f(x"1)
Oc
OL
0C
X
(21)
ac
0X
0x
0x
0X+1
aF
We assume that backpropagation has been done on layer (+1. This means in particular that axc+ stored in QRAM. However, shown Diagram (21). ax corresponds formally to ax and
8C
is
ac
oc
not DC Therefore, we will have to modify the values stored in QRAM to take into account non 8X
linearity, tomography and pooling, We will first consider how to implement
#C and HC OF7 through ax 5X where the same.
EX7
backpropagation, considering only convolution product, if Oc and
ac
ac Then we will detail how to simply modify ax priori, by setting some of its values to 0.
E.2.1 QUANTUM CONVOLUTION PRODUCT
In this section we consider only the quantum convolution product without non linearity, tomography nor pooling, hence writing its output directly as X Regarding derivatives, the quantum convo- lution product is equivalent to the classical one. Gradient relations (17) and (18) remain the same. Note that the e-approximation from Section D.1.2 doesn's participate in gradient considerations.
The gradient relations being the same, we still have to specify the quantum algorithm that imple- ments the backpropagation and outputs classical description of ac and Oc We have seen that the ax aF two main calculations 17 and (18) in fact matrix-matrix multiplications both involving Bc the reshaped form of 7 For each, the classical running time
HW HWD*). and Theorem G.I quantum algorithm to perform efficiently
We know from Theorem matrix-vector multiplication and return a classical state with &oo norm guarantees. For a matrix V and a vector b, both accessible from the QRAM, the running time to perform this operation
is O (a(V)n()) log 1/6) where x(V) is the condition number of the matrix and p(V) is matrix 82
parameter defined in Equation (5) Precision parameter å > 0 is the error committed in the approxi- mation for both Theorems E7 and G.I
We can therefore apply theses theorems to perform matrix-matrix multiplications, by simply de- composing them in several matrix-vector multiplications. For instance, in Equation (I7). p the matrix aL could be (At)" and the different vectors would be each column of gyt The global running time to perform quantumly Equation (17 is obtained by replacing H(V) by sl( (y(+)))) + m(A") and k(V) ec by <((AT)T. 5y(4r) ). Likewise, for Equation (18) we have nu( ( + FF) and nel (( (F+)T).
OC
dc
Note that the dimension of the matrix doesn't appear in the running time since we tolerate a Eoo norm guarantee for the error, instead of & guarantee (see Section G for details). The reason why loo tomography is the right approximation here is because the result of these linear algebra operations rows of the gradient matrices, that are not vectors in an euclidean space, but series of numbers for which we want to be 8-close to the exact values. See next section for more details.
It is a open question see if one can apply the same sub-sampling technique as in the forward pass (Section D.I. and sample only the highest derivatives of ac ØxT, to reduce the computation cost while maintaining good optimization. We then have understand which elements of OC to zero to take into account the effects the non linearity, tomography and pooling.
ax*4T must be set
F.2.2 QUANTUM NON LINEARITY AND TOMOGRAPHY
To include the impact of the non linearity, one could apply the same rule in (19). and simply replace ReLu by capReLu. After the non linearity, we obtain ((x+t) and the gradient relation would be given by
26

---

Published as a conference paper at ICLR 2020
Oc
oc Los(x otherwise
if0 S X X fetti SC
(22)
0x jett s de+1
an element of X was negative or bigger than the cap C, its derivative should be zero during the backpropagation. However, this operation quantum algorithm, one cannot record at which positions (it+1 ( df+1) the activation function was selective or not. The gradient relation (22) cannot be implemented posteriori. We provide a partial solution to this problem, using the fact that quantum tomography must also be taken into
performed in quantum superposition. In the
account for some derivatives. Indeed, only the points (i++1, , d)+1) that have been sampled should have an impact on the gradient of the loss. Therefore we replace the previous relation by
ac
(xx+ p g0+1, (oftt,jj+t dl+1) was sampled
(23)
OX T+T
0 otherwise
jet fett
Nonetheless, we can argue that this approximation will be tolerable. In the first case where E+1
X X,e+1, jeet1,et1,
the derivatives can be set zero as they should. But in practice, their values will be zero after the activation function and such points would not have a chance to be sampled. In
conclusion their derivatives would be zero as required. In the other case, where f++
(4+1,jt-1,d" _ > C,
the derivatives can not be set to zero as well but the points have high probability of being sampled. Therefore their derivative will remain unchanged, as we were using a ReLu instead of capReLu. However in cases where the cap C is high enough, this shouldn't be source of disadvantage in practice.
E.2.3 QUANTUM POOLING
From relation
we can take into account the impact of quantum pooling (see Section D.2.2 on the derivatives. This case is easier since one can record the selected positions during the QRAM update. Therefore, applying the backpropagation is similar to the classical setting with Equation 20
23
OC 0x++I
ac e Jer jets Jo1
if (itt1, jetz dl+2) was selected during pooling
g+1 (0+1 ar+1
0 otherwise
(24)
Note that know कズ is equal - the gradient with respect the input of layer E+ 1,
8C
8C
known by assumption and stored in the QRAM.
E.3 CONCLUSION AND RUNNING TIME
Oc In conclusion, given øy in the QRAM, the quantum backpropagation first consists in applying the relations (24) followed by (23). The effective gradient now take into account non linearity, tomography and pooling that occurred during layer f. We can know use apply the quantum algorithm for matrix-matrix multiplication that implements relations (88 and (17).
Note that the steps in Algorithm could also be reversed: during backpropagation of layer + 1, 8C when storing values for each elements of σytи in the QRAM, one can already take into account
24 and (3 of layer f. In this case directly store ax at supplementary cost.
dc
Therefore, the running time of the quantum backpropagation for layer given as Algorithm 2 corresponds to the sum of the running times of the circuits for implementing relations 17 and 18) We finally obtain
27

---

Published as a conference paper at ICLR 2020
O (((u(A)) + u ))trr)) which can be rewritten
x((AA) gytT) + (el of + #((F)) ni pl (FF))T)
lon 1
OL o (((M(A)) 1L () kl (FF) (oyret)++(F Nl( ) ) log 1/8
OL
aL
(25)
82
Oc Besides storing ax. the main output is a classical description of DC 7F necessary to perform gradient
descent of the parameters of Fe. In the Appendix (Section [.4). which details the impact of the quantum backpropagation compared to the classical case, which can be reduced to simple noise addition during the gradient descent.
E.4 QUANTUM GRADIENT DESCENT AND CLASSICAL EQUIVALENCE
In this part we will see the impact of the quantum backpropagation compared to the classical case, which be reduced to simple noise addition during the gradient descent. Recall that gradient descent, in our case, would consist in applying the following update rule F +- -F > OFT with the learning rate A.
ac and its elements Zs.q = Let's note x aF
Oc From the first result of Theorem F.7 with
aF..
error 0, and the tomography procedure from Theorem G.I with same error ö, we can obtain classical description of with Z norm guarantee, such that:
[
σ |
5
in time Ō( (VV))(V)) log(o)) (( 82 I, as explained in Section
where we note V is the matrix stored in the QRAM that allows to obtain
E.2 The lo norm tomography is used so that the error is at most the
same for each component
Es.g
Es.q
V(s, q),
5
|
|||||
From the second result of the Theorem same error 8, such that
F.7
we can also obtain an estimate | of the norm, for the
||ا|| - ||0|||| S 8 ||0||
in time Ō xV) log(d)) (which does not affect the overall asymptotic running time). Using both results obtain unnormalized state close to ær such that, by the triangular inequality
8
2
J
||
||>0
00
|
T
||0|||
+
||>|||
x
|
| 2
|
||=|||
+
||0||2
IF
x
|
||
< ~111=11 + ||=||,
28
||>|||
in time (e In conclusion, with foo norm guarantee, having also access to the norm of the result is costless.
Finally, the noisy gradient descent update rule, expressed as Ft. + Ft. a.n the worst case with
OC
can written in
OFF
Oc
OL
0L
OF +
25
(26)
OF 5.g
OF
s.g
To summarize, using the quantum linear algebra from Theroem Theroem G. both with error ö, along with norm estimation with relative emror too, we can obtain classically the unnormalized values OFT such that
F.7 with too norm tomography from
ac
9C. aF
26
ll or equivalently
OFT
JL
0c
ac
((s.g),
28
(27)
OFt
OE 8.g
0
5.g
28

---

Published as a conference paper at ICLR 2020
Therefore the gradient descent update rule in the quantum case becomes Fb. which in the worst case becomes
F
>
ac
NOF!
Fr. -> (x
(10C OFF + 25
ac OF
Fd 2.9
(28)
This proves the Theorem F.1 This update rule can simulated by the addition of a random relative noise given a gaussian centered on O, with standard deviation equal to 6. This is how we will simulate quantum backpropagation in the Numerical Simulations.
Compared to the classical update rule, this corresponds to the addition of noise during the optimiza- BC tion step. This noise decreases as 0F 1|. which expected to happen while converging. Recall that the gradient descent is already stochastic process. Therefore, expect that such noise, with acceptable values of ó, will not disturb the convergence the gradient, as the following numerical simulations tend to confirm.
APPENDIX F PRELIMINARIES IN QUANTUM INFORMATION
We introduce basic and broad-audience quantum information background necessary for this work. For a more detailed introduction we recommend Nielsen & Chuang 2002a).
F.1 QUANTUM INFORMATION
Quantum Bits and Quantum Registers: The bit the most basic unit of classical information. It can be either in state O or 1. Similarly a quantum bit qubir, is quantum system that can be is state 10). [1} (the braket notation 1-) is a reminder that the bit considered a quantum system) or in superposition of both states [0} + 8 [1) with coefficients 3 E IC such that |a|2 + |8| = 1. The amplitudes a and / are linked to the probabilities observing either or 1 when measuring the qubit, since P(0) |a|2 and P(1) [/]22.
Before the measurement, any superposition possible, which gives quantum information special abilities in terms of computation. With qubits, the 2" possible binary combinations can exist simultaneously. each with a specific amplitude. For instance we can consider an uniform distribution Vn - (6) where (i) represents the 7th binary combination (e.g. |01.... ... 1001)). Multiple qubits together are often called a quantum register.
In its most general formulation, quantum state with n qubits can be seen as vector in complex Hilbert space of dimension 2". This vector must be normalized under Eg-norm, guarantee that the squared amplitudes sum to 1.
To process qubits and therefore quantum registers, we use quantum gates. These gates are unitary operators in the Hilbert space as they should map unit-norm vectors to unit-norm vectors. Formally, we can see quantum gate acting on n qubits as a matrix E C² such that Uut Utū I, where Ut is the conjugate transpose of U. Some basic single qubit
Quantum Computation:
gates includes the NOT gate (i
1 )) that inverts (0) and []), or the Hadamard gate 1 (1
that maps 10) + /
(10) + 1)) and [1) + J (10) - (1)), creating the quantum superposition.
Finally, multiple qubits gates exist, such the Controlled-NOl -OT that applies NOT gate target qubit conditioned on the state of a control qubit.
The main advantage of quantum gates is their ability to be applied to superposition of inputs. Indeed, given gate such that U (z) + lf(x)) we can apply it to all possible combinations once U Σ. (x)) t E. lf()))
We now state some primitive quantum circuits, which we will use in our algorithm:
For two integers i and j, For two real value numbers a > and > O, we can compare them using (a) (6) (0) la) (5) I(a & 6)). Finally, for real value numbers > can obtain its square (n) |0) (a))
check their equality with the mapping (t) (y) |0) + (t) ()) li 2))-
29

---

Published as a conference paper at ICLR 2020
Note that these circuits are basically reversible version of the classical ones and are linear in the number qubits used to encode the input values.
F.2 QUANTUM SUBROUTINES FOR DATA ENCODING
Knowing some basic principles of quantum information, the next step is to understand how data be efficiently encoded using quantum states. While several approaches could exist, we present the most common one called amplitude encoding, which leads to interesting and efficient applications.
Let x E Rdd be a vector with components (F1, ,T))- Using only [log(d) qubits, we can form (z). the quantum state encoding given by (a) Т Σド= 4, (j).. We see that the jth component Iÿ becomes the amplitude of [j). the jth binary combination (or equivalently the jth vector in the standard basis). Each amplitude must be divided by ||>>|| to preserve the unit 2y-norm of (x).
Similarly, for a matrix A E RRnd or equivalently for n vectors A, for i E [n]]. we can express each row of A as [A,) || E Asj lj)-
We can explain important definition, the ability to have quantum access matrix. This will be a requirements for many algorithms.
Definition 4 [Quantum Access to Data]
We say that we have quantum access to matrix A [gaxd if there exist procedure to perform the following mapping, for i E [n], in time T:
<)) 0) |2) IA.))
(0) - Σ. |A
By using appropriate data structures the first mapping can be reduced to the ability to perform a mapping of the form [t) ( (0) + (t) 15) (Azz). The second requirement be replaced by the
ability of performing i) (0) + }2) ||lll or to just have the knowledge of each norm. Therefore, makes it simpler obtain the quantum
using matrices such that all rows A, have the
access.
The time complexity T necessary for the quantum access can be reduced polylogarithmic dependence in and d if we consider the access to a Quantum Memory or QRAM. The QRAM Kerenidis & Prakash (2017a) is specific data structure from which quantum circuit can allow quantum access to data in time O(log (nd)).
Theorem F.1 (QRAM data structure, see Kerenidis & Prakash (2017))) Let A E Raxd there is data structure store the rows of A such that,
1. The time to insert, updute or delete single entry Aij is Olog((n))
2. A quantum algorithm with access to the data structure can perform the following unitaries in time T = =Ologg n).
(a) { 0 - (2) (A,) for foric [n]. (b) (0) Eie(a] |A:|] (i).
We now state important methods for processing the quantum information. Their goal is to store some information alternatively in the quantum state's amplitude or the quantum register as a bitstring.
Theorem F.2 [Amplitude Amplification and Estimation Brassard et al. (2002) Given a unitary operator U such that U : 10) + yP y) [0) + /1 plu-t) (1) in time T, where >> 0 is the probability of measuring "0", it is possible obtain the state ly) ()) using O v queries U, or estimate p with relative error 8 using O (pp)) queries to U.
Theorem F.3 (Conditional Rotation] Given the quantum state la), with a E [-1,1], it possible perform (a) (0) (a) (a (0) v (1)) with complexity Õ(1).
30

---

Published as a conference paper at ICLR 2020
Using Theorem
F3 followed by Theorem F2 it then possible transform the state
va 2==0 (mz))
into ||||| Σソ= (.).
In addition to amplitude estimation, we will make use of tool developed Wiebe et al. (2014a) to boost the probability of getting good estimate for the inner product required for the quantum convolution algorithm. In high level, we take multiple copies of the estimator from the amplitude estimation procedure, compute the median, and reverse the circuit to get rid of the garbage. Here provide a theorem with respect to time and not query complexity.
Theorem F,4 (Median Evaluation, see Wiebe et al. 2014a)) Let U be a unitary operation that maps
u: 100) + 1a, vi
for some 1/2 < a S 1 in time T. Then there exists quantum algorithm that, for any A 0 and for any 1/2 ag S a. produces state (V) such that | - 100010 [z)) || I /2A for some integer L, time
In(1/A)
2T
2 (laol 2
F.3 QUANTUM SUBROUTINES FOR LINEAR ALGEBRA
In the recent years, as the field of quantum machine learning grew, its "toolkit" for linear alge- bra algorithms has become important enough allow the development of many quantum machine learning algorithms. We introduce here the important subroutines for this work, without detailing the circuits or the algorithms.
Definition 5 For a matrix A, the parameter p(A) is defined by ((A) where sy(A) mlx:(])A:))))..
minpe(o.1] (IAll / (2))())))
The next theorems allow to compute the distance between vectors encoded as quantum states, and use this idea to perform the k-means algorithm.
Theorem E. [Quantum Distance Estimation Wiebe et al. (2014b), Kerenidis et al. (2019)) Given quantum access in time T is a quantum algorithm that, for any pair (i,j), performs the following mapping (i) l5) 10) + (i) 1)) (Us, v;)),, estimating the euclidean distance between un and vj with precision (f((u, U/) d (u,, 0z)l S E for any e > 0. The algorithm has a running time given by Ö(Tn/e), where max: (I]ugll [[u,]]), assuming that min; min:((]u:]])) = min, (Ilus)) 1.
matrices U and V with rows u; and Vj of dimension d, there
Theorem F.6 (Quantum k-means clustering Kerenidis et al. (219))
Given quantum access in time to a dataset V E kanx there a quantum algorithm that outputs with high probability lo centroids -1, .Ck that are consistent with the output of the k-means algo-
rithm with noise 8 >> 0, in time Ö(T x (V) x(V)((V) + ()(() ) + 1.2 n(V) iteration.
<(V))((V)) per
82
Definition 6 For a matrix V E Raxd its parameter 77() is defined as as m|xx((| assuming min, min]((]
max, mine[l]u or as
In theorem [6 the other parameters in the running time can be interpreted as follows 8 is the precision in the estimation of the distances, but also in the estimation of the position of the centroids. x(V) is the condition number of V and μ(V) is defined above (Definition 5). Finally, in the case of well clusterable datasets, which should be the case when we will apply k-means during spectral
clustering, the running simplifies to Ö(T x (2222 33 2..5
Note that the dependence in n is hidden in the time to load the data. This dependence becomes polylogarithmic in n if assume access QRAM.
31

---

Published as a conference paper at ICLR 2020
Chaakbbon et al. (2018) Let M Raxd and I E Rd. Let 51, 62 > If M is stored in appropriate QRAM data structures and the time to
Theorem F.7 (Quantum Matrix Operations, Chakraborty
prepare (x) is Tz, then there exist quantum algorithms that with probability least 1 - 1/plly(d) return
1. A state 12) such that [||z) - || & 81 in time Note that this also implies |||=) Mx Sn
2. Norm estimate 2 E (1 62) ||M with relative error 82. time Ö(T, ((M))((M)) log(1/61)).
The linear algebra procedures above also be applied any rectangular matrix V Raxd by considering instead the symmetric matrix V VT
0
APPENDIX G ALGORITHM AND PROOF FOR foo NORM TOMOGRAPHY
Finally, we present a logarithmic time algorithm for vector state tomography that will be used to re- cover classical information from the quantum states with &o norm guarantee. Given a unitary that produces quantum state (z) | Ed-1 Ij (j). by calling Ollog d/6²) times U, the tomography
algorithm is able to reconstruct vector X that approximates (a) with & norm guarantee, such that (X) | S 6, or equivalently that Vi E [d] x;; X,1 s 6. Such a tomography is of interest when the components 2; of a quantum state are not the coordinates of an meaningful vector some linear space, but just series of values, such that don't want overall guarantee on the vector (which the case with usual lz tomography) but a similar error guarantee for each component in the estimation.
Theorem G.1 (Coo Vector state tomography) Given access unitary U such that U (x) and its controlled version in time TU)), there is a tomography algoritium with time complexity O(T(U) d that produces unit vector X E Rd such that (1 (1p/ppoyydd).
x
< 5 with probability at least
The proof of this theorem is similar to the proof of the fnrn tomography by Kerenidis & Prakash 20188. However the lo norm tomography introduced in this paper depends only logarithmically and not linearly in the dimension d. Note that in our case, T(') will be logarithmic in the dimension.
Theorem G.2 [L2 Vector state tomography Kerenidis & Prakash (2018)] Given access to unitary U such that U (0) = {x) and its controlled version in time TÚU), there is an algorithm that allows X x 1||
to outpul classical vector X E IRd with f--norm guarantee
< for any ō >> 0, in time
O(T(U) dogg(d)
In the following we consider a quantum state (x) Exelaj Ts [i), with a Rdd and ||0|||2
The following version of the Chernoff Bound will be used for analysis of algorithm
Theorem G.3 (Chernoff Bound) Let Xz. for E [N], be independent random variables such that X, [0, 1] and let X Eje(n) Xz. We have the three following inqualities:
1. For 0 < 3 1 (1 3] < PPX[X/2
0 (1 + x < e 1 [|
2. For
3. For 0 < P| E
3E| $ PEE by composing 1. and 2.
32

---

Published as a conference paper at ICLR 2020
Algorithm 3 Lo norm tomography
Require: Error > 0, access to unitary U 10) + (x) = Lie(ag 2i (t),
the controlled version of U,
QRAM access.
Ensure: Classical vector X E IR such that x
1 and | x 5.
1: Measure N
I6 copies of (z) in the standard basis and count nı, the number of times the 8
outcome is observed. Store yPi /na/N in QRAM data structure.
2: Create N
36 copies of state 72 _ (0} Eield 2h (x) + Vz (T) Eield vPi 10).
8"
3: Apply an Hadamard gate on the first qubit to obtain
(0) = Σ ((x, + vp:) 0, + (I,- /p:) 11, 2
LE|d]
4: Measure both registers of each copy in the standard basis, and count n0,, i) the number of time the outcome (0, i) is observed.
5: Set (i)) +1 if n0, i) > 0.4Np, and (2) = -1 otherwise.
6: Output the unit vector X such that Vi E [N], X₁ di /P:
Theorem G.4 Algorithm 3 produces an estimate X Rd such that X x
< (1+ 22) with
probability at least
70.83
Proving | - x I O()) is equivalent to show that for all i E [d]. we have |x; - -X,1 [c.
pP) S (5). Let S be the set of indices defined by 5 = {i E [d]: |aaa > 5}. We will separate the proof for the two where i and & S.
Case I:
We will show that if E S, we correctly have oii) sgn(x;) with high probability. Therefore we will need to bound [r, (i) = ||=,|| -Pal.
We suppose that r; 0. The value of aii) correctly determines sgn(æ,) ) if the number of times we have measured (0, i) at Step 4. is more than half of the outcomes, iee. n00, i) > (0, i)]. I, < O, the same arguments holds for n11, i). We consider the random variable that represents the outcome of a measurement on state (Ø). The Chernoff Bound, part with 3 = 1/2 gives
(0, i) < B|n(0, i)]] S -B/(0,0]]/
(29)
From the definition of (d) we have B[n(0, i)] = 2 (a. + 3 We will lower bound this value with the following argument.
For the h measurement of (r),, with & E [N], let X be a random variable such that X₃ = if the outcome i, and otherwise. We define X Exe(Ny Xg. Note that X n, Np, and E[X] Nxf. We can apply the Chernoff Bound, part 3 on X for 3 = 1/2 to obtain,
P - E 2 E[x]/2] < -[X]/12 -
(30)
F|l2 - pvl 1 / 11
We have N
36 Ind and by assumption x? > 82 (since E S). Therefore,
PP pil 2 / <e
36 In d/12 1/d
33

---

Published as a conference paper at ICLR 2020
This proves that the event | pil 1 x2/2 occurs with probability at least 1 de if E S. This previous inequality is equivalent to /2p:/3 & | S /2,.. Thus, with high probability we have E/n(0, i)] = - (z4 + vpi)² 2 0.82.pp,, since 2 < | Moreover, since Ip S xf/2, ([n a)] 2 0. 0.82N2 14.7 d. Therefore, equation equation 29 becomes
Pln(O, 1) S 0.41Np e--183lne 1/d
We conclude that for E S, if (00, i) > 0.41Nps, the sign of x is determined correctly by o()) with high probability 2t.33, as indicated in Step 5.
We finally show | - (1) ||r /pal is bounded. Again by the Chernoff Bound (3.) we have, for 1:
P|[a, pal 2 Bxy) I Na2/33
By the identity |x] pal (1ra) vps)
vp:) we have
x
[zi /ps
2 5 | + Vis
S c No
Since vPr > O, we have 8 27
S 1 |zs B|as|, therefore IP ||as| vps 2 g|aal s
/z.l-vpi
B N2N2/13, Finally, by chosing B 6/ | < 1 we have
P 1
Vp
8 S 361nd/3 1/d
We conclude that, if S, we have |2; - X21 < 8 with high probability.
Since |S| & d, the probability for this result to true for all E S is 1 5.53. This can be proved by using the Union Bound on the correctness of (i).
Case i i S.
If $ S, we need to separate again in two cases. When the estimated sign is wrong, i.e. (i) -agn(x;), we have to bound Iz; (i) /p. = || + Pil. On the contrary, if it is correct, i.e.
(i) (x;) we have bound [z] (1)) / P || one hound is necessary.
Vpl
S || + vP.l. Therefore only
We use Chernoff Bound (2.) on the random variable with B > 0 to obtain
P(p > (1 B)x < e2ry Na
22
#4
We chose 3 = //// and obtain P(p; > x: + <
538 = 1/d Therefore, if & S, with very
high probability 1 diz we have p; < x + 82 $ 28
We can conclude and bound the error:
x X, S ||
pi
< 8 25 (1 v2)6
Since |S| < d, the probability for this result to be true for all & S is gi This follows from
applying the Union Bound on the event p; x? + 82.
34

---

Published as a conference paper at ICLR 2020
APPENDIX H ADDITIONAL NUMERICAL SIMULATIONS
Thiiinn curves for e=0.01, C=10.0, 6=0.01
Trainnn curves for e=0.01, C=10.0, d=0.1
CNN
CNN
QCNN a-015
QCXN.
QCNN e-0.
1.5
1.5
QCNN a-03
QCNN mm02
QCNN..=011
QUNN
1.0
1.3
0.5
20000
40000
00000
8000
100000
13000
20000
0000X
60000
3000
100000
1200000
Decallime
leecaloos
Training mivee for e=111 C=10.0, 6=0.1
Training curves for e=0.1. C- 10.0. 6=0.01
CNN
CNN
2.0
2.0
QCNN am05
Q020N
QCNN m-0.44
QC20
1.5
QCNN 0-03
QCNN o-30
QCNN o-.01
0.0
100000
Iterations
Iterations
Training for e=0.01, C=2.0, 6=0.01
Training for c=0.01, C=2.0, 8-0.1
CNX
CNX
QCNN
QCNN
QCNN a-
1.5
QCNN.a-03
1.5
QCNN
QCNN:
QUNN ow02
Q0NN..=01
QCNN
1.0
1.3
0.5
0.0
20000
40000
60000
80000
100000
120000
0.0 20000
5000
60000
80000
100000 120000
Itorations
Iteratims
Figure 9: Numerical simulations of the training of the QCNN. These training curves represent the evolution of the Loss as we iterate through the MNIST dataset. For each graph, the amplitude estimation error (0.1, the non linearity cap C. (2, 10), and the backpropagation error 5 (0.1, 0.01) are fixed whereas the quantum sampling ratio a varies from 0.1 to 0.5. We can compare each training curve the classical learning (CNN). Note that these training curves are smoothed, over windows of 12 steps, for readability.
In the following we report the classification results of the QCNN when applied on the test set (10.000 images). We distinguish use cases: in Table the QCNN has been trained quantumly as described in this paper, whereas in Table first have trained the classical CNN, then transferred the weights to the QCNN only for the classification. This second use case has global running time worst than the first one, but we see it as another concrete application: quantum machine learning could be used only for faster classification from a classically generated model, which could be the case for high rate classification task (e.g. for autonomous systems, classification over many simultaneous inputs). We report the test loss and accuracy for different values of the sampling ratio the amplitude estimation error e, and for the backpropagation noise å in the first case. The cap C fixed at 10. These values must compared to the classical CNN classification metrics, for which the loss is 0. 129 and the accuracy is 96. %. Note that used relatively small CNN and hence
35

---

Published as a conference paper at ICLR 2020
the accuracy is just over 96%, lower than the best possible accuracy with larger CNN.
QCNN Test Classification
6
0.01
0.1
0
0.01
0.1
0.01
0.1
Loss
0.519
0.773
2.30
2.30
0.1
Accuracy
82.8%
74.8%
11.5%
11.7%
Loss
0.334
0.348
0.439
1.367
0.2
Accuracy
89.5%
89.0%
86.2%
54.1%
Loss
0.213
0.314
0.381
0.762
0.3
Accuracy
93.4%
90.3%
87.9%
76.8%
Loss
0.177
0,215
0.263
1.798
0.4
Accuracy
94.7%
93.3%
91.8%
34.9%
Loss
0.142
0.211
0.337
1.457
0.5
Accuracy
95.4%
93.5%
89.2%
52.8%
Table 4: QCNN trained with quantum backpropagation MNIST dataset. With C. 10 fixed.
QCNN Test - Classification
0.01
0.1
Loss 1.07
1.33
0.1
Accuracy 86.1% 1%
78.6%
Loss 0.552
0.840
0.2
Accuracy 92.8%
86.5%
Loss 0.391
0.706
0.3
Accuracy
94,3%
85.8%
Loss 0.327
0.670
0.4
Accuracy
94.4%
84.0%
Loss 0.163
0.292
0.5
Accuracy
95.9%
93.5%
Table 5: QCNN created from a classical CNN trained on MNIST dataset. With 5 0.01 and
C' = 10 fixed.
36


Reviews:
[{"review_id": "SylabRM85H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors provide a comprehensive study, with theory and classical simulation of the quantum system, on how to increaese the speed of CNN inference and training using qubits. They proved an intrigued compilation of a quantized convolutional system.  \n\nFor an audiance who are not quantum experts one could clarify a few properties of the described \"quantization\".  It is not able to take multiple images in at the same time as quantum superpositions. Sometimes the expectence of a quantum machine leanring is that it would train the system at a single instance. Here the increase in effciency comes from being able to perform marix multiplication in quantum realm.\n\n The manuscripd describes a creative way to bring bolean operartions-defined non-linearities into quantum neural networks, at the cost of having to force the system back to classical domain at each layer - and then encoding it back to qubits for the next layer operations. The price has to payed as unitary operators  (the ones that preserve entaglement) are inherently linear.\n\nRemarks:\nThe authors should point out how this is specific to convolutional neural networks. It looks to me that the same algorithm could be used for fully connected or even attention based systems, as it is just a matrix multiplication as well. Anyway, the manuscript provides the take into account the steps required specifically for a CNN.\n\nSome minor remarks:\nFor classical systems the capped Relu is inferior as it reduces the range of values of activations where there is driving force. Sometimes one is using a parametrized version of ReLU that has a small positive slope for negative values.\nIt is not clear to me how this would not be the case with a quantum implementions. In your simulations, does the value of the saturation constant C, change the speed of convergence to a good solutions. \n\nThe capped Relu reminds me a lot of a Tanh non-linearity  that works well for LSTMs but are not very good for CNNs.\n\nI would suggest that for the conference presentation the authors try to bring out the essential within a less formal setting to open it to a wider ML audience.  For the manuscript the level is good with a proper use of appendix to shorten the main narrative.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SyeOQqnPqB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission proposed a quantum convolutional neural network (QCNN). The theoretical results in section 3 state the existence of the QCNN satisfying certain conditions. The QCNN is given by sections 4 and 5, with empirical evaluates in section 6. This subject is out of my usual area. However, I tend to think this subject is interesting to the ICLR audience due to the recent advancement in quantum computing.\n\ntitle, remove \"conference submissions\"\n\nSection 2, introduce QRAM.\n\nSomewhere around section 2-3, and in section 6, it has to be mentioned whether the proposed QCNN requires special hardware, and what is the hardware, and why it is required.\n\nNote the cited Cong et al. (2018) has been published in nature physics. As you both used the term \"QCNN\", it is better to explain more clearly what is the main difference in the main text.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "S1g6EebaKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a quantum version of the convolutional neural networks. They derive equivalent versions the computation of both the convolution operation and the back-propagation in the quantum computing framework. The authors claim a potential exponential speed up in the computation in the size of the kernel which would make possible to process much bigger inputs or just speed up current tasks involving images mainly. They exemplify the method on MNIST using quantum artifacts simulation using PyTorch and show their method is competitive with SoA.\n\nI think the paper is well written and provides a nice discussion about how quantum computing can be applied to CNNs. I appreciate that both the forward and backward passes are studied although most of the technical details are in appendices. So, I felt the paper  itself was a bit optimistic about the impact of quantum computing on CNNs.\n\nEspecially, I found the experimental section was missing details. I am not a quantum computing expert but I was a bit surprised that, in the context of CNNs, the introduction of quantum noise was just considered as introducing noise in the image and the gradient and then applying normal CNNs to the resulting image. Standard CNNs can probably deal with such noise and noisy gradient descent is not a big issue as such (it can even avoid local minima). But CNNs are notoriously known to reduce the number of weights in a network because of weight sharing. So, it is not all about making one convolution faster but also to compute invariant representations by sharing weights over different parts of the inputs. I would have been interested by a discussion about how quantum noise may impact this property and I didn't find this in the paper nor the appendices. \n\nAlso the author confess that the learning is not stable and results on MNIST to be the best they could get. I think it would be worth testing on large scale problems and see whether larger kernels with such noisy conditions would really improve the performance. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklnChipKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a quantum algorithm for approximating the forward pass and gradient computation of a classical convolutional neural network layer with pooling and a bounded rectifier activation. This algorithm has complexity bounds that would open up (for instance) the possibility of exponentially large filter banks, and the authors show through a simple, classical simulation approach that the resulting network is also likely to be trainable.\n\nFeedback:\n\nA few typos/formatting issues:\n- The title accidentally includes \"Conference Submissions\"\n- The in-text citation format frequently has the parentheses in the wrong place; this is surprisingly distracting!\n\nPreliminaries:\n- Maybe explain what the ith vector in the standard basis is in terms of |0> and |1>? I assume the answer is along the lines of |000>, |001>, |010>, etc.?\n\nMain results:\n- The sentence \"a speedup compared to the classical CNN for both the forward pass and for training using backpropagation in certain cases\" is ambiguous; does \"in certain cases\" qualify only training speed or also forward pass speed?\n\n- There's a clear separation of background (which is concise and well explained) and contributions, but maybe it would be worth connecting the introduced algorithm more closely to existing work in non-convolutional quantum neural networks?\n\n- Can you briefly justify (or cite) the claim that \"most of the non linear functions in the machine learning literature can be implemented using small sized boolean circuits\"?\n\n- I'm a little confused about the discussion of quantum importance sampling on page 4. Could you give some intuition for the relationship between eta and the fraction of output values that are on average flushed to zero (is this 1 minus sigma?), and perhaps connect this to the literature about activation pruning and sparse NNs?\n\n- Maybe define what you mean by \"tomography\" for ML folks without the quantum background?\n\n- I'm convinced by the simulations, even though I shouldn't really be convinced by anything on MNIST... It just seems like the perturbations you're applying are all things that modern neural networks take in stride.\n\n- The discussion of using a sigma-based classical sampling rather than the eta-based quantum importance sampling mentions a \"Section C.1.15\" which does not exist (I think you mean the end of Section C.1.5).\n\n- Re: \"We will use this analogy in the numerical simulations (Section 6) to estimate, for a particular QCNN architecture and a particular dataset of images, which values of σ are enough to allow the neural network to learn.\" My understanding is that you're getting empirical estimates of which values of sigma are enough; it would be valuable to convert those to estimates of which values of eta would be enough (given quantum networks of the size used in the classical simulation experiment, or given larger networks).\n\n- The sampling procedure based on sigma might be inefficient in your PyTorch implementation, but it's certainly something that GPUs are fairly well suited to computing. There might be other PyTorch operators that would help here (perhaps Bernoulli sampling?) or if nothing else you could write a small custom CUDA kernel.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four reviewers have assessed this paper and they have scored it as 6/6/6/6 after rebuttal. Nonetheless, the reviewers have raised a number of criticisms and the authors are encouraged to resolve them for the camera-ready submission. Especially, the authors should take care to make this paper accessible (understandable) to the ML community as ICLR is a ML venue (rather than quantum physics one). Failure to do so will likely discourage the generosity of reviewers toward this type of submissions in the future.
Decision: Accept (Poster)