はじめに
量子プログラミングを対象とした競プロのコンテストが開催されました。今回は、その参加報告をしたいと思います。
量子プログラミングとは
量子プログラミングは、量子コンピューティングを行うために、量子ビットを操作する量子回路（量子ゲートの集まり）の構成を記述するプログラミングのことです。
従来のコンピュータにおけるビットは、$0,1$の2状態のみを表現出来るのに対して、量子ビットは量子状態$\ket{\psi}$を表現できます。$\ket{0} = \left(\begin{eqnarray}1 \\ 0 \end{eqnarray} \right)$, $\ket{1} = \left(\begin{eqnarray}0 \\ 1 \end{eqnarray} \right)$とすると、量子状態$\ket{\psi}$は以下のようにベクトルで表現することが出来ます。
$$\ket{\psi} = a \ket{0} + b \ket{1} = \left(\begin{eqnarray}a \\ b \end{eqnarray} \right),
|a|^2+|b|^2 = 1 \ \ (a,b \in \mathbb{C})$$
同様に、量子ゲートは行列で表すことが出来て、例えば1量子ビットに対する量子ゲートは、$Z = \left(\begin{matrix}1&0\\ 0&-1 \end{matrix} \right)$などと表現されます。
また、$n$量子ビットに対するゲート（$n$量子ゲート）というものもあり、そちらは$2^n \times 2^n$の行列で表されます。
詳しくは、QCoderのQ&Aページにも紹介されている以下のページなどをご参照頂ければと思います。
第一回コンテスト
2024年1月20日に第一回コンテストが行われましたので、参加しました。
問題の中で、個人的に面白かったのがB3とB4でしたので、感想のようなものを以下に記述してみました。
いろいろ割愛していますので、詳細はQCoderの解説をご参照頂ければと思います。
問題B3
自然数$n(\le 5), L(\le 2^n)$が与えられたときに、$\ket{0}, \ket{1} \dots \ket{L-1}$の振幅に$-1$を掛けるプログラムを作ることになる
いま、入力は$\ket{\psi} = a_0\ket{0}+ a_1\ket{1}+ \dots + a_{2^n -1}\ket{2^n -1}$で表される。ここで整数はリトルエンディアンに従ってエンコードされており、$\ket{0}= \ket{000 \dots 0}, \ket{1} = \ket{100 \dots 0},\ket{2^n -1}=\ket{111 \dots 1}$である。
『$\ket{2^n -1}$だけに$-1$を掛ける方法が存在する』ので、任意の$\ket{i}$を$\ket{2^n -1}$に変換して、また元に戻すことが出来るなら、それを$\ket{0}, \ket{1} \dots \ket{L-1}$で繰り返せば良い。この変換を写像と考えると、任意の$\ket{i}$に対して$\ket{2^n -1}$への全単射$f_i$を作ることが出来れば、逆変換しても係数は他と合算されることなく保たれるということである。実は、$f_i$は、全単射である$X$ゲートで構成出来る。
よって、$\ket{i}$に対して、（１）$f_i$を作用、（２）$-1$を掛ける、（３）$f_i^{-1}$を作用させれば、$\ket{i}$にだけ$-1$を掛けられるので、これを$i=0 \sim L-1$で繰り返せば良い。
問題B4
問題B4は、B3の同じ問題だが、回路の深さ（実行するゲート数）の上限が50に設定されている。B3は回路の深さが少なくとも$2L$以上になるので、$L > 25$のときに条件を満たせない。
B3では、『$\ket{2^n -1}$だけに$-1$を掛ける方法が存在する』と書きましたが、実は複数制御$Z$を用いて$-1$を掛ける方法があるから、《$n$ビット中の一部だけでも1で満たせれば$-1$を掛ける方法が存在する》ことを利用する。
アイデアとしては、B3のように$\ket{i}$に対して逐次で行うのではなく、いくつかの$\ket{i}$に対してまとめて$-1$を掛ける操作を行う。
あとは、$L$より小さい値の特定だが、上位桁からのビットを$\ket{L}$と比較すると同時に、複数制御$Z$の対象も準備出来るような分け方を行っている。めちゃくちゃテクニカルというか、トリッキーな方法に見えますが、面白いですね。
上のやり方を観ると、$L=2^m$だったら、$m \sim n-1$桁目（0桁目からカウント）を反転させて、複数制御$Z$（$m+1 \sim n-1$制御、$m$桁目に$Z$）を使えば一発で変換出来て楽しいですね。
（余談）量子人材育成
量子コンピュータ界隈を眺めていると、実用的な量子コンピュータが意外と早く実現されるかも知れないという話もあるので、学生の方々などは今から勉強するのは丁度良い頃合いかも知れません。
量子コンピュータ界隈も、Cloudなどと同様に、人材育成からということで、ちょっと検索しただけでも様々なプログラムが見つかります。これから量子人材が徐々に増えていくことを期待しています。
さいごに
第1回目のコンテストは、何も準備せずに突っ込んだので、もう少し勉強して、次回に臨みたいと思います。
それではまた。