CRYPTRECシンポジウム2022

量⼦コンピュータと暗号
2022年7⽉5⽇

JST研究開発戦略センター(CRDS)
フェロー 嶋⽥ 義皓
© 2022 CRDS

国⽴研究開発法⼈科学技術振興機構 研究開発戦略センター
Center for Research and Development Strategy Japan Science and Technology Agency

量⼦⾰命
次なる“半導体”級イノベーションへの期待
量⼦センサー

量⼦ICT社会

量⼦暗号・量⼦通信
量⼦コンピューター

相補性

量⼦技術2.0

猫状態

量⼦情報＆量⼦物性

量⼦テレポーテーション

量⼦シミュレーション

ホログラフィー原理
複製不可能定理
量⼦もつれ

量⼦マテリアル

ベル不等式

EPR相関

マクロ量⼦現象

量⼦相制御

量⼦⼲渉

量⼦1.0
不確定性原理© 2022 CRDS

2

トンネル効果エネルギー準位
バンド構造

半導体技術
光通信

ICT

トポロジカル物質

Google検索 “Quantum Computer will…”
2019/6/20

2021/6/24

2022/6/29

QC will never work

Will QC destroy bitcoin

QC will be

QC will kill bitcoin

Will QC break bitcoin

QC will destroy bitcoin

QC will destroy bitcoin

Will QC be built

QC will never work

QC will failWill QC replacesupercomputer

QC will break encryption

QC will be

QC will never work

QC will change the world

QC will not work

QC will be

QC will change everything

How QC will change theworld

Why QC will fail

QC will not work

What will a QC do

When will QC be available

QC will never work reddit© 2022 CRDS3

量⼦未来社会ビジョン© 2022 CRDS4

内閣府「量⼦未来社会ビジョン」（2022/4/22)
https://www8.cao.go.jp/cstp/ryoshigijutsu/ryoshi_gaiyo_print.pdf

1.

© 2022 CRDS

5量⼦コンピュータの基礎ビットと量⼦ビット
コンピュータ量⼦コンピュータ
量⼦ビットビットビット
𝑥 ∈ {0,1}
論理ゲート

𝜓⟩ = 𝑎 0⟩ + 𝑏 1
量⼦論理ゲートゲート• 0 または 1• コピーが可能© 2022 CRDS

6

• 0 と 1の重ね合わせ状態• コピーは不可能• 量⼦もつれ利⽤可能
A. Trabesinger, Nature 543, S2–S3 (2017)

量⼦コンピュータの計算原理
０．初期化

指数的規模の組み合わせの超並列処理

１．超並列処理

重ね合わせ状態に対する量⼦ゲート操作

2N通りの状態の重ね合わせ

１つ１つの確率は指数的に⼩さい２．確率の波の⼲渉

正答確率の増幅（それ以外の答えの削減）

３．測定

量⼦ビットの状態を測定し、結果を取り出す© 2022 CRDS

7

http://seedmagazine.com/content/article/cribsheet_15_quantum_computing様々な量⼦アルゴリズム*Noisy IntermediateScale Quantum

多数の量⼦アルゴリズムが知られているが、NISQ＊では⼗分な性能が出ない
アルゴリズムサブルーチン

量⼦加速

データ

PEA

指数

古典

量⼦化学計算（Full-CI）[Lanyon+, 2009]

PEA

指数

古典

グローバー検索 [Grover, 1996]

AA

⼆次量⼦

線形連⽴⽅程式 [Harrow+, 2009]

PEA

指数

量⼦

K-medians [Aimeur+, 2013]

AA

⼆次

古典

階層的クラスタリング [Aimeur+, 2013]

AA

⼆次

古典

K-means [Lloyd+, 2013]

(AA)

指数

量⼦

主成分分析 [Lloyd+, 2013]

HHL

指数

量⼦

主成分分析 [Kerenidis+, 2016]

HHL+QW指数

量⼦NN [Narayanan+, 2000]

AA

SVM [Anguita+, 2003]

AA

⼆次

古典

SVM [Rebentrost+, 2013]

HHL

指数

量⼦近傍法 [Wiebe, 2014]

AA

⼆次

古典

回帰 [Bisio+, 2010]-

基本アルゴリズム ショアの素因数分解 [Shor, 1994]

教師なし
機械学習

教師あり
機械学習

© 2022 CRDS

8

古典

量⼦

PEA: 位相推定
AA: 振幅増幅
QW: 量⼦ウォーク
HHL: HarrowHassidim-Lloyd量⼦プログラムは量⼦回路で書かれる
量⼦アルゴリズムで利⽤される頻出サブルーチン
位相推定(PEA)

グローバー検索

HHL*

