量子アルゴリズムの魅力(競プロer向け)

今回は量子アルゴリズムの記事を書いてみました。私は現在M1で、この量子アルゴリズムについての研究を行っています。今回の記事はタイトル通り主に競プロer向けです。具体的には

• 計算量の概念、 の意味が分かる

人に向けた記事です。誰でも量子計算の魅力を理解できる記事も書きたいとは思っています。しかし、まだ記事を書くのに慣れていないこともあり、ターゲットを絞った方がいいと思ったので、今回は競プロer向けとさせていただきます。そして二つの強力な量子アルゴリズム、GroverのアルゴリズムとShorのアルゴリズムについて簡単に解説しようと思います。

量子アルゴリズムとは？

「そもそも量子アルゴリズムって何？」という人も多いと思います。簡単に言うと量子コンピューターを使ったアルゴリズムです。では量子コンピューターが何か、どうやって作るのか？と聞かれると、実は私も答えることができません。 抽象的に言うと、「量子力学特有の現象を使うことで計算を行う、現代のコンピューターと比べてとても高速なコンピューター」です。 私は「量子アルゴリズムを使って何ができるか？」を研究しているだけで、量子コンピューターを作る研究をしているわけではありません。 逆に言うと、どうやって作るかを知らなくても、何ができるかは研究することはできるのです！

なんで高速に計算できるの？

これを細かく説明しようとすると、また記事の更新がしばらく止まりそうなので、重要なことだけ言います。

一つのプロセッサで並列計算ができるからです。

つまり任意の自然数と配列とについて、 を１ステップで同時に計算できます。すごく速いです。厳密に言うと計算ができるだけで、結果として我々が得られるのはの中で一つだけなので、計算には少し工夫が必要なのですが。この得られる結果が一つなのが量子特有の難しい部分なので、この解説はまた今度にさせてください。

Groverのアルゴリズムとは

これが書きたいので競プロer向けの記事にしました。Groverのアルゴリズムがどんなアルゴリズムかと言うと

時間かかる全探索を、時間で行うことができる

アルゴリズムです。競プロerの方ならGroverのアルゴリズムがとても強力なアルゴリズムであることが理解できるかと思います。もともと全探索にかかる時間が なら 時間でできます。競プロ的にはチートですね。 このアルゴリズムを応用した様々な問題を解く高速なアルゴリズムが、現在研究されています。

Shorのアルゴリズムとは

もう一つ、Shorのアルゴリズムという有名なアルゴリズムがあります。これは

素因数分解をビット数についての多項式時間で解くことができる

アルゴリズムです。このアルゴリズムの存在が示されているため、量子コンピューターが開発されると、RSA暗号が終わるなどと言われています。 今のところ、このアルゴリズムを使うために必要なビット数を持つ量子コンピューターは、まだ存在していません。いつか開発される日が来るとは言われていますが。 このアルゴリズムは量子フーリエ変換(FFTではなくQFT)を使ったアルゴリズムです。この量子フーリエ変換を応用した様々なアルゴリズムも、現在研究されています。

すごさは分かったけど難しいんでしょ？

この二つのアルゴリズムを理解するのに必要な知識は、線形代数の知識だけです。量子力学の知識は必要ないです。この二つのアルゴリズムが、具体的にどういう計算を行うアルゴリズムなのかは、線形代数だけで理解することができます。 量子計算と言うと物理の分野だと思ってしまう方が多くいると思います。しかし実際は、数学の知識さえあれば誰でも勉強できる分野です(アーキテクチャを除けば)。 少しでも多くの競プロerの方が、量子アルゴリズムに興味を持ってくれたらなぁと思って書いてみました。興味を持った方、一緒に量子アルゴリズムの勉強をしてみませんか？