{"created":"2025-01-19T01:12:11.209716+00:00","updated":"2025-01-19T17:57:07.534816+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00210989","sets":["1164:2592:10486:10582"]},"path":["10582"],"owner":"44499","recid":"210989","title":["線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-04-30"},"_buckets":{"deposit":"4793ce83-92c4-498e-b0db-a8c4d86a7a84"},"_deposit":{"id":"210989","pid":{"type":"depid","value":"210989","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析","author_link":["535257","535259","535260","535258"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析"},{"subitem_title":"Experimental analysis of a classical algorithm spoofing linear cross-entropy benchmarking","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2021-04-30","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"三重大学大学院工学研究科情報工学専攻"},{"subitem_text_value":"三重大学大学院工学研究科情報工学専攻"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Information Engineering, Graduate School of Engineering, Mie University","subitem_text_language":"en"},{"subitem_text_value":"Department of Information Engineering, Graduate School of Engineering, Mie University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"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/210989/files/IPSJ-AL21183013.pdf","label":"IPSJ-AL21183013.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL21183013.pdf","filesize":[{"value":"1.3 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"4424123e-1102-469b-8d4d-05e1787e1065","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"鈴木, 健介"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"河内, 亮周"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kensuke, Suzuki","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akinori, Kawachi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","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":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"量子計算機は古典計算機に対し，特定の計算において指数関数的に早く実行できることが期待されている (量子超越性)．しかし現在の量子計算機では計算途中にノイズが発生してしまい，誤り訂正ができないため正確な結果を出力することは難しい．そこで 2019 年に Arute ら Google のチームは線形交差エントロピー試験 (線形XEB) を用いて，ある程度の誤差を許容するような問題設定を行うことで，実験的に「量子超越性」を示した．それに対し Barak らは，線形 XEB を直接ターゲットとした古典アルゴリズムを考えることで，制限はあるが古典計算機でも高速に解けることを理論的に示した．しかし Barak らの研究では古典アルゴリズムの具体的な構成や性能については言及されていない．そこで本研究では Barak らの提案した古典アルゴリズムを改良し，具体的な構成を与えた．さらにそれを基に実験的解析を行い，具体的な性能を提示する．また，彼らのアルゴリズムにおいて理論的解析の前提となるパラメータ設定が不可能である具体的な例を構成する．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Quantum computers are expected to be exponentially faster than classical computers in a specific computational task (quantum computational supremacy). In 2019, the Google team experimentally demonstrated quantum computational supremacy over a designated problem that can be solved even by the current noisy quantum computer by using the linear cross-entropy benchmark (linear XEB) . Barak et al., on the other hand, theoretically showed that some restricted version of the problem can be solved efficiently even on classical computers, by designing a classical algorithm that directly targets the linear XEB. In this paper, we give an explicit construction of the classical algorithm and perform experimental analysis to show the concrete performance. In addition, we provide an explicit quantum circuit that does not satisfy an assumption of some parameter setting for their theoretical analysis.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2021-04-30","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"13","bibliographicVolumeNumber":"2021-AL-183"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":210989,"links":{}}