ユニタリー⾏列の固有値を求め補助量⼦ビットに⼆進⼩数で書き込む（固有値の⼆進⼩数表⽰n桁がn個の補助量⼦ビットに書き込まれる）N要素の未整序データベースの中から探索を⾏う（欲しい答えの固有状態をマーキングし、振幅増幅反転の繰り返しによって正答率を上げる）

逆⾏列や⾏列積の演算を⾼速に⾏う（⾏列の固有値を位相推定で並列的に求め、それぞれの固有ベクトルを固有値で割る。⾏列積も同様）

素因数分解
量⼦化学計算検索組み合わせ最適化
クラスタリング

連⽴⽅程式・線形回帰
主成分分析
サポートベクタマシン© 2022 CRDS

9*Harrow-Hassidim-Lloyd量⼦回路＝量⼦ゲート列＝２N次元の⾏列
量⼦回路

ベクトル操作

３量⼦ビット ＝ 23 次元ベクトル→ 量⼦回路= 2n x 2n のユニタリ⾏列© 2022 CRDS

10量⼦ビット実現⽅法
制御技術として⼀歩進んでいるのは主に２⽅式

ほかにも、NMR、Si量⼦ドット、光、冷却原⼦などの物理系も着実な研究が進められている

超伝導回路⽅式|0⟩|1⟩+q-q-q+q

イオントラップ⽅式|0⟩|1⟩(Courtesy: Christopher Monroe)© 2022 CRDS

11量⼦ゲートはソフトウェア
量⼦回路はソフトウェアであり、量⼦ゲートに物理的実体はない
超伝導の場合、量⼦ゲート操作＝⾼周波パルス（マイクロ波）

実際のパルスゲート操作© 2022 CRDS

12P. J. J. OʼMalley et al., Phys. Rev. X 6, 031007 (2016).

量⼦版ムーアの法則
集積度は上がってきている。NISQを如何に使いこなすかが鍵
1000000

1.5年で２倍量⼦ビット数

100000

誤り耐性
量⼦コンピュータ

10000

３年で２倍
1000

NISQ
時代

100

イオントラップ⽅式

10超伝導回路⽅式

11990
19 900.1© 2022 CRDS

13

６年で２倍

2000
20 00

2010
20 10

2020
20 20

2030
20 30

2040
20 40

2050
20 50

ニ ス クNISQ時代の量⼦コンピュータ
フルの量⼦コンピュータ（誤り耐性QC）はまだ⼿に⼊らないが…
Noisy

ノイズあり

Intermediate-Scale

中規模スケールのQuantum device

量⼦デバイス

量⼦誤り訂正が不⼗分で、エラー率は⾼い。

50〜100量⼦ビット程度

量⼦効果を使うデバイス

何かには使えそう。

John Preskill(CalTech)

限られたハードウェア資源を活かす知恵とソフトウェアが重要© 2022 CRDS

14

John Preskill, “Quantum Computing in the NISQ era and beyond”, Quantum 2, 79 (2018).

キラーアプリケーション（の候補）
量⼦化学・量⼦多体系

機械学習・最適化（例）• ⾼精度の物性予測、分⼦・材料設計• 反応・ダイナミクスのシミュレーション（例）• 巨⼤な⾏列の固有値・特異値• サンプリング• 主成分分析、クラスタリング、分類、SVM etc…

問題設定がそもそも量⼦⼒学で定式化されているので、量⼦計算のほうが効率的なはず。

© 2022 CRDS

15

問題設定は量⼦と無関係だが、線形代数の構造や⾼次元の表現能⼒を上⼿に利⽤できそう。

2.

© 2022 CRDS

16

量⼦コンピュータと暗号

Shorのアルゴリズム
量⼦位相推定アルゴリズムで周期発⾒を指数加速

ユニタリ⾏列Uの固有値から位数を求められる固有値位相推定アルゴリズム

位数発⾒アルゴリズム© 2022 CRDS

17

量⼦コンピュータと暗号
耐量⼦コンピュータ暗号

Post-quantum cryptography（PQC）。quantum-resistant / quantum-proof とも。

代表例© 2022 CRDS

共通鍵暗号

AES

公開鍵暗号

RSA暗号
楕円曲線暗号18

量⼦アルゴリズム
グローバー検索（共通鍵を総当たりで探索）

ショアのアルゴリズム（素因数分解・離散対数問題が多項式時間で解ける）

対策

鍵⻑を２〜３倍に延伸

耐量⼦コンピュータ
暗号への移⾏

（補⾜）QKDとPQC
量⼦暗号鍵配送（QKD）とPQCは似て⾮なるもの
共通鍵暗号
平⽂

平⽂同じ鍵（共通鍵）© 2022 CRDS

19

公開鍵暗号
平⽂

公開鍵

平⽂

鍵ペア

秘密鍵

同じ鍵で暗号化・復号

公開鍵で暗号化、秘密鍵で復号

