Classical and Quantum Algorithms for Orthogonal Neural Networks
Authors: Jonas Landman
Natansh Mathur
Iordanis Kerenidis
Venue: ICLR 2022 Submitted (2022)
Keywords: orthogonal neural networks
orthogonality
quantum computing
quantum machine learning
quantum deep learning
complexity
quantum computer

Abstract: Orthogonal neural networks have recently been introduced as a new type of neural network imposing orthogonality on the weight matrices. They could achieve higher accuracy and avoid evanescent or explosive gradients for deep architectures. Several classical gradient descent methods have been proposed to preserve orthogonality while updating the weight matrices, but these techniques suffer from long running times and/or provide only approximate orthogonality. In this paper, we introduce a new type of neural network layer called Pyramidal Circuit, which implements an orthogonal matrix multiplication. It allows for gradient descent with perfect orthogonality with the same asymptotic running time as a standard fully connected layer. This algorithm is inspired by quantum computing and can therefore be applied on a classical computer as well as on a near term quantum computer. It could become the building block for quantum neural networks and faster orthogonal neural networks.

Under review as a conference paper at ICLR 2022
CLASSICAL AND QUANTUM ALGORITTMS FOR ORTHOGONAL NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Orthogonal neural networks have recently been introduced as new type of neu- ral networks imposing orthogonality on the weight matrices. They could achieve higher accuracy and avoid evanescent or explosive gradients for deep architec- tures. Several classical gradient descent methods have been proposed to preserve orthogonality while updating the weight matrices, but these techniques suffer from long running times and/or provide only approximate orthogonality. In this paper, we introduce new type of neural network layer called Pyramidal Circuit, which implements orthogonal matrix multiplication. It allows for gradient descent with perfect orthogonality with the same asymptotic running time as a standard fully connected layer. This algorithm is inspired by quantum computing and can therefore be applied on a classical computer as well as on a near term quantum computer. could become the building block for quantum neural networks and faster orthogonal neural networks.
INTRODUCTION
In the evolution of neural network structures, adding constraints to the weight matrices has often been an effective path. Recently, orthogonal neural networks (OrthoNNs) have been proposed Dia et al. (2019); Wang et al.] (2020): Nosarzewski (2018); Bansal et al. (2018) as new type of neu- ral networks for which, at each layer, the weight matrix should remain orthogonal. This property is useful reach higher accuracy performance and avoid vanishing or exploding gradient for deep architectures. Several classical gradient descent methods have been proposed to preserve the orthog- onality while updating the weight matrices. However, these techniques suffer from longer running time and sometimes only approximate the orthogonality. In particular, the main method for achiev- ing orthogonality during training is to first perform the usual gradient descent to update the weight matrix (which is now not going to be orthogonal) and then perform Singular Value Decomposition orthogonalize almost orthogonalize the weight matrix. We can see then why achieving orthog- onality hinders a fast training, since at every step an SVD computation needs to be performed (See Section A.
In the emergent field of quantum machine learning, several proposals have been made to implement neural networks. Some algorithms rely on long term and perfect quantum computers Kerenidis et al. (2020); Allcock et al. (2018), while others try to harness the existing quantum devices using variational circuits Cong et al. (2019); Farhi Neven (2018). As in classical neural networks, they use gradient descent methods to update the quantum parameters of the circuits. Such quantum neural networks have been trained for very small sizes, however there is still a need to understand how such architectures will scale and whether they will provide efficient and accurate training.
In this work, we present a new training method for neural networks that preserves perfect orthogonal- ity while having the same running time usual gradient descent methods without the orthogonality condition, thus achieving the best of both worlds, most efficient training and perfect orthogonality.
The main idea comes from the quantum world, where we know that any quantum circuit corresponds to an operation described by a unitary matrix, which if we only use gates with real amplitudes an propose novel
orthogonal matrix. In particular, there is an efficient way to map the elements of the orthogonal weight matrix to the parameters of the gates of the quantum circuit and vice versa. In other words, while performing gradient descent on
archiietttee quantum circuit, for which

---

Under review as a conference paper at ICLR 2022
the elements of the weight matrix individually does not preserve orthogonality, performing gradient descent on the parameters of the quantum circuit preserves orthogonality (since any quantum circuit with real parameters corresponds to an orthogonal matrix) and is equivalent updating the weight matrix. We also prove that performing gradient descent on the parameters of the quantum circuit can be done efficiently classically (with constant update cost per parameter) thus concluding that there exists a quantum-inspired, but fully classical way of efficiently training perfectly orthogonal neural networks.
Moreover, the special-architecture quantum circuit we defined has many properties that make it a good candidate for NISQ implementation: uses only one type of quantum gates, requires simple connectivity between the qubits, has depth linear in the input and output node sizes, and benefits from powerful error mitigation techniques that make resilient to noise. This allows us to also propose an inference method running the quantum circuit on data which might offer a faster running time, given the shallow depth of the quantum circuit.
Our main contributions are summarized in Table [ where we have considered the time to perform a feedforward pass, or one gradient descent step. single neural network layer is considered, with input and output of size n.
Algorithm
Feedforward Pass
Weight Matrix Update
Quantum Pyramidal Circuit (This work)
2n/6² = O
0n22/89
Classical Pyramidal Circuit (This work)
2n(n 1) = (n
O
Classical Approximated OrthoNN (SVB)
n² O(n²)
(
Classical Striet OrthoNN (Stiefel Manifold)
n² O(n²)
(
Standard Neural Network (non orthogonal)
n² (n²)
(nn))
Table 1: Running times summary. n is the size of the input and output vectors, the error parameter in the quantum implementation. See Appendix Section for details on related work classical approximated and strict OrthoNN.
A PARAMETRIZED QUANTUM CIRCUIT FOR ORTHOGONAL NEURAL NETWORKS
In this section, we define a apecial-architettune parametrized quantum circuit that will be useful for performing training and inference orthogonal neural networks. As we said, the training will be completely classical in the end, but the intuition the new method comes from this quantum circuit, while the inference can happen both classically by applying this quantum circuit. A basic introduction to quantum computing concepts necessary for this work is given in the Appendix (Section A.3).
2.1
THE RBS GATE
The quantum circuit proposed in this work (see Fig which implements a fully connected neural network layer with an orthogonal weight matrix, uses only one type of quantum gate, the Reconfig- urable Beam Splitter (RBS) gate. This two-qubit gate is parametrizable with one angle 0 E [0, 2m). Its matrix representation is given as:
0
0
0 cos sin
[101) + cos 0 (01 sin 0 110) (110) + sin f (01) cos 0 110)
RBS(O)
RBS(O):
0
sin 0
cos 0
We can think of this gate as rotation in the two-dimensional subspace spanned by the basis { {01). [10)}, ). while it acts as the identity in the remaining subspace {J00). [11)]. Or equivalently, starting with two qubits, one in the [0) state and the other one in the state [1). the qubits can be swapped or not in superposition. The qubit [1) stays on its wire with amplitude cos f or switches sin 0 if the new wire is above (01) + [10)). Note that in the two other cases ((00) and [11)) the RBS gate acts identity.
with the other qubit with amplitude + sin 0 if the new wire is below ([10) +> (01))
2

---

Under review as a conference paper at ICLR 2022
COS
Sin(O)
sin (
cos !
0
Figure I: Representation of the quantum mapping from Eq I on two qubits.
2.2 QUANTUM PYRAMIDAL CIRCUIT
We propose quantum circuit that implements orthogonal layer of neural network. The circuit is a pyramidal structure of RBS gates, each with an independent angle, as represented in Fig In Section 2.3 and 3 more details provided concerning respectively the input loading. and the equivalence with a neural network's orthogonal layer.
8,
8,2
3,4
8g
0g
030
0:7
0
%,
8
0
0
0,5
Pn
0
8,2
(a)
(b)
Figure 2: (a) Quantum circuit for 8x8 fully connected, orthogonal layer. Each vertical line corresponds to an RBS gate with its angle parameter. And (b), the equivalent classical orthogonal neural network 8x8 layer.
To mimic given classical layer with quantum circuit, the number of output qubits should be the size of the classical layer's output. We refer to the square case when the input and output sizes equal, and to the rectangular case otherwise (Fig
The important property to note is that the number of parameters of the quantum pyramidal circuit corresponding to a neural network layer of size n x is (2n - 1 d) d/2 exactly the same as the number of degrees of freedom of an orthogonal matrix of dimension n x d.
8,
0
0
4
0,
0,
6
0,
13
0,
e,
8,
6,.
(b)
Figure 3: (a) Quantum circuit for a rectangular 8x4 fully connected orthogonal layer, and (b) the equivalent 8x4 classical orthogonal neural network. They both have 22 free parameters.
For simplicity, we pursue our analysis using only the square case but everything can be easily extended to the rectangular case. As we said, the full pyramidal structure of the quantum circuit
3

---

Under review as a conference paper at ICLR 2022
described above imposes the number of free parameters to be N nnnn 1)/2, the exact number of free parameters to specify a n X n orthogonal matrix.
In Section will show how the parameters of the gates of this pyramidal circuit can be easily related to the elements of the orthogonal matrix of size nxn that describes it. We note that alternative architectures can be imagined long the number of gate parameters is equal to the parameters of the orthogonal weight matrix and a simple mapping between them and the elements the weight matrix can be found.
Note finally that this circuit has linear depth and is convenient for near term quantum hardware platforms with restricted connectivity. Indeed, the distribution of the RBS gates requires only nearest neighbor connectivity between qubits.
2.3 LOADING THE DATA
Before applying the quantum pyramidal circuit, we will need to upload the classical data into the quantum circuit. We will use one qubit per feature of the data. For this, we use unary amplitude
encoding of the input data. Let's consider an input sample = (Fo."" , Tn-1)
R such that
||>||| = 1. We will encode it in a superposition of unary states:
(x) To 10 0) + 21 1010--. 0)
Fn-1 10....1. 01)
We can also rewrite the previous state as (z) En-1 2y lez), where (e:) represents the jth unary state with [1) in the 1t position 10..- 1..--110- ... 0). Recent work Kerenidis (U.S. Patent Application No. 16/986,553 and 16/987,235 2020) proposed a logarithmic depth data loader circuit for loading such states. Here we will use a much simpler circuit. is a linear depth cascade of n- 11 RBS gates which, due to the particular structure of our quantum pyramidal circuit, only adds 2 extra steps to our circuit.
11]
%
0,
0
0
0,
0
0,
(0)
0g
8,
8/g
8
10}
0
0,
0
8,0
0,g
(0)
0,
0
1,
8gg
(0)
8,
8,
10)
20
10)
6
10)
Figure 4: The 8 dimensional linear data loader circuit (in red) is efficiently embedded before the pyramidal circuit. The input state is the first unary state. The angles parameters co., ,n 2 are classically pre-computed from the input vector.
The circuit starts in the all (0) state and flips the first qubit using an X gate, in order to obtain the unary state [10-..0) 0) as shown in Fig Then a cascade of RBS gates allow to create the state (x) using a set of n angles ag.
an-2. Using [q. we will choose the angles such that, after the first RBS gate of the loader, the qubits would be in the state xp 1100...) sin(oo) (010-..) and after the second one in the state [100.., + 21 (010...) + sin(a)))in(ar) (001...) and so on, until obtaining [x) as in 2). To this end, we simply perform a classical preprocessing to compute recursively the n 1 loading angles, in time O(n). We choose oo arccos(zo). on = arccos(z1 sin "((o)), 02 = arccos( sin ((o) sin (aa)) and so on.
The ability of loading data in such way relies on the assumption that each input vector is nor- malized, i.e. ||~||| 1. This normalization constraint could seem arbitrary and impact the ability to learn from the data. In fact, in the case of an orthogonal neural network, this normalization shouldn't i degrade the training because orthogonal weight matrices are in fact orthonormal and thus norm- porm-preseriing.. Hence, changing the norm of the input vector, by diving each component by || in both classical and quantum settings is not a problem. The normalization would impose that each input has the same norm, or the same "luminosity" in the context of images, which can be helpful or harmful depending on the case.
4

---

Under review as a conference paper at ICLR 2022
3 ORTHONNS FEEDFORWARD PASS
In this section, we will detail the effect of the quantum pyramidal circuit on an input encoded in a unary basis, as in Eq.2) 2.. We will also see in the end how to simulate this quantum circuit classically with a small overhead and thus be able to provide a fully classical scheme.
Let's first consider one pure unary input, where only the qubit j is in state [1) (e.g. (00000010)).
This unary input will transformed into a superposition of unary states, each with an amplitude. If we consider again only one of these possible unary outputs, where only the qubit is in state (1), its amplitude can be interpreted as a conditional amplitude to transfer the [1] from qubit j to qubit Intuitively, this value is the sum of the quantum amplitudes associated to each possible path that connects the qubit j to qubit i, as shown in Fig Using this image of connectivity between input and output qubits, we can construct a matrix W E R=*n, where each element Wa; is the overall conditional amplitude to transfer the [1) from qubit j to qubit i.
(0)
(0]
0,
0
0
100
2/
2
10)
[0]
0
0g
0g
0,4
027
10)
(0]
8,
8g
0/g
(0)
(0)
0
0,2
8yg
(0)
(0)
,r
024
10)
[1)
8
11)
(0)
2:2
10)
(0)
Figure 5: The three possibles paths from the 7th unary state the 6th unary state, on an 8x8 quantum pyramidal circuit.
5 shows an example where exactly three paths can be taken to map the input qubit j = 6 (the 7th (the 6th unary state). Each path comes with a certain amplitude. For instance, one of the paths (the red one in 5 moves up at the first gate, and then stays put in the next three gates, with a resulting amplitude of - sin() cos(017) (0s()))) cos(f21). The sum of the amplitudes of all possible paths give us the element Woo of the matrix W (where, for simplicity, s(0) and c(f) respectively stand for (f) and cos())):
unary state) to the qubit
+ In fact, the x matrix W can be seen as the unitary matrix of our quantum circuit if we solely consider the unary basis, which is specified by the parameters of the quantum gates. A unitary is a complex unitary matrix, but in our case, with only real operations, the matrix is simply orthogonal. This proves the correspondence between any matrix W and the pyramidal quantum circuit.
W36 = -s(01s)c (1(()))((0)))))))))))))))))))))) (02))) (023) - s(116
(3)
The full unitary Uw in the Hilbert Space of our n-qubit quantum circuit is 2n x 2n matrix with the n x n matrix W embedded in it as a submatrix on the unary basis. This is achieved by loading the data unary states and by using only RBS gates that keep the number of Os and Is constant.
For instance, as shown in Fig a 3-qubit pyramidal circuit is described as a unique 3 x matrix, that can be easily verified to be orthogonal.
In Fig 5 we considered the case of single unary for both the input and output. But with actual data, as seen Section [2.3 input and output states are in fact superposition of unary states. Thanks to the linearity of quantum mechanics in absence of measurements, the previous descriptions remain valid and can be applied on a linear combination of unary states.
Let's consider an input vector & E RR encoded quantum state |a) Σ'=
x, les) where les)
represents the jth unary state (see Section 2.3). By definition of W, each unary le;) will undergo proper evolution (e;) + Σn= Wi (ez). This yields, by linearity, to the following mapping
(x) + Σ
Wa ley)
(4)
5

