量子コンピューターによる暗号への影響に関する，
NICTセキュリティ基盤研究室の取り組み

サイバーセキュリティシンポジウム2023

国立研究開発法人情報通信研究機構 サイバーセキュリティ研究所
セキュリティ基盤研究室 主任研究員 青野 良範
2023/02/17 15:05-15:35

自己紹介
青野 良範（AONO, Yoshinori）
国立研究開発法人情報通信研究機構（NICT）
サイバーセキュリティ研究所 セキュリティ基盤研究室 主任研究員

略歴
東京工業大学 情報理工学研究科 数理・計算科学専攻（理学）2011年に情報通信研究機構サイバーセキュリティ研究所に入所後、
公開鍵暗号の安全性評価に関わる研究を行う。
2019年より慶應義塾大学量子コンピューティングセンターとともに共同研究を開始、量子コンピュータの公開鍵暗号に対する影響を調査。

NICT サイバーセキュリティシンポジウム

講演資料

p.2

目次
★研究背景説明（量子コンピュータと暗号に関する研究活動の調査）★量子コンピュータを用いた離散対数問題の計算実験と将来予測
RSA-2048
RSA-1024？

Now

RSA暗号の量子解読計算量[Gidney-Ekerå, 2019]

2050
2048

※量子デバイスのCNOTゲートエラーが1年ごとに半分になるトレンドが長期間続くと仮定したときの予測

NICT サイバーセキュリティシンポジウム

講演資料

p.3

量子コンピュータの発展と暗号への影響✔量子コンピュータが発展すると公開鍵暗号の解読がおそらく現実的な時間で可能になる [Shor@ANTS, FOCS1994]

現在使われている
公開鍵暗号・署名が危殆化

CRYPTREC暗号リスト（最終更新2022/04/30）✔現代暗号に影響する範囲として特にRSA暗号、楕円曲線暗号など（素因数分解、離散対数問題が量子多項式時間で解ける）

NICT サイバーセキュリティシンポジウム

講演資料

p.4

量子コンピュータの発展と暗号への影響✔量子コンピュータが発展すると暗号解読が大幅に高速化する [Grover@STOC1996]

現在使われている
共通鍵暗号・ハッシュ関数に影響

CRYPTREC暗号リスト（最終更新2022/04/30）✔共通鍵暗号・ハッシュ関数の解読計算量が大幅に下がる： 2𝑛 → 20.5𝑛• ETSI GR QSC 006 V1.1.1, Limits to Quantum Computing applied to symmetric key sizes (2017)• CRYPTREC技術報告書「量子コンピュータが共通鍵暗号の安全性に及ぼす影響の調査及び評価」 (2019)
NICT サイバーセキュリティシンポジウム

講演資料

p.5

量子コンピュータの発展と暗号への影響✔有名なShor, Grover以外でも，大型の量子コンピュータが登場することで様々な暗号に影響を与えることが知られている．
• RSA暗号，楕円曲線暗号のように量子コンピュータで安全性が極端に低下するもの→新しい暗号（耐量子計算機暗号）への移行• 共通鍵暗号，ハッシュ関数のように量子コンピュータで安全性が低下するがそれでも安全と考えられるもの →パラメータの見直し★耐量子計算機暗号の普及までのスケジュール
公募• NIST(米)• CACR(中)• KpqC(韓)標準化
移行スケジュール設計
NIST, ETSI, IETF,
NcCOE, ETSIISO, etc.
ガイドライン作成

普及

CRYPTREC(日), NSA Suite(米), BSI(独)ANSSI(仏), ROSSTANDART TC26(露), etc.
NICT サイバーセキュリティシンポジウム

講演資料

p.6

暗号の移行スケジュールを立てるために■いつが普及準備のタイムリミットなのか？
普及閾値
■Mosca’s model (2015)
Y(システム移行にかかる時間)

X(データ保護期間)

Z(量子コンピュータ大型化)

Z < Y+X ⇒Time★WHEN is Q-day?

Mosca and Piani “Quantum Threat Timeline Report 2021” より引用・加筆
NICT サイバーセキュリティシンポジウム

講演資料

p.7

When is Q-day? 文献調査 1/3✔Metaculus★オンラインの予測サイト△誰でも投票可能✔2023/1/24現在の状況• 202個/81人の予測• 中央値 2042年

NICT サイバーセキュリティシンポジウム

講演資料

p.8

When is Q-day? 文献調査 2/3✔専門家の予測（招待講演＆アンケート）

