講演抄録/キーワード |
講演名 |
2021-05-08 11:30
線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析 ○鈴木健介・河内亮周(三重大) COMP2021-7 |
抄録 |
(和) |
量子計算機は古典計算機に対し,特定の計算において指数関数的に早く実行できることが期待されている(量子超越性).しかし現在の量子計算機では計算途中にノイズが発生してしまい,誤り訂正ができないため正確な結果を出力することは難しい.そこで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 / / / / |
文献情報 |
信学技報, vol. 121, no. 11, COMP2021-7, pp. 46-53, 2021年5月. |
資料番号 |
COMP2021-7 |
発行日 |
2021-04-30 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2021-7 |
研究会情報 |
研究会 |
COMP IPSJ-AL |
開催期間 |
2021-05-07 - 2021-05-08 |
開催地(和) |
オンライン開催 |
開催地(英) |
Online |
テーマ(和) |
|
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2021-05-COMP-AL |
本文の言語 |
日本語 |
タイトル(和) |
線形交差エントロピー試験を突破する古典アルゴリズムの実験的解析 |
サブタイトル(和) |
|
タイトル(英) |
Experimental analysis of a classical algorithm spoofing linear cross-entropy benchmarking |
サブタイトル(英) |
|
キーワード(1)(和/英) |
量子超越性 / quantum computational supremacy |
キーワード(2)(和/英) |
線形交差エントロピー試験 / linear XEB |
キーワード(3)(和/英) |
古典アルゴリズム / classical algorithm |
キーワード(4)(和/英) |
実験的解析 / experimental analysis |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
鈴木 健介 / Kensuke Suzuki / スズキ ケンスケ |
第1著者 所属(和/英) |
三重大学 (略称: 三重大)
Mie University (略称: Mie Univ.) |
第2著者 氏名(和/英/ヨミ) |
河内 亮周 / Akinori Kawachi / カワチ アキノリ |
第2著者 所属(和/英) |
三重大学 (略称: 三重大)
Mie University (略称: Mie Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2021-05-08 11:30:00 |
発表時間 |
20分 |
申込先研究会 |
COMP |
資料番号 |
COMP2021-7 |
巻番号(vol) |
vol.121 |
号番号(no) |
no.11 |
ページ範囲 |
pp.46-53 |
ページ数 |
8 |
発行日 |
2021-04-30 (COMP) |