---

Under review as a conference paper at ICLR 2022
c(0 - x - =(0))((0)))(())) ((0))c(()))(())))))))))))))))))) + ((0))s(())) =(0))s(82)
-s(0 - )())))
((0))s(Ba)
e,
8
c( ((()))((((())))) s(0))s(9))
(80))((0)) c(0p)
9
a(t )=(())
Figure 6: Example of 3 qubits pyramidal circuit and the equivalent orthogonal matrix. c(0) and s(0) respectively stand for cos(f) and sin(O).
(0)
(0)
0,
0
8,
9,
(0)
1/v2
B
B
(1)
(1)
10)
B
0
Data
103
Loader
00)
(0)
+|
18)
(
0)
(0)
(0)
(0]
(0)
8..
(0)
1/v3/
(0)
8,
0,
0.g
0.
1/V2
(0)
9
9,
(0)
B,,
10)
6,
10)
0,
[1]
Figure 7: Schematic representation pyramidal circuit applied on a loaded vector æ with two non- zero values. The output is the unary encoding of y Wz where W is the corresponding orthogonal matrix associated with the circuit.
As explained above, our quantum circuit is equivalently described by the sparse unitary Uw R²2 x2" or on the unary basis by the matrix W IR*x", This can be summarized with
Uw (x) [Wx)
We from Eq. and Eq. that the output is in fact ly), the unary encoding of the vector y Wa, which is the output matrix multiplication between the n x n orthogonal matrix W and the input E R.. As expected, each element of y is given by diagram representation of this mapping.
i= Waa See Fig for
Therefore, for any given neural network's orthogonal layer, there is a quantum pyramidal circuit that reproduces it. On the other hand, any quantum pyramidal circuit is implementing an orthogonal layer of some sort. Additional details concerning multi-layers branching, the tomography at the end of each layer, and the way to apply the non linearities are given in the Appendix, Section A.4
As side note, can ask if circuit with only log(n) qubits could also implement an orthogonal matrix multiplication size n x n. Indeed, it would be a unitary matrix "x but since circuit should also have 7e(n 2 free parameters to tune, this would come at a cost of large depth, potentially unsuitable for NISQ devices.
Classical implementation While we presented the quantum pyramidal circuit as the inspiration of the new methods for orthogonal neural networks, it not hard to see that these quantum circuits can be simulated classical with a small overhead, thus yielding classical methods for orthogonal neural networks.