NICT サイバーセキュリティシンポジウム

講演資料

p.9

When is Q-day? 文献調査 2/3✔専門家の予測（招待講演＆アンケート）

NICT サイバーセキュリティシンポジウム

講演資料

p.10

When is Q-day? 文献調査 2/3✔専門家の予測（招待講演＆アンケート）△予測年-発表年≒15年の法則……一部ではQuantum jokeと呼ばれているらしい？

★もう少しデータに基づいた将来予測が必要
NICT サイバーセキュリティシンポジウム

講演資料

p.11

When is Q-day? 文献調査 3/3

量子Cの計算能力★過去の実績からの外挿

RSA-2048を解くための計算量

★

■Now

西暦
2023.2

Q-day
NICT サイバーセキュリティシンポジウム

講演資料

p.12

■必要な仕事① 単位を決める② 過去のトレンドを調べて将来を予測• 指数関数的な成長を仮定（○○版ムーア）• 未知の物理的な限界は無いと仮定• 新技術による加速、予算・エネル
ギーの制約による原則も無いと仮定③ 暗号の解読計算量の見積もり①

FLOPS (Peak Performance)

過去の実績からの外挿に関する先行研究③②• RSA-○○を1年間で解読する性能※CRTPTREC Report 2021 図3.2-1をスライド向けに改変
NICT サイバーセキュリティシンポジウム

講演資料

p.13

単位選択に関する先行研究△FLOPSのようなデファクトスタンダードが確立していれば良いのだが、現状(NISQ)量子コンピュータの性能を測るための評価軸は様々なものが提案中✔全体的な傾向として• 計算速度は気にしない• 答えを知った上でそこからの近さを測る（NISQデバイス向け）★将来予測に求められる性質• 単一指標• ロードマップ、過去のトレンドからの将来予測が用意されている
NICT サイバーセキュリティシンポジウム

講演資料

p.14

単位選択の重要性 (Quantum Volume)✔Quantum Volume (量子体積)
・2019年IBMの研究者により提案
・回路計算型量子コンピュータの汎用的なベンチマークを基にしている★IBMがロードマップを公開（少なくとも2倍/年：指数関数的な成長）

深さ𝑑𝑘量子ビット量子回路⇔

𝑄𝑉 = 2min(𝑘,𝑑)△将来予測の（あまり上手くない）例 [Aono et al. QIT43 (2020)]✔2020年10月の時点で𝑄𝑉 = 64 = 26 , 大体6量子ビットの（あまり深くない）回路を実行可能✔毎年QVが2倍⇒実行可能な回路サイズが毎年+1量子ビット△𝑛ビットの素因数分解回路で最良のものでも𝑘 = 2𝑛 + 2量子ビット必要
RSA-2048だとそれぞれ4000年後、 EdDSA(448ビット)でも1300年後
NICT サイバーセキュリティシンポジウム

講演資料

p.15

単位選択の重要性 (分解された数のトレンド)★素因数分解の実験報告からの将来予測を試みる✔この20年間で30件ほどの実験報告（Shorに限っても10件）

QAOA
アニーリングShor✔ Shor以外の伸びは凄まじいがアルゴリズムが異なりトレンド予測が困難
NICT サイバーセキュリティシンポジウム

講演資料

p.16

Shorに関する回路サイズの伸び✔2010年以前はNMR, フォトニック
による実験✔近年は超電導量子C★特殊化された回路の実行• 分解対象の数に現れない部分での進歩• 少しずつ大型化して一般的なものに近づいている• 解けたかどうかの基準が統一されていない

Skosana-Tame (2021)
5 qubits, (数値の圧縮表現)

NMR, VSP+01★状況をもっと詳しく見るための
量子C実機による実験が必要

Vandersypen et al. (2001)
7 qubits, NMR

Amico et al. (2019)5 qubits(指数部分の分割実装)

Lucero et al. (2012)
3 qubits, Josephson gate

CRYPTREC外部評価報告書『Shor のアルゴリズム実装動向調査』(2021)より
NICT サイバーセキュリティシンポジウム

講演資料

p.17

ここまでのまとめ✔耐量子計算機暗号への移行スケジュールのためにQ-dayの予測が必要✔Q-dayの予測のために予測のグラフが必要• 計算性能の指標（縦軸）は単一かつロードマップのあるものが欲しい✔単一でロードマップのある指標はいくつか存在する• NISQ向けロードマップを単純に引き延ばすとあまり良くない予想になる
可能性★先行研究の多くは部分回路を使った予備実験的なもの• 解けたかどうかの基準が統一されていない

