量子プログラミングなんもわからん人の量子プロコンQPC001感想戦（A系問題）

概要

先日、QCoderというサイトで、量子プログラミングを用いたプログラミングコンテストQCoder Programming Contest 001（以下、QPC）が開催されました。簡単に言えば競プロでお馴染みAtCoderの量子プログラミング版です。

開催期間内は手が付けられませんでしたが、その後、解説を読みながら実装の仕方などを確認したので、自分のための備忘録も兼ねてこちらに残しておきたいなと思います。

この記事では、A1〜A5の問題について記載します。まだBの問題群は理解しきれていません…。

この記事は、もともと量子プログラミングなんも分からんかった人が書いていますし、量子ビットの理論を理解したわけではなく、問題における解法を把握したに留まります。内容が厳密ではなかったり、間違っていることもあるかもしれません。その際はコメントなどでご指摘いただければ幸いです。

初心者が噛み砕いて理解した内容が、これから学習される方の参考になれば嬉しいなと思っています。

QPCの基礎的な部分

QPCの提出は、Pythonのqiskitというライブラリを用いたプログラムに限定されます。プログラムの雛形が提示され、指定された部分にコードを追記して提出します。また、現状でQCoderにはAtCoderのようなレーティングの機能はありません。

量子プログラミングの基礎的な部分

公式のQAには、学習教材の紹介があります。しっかりと量子プログラミングを学習したい方は、こちらもご参照ください。また、同ページ内にはこの後記載するような量子プログラミングの基礎的な部分の解説も記載されています。

以下では、「量子ビット」「量子状態」「量子ゲート」「量子回路」について自分なりにまとめます。すでにこれらを理解されている方は、読み飛ばしてください。

量子ビット・量子状態

量子コンピュータでは、1ビットを0か1か分からない確率的なものとして扱います。これは、ビット1つで「0である確率が〇〇％、1である確率が〇〇％な状態」を表すということです。このようなビットを量子ビットと呼び、その状態はベクトルで表されブラケット記法で表記されることが多いです。

今、0である確率が100％の場合は $\ket{0} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ と、1である確率が100%の場合 $\ket{1} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$ と表します。

この2つの量子ビットを用いて、0である確率が $|\alpha|^2$ 、1である確率が $|\beta|^2$ であるような任意の量子ビット $\ket{\psi}$ を、次のように表すことができます。

\ket{\psi} = \alpha\ket{0} + \beta\ket{1} = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}

複数量子ビット

上記までは1ビットの表現したが、2ビット以上の場合でも同様に表現できます。

簡単に2ビットで考えると、00である確率が $|a_1|^2$ 、10である確率が $|a_2|^2$ 、01である確率が $|a_3|^2$ 、11である確率が $|a_4|^2$ である場合、以下のように表せます。

$$\ket{\psi} = a_1\ket{00} + a_2\ket{10} + a_3\ket{01} + a_4\ket{11} = \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{pmatrix}$$

同様に一般化してnビットの場合でも、以下のようになります。

\ket{\psi} = a_0\ket{\underbrace{0...0}_n} + a_1\ket{\underbrace{10...0}_n} + ... + a_{2^n-1}\ket{\underbrace{1...1}_n} = \begin{pmatrix} a_0 \\ \vdots \\ a_{2^n - 1} \end{pmatrix}

計算基底状態

解説やQAの中にはこの計算基底状態という表現がたびたび出ていました。数学用語なのかもしれませんが自分があまり詳しくないので、自分なりの理解で「確定的な状態のこと」という意味で扱います。この辺り、詳しい方いらっしゃったら教えてください。

上記までで出てきた $\ket{0}$ は必ず0という状態ですし、 $\ket{10}$ は必ず10という状態ですので計算基底状態です。

そして、こうした計算基底状態は、01のような2進数表記に加え、10進数にした表記を用いる場合もあります。注意が必要なのは、QCoderのサイト内の書き方では一般的な2進数表記とブラケットでの表記が上位ビットと下位ビットが逆であるということです。高校数学などでは右側を下位として $011_{(2)}=3_{(10)}$ と表しますが、ブラケット記法では左側を下位として $\ket{011}=\ket{6}$ と表現します。

