The classical machine learning (ML) [1],[2] theory was created in 1950, but only 9 years later in 1959 Arthur Samuel gave a definition being “.... computers learning without being explicitly programmed”. It should understand that the functions (inputs-outputs) are deduced from a set of training data. The classical ML is characterized with: 1) supervised learning, i.e. classes of inputs corresponds to different classes, (2) unsupervised learning, i.e. the large data are summarized into a few stereotypes, and (3) reinforcement learning, i.e. rewards, reinforce the current strategy. Normally the classical MLs are working with big data, see [3],[4],.
The quantum Machine Learning (QML) are characterized by using quantum computing into the theory. One uses the ordinary interpretation of qubits, 1-qubit quantum gates, such as the Pauli matrices, etc.
then the 2-qubit gates like
and finally, Measurements
One uses the quantum algorithms to solve the ML problems with quantum computing. The most important ingredients in QML are: - choices of training sets, i.e. fi-nite sets of given vectors in order to then find some value corresponding to another input, - pattern completion, i.e. adding missing informations to incomplete inputs, and - associative memory, i.e. retrieving stored memory vectors upon an input.
This paper is the second part of the paper [8], in which we continue to treat the cases of polynomial regression with the high probability region bounds used as the corresponding thresholds. In Section II, we analyze the comceptions of classical aritificial neural networks (ANN) and quantum neural networks (QNN). The next section III is devoted to the problem of training the least square quantum neural networks (LS-QNN), like the least square interpolation, the general polynomial regression quantum neural network (PR-QNN) and the chi-squared test training (-QNN) in the next section IV. We look at the problem of least square problem (LSP) solution of the general polynomial regression and propose to use the quantum Gauss-Jordan Elemination (GJE) Code to solve the LSP equation. This let us to make the network works outperform the classical approaches. The paper is fin-ished with a conclusion in section IV and the last section V is our acknowledgments.
Following the model of Deutsch, a quantum neural network QNN(s, d) is a set of all quantum circuit of seize s and depth d with thresholds bounded by w. Quantum gates are interconnected by wires, preserve the sources and sink gates (measured the qubits and removed the entanglements with the maining qubits. Examples of QNNs are the implementation of NAND gate, dissipative ) and sink gates.
A threshold circuit is a boolean function :
of n integral variables
such that
) = 1 if and only if
∆. The class T C(s(n), d(n)) of threshold circuits of size s(n) and depth d(n), weighted by weight bound w can be approximated by elementary functions.
An equality threshold circuit is a boolean function :
of n integral variables
such that
) = 0 if and only if
= 0. The class EC(s(n), d(n)) of equality threshold circuits of size s(n) and depth d(n), weighted by weight bound w can be approximated by elementary functions.
It was proven that )) of weight bound O(s(n)) and
) + 1) of weight bound
)). And finally,
log s(n)), 2d(n)) of precision O(log w + d(n) log s(n)). (Theorem 4.6 from [9]).
The question is whether a QNN can be implemented on Quantum Turing Machine (QTM) (Church-Turing Thesis) is difficult to answer: Quantum computing showed that it is No, but physicists speculate that it is Yes.
First we remind that many problem, including the least squared problem and polynomial interpolation problems are reduced to solving systems of linear equations. In the previous work [6] we had showed that the Gauss-Jordan elimination procedure is consisting of an application of searching the pivot columns, which is reduced to use the Gover’s Search Algorithm and by the way necessary arithmetic operations over rows. The following lemma [8] is fundamental in many problems of namely the least square or the polynomial interpolation quantum neural networks.
Lemma 1 The quantum Gauss-Jordan Elimination Code can be implemented in QNN.
Let us consider the polynomial f(x) = of degree N on n variables, with unkown coefficients
, those we want to inpterpolate, and let (
),
= (
be the N + 1 interpolating points of the polynomial, x = (
) be the unkown variables,
= Π
= 0, . . . , N. The system of interpolating equations is a system of N+1 equation on N + 1
= 0, . . . , N:
The determinant of the system is of the Vandermonde type and of size (N + 1) + 1)
then the system can be written as
The matrix of the system is nonvanishing if the interpolating points are in a generic position. In that case the solution of the system is [= (
, where b = [
.
In general case the matrix can not be invertible, but the system is consistent. Based on Lemma 1, we can use the Gauss-Jordan elimination procedure on quantum neural networks to find out a basis of the null-space of the augmented matrix of the system (3.1). Let (be the Moore-Penrose pseudoinverse of
, then the solution to the interpolation problem is [
] = (
., where b = proj
].
The general interpolated solution is
We have therefore the following result
Theorem 2 The Least Square Quantum Neural Network (LS-QNN) and Polynomial Interpolation Quantum Neural Networks(PI-QNN) are implementable on QNN, with complexity ).
We now apply the Least Square Method to the problem of (general) regression (GRP). Let us remind that the Grover’s Searh Code can be implemented in QNN because the basic step is to repeatedly use the XOR quantum network gate [8]. The method of QGJE [6] is based on use of the Quantum Grover’s Search to find the pivot columns in the matirx .
We have therefore the following result
Theorem 3 The Polynomial Regression Quantum Neural Network (PR-QNN) is implementable, i.e. the GRP can be solved by a QNN, with complexity ).
Let us analyze how to train the GRP code in QNN. With the above interpolating quantum code, we can divide the data into to treatment: regression treatment
= [ˆ
] and residual treatment
= [
], where
Let us denote by
where r is the Pearson correlation, r = Cor(X, Y ). We may fix a level of explained proportion of variance and define the F-ratio
. Therefore we define the training threshold as if the F-ratio is in the high probability 1
region
In the nonparametric statistics, the -test plays important roles in many problems like contingency tables, homogeneity, ....... Let use conside the corresponding quantum code in QNN. Denote by e = [
be a contingency matrix of expected values
. The random distribution X = [
] is a matrix of size
. The degree of freedom is
. The chi-squared statistic is of form
Our aim is to implement the -test in a QNN and use the chi-sqaured test as the rule of training.
Theorem 4 The Chi-Squared Quantum Neural Network (-QNN) is implementable, , i.e. the
-test can be solved by a QNN, with complexity
1)
1)).
Indeed, the high probability 1 region is
for a fixed -level of confidence and the training rule is to sink the network if the constraint is faile to be satisfied. If the constraint holds, it passes to the next layer of QNN.
We implemented the quantum neural networks: the least square quantum Neural Network (LS-QNN) and the polynomial interpolation quantum neural networks (PI-QNN), the Polynomial Regression Quantum Network (PR-QNN) and the Chi-Squared Quantum Neural Network (-QNN). The training rules are provided with the corresponding test from Statistics.
The authors express their sincerle thanks to Professor K. Nagata, Professor G. Resconi, Professor T. Nakamura, Professor S. Heidari and the referees for careful reading the manuscripts and valuable comments.
[1] N. Wiebe, A. Kapoor, K. Swore, Quantum deep learning, arXiv:1412.3489v2[quant-ph], 2015.
[2] G. Hinton, A Practical Guide to Training Restricted Boltzmann Machines, Department of Computer Science, University of Toronto.
[4] A. A. Ezhov, D. Ventura, Quantum neural networks, in
[6] D. N. Diep, D. H. Giang, N. V. Minh, Quantum Gauss-
[8] D. N. Diep, Some quantum neural networks, Intl. J. Theor. Phys. (to appear).
[9] S. Gupta, R.K. P. Zia, Quantum Neural Network, Journal of computer and system sciences, 63(2001), 355-383.