NICT サイバーセキュリティシンポジウム

講演資料

p.18

目次
• 研究背景説明（量子コンピュータと暗号に関する先行研究の調査）• 量子コンピュータを用いた離散対数問題の計算実験と将来予測
RSA-2048
RSA-1024？

RSA暗号の量子解読計算量[Gidney-Ekerå, 2019]

2050
2048

Now
※量子プロセッサのCNOTゲートエラーが1年ごとに半分になるトレンドが長期間続くと仮定したときの予測
NICT サイバーセキュリティシンポジウム 講演資料

p.19

研究内容の概要★量子コンピュータの暗号に対する将来的な影響を調査する目的で，4者での共同研究• 情報通信研究機構• 三菱UFJフィナンシャル・グループ• 慶應義塾• みずほフィナンシャルグループ★『解けた』の基準作り✔量子コンピュータから何が出てきたら問題が解けたと主張できるのか？
• 将来予測をするベースとして『今の量子Cはどこまでの問題が解けるのか』• 予測図を描くにしても『性能指数が○○を超える量子コンピュータはRSA-△△,
DLP-△△を解くことができる』ということが読み取れるようにしたい★離散対数問題の実験△回路が最小になるインスタンス： 2 𝑧 ≡ 1 mod 3 , 2 𝑧 ≡ 2 (mod 3)△教科書に載っている15の素因数分解回路はまだ厳しい★実験とロードマップからの将来予測
NICT サイバーセキュリティシンポジウム

講演資料

p.20

実験の役割分担
実際に解く問題・
インスタンス選択

NICT

三菱

みずほ

慶應義塾

• RSA or DLP• Size of instances

論理レベル回路設計
回路のトランスパイル＆最適化
量子コンピュータ実機
での実行
出力結果の後処理
NICT サイバーセキュリティシンポジウム

講演資料

p.21

NISQコンピュータの実行
NISQ量子コンピュータの実行順序
1: 0011010101
2: 1101010111
3: 0101100111

後処理

･･･

量子回路
（論理レベル）

量子回路

同じ回路を
（トランスパイル後） 何千回も実行

8190: 0101100111
8191: 0011001110
8192: 1101001010

解の候補が何千個も出てくる✔同じ回路を何度も実行して測定を行う• 量子Cはある確率分布からのサンプル（＋ノイズ）をビット列として出力• ビット列を後処理して離散対数，素因数の候補を出力• ノイズが大きいとほぼ乱数になる△今のところ、小さいインスタンスの回路しか実行できない• 離散対数問題（2𝑧 ≡ 1 mod 3）、素因数分解(15)• 何千回も実行したらたとえ乱数でも1、2回は当たる
量子コンピュータの写真：https://www.flickr.com/photos/ibm_research_zurich/51331567650/in/album-72157703845574031/

NICT サイバーセキュリティシンポジウム

講演資料

p.22

実験結果と解釈
2 𝑧 ≡ 1 mod 3

2 𝑧 ≡ 2 mod 3

論理レベル回路
トランスパイル後

実行後の
確率分布

実機出力≈シミュレーション
解けている！

実機出力≈シミュレーション？
解けている……？

★実験成功を定量的に測る何らかの基準が必要
NICT サイバーセキュリティシンポジウム

講演資料

p.23

正解率ベースの成功定義

確率★量子(NISQ)コンピュータによる実験が成功したかどうかを定量的に測りたい✔先行研究：確率変数のスコアによる中間値基準の判定
実機の出力(0～100点)一様分布(0点)
理想的な出力(100点)
測定ビット列• 確率分布に対して数値を割り当てる• 数値が中間値よりも上ならば実験成功とする
Score(実験) > (Score(理想)+Score(ランダムノイズ))/2 ⇒■我々のスコアは後処理アルゴリズムの正解率とした• 離散対数問題の解の候補𝑧に対して，𝑔 𝑧 ≡ 𝑎 (mod 𝑝)を満たすかどうか
NICT サイバーセキュリティシンポジウム

講演資料

p.24

正解率

実際の実験（2𝑧 ≡ 2 mod 3 は解けているか？）★実機出力の正解率の他に、４種類のシミュレーションを行い正解率を比較• 量子ノイズの無い回路の出力• 一様ランダムなビット列• これらの平均値が成功のしきい値△結論としてまだ解けていない• いつ解けるようになるのか？