コメントでご指摘いただき、2進数表記の上位ビットの位置について、「QCoderのサイト内の書き方では」という文言を追記しました。ブラケット記法でどちら上位ビットとして記述するかは、書籍やライブラリなどによっても変わるようです。

同様に2ビットの計算基底状態であれば次のように表現できます。

\underbrace{\ket{0}}_{\text{10進数}} = \underbrace{\ket{00}}_{\text{2進数}},\ \ket{1} = \ket{10},\ \ket{2} = \ket{01},\ \ket{3} = \ket{11}

量子ゲート

量子ゲートは、大雑把にいうと足し算の＋、引き算の－のような演算子と言えるのかなと思います。古典的コンピュータで言えば論理ゲートとも言えるでしょう。

古典ビット0がNOTゲートを通ると1になります。同様に量子ビット $\ket{0}$ が $X$ ゲートという量子ゲートを通ると $\ket{1}$ になります。

量子ゲートの種類は様々あって、ここの知識を深めていくことが、量子プログラミングの第一歩になるのかなと感じました。この先のAの問題群は、この量子ゲートを上手いこと組みわせて目的の状態を作るということをしていきます。

また、論理ゲートにおけるANDゲートやORゲートのように、複数の量子ビットに関係して作用する量子ゲートもあります。以下の制御ゲートが主な例です。

参考：List of quantum logic gates (Wikipedia)

制御ゲート

量子ゲートの一種で、2つの量子ビットに関係して作用します。このうち1つは「制御ビット」、他方は「対象ビット」となります。制御ゲートは、「制御ビット」が $\ket{1}$ である計算基底状態にのみ、対象ビットに対してゲートが作用します。

例えば $\ket{00}, \ket{10}, \ket{01}, \ket{11}$ の4つの量子ビットがあり制御ビットが1桁目であれば、 $\ket{10}, \ket{11}$ の計算基底状態に対してのみゲートが作用することになります。

制御X(CX)ゲートであれば、対象ビットが反転されるので、制御ビット1桁目、対象ビット2桁目であれば $\ket{00}+\ket{10}+\ket{01} \xrightarrow{CX(0, 1)} \ket{00}+\ket{11}+\ket{01}$ となります。

量子回路

Aの問題群は「〜〜というような操作を量子回路qc上に実装せよ」というような問題文になっています。この量子回路は、古典的コンピュータの論理回路のように、いくらかの量子ゲートを組み合わせて作る一通りの操作の集まりというような表現になるのかなと思います。古典的なプログラミングで言えば、処理を記述した関数のようなものとでもいえるでしょうか。

厳密には、関数にあたる処理をまとめたものには、オラクルという別の要素があるようですが…。

プログラムでの実装

Pythonのライブラリであるqiskitで量子プログラミングを扱う実例を見ていきます。

まず、以下のコードでn量子ビットからなる量子回路を作成します。

qc = QuantumCircuit(n)

これに対し、以下のようにゲートを作用させていきます。1行目では引数で0桁目のビットにHゲートを作用させています。その後、0桁目のビットを制御ビット、1桁目のビットを対象ビットとして2行目でCXゲートを作用させています。桁数はどちらも0始まりです。

qc.h(0)
# qc.cx(control qubit, target qubit)
qc.cx(0, 1)

解説を見ながら問題を解く

A1

Generate Plus state

問題文

ゼロ状態からプラス状態 $\ket{+}$ を作り出す操作を、1量子ビットをもつ量子回路 qc上に実装せよ。
プラス状態 $\ket{+}$ は次式で定義される。
$$\ket{+} = \frac{1}{\sqrt{2}} (\ket{0} + \ket{1}) \nonumber$$

解説

この問題は、量子ゲートを用いて量子ビットの状態を操作するということの基本を問う問題でした。「プラス状態」というのは正直よく分からないのですが、これは0の確率も1の確率も、どちらも同じ1/2であるような状態を作るという操作にあたります。（確率は係数に当たる $\frac{1}{\sqrt{2}}$ の絶対値の二乗で表される）こういう状態を確率的な重ね合わせ状態というように表現するようです。

