量子コンピュータ（実機）で量子フーリエ変換する

# はじめに
[前回の記事](http://qiita.com/converghub/items/6957c6673513a5a373b6)ではIBM Qのシミュレータを使用して，４量子ビットまでの量子フーリエ変換に挑戦しました。

しかし，実際の量子コンピュータでは物理的な制約のため，ゲートの配置をよく考えないといけない旨，[参考書](https://www.amazon.co.jp/%E3%82%AF%E3%83%A9%E3%82%A6%E3%83%89%E9%87%8F%E5%AD%90%E8%A8%88%E7%AE%97%E5%85%A5%E9%96%80-IBM%E3%81%AE%E9%87%8F%E5%AD%90%E3%82%B7%E3%83%9F%E3%83%A5%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%A8%E9%87%8F%E5%AD%90%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF-%E4%B8%AD%E5%B1%B1-%E8%8C%82/dp/4877834087/ref=sr_1_1?s=digital-text&ie=UTF8&qid=1499936126&sr=8-1&keywords=%E3%82%AF%E3%83%A9%E3%82%A6%E3%83%89%E9%87%8F%E5%AD%90%E8%A8%88%E7%AE%97%E5%85%A5%E9%96%80)に書かれてありました。

そこで今回は，実機の量子コンピュータ（ibmqx2）を使用して，３量子ビットの量子フーリエ変換することを目標に試行錯誤した記録を，備忘録としてまとめます。

４量子ビット・５量子ビットの量子フーリエ変換は実装困難でした。
もしできる方がいらっしゃれば是非教えていただきたいです。

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$

# シミュレータと実機の違い
回路を作るにあたり，簡単に違いをまとめます。

## 制御NOTゲートの配置制約（ibmqx2）
IBM Qの実機ibmqx2の量子ビットの配置は下記のようになっています。

![ibmqx2-connections.png](https://qiita-image-store.s3.amazonaws.com/0/104268/6c134348-324b-8bfc-3ad8-617e56218501.png)

制御NOTゲートの目標ゲートが配置できない量子ビット（Q$_0$，Q$_3$）があるので，上図からQ$_2$を上位ビットとして実装してみることにしました。


## 使用可能ゲート
現時点で，シミュレータと実機（ibmqx2）では使用可能なゲートが，次のように異なります。

| シミュレータ | ibmqx2 | 
|:-----------:|:------------:|
|![スクリーンショット 2017-07-14 21.21.40.png](https://qiita-image-store.s3.amazonaws.com/0/104268/28ab0189-93c9-eaef-7b56-462dcebe6391.png)|![スクリーンショット 2017-07-14 21.21.19.png](https://qiita-image-store.s3.amazonaws.com/0/104268/a2f7a517-2373-9e01-7040-dd9ed23180e2.png)|

前回の記事で使用したcU1ゲートが，ibmqx2を利用する際は選択できません。
これは，シミュレータ上ではゲートの配置に制約がないため，サブルーチンとして容易に提供できるからだと思われます。

そこで，今回はcU1ゲートと等価な回路を自作して，量子フーリエ変換を実行したいと思います。

# 制御U1ゲートの実装
制御NOTゲートと位相シフト演算を利用します。
前回使用した位相行列$R_k$をもう一度書き起こします。

```math
R_{k}=
   \left(\begin{array}{cc}
      1 & 0 \\
      0 & e^{\frac{2\pi i}{2^k}} \\
    \end{array}
  \right)
```

## 制御Sゲート
制御ゲートが$\ket{0}$のときは何もせず，$\ket{1}$のときのみ位相シフト演算Sを受けるように回路を組みます。
下式のように，制御NOTゲートと$R_3$を組み合わせることでできそうです。

```math
R_3^{\dagger}R_3=I 
\\ \, \\
XR_3^{\dagger}XR_3 = 
  \left(
    \begin{array}{cc}
      0 & 1 \\
      1 & 0
    \end{array}
  \right)
  \left(
    \begin{array}{cc}
      1 & 0 \\
      0 & e^{-\frac{\pi}{4}i}
    \end{array}
  \right)
  \left(
    \begin{array}{cc}
      0 & 1 \\
      1 & 0
    \end{array}
  \right)
  \left(
    \begin{array}{cc}
      1 & 0 \\
      0 & e^{\frac{\pi}{4}i}
    \end{array}
  \right)
= e^{-\frac{\pi}{4}i}
  \left(
    \begin{array}{cc}
      1 & 0 \\
      0 & i
    \end{array}
  \right)
= e^{-\frac{\pi}{4}i} S
```

上式に係数 $e^{-\frac{\pi}{4}i}$が現れました。

この係数を打ち消すため，制御ゲートに$R_3$演算を入れておけば，制御Sゲートが作れそうです。また，$R_3=T$なので，制御Sゲートは次のようになります。

![スクリーンショット 2017-07-14 22.12.02.png](https://qiita-image-store.s3.amazonaws.com/0/104268/847a5f40-9e8c-9ac3-e21f-5f7529a019e6.png)

なお，U1ゲートを利用しても作成することができます。
![スクリーンショット 2017-07-14 23.25.26.png](https://qiita-image-store.s3.amazonaws.com/0/104268/86a0f5dc-41fa-4cbf-22ba-54c3d9efeb5f.png)

ついでに，制御$S^{\dagger}$ゲートも実装しておきます。下記のようになります。
![スクリーンショット 2017-07-15 10.25.21.png](https://qiita-image-store.s3.amazonaws.com/0/104268/b1733645-7cca-8f1b-eac4-b42cc4553d2f.png)



## 制御Tゲート
制御Sゲートと同様に下式を得ます。

```math
R_4^{\dagger}R_4=I 
\\ \, \\
XR_4^{\dagger}XR_4 = 
  \left(
    \begin{array}{cc}
      0 & 1 \\
      1 & 0
    \end{array}
  \right)
  \left(
    \begin{array}{cc}
      1 & 0 \\
      0 & e^{-\frac{\pi}{8}i}
    \end{array}
  \right)
  \left(
    \begin{array}{cc}
      0 & 1 \\
      1 & 0
    \end{array}
  \right)
  \left(
    \begin{array}{cc}
      1 & 0 \\
      0 & e^{\frac{\pi}{8}i}
    \end{array}
  \right)
= e^{-\frac{\pi}{8}i}
  \left(
    \begin{array}{cc}
      1 & 0 \\
      0 & e^{\frac{\pi}{4}i}
    \end{array}
  \right)
= e^{-\frac{\pi}{8}i} T
```
よって，制御Tゲートは下記のようになります。
![スクリーンショット 2017-07-14 22.40.03.png](https://qiita-image-store.s3.amazonaws.com/0/104268/9a8c7a8e-3dc8-6ec2-955d-5df01a92f81b.png)

こちらも，制御$T^{\dagger}$ゲートを実装しておきます。下記のようになります。
![スクリーンショット 2017-07-15 10.28.59.png](https://qiita-image-store.s3.amazonaws.com/0/104268/14ee0274-b07b-1617-ee61-8e1dd070e3cf.png)


## 念のため確認
制御Tゲートの量子回路に，それぞれ$\ket{1}\frac{\ket{0}+\ket{1}}{\sqrt{2}}$，$\ket{1}\frac{\ket{0}-\ket{1}}{\sqrt{2}}$を入力させたときの出力結果が期待通りになるか数式を追って確認します。
制御ゲートが$\ket{1}$なので，目標ゲートの出力が$\frac{\ket{0}+e^{\frac{\pi}{4}i}\ket{1}}{\sqrt{2}}$，$\frac{\ket{0}-e^{\frac{\pi}{4}i}\ket{1}}{\sqrt{2}}$になると期待できます。
<br>

```math
\begin{align}
\ket{1}\frac{\ket{0} \pm \ket{1}}{\sqrt{2}}
&\xrightarrow{I \otimes U1(\frac{\pi}{8})}
\ket{1}\frac{\ket{0} \pm e^{\frac{\pi}{8}i}\ket{1}}{\sqrt{2}}
\xrightarrow{CNOT}
\ket{1}\frac{\ket{1} \pm e^{\frac{\pi}{8}i}\ket{0}}{\sqrt{2}} \\
&\xrightarrow{I \otimes U1(-\frac{\pi}{8})}
\ket{1}\frac{e^{-\frac{\pi}{8}i}\ket{1} \pm e^{\frac{\pi}{8}i}\ket{0}}{\sqrt{2}}
\xrightarrow{CNOT}
\ket{1}\frac{e^{-\frac{\pi}{8}i}\ket{0} \pm e^{\frac{\pi}{8}i}\ket{1}}{\sqrt{2}} \\
&\xrightarrow{U1(\frac{\pi}{8}) \otimes I}
e^{\frac{\pi}{8}i}\ket{1}\frac{e^{-\frac{\pi}{8}i}\left(\ket{0} \pm e^{\frac{\pi}{4}i}\ket{1}\right)}{\sqrt{2}} 
= \ket{1}\frac{\ket{0} \pm e^{\frac{\pi}{4}i}\ket{1}}{\sqrt{2}}
\end{align}
```
<br>
期待通りになりました。これで一安心です（式変形が間違っていなければ・・・）。


# ibmqx2で実装
以上を踏まえて，ゲート配置の制約を気にしつつ，３量子ビットの量子フーリエ変換ゲートを作ります。
今回は，入力が$\ket{\text{q}[2]\text{q}[4]\text{q}[3]}$となるように組みました。

![visualIBMQASM.png](https://qiita-image-store.s3.amazonaws.com/0/104268/953fe5a0-c54c-1d23-939a-e2e6129ccd8e.png)


これを計算すると，入力が$\ket{000}$なので，出力は等確率で観測される重ね合わせ状態になっているはずです。
全く同じ回路をシミュレータ，ibmqx2で実行した結果を示します。Shotsは8192です。
<br>
■　入力が$\ket{000}$の場合

| シミュレータ | ibmqx2 | 
|:----------------:|:------------:|
|![スクリーンショット 2017-07-15 0.29.16.png](https://qiita-image-store.s3.amazonaws.com/0/104268/a6eaad27-9f1e-ba7c-efe3-b9645c674e52.png)|![スクリーンショット 2017-07-15 9.19.37.png](https://qiita-image-store.s3.amazonaws.com/0/104268/b920cc07-d033-e5e8-27f0-f71b90b48fad.png)|



■　入力が$\ket{111}$の場合

| シミュレータ | ibmqx2 | 
|:----------------:|:------------:|
|![スクリーンショット 2017-07-15 9.18.45.png](https://qiita-image-store.s3.amazonaws.com/0/104268/a342a6b0-6594-c58e-fa36-b9befe27d27f.png)|![スクリーンショット 2017-07-15 9.20.41.png](https://qiita-image-store.s3.amazonaws.com/0/104268/563f14a6-99c2-909e-bc29-02fbf418b9c3.png)|


実機では誤差が出ました。

シミュレータでは期待した出力ですが，
誤差が大きいとゲートが合っているのか少し心配になってきました。
<br>
せっかくなので，数式を変形して確認したいと思います。

## ゲートの確認
では，確認していきます。

入力は，$\ket{q[2]q[4]q[3]}=\ket{q_2 q_4 q_3}$とします。
表記について，例えば$CNOT_{4,2}$の4，２はそれぞれ制御ゲート，目標ゲートとします。

```math
\begin{align}
\ket{q_2 q_4 q_3} 
&\xrightarrow{H \otimes I \otimes I}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_2}{2}\right)}\ket{1}}{\sqrt{2}}\ket{q_4 q_3}
\xrightarrow{T \otimes I \otimes I}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_2}{2}\right)}e^{\frac{\pi}{4}i}\ket{1}}{\sqrt{2}}\ket{q_4 q_3}　\\
&\xrightarrow{CNOT_{4,2}}
\frac{\ket{0 \oplus q_4}+e^{2\pi i \left(\frac{q_2}{2}\right)}e^{\frac{\pi}{4}i}\ket{1 \oplus q_4}}{\sqrt{2}}\ket{q_4 q_3} \\
&\xrightarrow{T^{\dagger} \otimes I \otimes I}
\frac{\left(e^{-\frac{\pi}{4}i}\right)^{\left(0 \oplus q_4\right)} \ket{0 \oplus q_4}+e^{2\pi i \left(\frac{q_2}{2}\right)}e^{\frac{\pi}{4}i}\left(e^{-\frac{\pi}{4}i}\right)^{\left(1 \oplus q_4\right)}\ket{1 \oplus q_4}}{\sqrt{2}}\ket{q_4 q_3} \\
&\xrightarrow{CNOT_{4,2}}
\frac{\left(e^{-\frac{\pi}{4}i}\right)^{\left(0 \oplus q_4\right)} \ket{0}+e^{2\pi i \left(\frac{q_2}{2}\right)}e^{\frac{\pi}{4}i}\left(e^{-\frac{\pi}{4}i}\right)^{\left(1 \oplus q_4\right)}\ket{1}}{\sqrt{2}}\ket{q_4 q_3} \\
&\xrightarrow{I \otimes T \otimes I}
\frac{\left(e^{-\frac{\pi}{4}i}\right)^{\left(0 \oplus q_4\right)} \ket{0}+e^{2\pi i \left(\frac{q_2}{2}\right)}e^{\frac{\pi}{4}i}\left(e^{-\frac{\pi}{4}i}\right)^{\left(1 \oplus q_4\right)}\ket{1}}{\sqrt{2}}\left(e^{\frac{\pi}{4}i}\right)^{q_4} \ket{q_4 q_3} \\
& =
\frac{\left(e^{-\frac{\pi}{4}i}\right)^{\left(0 \oplus q_4\right)}\left(e^{\frac{\pi}{4}i}\right)^{q_4} \ket{0}+e^{2\pi i \left(\frac{q_2}{2}\right)}\left(e^{-\frac{\pi}{4}i}\right)^{\left(1 \oplus q_4\right)}\left(e^{\frac{\pi}{4}i}\right)^{(1+q_4)} \ket{1}}{\sqrt{2}}\ket{q_4 q_3} \\
& = 
\frac{\ket{0}+e^{2\pi i \left(\frac{q_2}{2}+\frac{q_4}{2^2}\right)}\ket{1}}{\sqrt{2}}\ket{q_4 q_3} \\
&\xrightarrow{U1\left(\frac{\pi}{8}\right)\otimes I \otimes I}
\xrightarrow{CNOT_{3,2}}
\xrightarrow{U1\left(-\frac{\pi}{8}\right)\otimes I \otimes I}
\xrightarrow{CNOT_{3,2}}
\xrightarrow{I \otimes I \otimes U1\left(\frac{\pi}{8}\right)}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_2}{2}+\frac{q_4}{2^2}+\frac{q_3}{2^3}\right)}\ket{1}}{\sqrt{2}}\ket{q_4 q_3} \\
&\xrightarrow{I \otimes H \otimes I}
\xrightarrow{I \otimes T \otimes I}
\xrightarrow{CNOT_{3,4}}
\xrightarrow{I \otimes T^{\dagger} \otimes I}
\xrightarrow{CNOT_{3,4}}
\xrightarrow{I \otimes I \otimes T}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_2}{2}+\frac{q_4}{2^2}+\frac{q_3}{2^3}\right)}\ket{1}}{\sqrt{2}}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_4}{2}+\frac{q_3}{2^2}\right)}\ket{1}}{\sqrt{2}}\ket{q_3} \\
&\xrightarrow{I \otimes I \otimes H}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_2}{2}+\frac{q_4}{2^2}+\frac{q_3}{2^3}\right)}\ket{1}}{\sqrt{2}}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_4}{2}+\frac{q_3}{2^2}\right)}\ket{1}}{\sqrt{2}}
\frac{\ket{0}+e^{2\pi i \left(\frac{q_3}{2}\right)}\ket{1}}{\sqrt{2}} \\
&= 
\frac{\ket{0}+e^{2\pi i \left(0.q_2 q_4 q_3\right)}\ket{1}}{\sqrt{2}}
\frac{\ket{0}+e^{2\pi i \left(0.q_4 q_3\right)}\ket{1}}{\sqrt{2}}
\frac{\ket{0}+e^{2\pi i \left(0.q_3\right)}\ket{1}}{\sqrt{2}} 
\end{align}
```

後半は式変形も同じ形が多いので省略しました。出力時，前回同様上位ビットと下位ビットの順序が逆になりますが，どうやら合っていますね。


## 逆量子フーリエ変換
最後に，量子フーリエ変換した後，逆量子フーリエ変換するとどうなるか違いを確認したいと思います。
シミュレータでは元に戻るはずですが，ibmqx2ではそうならないと予想されます。
量子フーリエ変換したのち，逆量子フーリエ変換するゲートは以下のようになりました。

![visualIBMQASM.png](https://qiita-image-store.s3.amazonaws.com/0/104268/ea03701b-ba32-79a9-1297-61a141083cbd.png)

先ほどと同様に，全く同じ回路を使用して，入力が$\ket{000}$，$\ket{111}$の２通りで比較したいと思います。

■　入力が$\ket{000}$の場合

| シミュレータ | ibmqx2 | 
|:----------------:|:------------:|
|![スクリーンショット 2017-07-15 12.22.22.png](https://qiita-image-store.s3.amazonaws.com/0/104268/967f1f40-12a3-e2cb-b6e3-5950be1df159.png)|![スクリーンショット 2017-07-15 12.26.31.png](https://qiita-image-store.s3.amazonaws.com/0/104268/d9768dbb-1084-3f9b-a965-39e61df4fc41.png)|




■　入力が$\ket{111}$の場合

| シミュレータ | ibmqx2 | 
|:----------------:|:------------:|
|![スクリーンショット 2017-07-15 12.23.14.png](https://qiita-image-store.s3.amazonaws.com/0/104268/82c368f2-8944-9782-c232-47e72d0d5b1a.png)|![スクリーンショット 2017-07-15 12.28.20.png](https://qiita-image-store.s3.amazonaws.com/0/104268/63f114da-9b6c-faa8-eec2-4d5bbf3e286f.png)|

<br>
計算上は100%の確率で元に戻るはずが，実際の量子コンピュータではそうならないことが確認できました。

とくに２量子ビット以上異なる確率は低めにみえますが，勉強不足でこの結果をどう理解するべきかよくわかりませんでした。

量子フーリエ変換に限らず，こういう場合，例えばグローバーの振幅増幅手法の場合は，どのような結果になるか興味がわきますね。

# 最後に
ここまで読んでくださりありがとうございました。

実機で量子回路をするにあたり，計算式を紙に書きおこすことで曖昧に理解していた部分が解消され，とても勉強になりました。
とくに制御Uゲートを自分で用意するための数式変形および逆量子フーリエ変換。
（逆量子フーリエ変換の数式は省略しています。時間があればここに更新する形で追記します。）


今後は，因数分解アルゴリズムや誤り訂正のための学習を続ける予定です。

# 参考文献
[クラウド量子計算入門](https://www.amazon.co.jp/%E3%82%AF%E3%83%A9%E3%82%A6%E3%83%89%E9%87%8F%E5%AD%90%E8%A8%88%E7%AE%97%E5%85%A5%E9%96%80-IBM%E3%81%AE%E9%87%8F%E5%AD%90%E3%82%B7%E3%83%9F%E3%83%A5%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%A8%E9%87%8F%E5%AD%90%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF-%E4%B8%AD%E5%B1%B1-%E8%8C%82/dp/4877834087/ref=sr_1_1?s=digital-text&ie=UTF8&qid=1499936126&sr=8-1&keywords=%E3%82%AF%E3%83%A9%E3%82%A6%E3%83%89%E9%87%8F%E5%AD%90%E8%A8%88%E7%AE%97%E5%85%A5%E9%96%80)
[量子アルゴリズム](https://www.amazon.co.jp/dp/B01N0O3YCV)
Elementary gates for quantum computation (Barenco, 1995)