※Shorによる離散対数問題の特徴として、後処理アルゴリズムに複数個のビット列を入力することが可能で、それにより正解率が少しだけ上がる※ibm_kawasakiによる実験は2021年7月

NICT サイバーセキュリティシンポジウム

講演資料

p.25

正解率

実際の実験（2𝑧 ≡ 2 mod 3 は解けているか？）★実機ノイズのパラメータ化• CNOT error=0.07としたシミュレーション★error↓ 正解率↑

★CNOT error=0.04まで下げると成功になると予想される• 量子Cが進化しエラーレートが半分になるのを待つ※Shorによる離散対数問題の特徴として、後処理アルゴリズムに複数個のビット列を入力することが可能で、それにより正解率が少しだけ上がる※ibm_kawasakiによる実験は2021年7月

NICT サイバーセキュリティシンポジウム

講演資料

p.26

2𝑧 ≡ 2 mod 3 はいつ解けるのか？
✔ノイズが今の半分なると『解けた』と宣言できる• いつ半分になるのかを予測✔ IBMの量子プロセッサはCNOTゲートのエラーレートを公開している• 過去５年間の実績として毎年エラーレートが半減★エラーレートを半分にするには１年待てば良い★前頁の実験は2021年7月に
ibm_kawasakiを用いたもの

ibm_kawasaki

Picture from https://research.ibm.com/blog/heavy-hex-lattice
NICT サイバーセキュリティシンポジウム

講演資料

p.27

さらに遠い将来予測のために★色々な仮定を盛り込む必要がある★シミュレーション上でのCNOTエラー率とトランスパイル後のCNOTゲート数の関係の傾向✔解釈：回路中1か所でもエラーが起きると，後処理アルゴリズムが正しい答えを出さなくなる★毎年ノイズが半減⇒実行可能な回路規模が毎年倍増△搭載量子ビットによる制約は考えない

Aono et al., IEEE TQE (2022-3),
Fig. 11

NICT サイバーセキュリティシンポジウム

講演資料

p.28

近未来予想★トランスパイル後の実行可能CNOTゲート数は2021年7月リリースの
ibm_kawasakiで大体1/0.07=14• これが単純に1年で2倍になると仮定★教科書的な15の素因数分解回路（数値表現4量子,QFT4量子,#CNOT=86）
がそろそろ実行可能になるか？

NICT サイバーセキュリティシンポジウム

講演資料

p.29

遠い将来の予想★Gidney-Ekerå(2019)によると、RSA-2048を解くためには大体1.35×1010のCNOTゲート✔トランスパイルによる増大が無いと仮定しても大体2050年前後△不確定要素がかなり多い• Q-dayを遅らせる要因：物理的な限界• 早める要因：量子誤り訂正、量子メモリ、アルゴリズムの改良
RSA-2048
RSA-1024
？

Now

2050
2048

RSA暗号の量子解読計算量[Gidney-Ekerå, 2019]★量子誤り率が10-3～10-4程度まで下がると量子誤り訂正が効いてくるため、加速する可能性※量子プロセッサのCNOTゲートエラーが1年ごとに半分になるトレンドが長期間続くと仮定したときの予測
NICT サイバーセキュリティシンポジウム

講演資料

p.30

まとめ
★量子コンピュータと暗号に関する研究活動の調査• 量子コンピュータの大規模化により、公開鍵暗号が危殆化、共通鍵暗号・ハッシュ関数にも影響• 量子コンピュータの性能進化に関する将来予測が重要だが、単位のスタンダードはまだない★量子コンピュータを用いた離散対数問題の計算実験と将来予測• 現在の量子CでShorのアルゴリズムを実行するためには、何らかの簡略化を使う必要がある• ノイズが1年で半分になる等の仮定から将来予測をすると、RSA-2048は2050年ごろに解かれる
RSA-2048
RSA-1024？

RSA暗号の量子解読計算量[Gidney-Ekerå, 2019]

2050
2048

■量子誤り率が10-3～10-4程度まで下がると量子誤り訂正が効いてくるため、加速する可能性

Now※量子プロセッサのCNOTゲートエラーが1年ごとに半分になるトレンドが長期間続くと仮定したときの予測
NICT サイバーセキュリティシンポジウム

講演資料

p.31

ご清聴ありがとうございました

NICT サイバーセキュリティシンポジウム

講演資料

p.32

