Learning High Dimensional Multi-response Linear Models with Non-oracular Quantum Search
Learning High Dimensional Multi-response Linear Models with Non-oracular Quantum Search
复制标题
DOI：
10.1109/qce53715.2022.00018
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Jinyang Chen;Cheolwoo Park;Y. Ke
中科院分区：
文献类型：
--
作者：
Jinyang Chen;Cheolwoo Park;Y. Ke
本文用混合量子计算算法研究了高维多响应数据的线性回归模型。我们提出了一种基于识别系数矩阵中线性无关列的直观吸引人的估计方法。我们的方法放宽了现有文献中的低秩约束，允许秩随维度发散。采用一种新颖的非神谕量子搜索（NQS）算法选择线性无关的列，该算法比在电子计算机上实现的经典搜索方法要快得多。此外，NQS实现了与现有量子搜索算法相比接近最优的计算复杂度，并且不需要解状态的任何oracle信息。我们证明了所提出的估计方法具有良好的理论性质。通过大量的数值实验验证了该方法的有限样本性能，并与一些流行的竞争方法进行了比较。结果表明，在各种情况下，我们的方法优于所有替代方法。
This paper studies linear regression models for high dimensional multi-response data with a hybrid quantum computing algorithm. We propose an intuitively appealing estimation method based on identifying the linearly independent columns in the coefficient matrix. Our method relaxes the low rank constraint in the existing literature and allows the rank to diverge with dimensions. The linearly independent columns are selected by a novel non-oracular quantum search (NQS) algorithm which is significantly faster than classical search methods implemented on electronic computers. Besides, NQS achieves a near optimal computational complexity as existing quantum search algorithms but does not require any oracle information of the solution state. We prove the proposed estimation procedure enjoys desirable theoretical properties. Intensive numerical experiments are also conducted to demonstrate the finite sample performance of the proposed method, and a comparison is made with some popular competitors. The results show that our method outperforms all of the alternative methods under various circumstances.