Abstract:
We develop a new quantum neural network layer designed to run efficiently on a quantum computer but that can be simulated on a classical computer when restricted in the way it entangles input states. We first ask how a classical neural network architecture, both fully connected or convolutional, can be executed on a quantum computer using quantum phase estimation. We then deform the classical layer into a quantum design which entangles activations and weights into quantum superpositions. While the full model would need the exponential speedups delivered by a quantum computer, a restricted class of designs represent interesting new classical network layers that still use quantum features. We show that these quantum deformed neural networks can be trained and executed on normal data such as images, and even classically deliver modest improvements over standard architectures.

text: We develop a new quantum neural network layer designed to run efficiently on a quantum computer but that can be simulated on a classical computer when restricted in the way it entangles input states. We first ask how a classical neural network architecture, both fully connected or convolutional, can be executed on a quantum computer using quantum phase estimation. We then deform the classical layer into a quantum design which entangles activations and weights into quantum superpositions. While the full model would need the exponential speedups delivered by a quantum computer, a restricted class of designs represent interesting new classical network layers that still use quantum features. We show that these quantum deformed neural networks can be trained and executed on normal data such as images, and even classically deliver modest improvements over standard architectures.

heading: 1 INTRODUCTION
text: Quantum mechanics (QM) is the most accurate description for physical phenomena at very small scales, such as the behavior of molecules, atoms and subatomic particles. QM has a huge impact on our every day lives through technologies such as lasers, transistors (and thus microchips), superconductors and MRI.
A recent view of QM has formulated it as a (Bayesian) statistical methodology that only describes our subjective view of the (quantum) world, and how we update that view in light of evidence (i.e. measurements) (;t Hooft, 2016; Fuchs & Schack, 2013). This is in perfect analogy to the classical Bayesian view, a statistical paradigm extensively used in artificial intelligence where we maintain probabilities to represent our beliefs for events in the world.
The philosophy of this paper will be to turn this argument on its head. If we can view QM as just another consistent statistical theory that happens to describe nature at small scales, then we can also use this theory to describe classical signals by endowing them with a Hilbert space structure. In some sense, the ’only’ difference with Bayesian statistics is that the positive probabilities are replaced with complex ’amplitudes’. This however has the dramatic effect that, unlike in classical statistics, interference between events now becomes a possibility. In this paper we show that this point of view uncovers new architectures and potential speedups for running neural networks on quantum computers.
We shall restrict our attention here to binary neural networks. We will introduce a new class of quantum neural networks and interpret them as generalizations of probabilistic binary neural networks, discussing potential speedups by running the models on a quantum computer. Then we will devise classically efficient algorithms to train the networks for a restricted set of quantum circuits. We present results of classical simulations of the quantum neural networks on real world data sizes and related gains in accuracy due to the quantum deformations. Contrary to almost all other works on quantum deep learning, our quantum neural networks can be simulated for practical classical problems, such as images or sound. The quantum nature of our models is there to increase the flexibility of the model-class and add new operators to the toolbox of the deep learning researcher, some of which may only reach their full potential when quantum computing becomes ubiquitous.