---

Under review as a conference paper at ICLR 2022
This classical algorithm is simply the simulation of the quantum pyramidal circuit, where each RBS gate is replaced by a planar rotation between its two inputs.
As shown in Fig 8 propose a similar classical pyramidal circuit, where each layer is constituted of m(n-1) planar rotations, for a total of 4 =(n-1) (n²)) basic operations. Therefore our single layer feedforward pass has the same complexity (n²) as the usual matrix multiplication.
2
cos 9
6
COs 0
W
Fo
W
%
cio
-ain
ain
sinn
sin G.
-ain
cos 8
cos B.
cos
sin g.
-Sin 8
cos 0g
sio fg
-sin
cos 0
B
cos 0g
sin
cos 8g
0
Figure 8: Classical representation of single orthogonal layer on a 4x4 case (n=4) performing + y Wx. The angles and the weights can be chosen such that classical pyramidal circuit (left) and normal classical network (right) are equivalent. Each connecting line represents a scalar multiplication with the value indicated. On the classical pyramidal cireuit (left), inner layers Ç* are displayed. A timestep corresponds to the lines in between two inner layers (see Section for definitions).
One may still have an advantage in performing the quantum circuit for inference, since the quantum circuit has depth On)), instead of the (nn²) classical complexity of the matrix-vector multiplication. Nevertheless, as we will see below, the main advantage of our method is that we can now train orthogonal weight matrices classically in time O(n?), instead of the previously best-known O
ORTHONN TRAINING: ANGLE'S GRADIENT CALCULATION AND ORTHOGONAL MATRIX UPDATE
Basic introduction and notations to the backpropagation in fully connected neural networks are given in the Appendix, Section A.2
Looking through the prism of our pyramidal quantum circuit, the parameters to update are no longer the individual elements of the weight matrices directly, but the angles of the RBS gates that give rise to these matrices. Thus, setting based on the angles. We will start by introducing some notation for a single layer l, which will not be explicit in the notation for simplicity. We assume we have as many output bits input bits, but this can easily be extended to the reclangular case.
need to design an adaptation of the backpropagation method to
We first introduce the notion of timesteps inside each layer, which correspond to the computational steps in the pyramidal structure of the circuit (see Fig.). It is easy to show that for inputs, there will be 2n 3 such timesteps, each one indexed by an integer
E [O.... Amaz]. Applying timestep consists in applying the matrix w made of all the RBS gates aligned vertically at this timestep (w> is the unitary in the unary basis, see Section 3 for details). Each time timestep is applied, the resulting state is a vector in the unary basis named inner layer and noted Ç*. This evolution can be written as cλ+1 w <². We use this notation similar to the real layer E, with the weight matrix W' and the resulting vector zf (see Section A.2
In fact we have the correspondences <0 f for the first inner layer, which is the input of the actual layer, and z' Amax Amma for the last one. We also have W Amax ... w We use the same kind of notation for the backpropagation errors. At each timestep we define de an inner error 8 aÇa. This definition is similar to the layer error A
ac In fact 8z4-
will the same backpropagation formulas, without non linearities, retrieve each inner error
7

---

