さっきこれ見た： https://x.com/adamscochran/status/1962148452072124879?s=46 素人としては、複数の大規模な材料科学のブレークスルーの背後に道筋があるように思える。

ゲート数についてはよく分からないけど、必要な論理キュービットの数を見ると、伝統的なコンピュータがすでに因数分解した829ビットのRSA-250のような数を因数分解するには、まだまだ遠い感じだね。

現実的には、古典コンピュータがすでに数兆のトランジスタを持ってるから、数百万から数十億のキュービットが必要だよね。

じゃあ、「暗号的に有用」な数を因数分解するのに、どれくらいのゲートが必要なんだろう？これは二つの理由で難しい質問だよ。まず、「暗号的に有用」の明確な線引きがないこと。次に、そういう計算ができる量子コンピュータの正確な設計がまだ分からないこと。1985年に「意味的に有用」なニューラルネットワークを構築するのにどれくらいの従来のゲートが必要かを推定するのと似てる。でも、答えはほぼ確実に数百万だと思う。 [UPDATE] 予測が難しい第三の理由は、量子誤り訂正において、原始キュービットの誤り率と信頼性のある誤り訂正された仮想キュービットを構築するのに必要なゲート数のトレードオフがあること。原始キュービットの誤り率が低いほど、必要なゲート数は少なくなる。今のところ、どのくらいの原始誤り率が達成できるかは分からない。 > 量子コンピュータが今世紀に役立つ道筋ってあるのかな？今世紀はあと75年残ってるけど、それってテクノロジーの時間では永遠だよね。75年前の古典コンピュータの最先端は（ちょっと甘く見て）ユニバックだった。現代のコンピュータと比べてどれだけパワーが劣っていたかを考えるのは面白いよ、特にops/wattの観点でやると。計算はしてないけど、桁違いに多いと思う。もし量子コンピュータでも同じ進歩が達成できれば、2100年までには前量子暗号は確実に終わりだね。古典コンピュータの改善にはトランジスタという一つのブレークスルーが必要だったけど、量子コンピュータにはそれに相当するものがまだない。いつそれが起こるかは分からないけど、誰かが初めて解決するまでは全てが不可能に思えるんだ。

RSA 4096には、10^7のキュービットと10^-4の誤り率が必要だよ（桁の大きさね）。数百のキュービットでその低い誤り率を持って、すでに有用で価値のある量子化学計算ができるし、ポスト量子アルゴリズムが日々一般的になってきて、暗号解読用の量子コンピュータを作るインセンティブが減ってきてると思う。量子コンピュータは、暗号に使うのが難しい方向で最も早く進展すると思う。

最新の数字は、約1e6キュービットでエラー率が1e-4だって。 https://arxiv.org/abs/2505.15917。OPが言ってるゲートの意味では、エラー訂正された文脈での量を定量化するのは難しいんだ。自分のコードにネイティブな操作にコンパイルしたらね。1MHzの「クロック」（コードサイクル時間、専門家向け）を仮定すると、計算時間は約1週間くらいになる。ある意味、これはキュービットの数よりも達成が難しい指標かもしれない。量子エラー訂正の魔法（エラー率の指数的改善）は両方に作用するから、もしキュービットの忠実度がさらに9上がれば、キュービットの数もかなり改善されるよ。一方で、計算をいくつかのシステムに分ける必要があると、状況はかなり悪化する。

じゃあ、いくつのゲートがあれば「暗号的に有用な」数を因数分解できるの？ [1]の表5では、2048ビットのRSA整数を因数分解するのに70億のトフォリゲートが必要だと推定してる。 > 量子コンピュータが今世紀に役立つ道筋はあるの？ 数十億のゲートを実現するための道筋は量子エラー訂正だよ。[1]では、物理的な仮定に基づいて、25のサーフェスコードがその70億のゲートに十分だと推定してる。これで、1400の論理キュービットから100万の物理的なノイズのあるキュービットに増えるんだ。サミュエル・ジャックは今年のPQCryptoでかなり良い講演をしていて、そこでタイムラインについて推測してるよ [2]。（このブログ記事と[1]の著者です。） [1]: https://arxiv.org/pdf/2505.15917 [2]: https://www.youtube.com/watch?v=nJxENYdsB6c