暗号鍵の安全な共有が困難（鍵配送問題）

鍵の事前共有は不要だが耐量⼦性に課題（RSA、楕円曲線）

量⼦暗号鍵配送（QKD）

耐量⼦計算機暗号（PQC）

2048ビット整数の素因数分解にかかる時間
誤り耐性量⼦コンピュータのアーキテクチャに依存

数千万量⼦ビット、クロック10kHz程度で１年間連続動作が必要。アーキテクチャ最適化で計算時間は減少可能

2048ビット整数を１年で素因数分解
クロック© 2022 CRDS

20

アルゴリズムアーキテクチャ■ 1 Hz

BCDP考慮なし■ 1 MHz

BCDP考慮なし■ 1 MHzF

NTC（近接のみゲート操作可能）■ 1 MHzD

AC（遠距離もゲート操作可能）

R. Van Meter, C. Horsman, “A blueprint for building a quantum computer”, Comm. of the ACM 56, 84 (2013).

量⼦誤り訂正符合によるオーバーヘッド
2048bitの数の素因数分解 → 60億量⼦ビット必要と⾒積もられる
12000

論理量⼦ビット

x10000

誤り訂正（表⾯符号、d＝56）
量⼦ビットのエラー率0.2%x821

魔法状態蒸留（⾮クリフォード群ゲート利⽤のため）

x1.25

量⼦ビットの配線

x5

デバイスの歩留まり

6,000,000,000© 2022 CRDS

実⾏効率を鑑みてやや余裕をもっている値

物理量⼦ビット

現在の技術⽔準からみてかなり⾮現実的な値…

2000万量⼦ビットで８時間という結果も（エラー率10-3, 表⾯符合
サイクル1μs）
C. Gidney, M. Ekerå, “How to factor
2048 bit RSA integers in 8 hours
using 20 million noisy qubits”,
Quantum 5, 433 (2021).

R. Van Meter, C. Horsman, “A blueprint for building a quantum computer”, Comm. of the ACM 56, 84 (2013).

3.

© 2022 CRDS

22

今後の展望クラウド提供が進むNISQ量⼦コンピュータ
Qiskit (by IBM)
開発フレームワーク
（SDK）

GCP

●

●88881●25220

Cirq+TFQ (by Google)
Braket (by Amazon)

236279Pennylane (by Xanadu)●5372

Tket (by CQC)

●

4306

IBM

© 2022 CRDSAWS●

Q# (by Microsoft)

ハードウェア
（QPU）

Azure

⽉間DL数IBM

超伝導●●

GooglePypistat.org(2021.5.18〜6.18)●

Rigetti●

qciイオントラップ

IonQ

QAマシン

D-waveHoneywell-●
●

●

●

●

●
●

NISQのスケーラビリティ

幅

1Qゲートの忠実度 99%

10（エラー率1%）

量⼦ゲート

結果の忠実度(0.99)100= 36.6%
単純計算で…
20Qなら深さ５50Qなら深さ２の計算までしか有効でない

量⼦ビット© 2022 CRDS24

深さ 10NISQ量⼦コンピュータのベンチマーキング
IonQ（Latest, イオントラップ）© 2022 CRDS

25

IBM（Guadalupe, 超伝導量⼦ビット）

T. Lubinski, et al., "Application-Oriented Performance Benchmarks for Quantum Computing", arXiv:2110.03137 (2021).

量⼦誤り訂正
量⼦ビットに冗⻑性をもたせ、エラーを検出・訂正する
古典コンピュータのハミング符合と同じ考え⽅

ただし「量⼦コンピュータ特有の事情」の考慮が必要• ビット反転エラーに加えて位相反転エラーが存在• 任意の量⼦状態のコピぺは不可（No-Cloning定理）• 計算実⾏中のレジスタを護る必要がある（符号化されたまま演算）→ 万能論理量⼦ゲート• エラー検出・訂正に必要なゲート操作も⾼い確率で誤る → しきい値定理○ X ● X ○ZXZ
● Z ○ Z ●ZXZ
○ X ● X ○○ X ● X ○ X ● X ○ X ● X ○ZX
ZXZXZ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZX
ZX
ZXZ○ X ● X ○ X ● X ○ X ● X ○ZXZXZXZ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZXZXZXZ○ X ● X ○ X ● X ○ X ● X ○ZXZXZXZ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZX
ZXZXZ○ X ● X ○ X ● X ○ X ● X ○○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ZX
ZX
ZX
ZX
ZX
ZX
Z● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZXZXZXZXZXZXZ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ZXZXZXZXZXZXZ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZX
ZX
ZX
ZX
ZX
ZX
Z○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○
ZX
ZX
ZX
ZX
ZX
ZX
Z● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZXZXZXZXZXZXZ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○
ZX
ZX
ZX
ZX
ZX
ZX
Z● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZX
ZX
ZX
ZX
ZX
ZX
Z○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○
ZX
ZX
ZX
ZX
ZX
ZX
Z● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZX
ZX
ZX
ZX
ZX
ZX
Z○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ZXZXZXZXZXZXZ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ● Z ○ Z ●ZX
ZXZX
ZXZX
ZX
Z○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○ X ● X ○[[5,1,2]][[25,1,4]][[85,1,7]]量⼦の誤りを量⼦で訂正「量⼦誤り訂正符号」（例）２D表⾯符号 [[25,1,4]]25物理量⼦ビット = １論理量⼦ビット（符号距離d=4）© 2022 CRDS26