Under review as a conference paper at ICLR 2022
w
20
Amaz
8
8
8
1
815
8
8
82
8g
8
8
827
8,
8,3
8.a
a-1
2
8,
112
8,u
0,7
8
8z
82
Amaa
Figure 9: Quantum circuit for one neural network layer divided into timesteps (red vertical lines) À E [0,..., Amaz]. Each timestep corresponds to inner layer Ç* and an inner error 8*, The part of the circuit between two timesteps is an unitary matrix w in the unary basis.
vector 5d
(wr T gA+1. In particular, for the last timestep, the first to be calculated, we have (w mare A Finally, we can retrieve the error at the previous layer using the correspondence 8-1 8 ④ o'=
Amnar
The reason for this breakdown into timesteps the ability to efficiently obtain the gradient with respect to each angle. Let's consider one gate with angle 0;, acting at the timestep on qubits and i i will decompose the gradient & using each component, indexed by the integer k. of the
30;
inner layer and inner error vectors
BC 30;
8C
ac 30,
Ex 8.+1 alw (*)
aC
80:
Since timestep only composed of separated RBS gates, the matrix w> consists diagonally arranged 2x2 block submatrices given in [q. Only one of these submatrices depends the angle 9 considered here, at the position and + 1 the matrix. The above gradient can be rewritten as:
OC = (in(sin( + cos(0))
cos((c)) (- sin(O.)(;t))
(6)
00,
Therefore we have shown way to compute each angle gradient: During the feedforward pass, one must apply sequentially each of the 2n the inner layers Ç². During the backpropagation, timesteps in reverse. One can finally use a gradient descent on each angle 0;, while preserving the orthogonality of the overall equivalent weight matrix 0f of X 8C
(n) timesteps, and store the resulting vectors, obtains the inner errors 5^ by applying the
36
An interesting aspect of this gradient descent is the fact that the optimization is performed in the angle landscape, and not the equivalent weight landscape. These landscapes potentially be different and hence our optimization can produce different models. We leave open the question of finding a theoretical argument to compare the properties of both landscapes.
As one can see from the above description, this is in fact classical algorithm to obtain the angle's gradients, which allows us train our OrthoNN efficiently classically while preserving the strict orthogonality. To obtain the angle's 's gradient, one needs to store the 2n - 3 inner layers Ç* during the feedforward pass. Next, given the error the following layer, we perform backward loop on each limestep (see Fig 8). At each timestep, we obtain the gradient for each angle parameter, by simply applying 4q.44) This requires ((1) operations for each angle. Since there are at most n/2 angles per timesteps, estimating gradients has complexity of O(n²). After each timestep, the next inner error 8 is computed as well, using at most 4n/2 operations.
In the end, our classical algorithm allows us to compute the gradients of the n(n 1)/2 angles in O in order to perform a gradient descent respecting the strict orthogonality of the weight matrix. This is considerably faster than previous methods based on Singular Value Decomposition methods and provides a training method that is asymptotically as fast as for normal neural networks, while providing the extra property of orthogonality.
8

---

Under review as a conference paper at ICLR 2022
5 NUMERICAL EXPERIMENTS
We performed basic numerical experiments to verify the abilities of our pyramidal circuit, on the standard MNIST dataset LeCCm & Cortes 2010). Note that current quantum hardware and software are not yet suited for bigger experiments. We first compared the training of our Classical OrthoNN to the SVB algorithm from et al. (2019) (see Section DattfionAA...Rssseeeee Results as reported Fig IO and more in the Appendix, Section A.4.3 These small scale tests confirmed that the pyramidal circuits and the corresponding gradient descent on the angles were efficient for learning a classification task.
Learning Curves
100
Test Accuracy (%)
80
70
50
Pyramidal Orthogonal NN SVB Orthogonal NN
30
2000
4000
5000
Iterations
Figure 10: Training comparison between a [16,8,4] SVB OrthoNN from Jia et al. (2019) and our classical pyramidal OrthoNN. Test accuracy 1000 samples during 50 epochs of training the MNIST dataset on 5000 samples. Initial dimensionality reduction (PCA) was on the samples to fit the input layer of the networks. Shaded areas indicate the accuracy variance during minibatch updates of size 50.
Then, we implemented the quantum circuit on real quantum computer provided by IBM. We used 16 and gubits device perform respectively a [8.2] and a [4.2] orthogonal layer. A pyramidal OrthoNN was trained classically, and the resulting angles were transferred to test the quantum circuit on classification task on classes and of the MNIST dataset, over 500 samples. We compared the real experiment with simulated one, and the classical pyramidal circuit well. Results are reported in Table 2
Platform
Accuracy
Platform
Accuracy
Classical circuit [4,2]
98,4%
Classical circuit [8.2]
97,4%
IBM Simulator [4,2]
98,4%
IBM Simulator [8.2]
97,4%
ibmq bogota vl.4.32 3.32 [4.2]
98,0%
ibmq-guadaluug v1.2.17 [8,2]
95,0%
Table 2: Results of the Pyramidal OrthoNN on real quantum computers. ibmq bogota vl.4.32 and mong-gua vl.2.17 17 are respectively 5 and 16 qubits quantum computers.
CONCLUSION AND OUTLOOK
In this work, we have proposed for the first time training methods for orthogonal neural networks (OrthoNNs) that in quadratic time, significant improvement from previous methods based on Singular Value Decomposition. The main idea of our method is to replace usual weights and orthog- onal matrices with an equivalent pyramidal circuit made of woo-dimensional rotations. Each rotation is parametrizable by an angle, and the gradient descent takes place in the angle's 's optimization land- scape. This unique type of gradient backpropagation ensures perfect orthogonality of the weight matrices while improving the running time compared to previous works. Moreover, we propose both classical and quantum methods for inference, where the forward pass on a near term quantum computer would provide a provable advantage in the running time. This work expands the field of quantum deep learning by introducing new tools, concepts, and equivalences with classical deep learning theory. We have highlighted open questions regarding the construction of such pyramidal circuits for neural networks and their potential new advantages in terms of execution time, accuracy, and learning properties.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
In this paper, we have introduced new methods for implementing and training orthogonal neural networks. We have explained in detail each part of both algorithms' implementation (see Appendix for more details). The dataset used here for basic simulation is the well-known MNIST dataset, easily accessible to everyone.
It is in our belief that anyone with classical software skills can re-implement the classical algorithm (see Fig 9. in Python for instance. Similarly, on any quantum software platform, one can implement the quantum gates given in Fig I1 and perform the whole algorithm using Fig 12 Fig 10, and math- ematical details through the paper. This would allow simulating the quantum circuit using accessible platforms such IBM's qiskit.
However, in order to perform the actual experiment on a quantum computer currently accessible, as have done IBM 5 and 16 qubits devices, one must have access their service (or any other provider). Some quantum computers are available for free, but others require specific agreements.
8 ETHICS STATEMENT
Our work on quantum and classical algorithms for orthogonal neural networks is mainly theoretical work aiming at improving the complexity of neural networks training on current computers and near term quantum computers. Therefore, any ethical concerns regarding classical neural networks may also concern our work.
REFERENCES
Scott Aaronson. Read the fine print. Nature Physics, 11(4):291-293, 2015.
Jonathan Allcock, Chang- Yu Hsich, lordanis Kerenidis, and Shengyu Zhang. Quantum algorithms for feedforward neural networks. arXiv preprint arXiv:1812.03089/ 2018.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regular- izations in training deep enns? arXiv preprint 1810.09 2018
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 12722711233 2019.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks term pro- cessors. arXiv preprint 1802. 2018.
Brooks Foxen, Charles Neill, Andrew Dunsworth, Pedram Roushan, Ben Chiaro, Anthony Megrant, Julian Kelly, Zijun Chen, Kevin Satzinger, Rami Barends, et al. Demonstrating a continuous set of two-qubit gates for near-term quantum algorithms. Physical Review Letters, 125512):120504, 2020.
Robert Hecht-Nielsen. Theory of the backpropagation neural network. In Neural networks for perception, pp. 65 65-93. Elsevier, 1992.
Kui Jia, Shuai Li, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE transactions on pattern analysis and machine intelligence, 2019.
Lordanis Kerenidis. A method for loading classical data into quantum states for applications in ma- chine learning and optimization, U.S. Patent Application No. 16/986,553 and 16/987, 7,35, 2020.
Iordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep convolu- tional neural networks. In Proceedings of the International Conference on Leurning Representa- tions (ICLR), 2020.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL lecun. com wxdb/mniiiii.
10

---

Under review as a conference paper at ICLR 2022
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
Mario Lezcano-Casado and David Martunez-Rubio. Cheap orthogonal constraints in neural net- works: A simple parametrization of the orthogonal and unitary group. In International Confer- ence on Machine Learning. pp. 3794-3803 PMLR, 2019.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Benjamin Nosarzewski. Deep orthogonal neural networks. 2018.
Raul Rojas. The backpropagation algorithm. In Neural networks, pp. 149-182. Springer, 1996.
Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X Yu. Orthogonal convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recog- nition, pp. -15555 2020.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 RELATED WORK ON CLASSICAL ORTHONNS
The idea behind Orthogonal Neural Networks (OrthoNNs) to add a constraint to the weight ma- trices corresponding to the layers of neural network. Imposing orthogonality to these matrices has theoretical and practical benefits the generalization error Jia et al. (2019). Orthogonality ensures low weights redundancy and preserves the magnitude of the weight matrix's cigenvalues to avoid vanishing gradients. In terms of complexity, for single layer, the feedforward pass of an OrthoNN is simply matrix multiplication, hence has running time of (n²)) if X is the size of the thogonal matrix. It is also interesting to note that OrthoNNs have been generalized to Convolutional Neural Networks Wang al. (2020).
The main difficulty of OrthoNNs is to preserve the orthogonality of the matrices while updating them during gradient descent. Several algorithms have been proposed this end Wang al. (2020); Bansal et al. 20188; Lezcano-Casado & Martinez-Rubio (201)), but they all point that pure orthog- onality computationally hard conserve. Therefore, previous works allow for approximations: strict orthogonality is no longer required, and the matrices are often pushed toward orthogonality using regularization techniques during weights update.
We present two algorithms from Jia et al. (2019) for updating orthogonal matrices.
The first algorithm is an approximated one, called Singular Value Bounding (SVB). It starts by applying the usual gradient descent update on the matrix, therefore making it not orthogonal any- more. Then, the singular values of the new matrix are extracted using Singular Value Decomposition (SVD), their values are manually pushed to be close to 1, and the matrix is recomposed hence en- forcing orthogonality. This method shows less advantage on practical experiments JJia et al.] (2019). It has complexity of (n²²) due to the SVD, which in practice is better than the next algorithm. Note that this running time is still longer than O(n)), the running time to perform standard gradient descent.
The second algorithm can considered perfect since it ensures strict orthogonality by performing the gradient descent in the manifold of orthogonal matrices, called the Stiefel Manifold. In practice Jia et al. (019)) this method showed a substantially advantageous classification results on standard datasets. This algorithm requires (nn)) operations, but is very prohibitive in practice. We give an informal step-by-step detail of this algorithm (see Jia et al. (2019), Appendix G for details):
1. Compute the gradient G' of the weight matrix W.
2. Project the gradient matrix G in the tangent space, (The space tangent to the manifold at this point W): multiply G by some other matrices based on W:
- V-WWT)G + W 3 -
This requires several matrix -atrix multiplications. In the case of square x matrices, each has complexity Onn²). the result of this projection is called the manifold gradient Q.
3. update W' = W 1752, where 1j is the chosen learning rate.
4. Perform retraction from the tangent space to the manifold. To do so we multiply W" by Q factor of the QR decomposition, obtained using Gram Schmidt orthonormalization, which has complexity O(2n*).
A.2 CLASSICAL BACKPROPAGATION ALGORITHM
The backpropagation in a fully connected neural network well know and efficient procedure to update the weight matrix at each layer Hecht- (1992); Rojas (199).. At layer E, we note its weight matrices We and biases b². Each layer followed by a non linear function a, and can therefore be written as
a' = f-1 B²) (=²²)
(7)
After the last layer, one can define a cost function C that compares the output to the ground truth. The goal is calculate the gradient of C with respect to each weight and bias, namely aw and
ac
12

