量子コンピュータでRSA暗号を解くのに必要な物は？

# はじめに
量子コンピュータで、Shorのアルゴリズムを用いると、RSAの離散対数問題を位数推定という方法で求解できるのでは？というテーマはこちらで扱いました。

https://qiita.com/tarutaru000/items/bc299d14609d4470b04e

一方で、Shorのアルゴリズムは、
「理想的な量子コンピュータなら～～」のLong-termと呼ばれる部類のアルゴリズムですので、、
**量子コンピュータでRSAを解くというのは、まだ人類未踏の領域**でございます。

で、難しい。以上！と言ってもいいのですが、、
人類が何を手に入れたら量子コンピュータでRSAを解くことができるのか、
をまとめてみようというのが本稿のモチベーションです。

本稿は、下記の1.1 Our contributions and a summary of our resultsを参考に議論を進めます。

https://arxiv.org/abs/1905.09749

:::note warn
著者は産業界の１エンジニアであり、研究者でも専門家でも無いので、
間違っていたらごめんなさい。。ぜひ、コメントいただければと。。
:::

また、他の量子コンピュータ関係の他の記事は、下記で紹介しています。

https://qiita.com/shnchr/items/41fa7fd1284d74007a7c

# 大切にしたいこと
本論文[^1]著者のCraig Gidney氏は、下記にて**Actual Goal**を次のように語っています。

> **NOT** the goal: Reduce the time until RSA is broken

「量子コンピュータで早くRSAを破りたい！」とか「それを煽る！」とか**ではなく。**

> **Actual goal**: Understand how long until RSA is broken
> Replacing internet cryptosystems is a lot of work!
> How quickly dose that work need to get done?
> If the estimate is going to change, we want to know that while we can react.

**現実問題として、インターネット上の暗号システムの置き換えには10年単位の時間を要する。**
RSAが破られるまでの見積もりも日々変化するし、だから、人類は**それを正しく理解したい。**

::: note info
目的は「壊す・煽る」ではなく、「正しく理解」することである。
論文著者のこの精神に強く共感し、本稿でもこの精神を大切にしたいと思います。
:::

https://youtu.be/upTipX9yXNg?t=97

# RSA 2048bitを解くのに必要なモノ
引用論文[^1]のタイトル通り、**20 million noisy qubits** ですね。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/3fa96bb1-a2ba-0071-01c2-390d1739aa3a.png)

で、結論を先に示すと、

