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

# 概要
先日、[QCoder](https://www.qcoder.jp/)というサイトで、量子プログラミングを用いたプログラミングコンテスト[QCoder Programming Contest 001](https://www.qcoder.jp/contests/QPC001)（以下、QPC）が開催されました。簡単に言えば競プロでお馴染みAtCoderの量子プログラミング版です。

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

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

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

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

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

# 量子プログラミングの基礎的な部分
[公式のQA](https://www.qcoder.jp/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}$ を、次のように表すことができます。

```math
\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ビットの場合でも、以下のようになります。

```math
\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}$ と表現します。

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

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

```math
\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)](https://en.wikipedia.org/wiki/List_of_quantum_logic_gates)

### 制御ゲート
量子ゲートの一種で、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量子ビットからなる量子回路を作成します。

```python
qc = QuantumCircuit(n)
```

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

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

# 解説を見ながら問題を解く
## A1
**Generate Plus state**

[**問題文**](https://www.qcoder.jp/contests/QPC001/problems/A1)

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

[**解説**](https://www.qcoder.jp/contests/QPC001/editorials/A1)

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

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

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

```python
from qiskit import QuantumCircuit

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

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

## A2
**Generate Uniform Superposition State**

[**問題文**](https://www.qcoder.jp/contests/QPC001/problems/A2)

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

[**解説**](https://www.qcoder.jp/contests/QPC001/editorials/A2)

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

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

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

```python
from qiskit import QuantumCircuit

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

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

もしくは

```python
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})$**

[**問題文**](https://www.qcoder.jp/contests/QPC001/problems/A3)

> ゼロ状態から状態 $\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}$$

[**解説**](https://www.qcoder.jp/contests/QPC001/editorials/A3)

作りたい状態は一見すると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オリジン)

```python
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**

[**問題文**](https://www.qcoder.jp/contests/QPC001/problems/A4)

> ゼロ状態から状態 $\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でない任意の複素振幅を表す。（値は問わない）

[**解説**](https://www.qcoder.jp/contests/QPC001/editorials/A4)

今回は、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ゲートを作用

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

```python
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**

[**問題文**](https://www.qcoder.jp/contests/QPC001/problems/A5)

> ゼロ状態から状態 $\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}$$

[**解説**](https://www.qcoder.jp/contests/QPC001/editorials/A5)

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}$ とするためには以下の連立方程式が得られます。

```math
\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の球面上に表すブロッホ球というものもを用いて公式解説では説明されていました。ただ、自分の言葉で説明できるほど十分には理解できず、この記事では詳細に説明することは控えておきます。詳細は、[公式解説](https://www.qcoder.jp/contests/QPC001/editorials/A5)か他のリソースをご参照いただければと思います。

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

```math
\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`だけ回転させます。

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