【学習メモ】量子の話が難しいという話、量子アルゴリズムの計算量とか

自分用の学習メモとして記事に載せます。。
今回は特に誤りがある可能性が高いので、ご注意ください。

量子の話が難しい

量子コンピュータ、量子回路、量子アルゴリズム、この辺りの学習をしようとしたのですが、脳内に数式がイメージできずに挫折しました。。

量子回路を古典電気電子系で例えると、交流回路+デジタル回路のような雰囲気に感じました。交流回路では、何かしらの計算をするときに虚数を使って単位円で位相を表現すると思います。量子回路では、単位球(ブロッホ球)で量子の状態を表現することに加えて、デジタル回路(組合回路、順序回路)的なステートフルな話が入ってくる感じかなと思いました。単位円から単位球になって複雑に、さらにステートも考えないといけないのか、、、という感じで混乱しました。

学習リソース

学習リソースとしては、以下を参照しました。

• EMANの物理学
• Quantum Native Dojo
• Azure Quantum Coding

EMANの物理学では平易な文章で量子関連話題が説明されており、まず着手するには良い内容かなと思います。

Quantum Native Dojoでは数式をベースにして量子コンピュータの要素が1つ1つ説明されています。Quantum Native Dojoを読んでいて感じたのは、数式に対応するイメージを脳内に描く力が不足していると感じました。これが挫折要因と感じています。かなり腰を据えてやる必要がありそうです。

Azure Quantum CodingはQ#というプログラミング言語のウェブエディタです。Q#はマイクロソフトが公開している量子アルゴリズム開発用のプログラミング言語とのことです。
Hello, worldを実行すると、量子アルゴリズムらしく複数回の観測によって結果が得られます。
何をするときに使えそうなのか？　というのが重要ですが、「素因数分解」「離散対数問題」と思います。次のセクションで触れます。

量子アルゴリズムの計算量・記憶領域の消費量

量子アルゴリズムの計算量や記憶領域の消費量の話にまで持ち込めれば、応用分野ぐらい分かるだろう、と踏んで以下のようにGPTさんにまとめていただきました。

結論としては、セキュリティ関係に影響が大きそうです。今のところ。

未整序データベースの探索

検索アルゴリズム	ベスト計算量	平均計算量	ワースト計算量	記憶領域の消費量	説明
線形探索 (Linear Search)	$O(1)$	$O(n)$	$O(n)$	$O(1)$	データを先頭から順に比較。最良は最初に見つかる場合で $O(1)$。平均・最悪では全要素探索で $O(n)$。
ハッシュテーブル探索 (Hash-based Search)	$O(1)$	$O(1)$	$O(n)$	$O(n)$	衝突が少なければ平均で定数時間 ($O(1)$)。衝突が多発すると最悪 $O(n)$。
グローバーのアルゴリズム (Grover's Algorithm)	$O(1)$	$O(\sqrt{n})$	$O(\sqrt{n})$	$O(n)$ (量子ビット数依存)	量子アルゴリズム。古典的な $O(n)$ を $O(\sqrt{n})$ に高速化。ただしメモリや実装の量子ビット数に依存。

素因数分解 (Prime Factorization)

サブ指数時間は「$O(\exp((\log n)^\alpha))$」などで表します（指数関数より小さいが、多項式より大きいオーダー）。

アルゴリズム	ベスト計算量	平均計算量	ワースト計算量	記憶領域の消費量	説明
Number Field Sieve (古典最速級)	$O(\exp((\log n)^\alpha))$	$O(\exp((\log n)^\alpha))$	$O(\exp((\log n)^\alpha))$	サブ指数関数的に増加	大きな整数の素因数分解に対して現状最速級。厳密な式は $ \exp\bigl((c+o(1))(\log n)^{1/3}(\log \log n)^{2/3}\bigr) $ だが、ここでは簡単にサブ指数と表記。
Shorのアルゴリズム (量子)	$O((\log n)^k)$	$O((\log n)^k)$	$O((\log n)^k)$	$O(\mathrm{poly}(\log n))$ (量子ビット数)	量子フーリエ変換を用いて多項式時間 ($(\log n)^k$) で因数分解。大規模量子コンピュータが実現すれば古典手法を大幅に上回る。

離散対数問題

アルゴリズム	ベスト計算量	平均計算量	ワースト計算量	記憶領域の消費量	説明
古典最速級アルゴリズム（Number Field Sieve系など）	$O(\exp((\log n)^\alpha))$	$O(\exp((\log n)^\alpha))$	$O(\exp((\log n)^\alpha))$	サブ指数関数的に増加	素因数分解と同様、サブ指数時間。暗号においては有限体上や楕円曲線上の離散対数を解く際に重要。
量子アルゴリズム（Shorの離散対数アルゴリズムなど）	$O((\log n)^k)$	$O((\log n)^k)$	$O((\log n)^k)$	$O(\mathrm{poly}(\log n))$ (量子)	素因数分解と同様、量子フーリエ変換により離散対数を多項式時間で解決可能。大規模量子コンピュータがあれば暗号破壊に重大な影響。

ソーティング (Sorting)

比較モデル（要素同士を比較）

アルゴリズム	ベスト計算量	平均計算量	ワースト計算量	記憶領域の消費量	説明
クイックソート (Quick Sort, 古典)	$O(n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	良い分割なら $O(n \log n)$、悪い分割だと $O(n^2)$。再帰の深さでスタックを消費するので $O(\log n)$ の補助領域。
マージソート (Merge Sort, 古典)	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	常に安定した $O(n \log n)$ 。分割とマージで追加のメモリ $O(n)$ が必要。
量子ソート (Quantum Sorting)	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$ (量子ビット数依存)	比較モデルの下限 $ \Omega(n \log n)$ は量子でも大幅に下回れない。定数因子レベルの高速化はあるかもしれないが、漸近的な改善はなし。

行列乗算 (Matrix Multiplication)

$n \times n$ 行列に対する乗算

アルゴリズム	ベスト計算量	平均計算量	ワースト計算量	記憶領域の消費量	説明
ストラッセン (Strassen) など高速行列乗算 (古典)	$O(n^{2.81})$ など	$O(n^{2.81})$ など	$O(n^{2.81})$ など	$O(n^2)$ 以上	古典的 $O(n^3)$ より速いアルゴリズムが多数研究。最速は $O(n^{2.37182\ldots})$ 程度まで改善されているが非常に複雑。
量子行列乗算 (Quantum Matrix Multiplication)	(超多項式改善は未確立)	(同左)	(同左)	量子ビット数に依存	一般的な行列乗算における漸近的量子超越は見つかっていない。特殊構造を使う問題設定では量子の並列性で一部高速化が検討されている。

量子アルゴリズムの計算量・記憶領域の消費量、まとめ

つまり、以下のような感じらしいです。セキュリティ関係に影響が大きそうです。今のところ。

大きな改善が見込まれる問題

• 素因数分解(Shorのアルゴリズム)
• 離散対数問題(Shorのアルゴリズム)

ほとんど変わらない or 未確立な問題

• 未整序データベースの探索
• 行列乗算
• ソーティング

最後に

今回の短期量子コンピュータ理解しよう計画は失敗してしまいましたが、いつかは覇権を取るであろう技術だと思いますので、再チャレンジしたいと思います！