* **エラーレートが、$\color{red}{0.1％}$の量子系で、$\color{red}{23 \times 10^{6}}$(23M量子ビット）が必要です。**

これがどれだけの規模かというと、

* Google[^google]やIBM[^IBM]が約10年後の2030年までに目指す量子ビットが、**1M量子ビット**です。

[^google]: https://ia.acs.org.au/article/2021/google-is-building-a-1-million-qubit-quantum-computer.html

[^IBM]: https://fortune.com/2020/09/15/ibm-quantum-computer-1-million-qubits-by-2030/


よって、

* RSA2048を解くには、その**2030年目標の23倍**の物理量子ビットが必要です。加えて、、
* 現時点での一般的なエラーレートは**約1%**[^qchard]ですが、10倍の精度の**約0.1%** が必要です。

[^qchard]: [A. Rossi, P.G. Baity, V.M. Schäfer, M. Weides. <br/>Quantum computing hardware in the cloud: Should a computational chemist care?, 2021](https://arxiv.org/abs/2102.03248)を参考にさせていただいています。超伝導でも規模が小さいものやイオントラップ型は、量子ビットサイズに対して、Quantum Volumeも大きくシングルビッドのフィディリティも0.1%程度のものも存在しますが、規模を大きくしようとすると、現状のシングルビットフィディリティはやはり、今もまだ、1%程度ではないか。と考えています。

つまり、

:::note info
現状の<b>10倍の精度</b>（エラーレート）の量子系にて、GoogleやIBMの<b>2030年目標の23倍</b>の量子ビットが用意できれば、RSA2048を解くことができる「かもしれない」というお話でした。
:::
 
正直、現状では、「無理では…」というのが私の感想で、

* 量子コンピュータが出てきたから、すぐに、HTTPSが危険になるかも。　とか
* 暗号資産の安全性が脅かされるから、すぐに、現金化せねば～

的なことは無く、離散対数問題を安全性の根拠するRSAもしばらく安全では？といった感覚です。
一方で、

* なぜそんなに、膨大な数の物理量子ビットが必要になるのか？

そのロジックを理解しておくことは重要な気がします。
**そのロジックが崩れるような技術革新が起きれば**、「しばらくは安全」が崩れてしまうので、

ということで、なぜそんな膨大な物理量子ビットが必要になるのか？の議論を進めていきましょう。

# 「膨大な」を正しく理解する

「膨大な」がどの様に膨大なのかを議論していきましょう。
その為に、本論文[^1]のTable.1のここらへんから数字を拾わせて頂き、議論を進めましょう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/9f633c9d-b170-7592-1c69-f29054c13ee5.png)

で、少し整理するとこんな感じです。

||(ours)2019に記載の計算式|RSA 1024|RSA 2048|RSA 3072|
|---:|:---:|---:|---:|---:|
|Abstract Qubits[^abst]|$3n+0.002nlog(n)$|3,092|6,189|9,287|
|Measurement Depth[^depth]|$500n^2+n^2log(n)$|534,773,760|2,143,289,344|4,827,921,423|

[^abst]: 論文[^1]では、The number of logical qubits used in the abstract circuit model. Ignores qubits used for distillation and routing.と記載があり、論理量子ビット数を解釈しました。

[^depth]: 論文[^1]では、The length of the longest chain of dependent measurements, which determines the reaction limited runtime of an algorithm. These numbers are not adjusted to account for the chance of retrying.と記載があり、測定深度（ゲートの深さ）と解釈しました。誤解があればコメントいただけるとたすかります。

<!--
|Toffoli+T/2 Count|$0.3n^3+0.0005n^3log(n)$|327,491,256|2,624,225,018|8,865,238,768|
-->

数字を拾ってみると、

* RSA2048を解くのに必要な論理量子ビット数は、意外に少なく、$6K$論理量子ビット
* 一方で、量子回路の深さが果てしなく深く[^21b]、、、$2.1 \times 10^{10}$

[^21b]: 必要な量子ビット数23Mに対して、測定深度が21Bと量子ビット数を上回っていたので、違和感を感じたのですが、論文[^1]では、Uncomputation等のテクニックにより量子ビットの再利用が行われている記述があり、23Mの量子ビットを再利用しながら、計算を都度進めていくと最終的な測定深度は、その量子ビットサイズを遥かに上回る深さとなる。と理解していますが、誤解もありそうなのでコメント頂けますと幸いです。

つまり、**「膨大」** の正体は、**論理量子ビット数**ではなく、**量子回路の深さ**と理解することができます。

<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/306458e0-a34f-b824-1447-fd3628eb7d3c.png width="700px">


# 量子回路が深いとどうなるか？
単一のゲートのエラー発生率が低くても、それを繰り返すと系としてのエラー発生率は徐々に増大します。
イメージ的には、信頼性0.9の処理があり、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/d37e269a-0815-27c6-fd74-111b083530e8.png)


* ゲート1つを通過しただけでは、$90％$は正常に処理ができますが
* ゲート4つを通過後は、$0.9^4 = 66％$となります。そして、
* ゲート8つを通過すると、$0.9^8 = 43％$となり、半分以上間違える。

という様に、深い回路を作りたい場合には、単一のゲートのエラーレートを大きく下げる必要があります。
一方で、本論文[^1]の議論では、前提とする、**単一物理ゲートのエラーレートは、0.1％** を想定しています。