---

Under review as a conference paper at ICLR 2022
ac In the backpropagation, start by calculating these gradients for the last layer, then propagate B6E back to the first layer.
8 We will require to obtain the error vector at layer l defined by A ac One can show the backward recursive relation A = (we+1yr A++1 d'(),, where symbolizes the Hadamard product, or entry-wise multiplication. Note that the previous computation requires simply to apply the layer (ie apply matrix multiplication) in reverse. We can then show that each element of the weight gradient matrix layer is given by ac
aw jk = AJ af of-1 Similarly, the gradient with respect
to the biases is easily defined as
ac = D 065
Once these gradients are computed, we update the parameters using the gradient descent rule, with learning rate A:
ac ow jk
ac
Wf, Wfx.
bf bf
abg
A.3 PRELIMINARIES IN QUANTUM COMPUTING
We present a succinct broad-audience quantum information background necessary for this work. See Nielsen & Chuang 2002 for detailed course.
Qubits: In classical computing, a bit can be either 0 or 1. With a quantum information perspective, quantum bit qubit can be is state (0). [1]. We use the braket notation |-) to specify the quantum nature the bit. The qubits can in superposition that |a| 2 + | 1. The coefficients and 8 are called amplitudes. The probabilities of observing
both states a (0) - [11) where a, 3 such
either or when measuring the qubit are linked to the amplitudes:
p(0) la|2; p(1) 1
As quantum physics teaches us, any superposition is possible before the measurement, which gives special abilities in terms of computation. With a n qubits, 2" possible binary combinations (e.g. [01 ... 1001)) can exist simultaneously, each with its own amplitude.
A qubits system can be represented as normalized vector in a 2" dimensional Hilbert space. A multiple qubit system is called a quantum register. If (p) and 1q) are two quantum states or quantum registers, the whole system can be represented as a tensor product (p) & lq), also written as Ip) (g) or [p. g)
Quantum Computation: As logical gates in classical circuits, qubits or quantum registers are processed using quantum gates. A quantum gate is unitary mapping in the Hilbert space, preserv- ing the unit norm of the quantum state vector. Therefore, a quantum gate acting on n qubits is matrix U C such that UUT UT I, with Ut being the adjoint, conjugate transpose, of U.
Common single qubit gates include the Hadamard gate 1 v2 (1
-
that maps 10) + /2 (10)+ + +11)
1
and [1) + / (10) - [1)), creating the quantum superposition, the NOT gate
{1
that permutes
0
cos(0
cos (0/2)
sin (0 0/2)
(0) and [1), or Rg rotation gate parametrized by an angle f, given by
sin (0/()
cos(0/2)
0
0
Common two-qubits gates includes the CNOT gate
which is NOT gate applied
0
0
0
1
0
0
0
0
1
0
0
on the second qubit only if the first one is in state [1), or similarly the CZ gate
0
0
0
0
0
0
-1
13

---

Under review as a conference paper at ICLR 2022
In this work, the RBS gate given in Eq. IT. This gate can be implemented rather easily,
either as a native gate, known as FSIM Foxen et al. 2020), or using four Hadamard gates, two Rg
rotation gates, and two two-qubits CZ gates:
H
Ry (+0/2)
H
H
Ryy (-0/2)
H
Figure 11: A possible decomposition of the RBS(0) gate.
The main advantage of quantum gates their ability to be applied to a superposition of inputs. Indeed, given gate U such that U (xr) [f(x))) can apply it to all possible combinations of at once En (x)) + t Ez ((x))
A.4 ADDITIONAL DETAILS ON THE QUANTUM PYRAMIDAL CIRCUIT
A.4.1 TOMOGRAPHY AND ERROR MITIGATION
As shown in Fig when using the quantum circuit, the output a quantum state (y) = -W=). As often in quantum machine learning Aaronson (2015), it is important go all way and consider the cost of retrieving classical outputs, using a procedure called tomography. In our case this is even more crucial since, between each layer, the quantum output will be converted into classical one in order to apply a non linear function, and then reloaded for the next layer.
Error Mitigation Before detailing the tomography procedure, is interesting to notice that with our restriction to unary states, strong benefit appears for error mitigation purposes. Indeed, as we expect to obtain only quantum superposition of unary states at every layer, we can post process our measurements and discard the ones that present non unary states (í.c. states with more than one qubit in state [1), or the ground state). The most expected error is a bit flip between [1} and [0). The case where two bit flips happened, which would pass through our error mitigation, is even less probable.
Tomography Retrieving the amplitudes of a quantum state comes at cost of multiple measure- ments. which requires running the circuit multiples times, hence adding multiplicative overhead in the running time. A finite number of samples is also a source of approximation in the final result. In this work, we will allow for lo errors Kerenidis et al. (2020). The for tomography on quantum state ly) with unary encoding on qubits requires O[Tog (m)) measurements, where 8 >> 0 is the error threshold allowed. For each j E [n]] 1y51 will be obtained with an absolute error 8, and ly5l < 8, it will most probably not be measured, hence set to O. In practice, one would perform as many measurements as convenient during the experiment, and deduce the equivalent precision from the number of measurements made.
The next logical part is to obtain the sign of each component of the vector. Indeed, we only measure probabilities that are the square module of the quantum amplitudes (see Section A.3). In the case of neural networks, is important to obtain the sign of the layer's components in order to apply certain type of non linearities. For instance, the ReLu activation function is often used to set all negative components to O.
In Fig 12.
we propose specific enhancement our circuit obtain the signs of the vector's com- ponents at low cost. The sign retrieval procedure consists of three parts.
a) The cireuit is first applied as described above, allowing to retrieve each squared amplitude uz with precision 8 > O using the fx tomography. The probability of measuring the unary state les) (i.e. [100...)), is p(e1) -
b) We apply the same steps second time modified circuit. It has additional RBS gates with angle म 7/4 at the end, which will mix the amplitudes pair by pair. The probabilities measure (e1) and le2) are now given by p(e1) (y1 + y2)² 2 and p(ez) (31 2 Therefore if p(e)) > p(e2), we have sign(y)) * sign(y2). and if p(e)) < p(ez), we have sign(y1) sygn(y2). The same holds for the pairs (ya. 14). and
14

