こんにちは、毛利です。みなさんは変わった計算機を見かけたら何を思いますか? 僕は「たくさん計算させたいなぁ」とか「コンパイラを書きたいなぁ」みたいな気持ちになります。この記事では先日試験に合格して取得した量子プログラミングの資格について書きます。 ゲート型量子コンピューターの話 先に量子コンピューターの話をざっとしたいと思います。量子コンピューターには大雑把にはゲート型とアニーリング型の2種類があります。この記事では(取った資格と同じ)ゲート型の話をします。アニーリング型のほうは組合せ最適化などに使われているようです。 ゲート型の量子コンピューターは計算量が減る話が多いです。身近?なのだと素因数分解が理論上とてもはやいです(ショアのアルゴリズム)。他には、N通りの中から正解を探しだすのに、√Nに比例する回数の判定で正解を探しだせるグローバーのアルゴリズムというのもあります。例えるなら100