どうやって、エラーレート$0.1％$の物理系で、$2.1 \times 10^{10}$段のゲート測定を行うのでしょうか？

# ノイジーな量子ビットから、きれいな１ビットをつくる
## 誤り訂正符号上でのTゲート適用を考える
エラーレート$0.1％$は高精度に見えますが、$2.1 \times 10^{10}$段の測定深度を要する処理の前においては、ノイズが大きく、このままでは回路を構成することが出来ません。
そこで、この$0.1％$の物理量子ビットを束ねて、きれいな（高精度な）１ビットを作ります。

どうやって作るか？ですが、

https://qiita.com/shnchr/items/ec30fb2533d3cf6eec57

といった様に、物理量子ビットを複数用いて、誤りに強い量子ビットを作ります。
量子ビットに対する演算は、下記でも見たように、$H,T,CNOT$により完全系をなすので、論理量子ビット上でも、$H,T,CNOT$を使いたいのですが、実を言うと、論理量子ビット上では論理$T$ゲートを使うことが出来ません。

https://qiita.com/shnchr/items/ac8b6a0e2ee49ef6b383

理由としては、論理$T$ゲートがクリフォード演算子では無いから。なのですが、今はアウトラインだけを追いかけたいので詳細は省略します。
で、どうするかというと、誤り訂正符号によりエラーから保護された論理状態に対して、ゲートテレポーテーションを用いることで、間接的に$T$ゲートを作用させ$T$操作を実現します。

https://qiita.com/shnchr/items/70ec42cb369a9830e8c7

## 純度の高いTをどう準備するか？

ゲートテレポーテーションでは、$T$ゲートを準備する代わりに、$T$が作用した状態を準備します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/09f9be63-fa44-0109-831d-50f95578d315.png)

```math
\newcommand{\ket}[1]{\left| #1 \right\rangle}
```

* $\ket{\psi}$(上段)は誤り訂正符号にてエラー保護済みですが、$T\ket{+}$(下段)は、物理状態として準備します
* この$T\ket{+}$は、こういった簡単な回路で準備も可能ですが、この$T$にノイズがあったらどうでしょうか？
* せっかく、誤り訂正符号で守り抜いたきれいな状態も、汚い$T$によってノイズが混じってしまいます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/8b533913-a745-ade1-796d-205293240d36.png)

## 蒸留により高純度なTをつくる（魔法状態蒸留）
誤り訂正符号で守り抜いてきた論理状態に対して、適用しても害がないレベルに磨き上げられた$T$状態がほしいのですが、それを手に入れる手法が、**魔法状態蒸留**です。詳細は割愛しますが、ゲート適用と間接測定を繰り返し、高純度な$T$を作り上げることができるのですが、回路としてはこんなになります。。

