線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: 線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析
• タイトル / 言語: en
• タイトル: Experimental analysis of a classical algorithm spoofing linear cross-entropy benchmarking
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 三重大学大学院工学研究科情報工学専攻
• 著者所属: 三重大学大学院工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering, Graduate School of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering, Graduate School of Engineering, Mie University
• 著者名: 鈴木, 健介; 河内, 亮周
• 著者名(英): Kensuke, Suzuki; Akinori, Kawachi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 量子計算機は古典計算機に対し，特定の計算において指数関数的に早く実行できることが期待されている (量子超越性)．しかし現在の量子計算機では計算途中にノイズが発生してしまい，誤り訂正ができないため正確な結果を出力することは難しい．そこで 2019 年に Arute ら Google のチームは線形交差エントロピー試験 (線形XEB) を用いて，ある程度の誤差を許容するような問題設定を行うことで，実験的に「量子超越性」を示した．それに対し Barak らは，線形 XEB を直接ターゲットとした古典アルゴリズムを考えることで，制限はあるが古典計算機でも高速に解けることを理論的に示した．しかし Barak らの研究では古典アルゴリズムの具体的な構成や性能については言及されていない．そこで本研究では Barak らの提案した古典アルゴリズムを改良し，具体的な構成を与えた．さらにそれを基に実験的解析を行い，具体的な性能を提示する．また，彼らのアルゴリズムにおいて理論的解析の前提となるパラメータ設定が不可能である具体的な例を構成する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 13, p. 1-8, 発行日 2021-04-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会