この重ね合わせ状態は、アダマールゲート(Hゲート) を量子ビットに作用させることで実現できるそうです。この場合ではゼロ状態はHゲートを通って等確率な重ね合わせ状態に遷移します。

したがって、量子回路の1ビットにHゲートを作用させる下記のコードで実装ができました。h()メソッドに第１引数には、Hゲートを作用させるビットの桁を指定します。

from qiskit import QuantumCircuit

def solve() -> QuantumCircuit:
    qc = QuantumCircuit(1)

    # Write your code here:
    qc.h(0)
 
    return qc

A2

Generate Uniform Superposition State

問題文

整数nが入力として与えられる。
ゼロ状態から一様重ね合わせ状態 $\ket{A}$ を作り出す操作をn量子ビットをもつ量子回路qc上に実装せよ。
一様重ね合わせ状態 $\ket{A}$ は次式で定義される。

\begin{align} \ket{A} &= \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1} \ket{i} \nonumber\\ & = \frac{1}{\sqrt{2^n}} (\ket{\underbrace{0...0}_n} + ... + \ket{\underbrace{1...1}_n}) \nonumber \end{align}

解説

この問題も、A1と同様にすべての状態が等確率に現れる重ね合わせ状態を作るという操作でした。ただし、A1は1ビット対する操作だったのに対して、A2では任意のnビットからなる量子回路になっています。

この問題でも、重ね合わせ状態を作るためにはHゲートを作用させることでできるそうです。A1と違い、全ての量子ビットに対してHゲートを作用させることで、上記 $\ket{A}$ のような等確率な状態が作れます。

A1ではh()メソッドの引数で桁を渡し作用させる量子ビットを指定しました。この桁数をfor文で回して指定するか、rangeなどで範囲を指定してあげることで各量子ビットにHゲートを作用させることが可能なようです。

from qiskit import QuantumCircuit

def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)

    # Write your code here:
    qc.h(range(n))
 
    return qc

もしくは

from qiskit import QuantumCircuit

def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)

    # Write your code here:
    for i in range(n):
        qc.h(i)
 
    return qc

A3

Generate state $\frac{1}{\sqrt{2}} (\ket{0} + \ket{3})$

問題文

ゼロ状態から状態 $\ket{\psi}$ を作り出す操作を2量子ビットをもつ量子回路qc上に実装せよ。
状態 $\ket{\psi}$ は次式で定義される。
$$\begin{equation} \ket{\psi} = \frac{1}{\sqrt{2}} (\ket{0} + \ket{3}) = \frac{1}{\sqrt{2}} (\ket{00} + \ket{11}) \nonumber \end{equation}$$

解説

作りたい状態は一見するとA1のものに似ていますが、A3では量子ビットが2ビットあります。似ているといったので、ゼロ状態 $\ket{00}$ の1つ目のビットにHゲートを作用させることを考えてみます。すると、以下のような状態に遷移します。

$$\ket{00} \xrightarrow{H(0)} \frac{1}{\sqrt{2}} (\ket{00} + \ket{10})$$

あと $\ket{10}$ が $\ket{11}$ になってくれれば嬉しいですね。ここで、上で説明した制御ゲートを使います。今、この2つの状態を比べてみると、1つ目の量子ビットは1のまま変わらず、2つ目の量子ビットだけビットが反転しています。したがって、この1つ目の量子ビットを制御ビット、2つ目の量子ビットを対象ビットとして反転させるようなゲートを作用させれば良いことが分かります。

この操作は制御Xゲート(CXゲート) を使うことで実現できます。以下のように状態が遷移します。

$$\frac{1}{\sqrt{2}} (\ket{00} + \ket{10}) \xrightarrow{CX(0, 1)} \frac{1}{\sqrt{2}} (\ket{00} + \ket{11})$$

CXゲートはcx()メソッドで記述でき、第1引数に制御ビットの桁、第2引数に対象ビットの桁を渡します。今回の場合はcx(0, 1)とすれば良いです。(桁数は0オリジン)

from qiskit import QuantumCircuit

def solve() -> QuantumCircuit:
    qc = QuantumCircuit(2)

    # Write your code here:
    qc.h(0)
    # qc.cx(control qubit, target qubit)
    qc.cx(0, 1)
    
    return qc