---

Under review as a conference paper at ICLR 2022
c) We finally perform the same where the RBS are shifted by position below. Then compare the signs of the pairs (y2. Va). (ya, ys) and so on.
At the end, able recover each value y with its sign, assuming that y1 > for instance. This procedure has the benefit of not adding depth to the original circuit, but requires 3 times more runs. The overall cost of the tomography procedure with sign retrieval is given by (nn/8)).
a)
b)
Pyramid (W)
Pyramid (W)
Pyramid (W)
RBS(w44)
RBS(w14)
Loader(x)
Loader(x)
Loader(X)
Figure 12: First tomography procedure to retrieve the value and the sign of each component of the resulting vector (n) = (Wx). Circuit a) is the original one while circuits b) and c) have additional RBS gates with angle /4 at the end compare the signs between adjacent components. In all three cases an foo tomography is applied.
In Fig 13 we propose another method to obtain the values of the amplitudes and their signs. Com- pared the above procedure, relies on one circuit only, but requires an extra qubit and a depth of 3n + O(1) instead of 2n (()).
X
Pyramid (W)
(1-ii)
Load(1//i
Load(x)
Figure 13: Second tomography procedure to retrieve the value and the sign of each component of the resulting vector lt) (Wr), For a rectangular case with output of size m, the two opposite loaders at end must be on the last qubits only, and the CNOT gate between them connects the top qubits to the loader's top qubit as well.
This circuit initializes the qubits in (10) + [1)) J0), where the last [0) correspond to the n qubits that will be processed by the pyramidal circuit and the loaders.
Next, applying the data loader for the normalized input vector x (see Section 2.3 and the pyramidal circuit will, according to Eq. map the state
10) 10) + +11> Σ Warr les)
(10)
Then, we use an additional data loader for the uniform norm-1 vector ./...... ).) Note that this loader is simply built reverse order to fit the pyramid and limit the augmentation the depth. We also apply the adjoint of this loader after controlled operation the first extra qubit. Recall that a circuit U is followed by Ut, it is equivalent to the identity. Therefore, this will load the uniform state only when the first qubit in state [1):
Σ W les) +
[1) Σ
les)
(11)
22
/2
15

---

Under review as a conference paper at ICLR 2022
Finally, Hadamard gate will mix both parts of the amplitudes the extra qubit give us the desired state:
1 Waat + V les)
1 [ leg)
10)
[1)
W
(12)
On this final state, we can see that the difference in the probabilities of measuring the extra qubit in state 0 or and rest in the unary state ej is given by Pr(O, ej] - Pr(1, es] (W J
W Wf the most frequent output of the measurement the first qubit. To deduce as well the value of W,r, we simply use Pr(O, ez] or Pr[1, ez] depending on the sign found before. For instance, if Waar have Wf 2 2 Pr,0
/ VT. Therefore, for each j. we can deduce the sign of Wjr j by looking at
vB
Combining with the &o tomography and the non linearity, the overall of this tomography is given by ((n/8²) as well.
A.4.2 MULTIPLE QUANTUM LAYERS
%
9,
(0)
(0)
(0) R
By
(0)
(b)
Figure 14: A full neural network with layers [8,8,4,4]. (a) Classical representation. (b) The equiv- alent quantum circuit is concatenation of multiple pyramidal circuits. Between each layer one performs a measurement and applics a non linearity. Each layer starts with a new unary data loader.
In the previous sections, we have seen how to implement quantum circuit perform the evolution of one orthogonal layer. In classical deep learning, such layers are stacked gain expressivity and accuracy. Between each layer, a non-linear function is applied to the resulting vector. The presence of these con-lincasssies is key in the ability the neural network to learn any function Leshno et al. 1993).
The benefit of using our quantum pyramidal circuit is the ability to simply concatenate them to mimic multi layer neural network. After each layer, tomography of the output state |2) is per- formed to retrieve each component, corresponding to its quantum amplitudes (see Section A.4.I). A non linear function is then applied classically obtain a(2). The next layer starts with
16

---

Under review as a conference paper at ICLR 2022
new unary data loader (See Section 2.3 quantum circuits reasonable for NISQ devices, by applying the neural network layer by layer.
This hybrid scheme allows well to keep the depth of the
Note that the quantum circuits proposed in this work can rightfully be called "quantum neural net- works" even though this term is usually employed for any arbitrary variational circuit for their close- ness to neural networks. With quantum pyramidal circuits, control and understand the quan- tum mapping. It implements each layer and its non linearities, quantum neural networks are also different regarding the training strategies which closer the classical ones (see Section 4 for details). That being said, it is interesting to compare our pyramidal circuit to variational circuit with qubits and n - 1)/2 gates of any type, as we usually see in the literature. Using such circuits we would explore among all possible 2" x 2" matrices instead of n x n classical orthogonal matrices, but so far there's no theoretical ground to explain why this should provide an advantage.
modular way. Our orthogonal
Therefore, as an open outlook, one could imagine incorporating additional entangling gates after each pyramid layer (composed, for instance, of CNOT or CZ). This would mark step out of the unary basis but could effectively allow exploring more interactions Hilbert Space.
17