heading: 1.1 RELATED WORK
text: In Farhi & Neven (2018) variational quantum circuits that can be learnt via stochastic gradient descent were introduced. Their performance could be studied only on small input tasks such as classifying 4 × 4 images, due to the exponential memory requirement to simulate those circuits. Other works on variational quantum circuits for neural networks are Verdon et al. (2018); Beer et al. (2019). Their focus is similarly on the implementation on near term quantum devices and these models cannot be efficiently run on a classical computer. Exceptions are models which use tensor network simulations (Cong et al., 2019; Huggins et al., 2019) where the model can be scaled to 8×8 image data with 2 classes, at the price of constraining the geometry of the quantum circuit (Huggins et al., 2019). The quantum deformed neural networks introduced in this paper are instead a class of variational quantum circuits that can be scaled to the size of data that are used in traditional neural networks as we demonstrate in section 4.2.
Another line of work directly uses tensor networks as full precision machine learning models that can be scaled to the size of real data (Miles Stoudenmire & Schwab, 2016; Liu et al., 2017; Levine et al., 2017; Levine et al., 2019). However the constraints on the network geometry to allow for efficient contractions limit the expressivity and performance of the models. See however Cheng et al. (2020) for recent promising developments. Further, the tensor networks studied in these works are not unitary maps and do not directly relate to implementations on quantum computers.
A large body of work in quantum machine learning focuses on using quantum computing to provide speedups to classical machine learning tasks (Biamonte et al., 2017; Ciliberto et al., 2018; Wiebe et al., 2014), culminating in the discovery of quantum inspired speedups in classical algorithms (Tang, 2019). In particular, (Allcock et al., 2018; Cao et al., 2017; Schuld et al., 2015; Kerenidis et al., 2019) discuss quantum simulations of classical neural networks with the goal of improving the efficiency of classical models on a quantum computer. Our models differ from these works in two ways: i) we use quantum wave-functions to model weight uncertainty, in a way that is reminiscent of Bayesian models; ii) we design our network layers in a way that may only reach its full potential on a quantum computer due to exponential speedups, but at the same time can, for a restricted class of layer designs, be simulated on a classical computer and provide inspiration for new neural architectures. Finally, quantum methods for accelerating Bayesian inference have been discussed in Zhao et al. (2019b;a) but only for Gaussian processes while in this work we shall discuss relations to Bayesian neural networks.