A4

Generate state $\frac{1}{\sqrt{3}} (\ket{0} + \ket{1} + \ket{2}))$ I

問題文

ゼロ状態から状態 $\ket{\psi}$ を作り出す操作を2量子ビットをもつ量子回路qc上に実装せよ。
状態 $\ket{\psi}$ は次式で定義される。
$$\begin{equation} \ket{\psi} = a_0\ket{0} + a_1\ket{1} + a_2\ket{2} = a_0\ket{00} + a_1\ket{10} + a_2\ket{01} \nonumber \end{equation}$$
ただし、 $a_1, a_2, a_3$ は0でない任意の複素振幅を表す。（値は問わない）

解説

今回は、3つの計算基底状態からなる重ね合わせ状態を作りたいです。このように $2^n$ 個以外の計算基底状態からなる重ね合わせを作る場合は、制御アダマールゲート(CHゲート)を作用させることで生成できるそうです。

この問題でもまずは1つ目のビットにHゲートを作用させます。

$$\ket{00} \xrightarrow{H(0)} \frac{1}{\sqrt{2}} (\ket{00} + \ket{10})$$

そして1ビット目を制御ビット、2ビット目を対象ビットとしてCHゲートを作用させます。つまり、上記の $\ket{10}$ にのみHゲートが作用します。

$$\frac{1}{\sqrt{2}} (\ket{00} + \ket{10}) \xrightarrow{CH(0, 1)} \frac{1}{\sqrt{2}} \ket{00} + \frac{1}{2}(\ket{10} + \ket{11})$$

ここまでの操作で、 $\ket{00}$ と $\ket{10}$ が生成でき、計算基底状態の数も3つになりました。あとは $\ket{11}$ が $\ket{01}$ になって欲しいです。これは1つ目のビットの反転なので、CXゲートで生成できそうだとなります。したがって、2つ目のビットを制御ビット、1つ目のビットを対象ビットとしてCXゲートを作用させます。

$$ \frac{1}{\sqrt{2}} \ket{00} + \frac{1}{2}(\ket{10} + \ket{11}) \xrightarrow{CX(1, 0)} \frac{1}{\sqrt{2}} \ket{00} + \frac{1}{2}(\ket{10} + \ket{01}) $$

これにて、係数はバラバラですが、3つの計算基底状態からなる状態を生成できました。係数はバラバラなので、3つが同じ確率で現れるわけではないですね。

まとめると、この問題でする操作は以下です。

1. 1ビット目にHゲートを作用
2. 1ビット目を制御ビット、2ビット目を対象ビットとしてCHゲートを作用
3. 2ビット目を制御ビット、1ビット目を対象ビットとしてCXゲートを作用

この通りに量子回路を組み立てていきます。

from qiskit import QuantumCircuit

def solve() -> QuantumCircuit:
    qc = QuantumCircuit(2)

    # Write your code here:
    qc.h(0)
    qc.ch(0, 1)
    qc.cx(1, 0)

    return qc

A5

Generate state $\frac{1}{\sqrt{3}} (\ket{0} + \ket{1} + \ket{2}))$ II

問題文

ゼロ状態から状態 $\ket{\psi}$ を作り出す操作を2量子ビットをもつ量子回路qc上に実装せよ。
状態 $\ket{\psi}$ は次式で定義される。
$$\begin{equation} \ket{\psi} = \frac{1}{\sqrt{3}} (\ket{0} + \ket{1} + \ket{2}) = \frac{1}{\sqrt{3}} (\ket{00} + \ket{10} + \ket{01}) \nonumber \end{equation}$$

解説

A4問題との違いは、各計算基底状態の係数が全て $1/\sqrt{3}$ となっている点ですね。すなわち、3つが全て等確率で現れる状態であるということです。A4ではこの係数は何でもよいとされていました。

この問題は、A4における初めのHゲートを通した後の状態を $\frac{1}{\sqrt{3}} \ket{00} + \sqrt{\frac{2}{3}} \ket{10}$ とすることができれば実現できそうです。 $\ket{10}$ はこの後CHゲートを通して、係数が $1/\sqrt{2}$ 倍となるためです。

