Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization

• Item type: SIG Technical Reports(1)
• 公開日: 2021-10-07
• タイトル: Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• タイトル / 言語: en
• タイトル: Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Mizuho-DL Financial Technology Co., Ltd.
• 著者所属: Center for Quantum Information and Quantum Biology, Osaka University／Mizuho-DL Financial Technology Co., Ltd.
• 著者所属: Mizuho-DL Financial Technology Co., Ltd.
• 著者所属: Mizuho-DL Financial Technology Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Mizuho-DL Financial Technology Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Center for Quantum Information and Quantum Biology, Osaka University / Mizuho-DL Financial Technology Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Mizuho-DL Financial Technology Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Mizuho-DL Financial Technology Co., Ltd.
• 著者名: Kazuya, Kaneko; Koichi, Miyamoto; Naoyuki, Takeda; Kazuyoshi, Yoshino
• 著者名(英): Kazuya, Kaneko; Koichi, Miyamoto; Naoyuki, Takeda; Kazuyoshi, Yoshino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Linear regression is a basic and widely-used methodology in data analysis. It is known that some quantum algorithms efficiently perform least squares linear regression of an exponentially large data set. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error ε: the best one among the existing proposals is O(ε-2). In this paper, we propose a new quantum algorithm for linear regression, which has a complexity of O(ε-1) and keeps a logarithmic dependence on the number of data points ND. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ND, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Linear regression is a basic and widely-used methodology in data analysis. It is known that some quantum algorithms efficiently perform least squares linear regression of an exponentially large data set. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error ε: the best one among the existing proposals is O(ε-2). In this paper, we propose a new quantum algorithm for linear regression, which has a complexity of O(ε-1) and keeps a logarithmic dependence on the number of data points ND. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ND, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 量子ソフトウェア（QS）; 巻 2021-QS-4, 号 1, p. 1-9, 発行日 2021-10-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会