参考文献一覧■pp.4-5に関する資料• Shorによる素因数分解と離散対数問題の量子多項式時間アルゴリズム
Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
https://arxiv.org/abs/quant-ph/9508027• Groverによる量子探索アルゴリズム:
Lov K. Grover, A fast quantum mechanical algorithm for database searchhttps://arxiv.org/abs/quant-ph/9605043• 電子政府における調達のために参照すべき暗号のリスト（CRYPTREC暗号リスト、最終更新2022/04/30）
https://www.cryptrec.go.jp/list/cryptrec-ls-0001-2012r7.pdf■p.5の量子コンピュータの大型化による共通鍵暗号への影響に関する議論• ESTI, Limits to Quantum Computing applied to symmetric key sizes, ETSI GR QSC 006 V1.1.1 (2017-02)
https://www.etsi.org/deliver/etsi_gr/QSC/001_099/006/01.01.01_60/gr_qsc006v010101p.pdf• CRYPTREC技術報告書「量子コンピュータが共通鍵暗号の安全性に及ぼす影響の調査及び評価」 (2019)https://www.cryptrec.go.jp/exreport/cryptrec-ex-2901-2019.pdf■p.6のShor,Grover以外の量子アルゴリズムが暗号に与える影響に関する文献• Y. Aono et al. Quantum Lattice Enumeration and Tweaking Discrete Pruning, https://eprint.iacr.org/2018/546• Andrew M. Childs, David Jao, Vladimir Soukharev, Constructing elliptic curve isogenies in quantum subexponential time,https://arxiv.org/pdf/1012.4019.pdf

参考文献一覧■p.6の耐量子計算機暗号の公募に関する資料• NIST Post-Quantum Cryptography PQC, https://csrc.nist.gov/Projects/post-quantum-cryptography• CACR 全国密码算法设计竞赛通知, https://sfjs.cacrnet.org.cn/site/content/309.html• KpqC Competition, https://kpqc.or.kr/■p.6の耐量子計算機暗号の標準化に関する資料• NIST Post-Quantum Cryptography PQC, https://csrc.nist.gov/Projects/post-quantum-cryptography• ETSI Quantum-Safe Cryptography (QSC), https://www.etsi.org/technologies/quantum-safe-cryptography• IETF https://trac.ietf.org/trac/sec/wiki/PQCAgility■p.6の耐量子計算機暗号への移行に関する資料• ETSI releases migration strategies and recommendations for Quantum-Safe schemes,
https://www.etsi.org/newsroom/press-releases/1805-2020-08-etsi-releases-migration-strategies-and-recommendations-forquantum-safe-schemes• NIST Migration to Post-Quantum Cryptography, https://csrc.nist.gov/publications/detail/white-paper/2021/08/04/migration-topost-quantum-cryptography/final参考文献一覧■p.6の耐量子計算機暗号に関するガイドラインに関する資料• CRYPTREC,耐量子計算機暗号の研究動向調査報告書, https://www.cryptrec.go.jp/report/cryptrec-tr-2001-2018.pdf• NSA, Announcing the Commercial National Security Algorithm Suite 2.0, https://media.defense.gov/2022/Sep/07/2003071834/1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF• BSI TR-02102-1: "Cryptographic Mechanisms: Recommendations and Key Lengths" Version: 2023-1,
https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-021021.pdf?__blob=publicationFile&v=6• ANSSI views on the Post-Quantum Cryptography transition, https://www.ssi.gouv.fr/en/publication/anssi-views-on-the-postquantum-cryptography-transition/■p.7のタイムラインに関する資料• Michele Mosca, Cybersecurity in a Quantum World: will we be ready?
https://csrc.nist.gov/csrc/media/events/workshop-on-cybersecurity-in-a-post-quantum-world/documents/presentations/session8mosca-michele.pdf, 2015
• Michele Mosca and Marco Piani, 2021 Quantum Threat Timeline Report: Global Risk Institute,
https://globalriskinstitute.org/publication/2021-quantum-threat-timeline-report-global-risk-institute-global-risk-institute/■p.8: Metaculus内の量子コンピュータがRSAを破る日付の予想• https://www.metaculus.com/questions/3684/when-will-a-quantum-computer-running-shors-algorithm-or-a-similar-one-beused-to-factor-one-of-the-rsa-numbers-for-the-first-time/参考文献一覧■p.9-11の専門家の予測に関する資料• Matteo Mariantoni, Building a Superconducting Quantum Computer, PQCrypto 2014 invited talk
• Michele Mosca, Cybersecurity in a Quantum World: will we be ready?
https://csrc.nist.gov/csrc/media/events/workshop-on-cybersecurity-in-a-post-quantum-world/documents/presentations/session8mosca-michele.pdf, 2015
• Michele Mosca and Marco Piani, 2021 Quantum Threat Timeline Report: Global Risk Institute,
https://globalriskinstitute.org/publication/2021-quantum-threat-timeline-report-global-risk-institute-global-risk-institute/• 科学技術・学術政策研究所科学技術予測センター, 第11回科学技術予測調査 デルファイ調査• Emily Grumbling and Mark Horowitz, 米国科学・工学・医学アカデミーによる量子コンピュータの進歩と展望 (西森 秀稔 翻訳)■p.12の過去の実績からの外挿に関する資料• Jaime Sevilla and C. Jess Riedel, Forecasting timelines of quantum computing, arXiv:2009.05045, https://arxiv.org/abs/2009.05045• Tilman Runge, Dismantling the Quantum Threat, Master Thesis, 2022
• Aono et al., The present and future of discrete logarithm problems on noisy quantum computers, IEEE TQE 2022-3■p.13のグラフ参照先• CRYPTREC Report 2021, https://www.cryptrec.go.jp/report/cryptrec-rp-2000-2021.pdf

