WEKO3
アイテム
表面符号における素因数分解を行うShorアルゴリズムの計算量評価
https://ipsj.ixsq.nii.ac.jp/records/233696
https://ipsj.ixsq.nii.ac.jp/records/233696a369a425-cf0f-45d4-8177-5181d96163e3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-QS24011022.pdf (1.0 MB)
2026年3月21日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, QS:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-03-21 | |||||||||
| タイトル | ||||||||||
| タイトル | 表面符号における素因数分解を行うShorアルゴリズムの計算量評価 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Evaluation of Factorization by Shor’s Algorithm on Surface Code | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 三菱電機株式会社情報技術総合研究所 | ||||||||||
| 著者所属 | ||||||||||
| 筑波大学システム情報系 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Mitsubishi Electric Corporation | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| University of Tsukuba | ||||||||||
| 著者名 |
大西, 健斗
× 大西, 健斗
× 國廣, 昇
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Shor アルゴリズムは，素因数分解問題や離散対数問題を効率的に解く量子アルゴリズムであり，現在利用されている公開鍵暗号である RSA 暗号や楕円曲線暗号が解読可能となることが知られている．しかし，これらの問題を解くうえで課題となるのが，量子計算機のノイズである．従来研究では，表面符号のように，この量子計算機のノイズを低減する耐故障性の研究が進められている．特に，耐故障性を持つ量子計算機上で，現在利用されている公開鍵暗号の安全性解析を行うことは極めて重要である．本稿では，表面符号上において，Shor アルゴリズムにより素因数分解を解くために必要な計算コストの見積もりを行う．特に，本稿では，表面符号や魔法蒸留において必要なリソースについて，計算量的に評価するとともに，それらを踏まえた Shor アルゴリズムの計算コストを導出する． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Shor's algorithm solves the integer factoring problem and discrete logarithm problem. Currently used public-key cryptosystems, including RSA and elliptic curve cryptosystems, are broken by Shor's algorithm. However, noise during computation prevents from solving these problems. Many researchers have studied methods for decreasing noise during computation including surface code. Therefore, security evaluation on public-key cryptosystems on fault-tolerant quantum computers is very important. This paper evaluates computational costs of solving the integer factoring problem by Shor's algorithm on surface code. This paper also clarifies computational cost for Shor's algorithm including surface code and magic distillation. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA12894105 | |||||||||
| 書誌情報 |
研究報告量子ソフトウェア（QS） 巻 2024-QS-11, 号 22, p. 1-8, 発行日 2024-03-21 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2435-6492 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