* [Magic State Distillation](https://algassert.com/quirk#circuit={%22cols%22:[[%22H%22,%22H%22,%22H%22,%22H%22,%22H%22],[1,%22Z%22,%22Z%22,%22Z%22,1,%22%E2%8A%96%22],[1,%22Z%22,%22Z%22,1,%22Z%22,1,%22%E2%8A%96%22],[1,%22Z%22,1,%22Z%22,%22Z%22,1,1,%22%E2%8A%96%22],[1,1,%22Z%22,%22Z%22,%22Z%22,1,1,1,%22%E2%8A%96%22],[%22Z%22,%22Z%22,%22Z%22,%22Z%22,%22Z%22,1,1,1,1,%22%E2%8A%96%22],[%22Z%22,1,1,%22Z%22,%22Z%22,1,1,1,1,1,%22%E2%8A%96%22],[%22Z%22,1,%22Z%22,1,%22Z%22,1,1,1,1,1,1,%22%E2%8A%96%22],[%22Z%22,%22Z%22,1,1,%22Z%22,1,1,1,1,1,1,1,%22%E2%8A%96%22],[%22Z%22,1,%22Z%22,%22Z%22,1,1,1,1,1,1,1,1,1,%22%E2%8A%96%22],[%22Z%22,%22Z%22,1,%22Z%22,1,1,1,1,1,1,1,1,1,1,%22%E2%8A%96%22],[%22Z%22,%22Z%22,%22Z%22,1,1,1,1,1,1,1,1,1,1,1,1,%22%E2%8A%96%22],[1,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22,%22Z^%C2%BC%22],[1,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22,%22H%22],[1,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22,%22Measure%22],[1,%22X%22,%22X%22,%22X%22,1,%22%E2%80%A2%22],[1,%22X%22,%22X%22,1,%22X%22,1,%22%E2%80%A2%22],[1,%22X%22,1,%22X%22,%22X%22,1,1,%22%E2%80%A2%22],[1,1,%22X%22,%22X%22,%22X%22,1,1,1,%22%E2%80%A2%22],[%22Z%22,%22X%22,%22X%22,%22X%22,%22X%22,1,1,1,1,%22%E2%80%A2%22],[%22Z%22,1,1,%22X%22,%22X%22,1,1,1,1,1,%22%E2%80%A2%22],[%22Z%22,1,%22X%22,1,%22X%22,1,1,1,1,1,1,%22%E2%80%A2%22],[%22Z%22,%22X%22,1,1,%22X%22,1,1,1,1,1,1,1,%22%E2%80%A2%22],[%22Z%22,1,%22X%22,%22X%22,1,1,1,1,1,1,1,1,1,%22%E2%80%A2%22],[%22Z%22,%22X%22,1,%22X%22,1,1,1,1,1,1,1,1,1,1,%22%E2%80%A2%22],[%22Z%22,%22X%22,%22X%22,1,1,1,1,1,1,1,1,1,1,1,1,%22%E2%80%A2%22],[%22X%22,%22Chance4%22],[%22Amps1%22,%22|0%E2%9F%A9%E2%9F%A80|%22,%22|0%E2%9F%A9%E2%9F%A80|%22,%22|0%E2%9F%A9%E2%9F%A80|%22,%22|0%E2%9F%A9%E2%9F%A80|%22]]})

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/fe51128d-1856-ab6b-7113-3538c8370644.png" width=1200px>

## きれいなビットで計算する方法をまとめると
演算は誤り訂正符号のエラー保護下で進めるのだが、クリフォード演算でない$T$が論理状態には適用できないので、事前にこの高純度の$T$状態を大量に準備しておいて、$T$ゲートを掛けたいタイミングでは、ゲートテレポーテーションを使って$T$の効果を量子状態に反映する。手間がかかります。。
実際に、本論文[^1]においても、

>When factoring an n = 2048 bit RSA integer we are using a board of 226 · 63 logical qubits.
Approximately 25% of these qubits are being used for distillation, which we already accounted
for, and so we do not count them in this calculation.

といった記述があり、全量子ビットの約25%が、この魔法状態の蒸留の為に利用されているようです。
（詳細は著者も理解が追いつかないのですが、雰囲気として、すごいオーバヘッドを感じました。。）

# 量子誤り訂正の厳しさ
冒頭に見たようにRSA2048を解くためには、$2.1 \times 10^{10}$の測定深度が必要ですが、先程の信頼性・故障率の議論と同様に、これを実現するには、１論理量子ビットのエラーレートを、$10^{-14}$程度まで抑え込む必要があるようです。
では、物理何ビットを用いれば、この$10^{-14}$の１論理量子ビットを得ることができるのでしょうか？
表面符号[^surface]における物理誤り率を論理誤り率に換算する式については下記[^low]、

https://arxiv.org/abs/1808.06709

[^low]: [Austin G. Fowler, Craig Gidney. <br/> Low overhead quantum computation using lattice surgery, 2018](https://arxiv.org/abs/1808.06709)

にて、近似値が示されており、

```math
P_{Logical} = 0.1(100 \times P_{physical})^{(d+1)/2}
```

となるようです。
この数式は何を言っているか？というと、

* 所望の論理誤り率は、 $P_{Logical} =10^{-14}$
* 利用する物理系の誤り率は、$P_{physical} = 0.1％ = 10^{-4}$

ですので、下記となり

```math
10^{-14} \gt 0.1(100 \times 10^{-4})^{(d+1)/2}
```

これを満たすようにdを奇数で決めると、$d=27$となり、この$d$は何を表すかというと、下記の様に表面符号[^surface]上の符号距離を意味しており、dに対して、この表面符号[^surface]を構成する物理ビットは、

```math
2(d+1)^2 
```

で計算できます。つまり、$d=27$のときに必要な物理ビット数は、$2(27+1)^2=1568$となります。
**つまり、1568物理量子ビットを用いて、１論理量子ビットを構成する必要があるのです。**
（以下は、$d=5$のときの図で、白・黒の◯が量子ビットを表しています）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/dadc01e4-1ab7-e3dd-abcb-fcbabbf6c59c.png)

## エラーレート=1%で考える
今までの議論では、単一物理量子ビットのエラーレートを0.1%で考えてきましたが、現有する物理系の一般的なエラーレート1%でこの式を考えてみると、悲しき事実がわかります。

```math
P_{Logical} = 0.1(100 \times P_{physical})^{(d+1)/2}
```

$P_{physical}=1％=10^{-2}$を代入すると、


```math
P_{Logical} = 0.1(100 \times 0.01)^{(d+1)/2} = 0.1(1)^{(d+1)/2}
```

$1^{(d+1)/2}$は何を意味しているでしょうか？そうです、**1は何回掛けても1ですので、エラーレート1%時は、dの符号距離をいくら大きくし、物理量子ビットを増やしても、論理誤り率は改善しない**のです。

つまり、RSAを解くには、Long-termアルゴリズムを使うには、

人類は、膨大な量子ビットを、物理エラーレートを1%未満で実現する量子系を手に入れるしかないのです。Long-term厳しいです。。

# 今までの議論をまとめる
* RSAを量子コンピュータで解くためには、深い回路が必要
* 深さを得ようとすると、単一エラーレートを低く抑え込む必要があり
* 表面符号等を用いた上で、演算Tは魔法状態蒸留した論理Tをゲートテレポーテーションする

この背景で、膨大な物理量子ビットが必要になる。
「膨大」の意味を細かめに見ていきましたが、やはり、RSAが量子コンピュータで解かれる日はまだ来そうにありません。

# 安心していいのか？（ここからは思考実験）

:::note warn
以下の議論は、一個人の思考実験ですので、正確性を大きく欠くと思います。
「思考実験なのだな」とお付き合いいただければ幸いです。
:::

「すぐに」RSAが量子コンピュータで解かれる事はないと思います。
ただ、事実として、こういった話があります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/01f9d62e-6ff2-4eee-03e8-b4479ddca690.png)

