{"created":"2025-01-19T01:14:06.092438+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00213195","sets":["1164:10193:10565:10720"]},"path":["10720"],"owner":"44499","recid":"213195","title":["Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-10-07"},"_buckets":{"deposit":"5144fcfd-ccdb-4644-9dde-d9822304e05a"},"_deposit":{"id":"213195","pid":{"type":"depid","value":"213195","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization","author_link":["545041","545048","545045","545043","545042","545047","545044","545046"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization"},{"subitem_title":"Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2021-10-07","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Mizuho-DL Financial Technology Co., Ltd."},{"subitem_text_value":"Center for Quantum Information and Quantum Biology, Osaka University／Mizuho-DL Financial Technology Co., Ltd."},{"subitem_text_value":"Mizuho-DL Financial Technology Co., Ltd."},{"subitem_text_value":"Mizuho-DL Financial Technology Co., Ltd."}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Mizuho-DL Financial Technology Co., Ltd.","subitem_text_language":"en"},{"subitem_text_value":"Center for Quantum Information and Quantum Biology, Osaka University / Mizuho-DL Financial Technology Co., Ltd.","subitem_text_language":"en"},{"subitem_text_value":"Mizuho-DL Financial Technology Co., Ltd.","subitem_text_language":"en"},{"subitem_text_value":"Mizuho-DL Financial Technology Co., Ltd.","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/213195/files/IPSJ-QS21004001.pdf","label":"IPSJ-QS21004001.pdf"},"date":[{"dateType":"Available","dateValue":"2023-10-07"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-QS21004001.pdf","filesize":[{"value":"689.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"53"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"a841315e-076e-4892-bb5c-9fecda8f2b9d","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazuya, Kaneko"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Koichi, Miyamoto"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Naoyuki, Takeda"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuyoshi, Yoshino"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazuya, Kaneko","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Koichi, Miyamoto","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Naoyuki, Takeda","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuyoshi, Yoshino","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA12894105","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2435-6492","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"9","bibliographic_titles":[{"bibliographic_title":"量子ソフトウェア（QS）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2021-10-07","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicVolumeNumber":"2021-QS-4"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"links":{},"id":213195,"updated":"2025-01-19T17:14:18.825338+00:00"}