---

Under review as a conference paper at ICLR 2022
A.4.3 ADDITIONAL NUMERICAL SIMULATIONS
To complete the results reported in Section 5
provide additional numerical experiments testing our classical pyramidal circuit for orthogonal neural networks on small use cases, in Fig 15 below.
Curver
Learning
13
20
Accuracy (96)
Tox Aucuracy N94
Paremidal Orthogonal NN
Pyramidal Orthogonal NV
Orthogonal
Hinibaton Iterations
Ninibatch Ittrations
(a) [16.4]
(b) [16.4]
Leat Curves
Learning
Rest Accuracy (N)
60
80
Tox
Orthogonel
Pyramidel Ortnogonal SVB Orthogoral NN
SVB Orthogonal
1003
Minibtton Ittronions
3000
340
1000
Minibbach
25N .012 5000
(c) [16,8,4]
(d) [32,8,2]
Learning
Leaming Curxes
02
Test Accuraty (86)
20
Pyromidal Orthogenal
Pyramidel Orthogona MN
SVB Orthogonal NN
SVS Orthagonal NN
Minibatch Beerttoos
Minibatch Iterations (1 [32,16.4]
(c) [32,8,4]
Figure 15: Training comparison between the SVB OrthoNN from Jia et al. 2019) and our classical pyramidal OrthoNN. Test accuracy on 1000 samples during several epochs training the MNIST dataset on 5000 samples. Initial dimensionality reduction (PCA) was on the samples to fit the input layer of the networks. Shaded areas indicate the accuracy variance during minibatch updates of size 50.
18