何がすごいかというと、RSAのビット数$n$に対して、

**2016年の手法は、$n^3$オーダだった回路の深さが、2019年の手法では、$\color{red}{n^2}$オーダに改善**

これは、研究者ではない１エンジニアの感想に過ぎませんが、**技術革新の匂いを感じます。**

# 歴代の改善を並べてみる
:::note warn
<b>各手法が前提とする条件もバラバラなので、この議論にどれだけの意味があるかは不明です。</b>
:::

ですが、歴代の手法がどれだけの改善を成し遂げてきたのか？には興味があります。
幸いにもこの論文[^1]の**B2. Entries**にて歴代の手法を紹介する論文がリスト化されていたので、各手法[^Meter][^Jones][^Gormann]がどれだけの物理量子ビットを要求するか？をプロットしてみました。
こう見てみると、

[^Meter]: [R. Van Meter, T. D. Ladd, A. G. Fowler, and Y. Yamamoto. <br> Distributed Quantum Computation Architecture Using Semiconductor Nanophotonics, 2010](https://arxiv.org/abs/0906.2686)

[^Jones]: [N. Cody Jones, Rodney Van Meter, Austin G. Fowler, Peter L. McMahon, Jungsang Kim, Thaddeus D. Ladd, Yoshihisa Yamamoto.<br> Layered architecture for quantum computing, 2012](https://arxiv.org/abs/1010.5022)

[^Gormann]: [Joe O'Gorman, Earl T. Campbell.<br>Quantum computation with realistic magic state factories, 2017](https://arxiv.org/abs/1605.07197)


* 2010年には、**65億物理ビット**が必要とされていたRSAの解読も
* 2019年には、**23百万物理ビット**まで減少しており、技術は革新を続けています。

<img width=1200 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/3a3ad4ff-4d24-879d-0412-860effa931df.png>

# マシンメーカ各社のロードマップと見比べる
量子ビット拡大のロードマップを発表しているマシンメーカ（Google、IBM[^IBM_R]、IonQ[^IonQ]）の情報をマッピングしてみるとこんな構図となります。

こうやって見てみると、

* 現時点では、RSAを量子コンピュータで解くというのは、ほぼ「無理ゲー」です。
* ただ、「RSAを解くアルゴリズム」、「量子コンピュータメーカ」は双方、技術を磨き続けます
* そうすると、いつか、RSAが量子コンピュータで解かれるXデーが到来する。（かもしれません）

<img width=1200 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/6d70164b-0317-79e0-8dd9-e5f2fb38b04a.png>


[^IBM_R]: [IBM’s roadmap for scaling quantum technology](https://research.ibm.com/blog/ibm-quantum-roadmap)
[^IonQ]: [Scaling IonQ's Quantum Computers: The Roadmap](https://ionq.com/posts/december-09-2020-scaling-quantum-computer-roadmap)

# 我々はどうすべきなのだろう？
冒頭の議論に戻るのですが、

> **Actual goal**: Understand how long until RSA is broken
> Replacing internet cryptosystems is a lot of work!
> How quickly dose that work need to get done?
> If the estimate is going to change, we want to know that while we can react.

> **現実問題として、インターネット上の暗号システムの置き換えには10年単位の時間を要する。**
> RSAが破られるまでの見積もりも日々変化するし、だから、人類は**それを正しく理解したい。**

これに尽きるのかもしれません。

* RSAが破られるまでの見積もりも日々変わる（下図の、<font color="red">赤い矢印の力</font>）
* 量子コンピュータのハードウェアも日々成長する（下図の、<font color="blue">青い矢印の力</font>）

<img width=1200 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/79555726-c002-839c-c73a-a898cce05ef0.png>


ただ、双方ともに**研究者が最新情報を発信し続けてくれています**。
我々はその**最新情報にきちんと耳を傾け、**（もしかしたら来てしまう）Xデーに向けて、**10年単位の時間を要する暗号刷新という大事業を進めるのか？も判断しながら**、PQC(post quantum cryptography)時代を無事に迎えられるよう、**傾聴と行動の努力が求められるのかもしれません。**

# まとめ
研究者でもない１エンジニアの大変長い記事となってしまいましたが、いかがだったでしょうか？
そんな背景で、派手に間違っている可能性もありますのでｗｗ
ぜひ、専門家の発信する情報に耳を傾けていただければ幸いです。

※本稿の内容は個人の見解であり、所属する組織の公式見解ではありません。

[^surface]: [Austin G. Fowler, Matteo Mariantoni, John M. Martinis, Andrew N. Cleland. <br/> Surface codes: Towards practical large-scale quantum computation, 2012](https://arxiv.org/abs/1208.0928)


[^1]: [Craig Gidney and Martin Eker˚a. <br/> How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, 2021](https://arxiv.org/abs/1905.09749)