参考文献一覧■p.14の単位に関する参考文献• 量子ビットのロードマップに関するまとめは例えばhttps://www.adlittle.com/de/node/24039• IBMによるCNOTゲートの実績 https://research.ibm.com/blog/heavy-hex-lattice• 量子体積の提案論文はAndrew W. Cross et al., Validating quantum computers using randomized model circuits, Phys. Rev. A 100-3,(2019). また、実績とロードマップに関しては https://research.ibm.com/blog/quantum-volume-256• Q-score: Simon Martiel, Thomas Ayral, Cyril Allouche, Benchmarking quantum co-processors in an application-centric, hardwareagnostic and scalable way, IEEE-TQE, 2 (2021)• Generalized logical circuit: Jaime Sevilla and C. Jess Riedel, Forecasting timelines of quantum computing, arXiv:2009.05045,
https://arxiv.org/abs/2009.05045• Yulong Dong, Lin Lin, Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark, PQA 103-6• Ang Li et al.,QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation, ACM Transactions on
Quantum Computing• Algorithmic Qubits: A Better Single-Number Metric, https://ionq.com/posts/february-23-2022-algorithmic-qubits• SupermarQ: https://www.super.tech/supermarq/■p.15の素因数分解，離散対数問題の必要量子ビットに関する参考文献
Yasuhiro Takahashi and Noboru Kunihiro, A quantum circuit for shor's factoring algorithm using 2n + 2 qubits, Quantum Information &Computation, 6, 2 (2006)
Häner et al., Factoring using 2n + 2 qubits with Toffoli based modular multiplication, Quantum Information & ComputationVolume 17, 78 (2017)

参考文献一覧■p.16の素因数分解履歴に関する参考文献• Shorのアルゴリズムのサーベイ: CRYPTREC 外部評価報告書『Shorのアルゴリズム実装動向調査』
https://www.cryptrec.go.jp/exreport/cryptrec-ex-3005-2020.pdf• アニーリングによる素因数分解記録は主に以下を参考とした:山口，伊豆，イジング計算を用いた暗号解析について，オペレーション
ズ・リサーチ，2022-06■p.17の具体的な回路に関しては個々の論文を参照した• Vandersypen et al.,Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance, Nature, 414,
6866 (2001)• Lucero et al., Computing prime factors with a Josephson phase qubit quantum processor, Nature Physics, 8, 10 (2012)• Amico et al., Experimental study of Shor’s factoring algorithm using the IBM Q Experience, PRA 100-1 (2019)• Skosana and Tame, Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors (2021)■p.19以降の内容は主に以下の論文による• Aono et al.,超電導量子回路を用いた離散対数問題の求解実験, QIT43(2020)• Aono et al., The present and future of discrete logarithm problems on noisy quantum computers, IEEE TQE 2022-3■p.22 量子コンピュータの写真は以下のサイトから取得した
https://www.flickr.com/photos/ibm_research_zurich/51331567650/in/album-72157703845574031/■p.24の成功条件を中間値とすることに関しては、以下の先行研究をフォローした• Andrew W. Cross et al., Validating quantum computers using randomized model circuits, Phys. Rev. A 100-3, (2019)• T. Satoh, Y. Ohkura, and R. Van Meter, Subdivided phase oracle for NISQ search algorithms, IEEE-TQE, 1 (2020)■p.27のCNOTゲートの実績はhttps://research.ibm.com/blog/heavy-hex-lattice