量⼦超越と計算複雑性
量⼦計算は古典計算より早いのか︖

BQP

量⼦コンピュータで効率よく解ける問
題のクラスP ⊆ BPP ⊆ BQP ⊆ PSPACE
量⼦が古典より早いは「BPP ≠ BQP」を信じることになるが、⽰すのは困難「“弱い”量⼦コンピュータを古典計算で効率的にシミュレート可能 → 多項式階層が崩壊」を使って⽰す
弱い量⼦コンピュータの例
IQP、ボソンサンプリング、oneclean-qubitモデル、ランダム量⼦回路© 2022 CRDS

27

https://www.simonsfoundation.org/report2017/stories/scott-aaronson-quantum-and-classical-uncertainty/

量⼦技術の具体的な研究開発課題
量⼦コンピューティング
量⼦シミュレーション

量⼦計測
センシング

量⼦暗号・通信NISQマシンのキラーアプリ探索

ダイヤモンドNV中⼼作製技術

・量⼦化学計算/機械学習
・量⼦超越性・古典-量⼦ハイブリッドアルゴリズム

・⼤型・⾼品質化（T2向上）
・新材料探索ゲート型量⼦コンピュータ実機の試作
・超伝導量⼦ビット系

エラー耐性量⼦コンピューター基盤技術
・量⼦ソフトウェア
・量⼦誤り訂正⽅式
・様々な量⼦ビット系

複雑系の計算が可能な量⼦シミュレータ開発共通量⼦技術基盤

原⼦・分⼦・光科学
量⼦光学
量⼦エレクトロニクス© 2022 CRDS

28

QKDの社会実装と⼀般普及の促進
・BB84運⽤・品質保証
・市場投⼊・キラーアプリ探索
・低価格化

ダイヤモンドNV中⼼と量⼦もつれ光センサの医療・診断応⽤
・プロトタイプ製作
・脳磁計・⼼磁計
・イメージング技術

原⼦⼲渉計・光格⼦時計の実⽤性探索・⼩型化・可搬化
・⾼精度化
・「秒」の再定義・標準化

標準化活動への積極的寄与
・ETSI & ITU-T・耐量⼦-公開鍵暗号

⾼速化・⻑距離化に向けた量⼦中継技術、ネットワーク技術
・量⼦メモリー・全光量⼦
・量⼦望遠鏡・量⼦インターネット

単⼀光⼦制御技術

量⼦ビット基盤技術

異種の量⼦ビット間結合（ハイブリッド量⼦科学）

材料設計・製造、計測技術

・効率化・室温動作・光⼦検出器
・量⼦もつれ光⼦、多体量⼦もつれ制御
・固体量⼦ビット & 光 など

量⼦マテリアルトポロジカル量⼦物質
・トポロジカル量⼦コンピュータ
・トポロジカル絶縁体・ワイル磁性体

スピントロニクス材料

・半導体スピントロニクス
・スピンMOSFETデバイス

エネルギー変換材料

・スピン-ゼーベック効果
・スピン流

フォトニクス材料

・メタマテリアル・シリコン／ナノフォトニクス

・様々な量⼦ビット系

JST-CRDS 戦略プロポーザル「量⼦2.0 〜量⼦科学技術が切り拓く新たな地平〜」

CRDS 量⼦技術関連のプロポーザル・報告書
CRDSのwebサイトから無料でダウンロード可能です
量⼦技術全般については…

量⼦コンピュータについては…

量⼦マテリアルについては…

量⼦2.0 〜量⼦科学技術が切り拓
く新たな地平〜

みんなの量⼦コンピューター 〜
情報・数理・電⼦⼯学と拓く新しい量⼦アプリ〜

トポロジカル量⼦戦略〜量⼦⼒学の新展開がもたらすデバイスイノ
ベーション〜https://www.jst.go.jp/crds/report/CRDS-FY2019SP-03.html© 2022 CRDS

29

https://www.jst.go.jp/crds/report/CRDS-FY2018SP-04.html

https://www.jst.go.jp/crds/report/CRDS-FY2016SP-02.html