heading: 2 GENERALIZED PROBABILISTIC BINARY NEURAL NETWORKS
text: Binary neural networks are neural networks where both weights and activations are binary. Let B = {0, 1}. A fully connected binary neural network layer maps the N` activations h(`) at level ` to the N`+1 activations h(`+1) at level `+ 1 using weights W (`) ∈ BN`N`+1 :
h (`+1) j = f(W (`),h(`)) = τ
( 1
N` + 1 N∑̀ i=1 W (`) j,i h (`) i
) , τ(x) = { 0 x < 12 1 x ≥ 12 . (1)
We divide by N` + 1 since the sum can take the N` + 1 values {0, . . . , N`}. We do not explicitly consider biases which can be introduced by fixing some activations to 1. In a classification model h(0) = x is the input and the last activation function is typically replaced by a softmax which produces output probabilities p(y|x,W ), where W denotes the collection of weights of the network. Given M input/output pairs X = (x1, . . . ,xM ),Y = (y1, . . . ,yM ), a frequentist approach would determine the binary weights so that the likelihood p(Y |X,W ) = ∏M i=1 p(yi|xi,W ) is maximized. Here we consider discrete or quantized weights and take the approach of variational optimization Staines & Barber (2012), which introduces a weight distribution qθ(W ) to devise a surrogate differential objective. For an objective O(W ), one has the bound maxW∈BN O(W ) ≥ Eqθ(W )[O(W )], and the parameters of qθ(W ) are adjusted to maximize the lower bound. In our case we consider the objective:
max W∈BN log p(Y |X,W ) ≥ L := Eqθ(W )[log p(Y |X,W )] = M∑ i=1 Eqθ(W )[log p(yi|xi,W )] . (2)
While the optimal solution to equation 2 is a Dirac measure, one can add a regularization termR(θ) to keep q soft. In appendix A we review the connection with Bayesian deep learning, where qθ(W ) is the approximate posterior,R(θ) is the KL divergence between qθ(W ) and the prior over weights, and the objective is derived by maximizing the evidence lower bound.
In both variational Bayes and variational optimization frameworks for binary networks, we have a variational distribution q(W ) and probabilistic layers where activations are random variables. We consider an approximate posterior factorized over the layers: q(W ) = ∏L `=1 q
(`)(W (`)). If h(`) ∼ p(`), equation 1 leads to the following recursive definition of distributions:
p(`+1)(h(`+1)) = ∑
h∈BN` ∑ W∈BN`N`+1 δ(h(`+1) − f(W (`),h(`)))p(`)(h(`))q(`)(W (`)) . (3)
We use the shorthand p(`)(h(`)) for p(`)(h(`)|x) and the x dependence is understood. The average appearing in equation 2 can be written as an average over the network output distribution:
Eqθ(W )[log p(yi|xi,W )] = −Ep(L)(h(L))[gi(yi,h (L))] , (4)
where the function gi is typically MSE for regression and cross-entropy for classification.
In previous works (Shayer et al., 2017; Peters & Welling, 2018), the approximate posterior was taken to be factorized: q(W (`)) = ∏ ij qi,j(W (`) i,j ), which results in a factorized activation distribution as
well: p(`)(h(`)) = ∏ i p (`) i (h (`) i ). (Shayer et al., 2017; Peters & Welling, 2018) used the local reparameterization trick Kingma et al. (2015) to sample activations at each layer.
The quantum neural network we introduce below will naturally give a way to sample efficiently from complex distributions and in view of that we here generalize the setting: we act with a stochastic matrix Sφ(h′,W ′|h,W ) which depends on parameters φ and correlates the weights and the input activations to a layer as follows:
πφ,θ(h ′,W ′) = ∑ h∈BN ∑ W∈BNM Sφ(h ′,W ′|h,W )p(h)qθ(W ) . (5)
To avoid redundancy, we still take qθ(W ) to be factorized and let S create correlation among the weights as well. The choice of S will be related to the choice of a unitary matrix D in the quantum circuit of the quantum neural network. A layer is now made of the two operations, Sφ and the layer map f , resulting in the following output distribution:
p(`+1)(h(`+1)) = ∑
h∈BN`
∑ W∈BN`N`+1 δ(h(`+1) − f(W (`),h(`)))π(`)φ,θ(h (`),W (`)) , (6)
which allows one to compute the network output recursively. Both the parameters φ and θ will be learned to solve the following optimization problem:
min θ,φ R(θ) +R′(φ)− L . (7)
whereR(θ),R′(φ) are regularization terms for the parameters θ, φ. We call this model a generalized probabilistic binary neural network, with φ deformation parameters chosen such that φ = 0 gives back the standard probabilistic binary neural network.
To study this model on a classical computer we need to choose S which leads to an efficient sampling algorithm for πφ,θ. In general, one could use Markov Chain Monte Carlo, but there exists situations for which the mixing time of the chain grows exponentially in the size of the problem (Levin & Peres, 2017). In the next section we will show how quantum mechanics can enlarge the set of probabilistic binary neural networks that can be efficiently executed and in the subsequent sections we will show experimental results for a restricted class of correlated distributions inspired by quantum circuits that can be simulated classically.

heading: 3 QUANTUM IMPLEMENTATION
text: Quantum computers can sample from certain correlated distributions more efficiently than classical computers (Aaronson & Chen, 2016; Arute et al., 2019). In this section, we devise a quantum circuit
that implements the generalized probabilistic binary neural networks introduced above, encoding πθ,φ in a quantum circuit. This leads to an exponential speedup for running this model on a quantum computer, opening up the study of more complex probabilistic neural networks.
A quantum implementation of a binary perceptron was introduced in Schuld et al. (2015) as an application of the quantum phase estimation algorithm (Nielsen & Chuang, 2000). However, no quantum advantage of the quantum simulation was shown. Here we will extend that result in several ways: i) we will modify the algorithm to represent the generalized probabilistic layer introduced above, showing the quantum advantage present in our setting; ii) we will consider the case of multi layer percetrons as well as convolutional networks.

heading: 3.1 INTRODUCTION TO QUANTUM NOTATION AND QUANTUM PHASE ESTIMATION
text: As a preliminary step, we introduce notations for quantum mechanics. We refer the reader to Appendix B for a more thorough review of quantum mechanics. A qubit is the vector space of normalized vectors |ψ〉 ∈ C2. N qubits form the set of unit vectors in (C2)⊗N ∼= C2 N
spanned by all N -bit strings, |b1, . . . , bN 〉 ≡ |b1〉 ⊗ · · · ⊗ |bN 〉, bi ∈ B. Quantum circuits are unitary matrices on this space. The probability of a measurement with outcome φi is given by matrix element of the projector |φi〉 〈φi| in a state |ψ〉, namely pi = 〈ψ|φi〉 〈φi|ψ〉 = | 〈φi|ψ〉 |2, a formula known as Born’s rule.
Next, we describe the quantum phase estimation (QPE), a quantum algorithm to estimate the eigenphases of a unitary U . Denote the eigenvalues and eigenvectors of U by exp ( 2πi 2t ϕα ) and |vα〉, and assume that the ϕα’s can be represented with a finite number t of bits: ϕα = 2t−1ϕ1α + · · ·+ 20ϕtα. (This is the case of relevance for a binary network.) Then introduce t ancilla qubits in state |0〉⊗t. Given an input state |ψ〉, QPE is the following unitary operation:
|0〉⊗t ⊗ |ψ〉 QPE7−→ ∑ α 〈vα|ψ〉 |ϕα〉 ⊗ |vα〉 . (8)
Appendix B.1 reviews the details of the quantum circuit implementing this map, whose complexity is linear in t. Now using the notation τ for the threshold non-linearity introduced in equation 1, and recalling the expansion 2−tϕ = 2−1ϕ1 + · · · + 2−tϕt, we note that if the first bit ϕ1 = 0 then 2−tϕ < 12 and τ(2 −tϕ) = 0, while if ϕ1 = 1, then 2−tϕ ≥ 12 and τ(2 −tϕ) = 1. In other words, δϕ1,b = δτ(2−tϕ),b and the probability p(b) that after the QPE the first ancilla bit is b is given by:(∑ α 〈vα|ψ〉 〈ϕα| ⊗ 〈vα| )[ |b〉〈b|⊗1 ](∑ β 〈vβ |ψ〉 |ϕβ〉⊗|vβ〉 ) = ∑ α |〈vα|ψ〉|2δτ(2−tϕα),b , (9)
where [ |b〉〈b|⊗1 ] is an operator that projects the first bit to the state |b〉 and leaves the other bits
untouched.

heading: 3.2 DEFINITION AND ADVANTAGES OF QUANTUM DEFORMED NEURAL NETWORKS
text: Armed with this background, we can now apply quantum phase estimation to compute the output of the probabilistic layer of equation 6. Let N be the number of input neurons and M that of output neurons. We introduce qubits to represent inputs and weights bits:
|h,W 〉 ∈ Vh ⊗ VW , Vh = N⊗ i=1 (C2)i , VW = N⊗ i=1 M⊗ j=1 (C2)ij . (10)
Then we introduce a Hamiltonian Hj acting non trivially only on the N input activations and the N weights at the j-th row:
Hj = N∑ i=1 BWji B h i , (11)
and Bhi (B W ji ) is the matrix B = |1〉 〈1| acting on the i-th activation (ji-th weight) qubit. Note that Hj singles out terms from the state |h,W 〉 where both hj = 1 and Wij = 1 and then adds them
up, i.e. the eigenvalues of Hj are the preactivations of equation 1:
Hj |h,W 〉 = ϕ(h,Wj,:) |h,W 〉 , ϕ(h,Wj,:) = N∑ i=1 Wjihi . (12)
Now define the unitary operators:
Uj = De 2πi N+1HjD−1 , (13)
where D is another generic unitary, and as we shall see shortly, its eigenvectors will be related to the entries of the classical stochastic matrix S in section 2. Since UjUj′ = De 2πi N+1 (Hj+Hj′ )D−1 = Uj′Uj , we can diagonalize all the Uj’s simultaneously and since they are conjugate to e 2πi N+1Hj they will have the same eigenvalues. Introducing the eigenbasis |h,W 〉D = D |h,W 〉, we have:
Uj |h,W 〉D = e 2πi N+1ϕ(h,Wj,:) |h,W 〉D . (14)
Note that ϕ ∈ {0, . . . , N} so we can represent it with exactly t bits, N = 2t − 1. Then we add M ancilla resources, each of t qubits, and sequentially perform M quantum phase estimations, one for each Uj , as depicted in figure 1 (a). We choose the following input state
|ψ〉 = |ψ〉h ⊗ M⊗ j=1 |ψ〉Wj,: , |ψ〉Wj,: = N⊗ i=1 [√ qji(Wji = 0) |0〉+ √ qji(Wji = 1) |1〉 ] , (15)
where we have chosen the weight input state according to the factorized variational distribution qij introduced in section 2. In fact, this state corresponds to the following probability distribution via Born’s rule:
p(h,W ) = | 〈h,W |ψ〉 |2 = p(h) M∏ j=1 N∏ i=1 qji(Wji) , p(h) = | 〈h|ψ〉h | 2 . (16)
The state |ψh〉 is discussed below. Now we show that a non-trivial choice of D leads to an effective correlated distribution. The j-th QPE in figure 1 (a) corresponds to equation 8 where we identify |vα〉 ≡ |h,W 〉D, |ϕα〉 ≡ |ϕ(h,Wj,:)〉 and we make use of the j-th block of t ancillas. After M steps we compute the outcome probability of a measurement of the first qubit in each of the M registers of the ancillas. We can extend equation 9 to the situation of measuring multiple qubits, and recalling that the first bit of an integer is the most significant bit, determining whether 2−tϕ(h,Wj,:) = (N + 1)
−1ϕ(h,Wj,:) is greater or smaller than 1/2, the probability of outcome h′ = (h′1, . . . , h ′ M ) is
p(h′) = ∑
h∈BN ∑ W∈BNM δh′,f(W ,h) |〈ψ|h,W 〉D| 2 , (17)
where f is the layer function introduced in equation 1. We refer to appendix C for a detailed derivation. Equation 17 is the generalized probabilistic binary layer introduced in equation 6 where D corresponds to a non-trivial S and a correlated distribution when D entangles the qubits:
π(h,W ) = |〈ψ|D |h,W 〉|2 . (18)
The variational parameters φ of S are now parameters of the quantum circuit D. Sampling from π can be done by doing repeated measurements of the first M ancilla qubits of this quantum circuit. On quantum hardware e 2πi N+1Hj can be efficiently implemented since it is a product of diagonal two-qubits quantum gates. We shall consider unitaries D which have efficient quantum circuit approximations. Then computing the quantum deformed layer output on a quantum computer is going to take time O(tMu(N)) where u(N) is the time it takes to compute the action of Uj on an input state. There exists D such that sampling from equation 18 is exponentially harder classically than quantum mechanically, a statement forming the basis for quantum supremacy experiments on noisy, intermediate scale quantum computers (Aaronson & Chen, 2016; Arute et al., 2019). Examples are random circuits with two-dimensional entanglement patterns, which from a machine learning point of view can be natural when considering image data. Other examples are D implementing time evolution operators of physical systems, whose simulation is exponentially hard classically, resulting in hardness of sampling from the time evolved wave function. Quantum supremacy experiments give foundations to which architectures can benefit from quantum speedups, but we remark that the proposed quantum architecture, which relies on quantum phase estimation, is designed for error-corrected quantum computers.
Even better, on quantum hardware we can avoid sampling intermediate activations altogether. At the first layer, the input can be prepared by encoding the input bits in the state |x〉. For the next layers, we simply use the output state as the input to the next layer. One obtains thus the quantum network of figure 1 (b) and the algorithm for a layer is summarized in procedure 1. Note that all the qubits associated to the intermediate activations are entangled. Therefore the input state |ψh〉 would have to be replaced by a state in Vh plus all the other qubits, where the gates at the next layer would act only on Vh in the manner described in this section. (An equivalent and more economical mathematical description is to use the reduced density matrix ρh as input state.) We envision two other possible procedures for what happens after the first layer: i) we sample from equation 17 and initialize |ψh〉 to the bit string sampled in analogy to the classical quantization of activations; ii) we sample many times to reconstruct the classical distribution and encode it in |ψh〉. In our classical simulations below we will be able to actually calculate the probabilities and can avoid sampling.
Finally, we remark that at present it is not clear whether the computational speedup exhibited by our architecture translates to a learning advantage. This is an outstanding question whose full answer will require an empirical evaluation with a quantum computer. Next, we will try to get as close as possible to answer this question by studying a quantum model that we can simulate classically.

heading: 3.3 MODIFICATIONS FOR CLASSICAL SIMULATIONS
text: In this paper we will provide classical simulations of the quantum neural networks introduced above for a restricted class of designs. We do this for two reasons: first to convince the reader that the quantum layers hold promise (even though we can not simulate the proposed architecture in its full glory due to the lack of access to a quantum computer) and second, to show that these ideas can be interesting as new designs, even “classically” (by which we mean architectures that can be executed on a classical computer).
To parallelize the computations for different output neurons, we do the modifications to the setup just explained which are depicted in figure 1 (c). We clone the input activation register M times, an operation that quantum mechanically is only approximate (Nielsen & Chuang, 2000) but exact classically. Then we associate the j-th copy to the j-th row of the weight matrix, thus forming pairs for each j = 1, . . . ,M :
|h,Wj,:〉 ∈ Vh ⊗ VW,j , VW,j = N⊗ i=1 (C2)ji (19)
Fixing j, we introduce the unitary e 2πi N+1Hj diagonal in the basis |h,Wj,:〉 as in equation 11 and define the new unitary:
Ũj = Dje 2πi N+1HjD−1j , (20)
where w.r.t. equation 13 we now let Dj depend on j. We denote the eigenvectors of Ũj by |h,Wj,:〉Dj = Dj |h,Wj,:〉 and the eigenvalue is ϕ(h,Wj,:) introduced in equation 12. Supposing that we know p(h) = ∏ i pi(hi), we apply the quantum phase estimation to Ũj with input:
|ψj〉 = |ψh〉 ⊗ |ψ〉Wj,: , |ψh〉 = N⊗ i=1 [√ pi(hi = 0) |0〉+ √ pi(hi = 1) |1〉 ] , (21)
and |ψ〉Wj,: is defined in equation 15. Going through similar calculations as those done above shows that measurements of the first qubit will be governed by the probability distribution of equation 6 factorized over output channels since the procedure does not couple them: π(h,W ) =∏M j=1 |〈ψj |Dj |h,Wj,:〉|
2. So far, we have focused on fully connected layers. We can extend the derivation of this section to the convolution case, by applying the quantum phase estimation on images patches of the size equal to the kernel size as explained in appendix D.

heading: 4 CLASSICAL SIMULATIONS FOR LOW ENTANGLEMENT

heading: 4.1 THEORY
text: It has been remarked in (Shayer et al., 2017; Peters & Welling, 2018) that when the weight and activation distributions at a given layer are factorized, p(h) = ∏ i pi(hi) and q(W ) = ∏ ij qij(Wij), the output distribution in equation 3 can be efficiently approximated using the central limit theorem (CLT). The argument goes as follows: for each j the preactivations ϕ(h,Wj,:) = ∑N i=1Wj,ihi are sums of independent binary random variables Wj,ihi with mean and variance:
µji = Ew∼qji(w)Eh∼pi(h) , σ2ji = Ew∼qji(w2)Eh∼pi(h2)− µ2ji = µji(1− µji) , (22)
We used b2 = b for a variable b ∈ {0, 1}. The CLT implies that for large N we can approximate ϕ(h,Wj,:) with a normal distribution with mean µj = ∑ i µji and variance σ 2 j = ∑ i σ 2 ji. The distribution of the activation after the non-linearity of equation 1 can thus be computed as:
p(τ( 1N+1ϕ(h,Wj,:)) = 1) = p(2ϕ(h,Wj,:)−N > 0) = Φ ( − 2µj−N2σj ) , (23)
Φ being the CDF of the standard normal distribution. Below we fix j and omit it for notation clarity.
As reviewed in appendix B, commuting observables in quantum mechanics behave like classical random variables. The observable of interest for us, DHD−1 of equation 20, is a sum of commuting terms Ki ≡ DBWi Bhi D−1 and if their joint probability distribution is such that these random variables are weakly correlated, i.e.
〈ψ|KiKi′ |ψ〉 − 〈ψ|Ki |ψ〉 〈ψ|Ki′ |ψ〉 → 0 , if |i− i′| → ∞ , (24) then the CLT for weakly correlated random variables applies, stating that measurements of DHD−1 in state |ψ〉 are governed by a Gaussian distribution N (µ, σ2) with
µ = 〈ψ|DHD−1 |ψ〉 , σ2 = 〈ψ|DH2D−1 |ψ〉 − µ2 . (25) Finally, we can plug these values into equation 23 to get the layer output probability.
We have cast the problem of simulating the quantum neural network to the problem of computing the expectation values in equation 25. In physical terms, these are related to correlation functions of H and H2 after evolving a state |ψ〉with the operator D. These can be efficiently computed classically for one dimensional and lowly entangled quantum circuits D (Vidal, 2003). In view of that here we consider a 1d arrangement of activation and weight qubits, labeled by i = 0, . . . , 2N − 1, where the even qubits are associated with activations and the odd are associated with weights. We then choose:
D = N−1∏ i=0 Q2i,2i+1 N−1∏ i=0 P2i+1,2i+2 , (26)
where Q2i,2i+1 acts non-trivially on qubits 2i, 2i + 1, i.e. onto the i-th activation and i-th weight qubits, while P2i,2i+1 on the i-th weight and i + 1-th activation qubits. We depict this quantum circuit in figure 2 (a). As explained in detail in appendix E, the computation of µ involves the matrix element of Ki in the product state |ψ〉 while σ2 involves that of KiKi+1. Due to the structure of D, these operators act locally on 4 and 6 sites respectively as depicted in figure 2 (b)-(c). This
implies that the computation of equation 25, and so of the full layer, can be done inO(N) and easily parallelized. Appendix E contains more details on the complexity, while Procedure 2 describes the algorithm for the classical simulation discussed here.
Procedure 1 Quantum deformed layer. QPEj(U , I) is quantum phase estimation for a unitary U acting on the set I of activation qubits and the j-th weights/ancilla qubits. Hj is in equation 11. Input: {qij}j=0,...,M−1i=0,...,N−1 , |ψ〉, I, D, t Output: |ψ〉
for j = 0 to M − 1 do |ψ〉Wj,: ← ⊗N i=1 [√ qji |0〉+ √ 1− qji |1〉 ] |ψ〉 ← |0〉⊗t ⊗ |ψ〉 ⊗ |ψ〉Wj,: U ←De 2πi N+1HjD−1 {This requires to approximate the unitary with quantum gates}
|ψ〉 ← QPEj(U , I) |ψ〉 end for
Procedure 2 Classical simulation of a quantum deformed layer with N (M ) inputs (outputs). Input: {qij}j=0,...,M−1i=0,...,N−1 , {pi}i=0,...,N−1,P = {P j 2i−1,2i} j=0,...,M−1 i=1,...,N−1 ,Q = {Q j 2i,2i+1} j=0,...,M−1 i=0,...,N−1 Output: {p′i}i=1,...,M for j = 0 to M − 1 do
for i = 0 to N − 1 do ψ2i ← [√ pi, √ 1− pi ]
ψ2i+1 ← [√ qij , √ 1− qij ] end for for i = 0 to N − 1 do µi ← computeMu(i, ψ,P ,Q) {This implements equation 45 of appendix E} γi,i+1 ← computeGamma(i, ψ,P ,Q) {This implements equation 49 of appendix E} end for µ← ∑N−1 i=0 µi
σ2 ← 2 ∑N−2 i=0 (γi,i+1 − µiµi+1) + ∑N−1 i=0 (µi − µ2i )
p′j ← Φ ( − 2µ−N
2 √ σ2 ) end for
4.2 EXPERIMENTS
Table 1: Test accuracies for MNIST and Fashion MNIST. With the notation cKsS − C to indicate a conv2d layer with C filters of size [K,K] and stride S, and dN for a dense layer with N output neurons, the architectures (Arch.) are A: d10; B: c3s2-8, c3s2-16, d10; C: c3s2-32, c3s2-64, d10. The deformations are: [/]: P ji,i+1 = Q j i,i+1 = 1 (baseline (Peters & Welling, 2018)); [PQ]: P ji,i+1,Q j i,i+1 generic; [Q]: P j i,i+1 = 1,Q j i,i+1 generic.
Arch. Deformation MNIST Fashion MNIST A [/] 91.1 84.2
[PQ] 94.3 86.8 [Q] 91.6 85.1
B [/, /, /] 96.6 87.5 [PQ, /, /] 97.6 88.1 [Q, /, /] 96.8 87.8 C [/, /, /] 98.1 89.3 [PQ, /, /] 98.3 89.6 [Q, /, /] 98.3 89.5
We present experiments for the model of the previous section. At each layer, qij and Dj are learnable. They are optimized to minimize the loss of equation 7 where following (Peters & Welling, 2018; Shayer et al., 2017) we take R = β ∑ `,i,j q (`) ij (1 − q (`) ij ), and R′ is the L2 regularization loss of the parameters of Dj . L coincides with equation 2. We implemented and trained several architectures with different deformations. Table 1 contains results for two standard image datasets, MNIST and Fashion MNIST. Details of the experiments are in appendix F. The classical baseline is based on (Peters & Welling, 2018), but we use fewer layers to make the simulation of the deformation cheaper and use no batch norm, and no max pooling.
The general deformation ([PQ]) performs best in all cases. In the simplest case of a single dense layer (A), the gain is +3.2% for MNIST and +2.6% for Fashion MNIST on test accuracy. For convnets, we could only simulate a single deformed layer due to computational issues and the gain is around or less than 1%. We expect that deforming all layers will give a greater boost as the improvements diminish with decreasing the ratio of deformation parameters over classical parameters (qij). The increase in accuracy comes at the expense of more parameters. In appendix F we present additional results showing that quantum models can still deliver modest accuracy improvement w.r.t. convolutional networks with the same number of parameters.

heading: 5 CONCLUSIONS
text: In this work we made the following main contributions: 1) we introduced quantum deformed neural networks and identified potential speedups by running these models on a quantum computer; 2) we devised classically efficient algorithms to train the networks for low entanglement designs of the quantum circuits; 3) for the first time in the literature, we simulated the quantum neural networks on real world data sizes obtaining good accuracy, and showed modest gains due to the quantum deformations. Running these models on a quantum computer will allow one to explore efficiently more general deformations, in particular those that cannot be approximated by the central limit theorem when the Hamiltonians will be sums of non-commuting operators. Another interesting future direction is to incorporate batch normalization and pooling layers in quantum neural networks.
An outstanding question in quantum machine learning is to find quantum advantages for classical machine learning tasks. The class of known problems for which a quantum learner can have a provably exponential advantage over a classical learner is small at the moment Liu et al. (2020), and some problems that are classically hard to compute can be predicted easily with classical machine learning Huang et al. (2020). The approach presented here is the next step in a series of papers that tries to benchmark quantum neural networks empirically, e.g. Farhi & Neven (2018); Huggins et al. (2019); Grant et al. (2019; 2018); Bausch (2020). We are the first to show that towards the limit of entangling circuits the quantum inspired architecture does improve relative to the classical one for real world data sizes.

Review summaries:
The authors introduced the idea of quantum deformed neural network (DQNN) which allows substitution of the positive probabilities in Baysian statistics with complex amplitude inspired by Born representation of quantum wavefunction, thus allowing interference phenomena leading to possible speed up for running neural networks on quantum computers. Combining the complex amplitude and binary neural network the author introduces a new class of quantum neural networks which are the generalized probabilistic neural network. Then, they argue that this class of DQNN can efficiently run on quantum computers using phase estimation algorithms which scale linearly with the number of qubits. By creating entanglement between the activation and weights they show that this new form of DQNN can be simulated on classical computers for certain classes of problems that hold low entanglement. As a numerical experiment they show modest gain in accuracy on real world data both MNIST and fashion MNITS data.

The fundamental idea in this paper is to endow classical signals with a complex Hilberspace structure so as to harness the probabilistic nature of quantum mechaniscs for pattern recognition based on quantum computing principles. Following this idea, the authors consider (probabiistic) binary neural networks and develop a corresponding kind of quantum neural networks building on the concept of quantum phase estimation. They (convincingly) argue that this idea would make good use of the exponential speedup offered by quantum computers but can still be implemented on classical, digital devices. Experiments with image data corroborate this claim and demonstrate that simulations of the proposed quantum deformation showed improved accuracies when compared to  classical probabilistic binary neural networks.