Learning in High-Dimensional Multi-response Linear Models with Quantum non-Oracular Search (when the range of the coefficient matrix is known)

This paper studies the high-dimensional, low-rank multivariate linear model, which provides us with relevant information given a sample, with the help of a hybrid quantum computing algorithm (combining quantum and classical computing to solve a problem). The method estimates each of the entries of the coefficient matrix by identifying the linearly independent columns, in addition to estimating the error matrix. We will give a concrete example when the rank of the coefficient matrix is known. When the rank is unknown, we have a NP-hard problem with solution. The coefficient matrix is obtained through of a non-oracular quantum search algorithm (NQS), see [1],[2], in its initial stage, a combinatorial search must be performed on all possible ranks, then on all possible distributions of the linearly independent columns in the matrix. In our research we partially perform the execution of the mentioned quantum algorithm, however, we show in detail the critical part of it, which consists in reducing the loss function L_n defined in [1], [2], to a multivariate quadratic optimization problem, furthermore optimizing it, this stage is a starting point for the full implementation of the algorithm. We show only one optimization of all those to be performed through a combinatorial search specified in [1], [2]. The last stage of the NQS algorithm consists in elaborating an increasing sequence from the parameters of each optimization substituted in the loss function L_n, work which is not included in this article and which corresponds to an NP-hard problem (when the rank of the matrix is unknown). The understanding of our work will allow different areas of study with real multivariate data to make predictions such as demography, medicine, etc.