| 講演名 | 2021-05-08 線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析 鈴木 健介(三重大), 河内 亮周(三重大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 量子計算機は古典計算機に対し，特定の計算において指数関数的に早く実行できることが期待されている(量子超越性)．しかし現在の量子計算機では計算途中にノイズが発生してしまい，誤り訂正ができないため正確な結果を出力することは難しい．そこで2019年にAruteらGoogleのチームは線形交差エントロピー試験(線形XEB)を用いて，ある程度の誤差を許容するような問題設定を行うことで，実験的に「量子超越性」を示した．それに対しBarakらは，線形XEBを直接ターゲットとした古典アルゴリズムを考えることで，制限はあるが古典計算機でも高速に解けることを理論的に示した．しかしBarakらの研究では古典アルゴリズムの具体的な構成や性能については言及されていない．そこで本研究ではBarakらの提案した古典アルゴリズムを改良し，具体的な構成を与えた．さらにそれを基に実験的解析を行い，具体的な性能を提示する．また，彼らのアルゴリズムにおいて理論的解析の前提となるパラメータ設定が不可能である具体的な例を構成する． |
| 抄録(英) | 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. |
| キーワード(和) | 量子超越性 / 線形交差エントロピー試験 / 古典アルゴリズム / 実験的解析 |
| キーワード(英) | quantum computational supremacy / linear XEB / classical algorithm / experimental analysis |
| 資料番号 | COMP2021-7 |
| 発行日 | 2021-04-30 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2021/5/7(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 増澤 利光(阪大) |
| 委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 副委員長氏名（和） | 小野 廣隆(名大) |
| 副委員長氏名（英） | Hirotaka Ono(Nagoya Univ) |
| 幹事氏名（和） | 大下 福仁(奈良先端大) / 安藤 映(専修大) |
| 幹事氏名（英） | Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.) |
| 幹事補佐氏名（和） | 大舘 陽太(名大) |
| 幹事補佐氏名（英） | Yota Otachi(Nagoya Univ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析 |
| サブタイトル（和） | |
| タイトル（英） | Experimental analysis of a classical algorithm spoofing linear cross-entropy benchmarking |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子超越性 / quantum computational supremacy |
| キーワード(2)（和/英） | 線形交差エントロピー試験 / linear XEB |
| キーワード(3)（和/英） | 古典アルゴリズム / classical algorithm |
| キーワード(4)（和/英） | 実験的解析 / experimental analysis |
| 第 1 著者 氏名（和/英） | 鈴木 健介 / Kensuke Suzuki |
| 第 1 著者 所属（和/英） | 三重大学(略称：三重大) Mie University(略称：Mie Univ.) |
| 第 2 著者 氏名（和/英） | 河内 亮周 / Akinori Kawachi |
| 第 2 著者 所属（和/英） | 三重大学(略称：三重大) Mie University(略称：Mie Univ.) |
| 発表年月日 | 2021-05-08 |
| 資料番号 | COMP2021-7 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | COMP-11 |
| ページ範囲 | pp.46-53(COMP), |
| ページ数 | 8 |
| 発行日 | 2021-04-30 (COMP) |