Reviews:
[{"review_id": "iH7r4-49c3l", "reviewer": "Reviewer_oStG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Strengths:\n- single, unified architecture that can be implemented on classical and quantum devices\n- simple data loading procedure for quantum computer that does not require assumptions about qRAM\n- good error characteristics of the unary representation\n- experimental results showing similar accuracy for the classical implementation, implementation on a quantum simulator, and implementation on a quantum computer\n\nWeaknesses:\n- as the authors note, computing $|Wx>$ for $x$ with $n$ features uses $U_W |x>$ where $U_W$ is a $2^n \\times 2^n$ unitary, i.e., one needs $n$ qubits for an $n$-dimensional dataset\n- literature review for the classical orthogonal NNs is missing some prior work similar to the pyramidal circuit. Refs. [1] and [2] propose a decomposition of an orthogonal matrix in NNs into a product of simpler matrices, with $O(n^2)$ trainable parameters in total, in a way similar to how Q matrix is decomposed in QR decomposition. [1] uses Householder projections while [2] uses Givens rotations, essentially the same building block as the RBS gate.\n\n[1] Dorobantu et al., DizzyRNN: Reparameterizing Recurrent Neural Networks for Norm-Preserving Backpropagation\n\n[2] Mhammedi et al., Efficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections", "summary_of_the_paper": "A parameterization of NNs that guarantees orthogonality, and is easily implementable using classical as well as quantum computing. The paper proposes a \"pyramidal circuit\" as a model/architecture that can be implemented on quantum devices and, in the same form, on classical devices. On quantum devices, it is implemented using 2-qubit, 2-level gates (RBS gates), and on classical devices as a sequence of planar rotations. In both cases, there are $n(n-1)/2$ trainable parameters that also only need $O(n^2)$ in the backward pass.", "summary_of_the_review": "While the efficient parameterization guaranteeing orthogonality is not entirely novel in classical ML, showing a single architecture that works on GPUs and on NISQ devices can gather significant interest from ML and QML communities.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gTe0kQM5SM1", "reviewer": "Reviewer_HBaw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The novelty of this paper is high. By the introduction of Pyramidal Circuit, the authors can implement an orthogonal matrix multiplication, which allows for gradient descent with perfect orthogonality with the same asymptotic running time as a standard fully connected layer. I think this is a good contribution to the deep learning community. However, the experiments are not very convincing since they lack the comparison of running times.  Overall,  I think the results in this paper are important.\n", "summary_of_the_paper": "This paper replaces usual weights and orthogonal matrices in orthogonal neural networks with an equivalent pyramidal circuit made of two-dimensional rotations.  By this, the authors proposed a training method for orthogonal neural networks that run in quadratic time, which is a significant improvement from previous methods based on Singular Value Decomposition. The authors also performed some numerical experiments to verify the abilities of their pyramidal circuit, on the standard MNIST dataset, which showed that their methods are efficient for learning a classification task.", "summary_of_the_review": "This paper proposed a training method for orthogonal neural networks that run in quadratic time, which is a significant improvement from previous methods based on Singular Value Decomposition. However, the experiments are not very convincing since they lack the comparison of running times.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aMUAoQ0TbCZ", "reviewer": "Reviewer_h1gX", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "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": "Strength:\n1. The paper gives a detailed derivation of the construction of the orthogonal NN layer and gives detailed gradient computation.\n2. The orthogonal quantum NNs are implemented on real quantum machines.\n\nWeakness:\n1. Major: The contribution and novelty of the paper are debatable. Using 2-dimensional unitary planar rotators to construct arbitrary unitary operations is well-established [1]. The beam splitter gate is a tunable Mach-Zehnder interferometer (MZI).\nThe unitary group parametrization was described in Section 2 of “The Unitary and Rotation Groups, Francis D. Murnaghan, 1962”. Using triangular array (Reck style [2]) and rectangular array (Clements style [3]) to construct arbitrary unitaries was proposed years ago and are widely applied in optical neural networks [4]. Training rotation phases in the unitary parametrization space with various robustness/discretization considerations already exist in the literature [5]. There are also techniques proposed to train rotation phases directly on-chip/in situ without software-assisted backpropagation [6]. Prior work also exists to solve gradient explosion issues in RNNs using those unitary operators [7].\n\n2. Major: The robustness of the constructed orthogonal layer is debatable. The triangular array constructs an arbitrary unitary with 2N-3 depth. Such a deeply-cascaded layer will encounter severe angle error accumulation issues, which is a well-observed phenomenon in optical neural networks [8]. Shallower quantum neural layers might be more resilient to quantum noises. Rectangular (Clements’ style) and butterfly meshes will be more noise-tolerant.\n\n3. Major: Experiments are weak. Not enough data and experiments to support the effectiveness of the orthogonal QNN layer. Discussion on efficiency and robustness of the orthogonal layer is missing.\n\n4. Minor: Training such triangular quantum unitary layers using backpropagation consumes considerable memory as each stage needs to store intermediate results, which is not quite scalable or efficient. Also, training such unitary meshes in the rotation angle space is sensitive to initialization. Without careful initialization, the signals will collapse into the local paths with slow convergence [9].\n\n[1] Nicholas C. Harris, Jacques Carolan, Darius Bunandar, et al., “Linear programmable nanophotonic processors,” Optica, 2018.\n\n[2] M. Reck, A. Zeilinger, H. Bernstein, et al., “Experimental realization of any discrete unitary operator,” Physical review letters, 1994.\n\n[3] William R. Clements, Peter C. Humphreys, Benjamin J. Metcalf, W. Steven Kolthammer, and Ian A. Walmsley, “Optimal design for universal multiport interferometers”, Optica, 2016.\n\n[4] Y. Shen, N. C. Harris, S. Skirloet al., “Deep learning with coherent nanophotonic circuits,” Nature Photonics, 2017.\n\n[5] J. Gu, Z. Zhao, C. Feng, H. Zhu, R. T. Chen and D. Z. Pan, \"ROQ: A Noise-Aware Quantization Scheme Towards Robust Optical Neural Networks with Low-bit Controls,\" DATE, 2020.\n\n[6] Tyler W. Hughes, Momchil Minkov, Yu Shi, Shanhui Fan, “Training of photonic neural networks through in situ backpropagation and gradient measurement,” Optica, 2018.\n\n[7] Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, et al., “Tunable Efficient Unitary Neural Networks (EUNN) and their application to RNNs,” ICML, 2017.\n\n[8] Michael Y.-S. Fang, Sasikanth Manipatruni, Casimir Wierzynski, et al., “Design of optical neural networks with component imprecisions,” Optics Express, 2019.\n\n[9] Sunil Pai, Ben Bartlett, Olav Solgaard, David A. B. Miller, “Matrix Optimization on Universal Unitary Photonic Devices,” Physical Review Applied, 2019.\n", "summary_of_the_paper": "The authors introduce a quantum pyramidal circuit to achieve an orthogonal layer of a neural network, which is fast and can maintain orthogonality. The angle gradients are derived. The authors implement the orthogonal NN on simulators and quantum machines to demonstrate the effectiveness.", "summary_of_the_review": "The originality of the paper content needs further justification. The method introduced were well-established in photonic computing and the machine learning community.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0ci22s11lQC", "reviewer": "Reviewer_ji2w", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Comments and concerns:\n\n- Reproducibility states \"We have explained in detail each part of both algorithms’ implementation, it is in our belief that anyone with classical software skills can re-implement the classical algorithm.\" If this is the author's belief, what harm would it do to simply release the code? Furthermore, could a classically trained software developer manage to reproduce the experiments on the real quantum device in a reasonable time frame? It is doubtful, as I am a software engineer who works with ibmq devices every day, and I know first-hand that any dealings with such devices are highly nontrivial. I'm doubtful I could reproduce the results in this paper in a reasonable time frame, if at all.\n\n- Section 5 numerical experiments is lacking significant details. The authors claim to achieve 98% accuracy on a binary mnist classification task on the real quantum computer ibmq_bogota. State preparation and measurement error for qubits on this device (very) often exceed 2%. This fact alone makes me highly skeptical of the results. Perhaps the authors did something more clever than what was presented in the paper to achieve this result, but its impossible to know without the code released and without a very detailed description.\n\n- Its unclear to me how significant the results in table 2 are. MNIST with all 10 classes can be classified with >99% accuracy. PCA on MNIST with 2 principle components renders the classes 6 and 9 nearly linearly-separable. I question if 95% accuracy can be achieved by the correct placement of a hyperplane (using 4 principle components). If so, is the network playing a significant role at all?\n\n- Figure 10, if I'm reading this figure correctly, I believe its showing a test accuracy on MNIST of 85%. This is very low compared to state of the art, and low compared to simple off-the-shelf methods. Perhaps I'm not understanding the significance of this, or reading it wrong altogether.\n\n- Section 4 would benefit greatly by being organized into a mathematical proof format, where things are clearly defined beforehand and not just italicized if they mean something particular. Its hard to access the correctness of the claims in the format they're provided in.\n\n- Section 3 states \"Therefore, for any given neural network’s orthogonal layer, there is a quantum pyramidal circuit that reproduces it\". Again, a statement like this is big, and requires a mathematical proof. Some loose form of justification is provided.\n\n- Equation 5 doesn't make sense to me. If W is an n by n matrix, x is n-dimensional, then Wx is n-dimensional. If U_W is 2^n by 2^n, then how can it operate on x?\n\n- Figure 6, very hard to follow where this matrix came from. I believe its the product of RBS gates.\n\n- Section 2.2 states \"The important property to note is that the number of parameters of the quantum pyramidal circuit corresponding to a neural network layer of size n × d is (2n − 1 − d) ∗ d/2 exactly the same as the number of degrees of freedom of an orthogonal matrix of dimension n × d.\" I believe the authors intended to say \"weight matrix\" instead of \"layer\", as a neural network layer can consist of more than a weight matrix.\n\nTypesetting and typos:\n\n- Fig.1. vs Eq.(1). doesn't feel consistent. Furthermore, the absence of a space for \"Fig.#\" is quite strange. Same with equations, like \"n=4\" with no spaces.\n\n- Fig. 2(b), the lines in the figure are not a consistent weight and I can not figure out what the intended meaning of this is. If it relates to Fig. 2(a), its unclear how. If it doesn't, the caption isn't sufficient to understand why the network edges are different weights.\n\n- Quotation marks shift in style throughout the paper.\n\n- Suggestion: Instead of repeating multiple times that s(theta) and c(theta) are sine and cosine respectively, state this a single time early in the paper.\n\n- Decimal formatting, virtually all ICLR papers abide by the format \"123.50\" rather than \"123,50\" to indicate 123 and one half. This paper uses the latter.\n\n- Figure 5 \"7th unary state to the 6th\", but mathematically indexing starts from 0, so the 7th unary state corresponds to j=6. This point could potentially confuse.\n", "summary_of_the_paper": "The authors propose a new type of neural network layer called a Pyramidal Circuit. This layer implements an orthogonal matrix multiplication, and its claimed that it allows for gradient descent to be run while maintaining perfect orthogonality, and with the same asymptotic running time as an arbitrary fully connected layer. This algorithm is inspired by quantum computing, and it can be applied on a classical computer or a near term (NISQ) quantum computer. To add supporting evidence that the Pyramidal Circuit works, the authors include some experiments demonstrating that networks with Pyramidal Circuit(s) can achieve some level of accuracy on binary classification problems.", "summary_of_the_review": "The overall idea of pyramidal circuits as neural network layers may have some novel significance. My overall understanding of the evidence supporting the claims in this paper is weak. It is missing any type of demonstration/concrete-proof that network weight matrices remain orthogonal during training, in addition to missing any demonstration of the claimed convergence rate proof. Despite my greater confidence in understanding implementations, I believe its reproducibility is questionable, and the experimental descriptions are lacking. The experimental results appear to be weak, such as achieving an 85% test accuracy on MNIST. Overall it was a difficult paper to access.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a quantum pyramidal circuit for the computation of orthogonal layers in neural networks and implements the algorithm on simulators and on a quantum computer to illustrate its effectiveness. It also obtains an O(n^2) classical algorithm for forward and backpropagation.

The reviewers generally found strength in the derivations and implementation on real quantum machines. Some reviewers regarded the contributions as strong and novel, while others expressed skepticism about the novelty and the robustness of the algorithm. Having read the paper in detail, I concur with the several reviewers who found the literature review of classical orthogonal NNs to be lacking. In particular, one reviewer highlights similarities with Householder reflections and Givens rotations, for which substantial literature already exists. Without a proper comparison to this existing work, it is not possible to properly assess the novelty or relative contributions of the current paper.

Beyond an extended discussion of related work, the paper would also benefit from improved experimental analysis. While the paper is framed around the quantum algorithm, the main contributions are described as a novel and efficient classical algorithm. This would indeed be a contribution of interest to the broader (non-quantum) ICLR community, but there is no experimental evidence supporting the utility of the proposed methods. An analysis that compares the classical algorithm to the numerous prior works that parameterize orthogonal layers would be an essential addition. As it stands, I cannot recommend the paper for publication.
Decision: Reject