このような係数が等確率ではない重ね合わせの遷移は、Hゲートではなく回転ゲートというものを用いて実現できるようです。

一般に任意の量子ビット $\ket{\psi'}$ の状態は角度のパラメータ $\theta, \phi$ を用いて以下のように表現できます。

$$\ket{\psi} = \cos(\theta/2) \ket{0} + (\cos(\phi) + i \sin(\phi))\sin(\theta/2) \ket{1}$$

今回、虚数成分は0ですので $\phi = 0$ としてよく、 $\frac{1}{\sqrt{3}} \ket{00} + \sqrt{\frac{2}{3}} \ket{10}$ とするためには以下の連立方程式が得られます。

\left\{ \, \begin{aligned}
& \cos(\theta/2) = 1/\sqrt{3} \\
& \sin(\theta/2) =  \sqrt{2/3}
\end{aligned}
\right.

これを解くと $\theta = 4 \arctan\left(\frac{\sqrt{6}}{3 + \sqrt{3}}\right)$ となります。今、この角度パラメータ $\theta$ はy軸上の回転角を表すので、y軸上の回転ゲートである $R_y$ ゲートを利用して $\theta$ の回転を加えることで、 $\ket{00} \xrightarrow{Ry(\theta, 0)} \frac{1}{\sqrt{3}} \ket{00} + \sqrt{\frac{2}{3}} \ket{10}$ と遷移させることができました。

この回転の話は、1量子ビットの量子状態を半径1の球面上に表すブロッホ球というものもを用いて公式解説では説明されていました。ただ、自分の言葉で説明できるほど十分には理解できず、この記事では詳細に説明することは控えておきます。詳細は、公式解説か他のリソースをご参照いただければと思います。

この後はA4と同様に、CHゲートとCXゲートを作用させてこの問題を解くことができます。

\begin{align}
\ket{00} &\xrightarrow{Ry(\theta, 0)} \frac{1}{\sqrt{3}} \ket{00} + \sqrt{\frac{2}{3}} \ket{10} \nonumber \\
&\xrightarrow{CH(0, 1)} \frac{1}{\sqrt{3}} (\ket{00} + \ket{10} + \ket{11}) \nonumber \\
&\xrightarrow{CX(1, 0)} \frac{1}{\sqrt{3}} (\ket{00} + \ket{10} + \ket{01}) \nonumber
\end{align}

これらの操作をプログラム上では以下のように実装します。まず角度の変化量thetaを求め、それを用いて回転ゲートにあたるry()メソッドを使用しています。ry()メソッドの引数は、第1引数が回転の角度、第2引数が回転対象のビットの桁です。今回は1つ目のビットをthetaだけ回転させます。

from qiskit import QuantumCircuit
import math
 
def solve() -> QuantumCircuit:
    qc = QuantumCircuit(2)

    # Write your code here:
    theta = 4 * math.atan(math.sqrt(6)/ (3 + math.sqrt(3)))

    qc.ry(theta, 0)
    qc.ch(0, 1)
    qc.cx(1, 0)

    return qc

まとめ

この記事では、量子プログラミングの初歩的な話とQPC001のAの問題群の解説をまとめました。量子ゲートを組み合わせるところは、理解できるとパズルのようで楽しかったです🥰

量子プログラミングの解法で汎用性の高そうなことは、以下の内容かなと思っています。

• Hゲートは等確率の重ね合わせの状態を作ることができる。
• Xゲートはビットを反転する。
• 制御ゲートは、制御ビットと対象ビットの複数のビットに対して関係する。
  • 対象ビットが1である計算基底状態に対してゲートが作用する。
  • CXゲートは対象ビットに対してXゲートを作用する。
  • CHゲートは対象ビットに対してHゲートを作用する。
• 回転ゲートを用いて重ね合わせの状態を作ることもできる。
  • $\theta$ 周りに回転させる場合には、y軸まわりの $R_y$ ゲートを使用する。

まだまだ、BとCの問題群は理解しきれいていませんし、もっと学びを深める必要があるものばかりですが、これからも少なからず量子プログラミングは取り組んで生きたなと思いました。