「（ちょっと余談だけど、この因数分解-21回路にかけられた最適化の量は、大きな数を因数分解する際に可能なものとは多分かけ離れてると思う。もっと現実的な最適化の量だと、因数分解-15回路の500倍のコストの回路ができるだろうけど… 100倍のオーバーヘッドでも十分に私のポイントを伝えられる。ともあれ、この回路で使われている条件付き4での乗算サブルーチンを見つけるために高額なコンピュータ検索を行ってくれたノア・シャッティに特別な感謝を。）」

ちょっと話が逸れるけど、暗号学者たちは新しいギガワットデータセンターでRSA1024を因数分解するのは不可能だと確信してるの？最速の既知のアルゴリズムでも、合理的な時間内に因数分解するにはまだ遅すぎるみたいだけど。近い将来にこれらのアルゴリズムに改善がないという合意があるの？

RSA1024のコストの推定は、4ビットのケースから外挿するんじゃなくて、ターゲットサイズでの明示的な回路構造を使ってるんだ。だから、投稿で指摘されている不連続性も暗黙的に考慮されてる。だから、この投稿はそのコストには影響しないよ。

量子システムの物理的刺激や、タンパク質の折りたたみ、機械学習なんかは、AlphaFoldの後でもまだやることがあるのかな？

対称暗号（AESやChaCha、SHA-2ファミリーも含む）については、量子攻撃をキー長を半分にするような「ミート・イン・ザ・ミドル攻撃」として手を振って説明できる。この攻撃があったからこそ、DESを強化する際に3DESになったんだ。結構手を振る部分が多いけど、実際の量子コンピュータは非量子コンピュータと同じコストや速度、小ささではないし、スピードアップも単純に半分にはならない。だけど、例えばAES-128が仮想のAES-64と同じくらい弱いとしたら、それでもAES-256があるから大丈夫って言える。だけど、主な焦点はキー交換にある。なんでかって？キー交換は秘密を声に出さずに合意する賢い部分だから。KEXを使うと、アリスとボブが秘密に合意するけど、どちらもそれを口にしない。これを破ると、他の全てを暗号化するために使われた秘密を知ることができる。過去に録音した会話も含めてね。もし未来の悪党が量子コンピュータを持っていたら、キー交換によって今は読めない既存の会話を読み取れるけど、署名アルゴリズムを破ったところで、今のものを過去にさかのぼって署名することはできない。だからKEXに焦点が当たるんだ。そういうものが存在するか、すぐに実現することが明らかになったら、署名などの他の問題を解決することが重要になるけど、KEXに関してはもう手遅れなんだ。

どうやって？っていうのは必須だよね。ちょっと面白いけど、無知で大げさで、内容が薄い感じがする。

115倍は（あまり現実的ではない）大量の最適化を行うことで得られたんだ。

最小限の実装は不安定で信頼性がないっていう考えだと思う。詳細は分からないけど、量子誤り訂正キュービットについては、N個のキュービットを巧妙に接続して非常に安定したキュービットとして機能させるための研究がたくさんある。「デコヒーレンス時間」みたいな用語も出てくるし、これが急速に大量のキュービットに拡大することを想像できるよ。

要するに、21を因数分解する回路を作るためにかかる最適化作業の量が、15を因数分解する回路よりも約100倍大きいのは、もっと大きな数字には現実的じゃないってことだよね。だから、一般的なルールとしては、因数分解する数が増えるごとに、約500倍のゲートが必要になるってことだ。

より現実的な最適化の量は、実はあまり最適化しないことだと思う。正確に言うと、大きなサイズでの最適化の恩恵は、N=21の回路の時よりも少なくなると予想されてる。

[遅延]