量子コンピューターにはモナドがよく似合う


本日 12月17日を数で表すと 1217。199番目の素数、スーパー素数（素数の数列における素数番目の素数）の日です。今回、17番目の [Advent Calender 2017 Haskell（その2）](https://qiita.com/advent-calendar/2017/haskell2) に参加させて頂きます。望月新一教授による宇宙際タイヒミューラー理論の ~~論文査読が完了し、正しさが認められたという~~ 嬉しいニュース[^8]が報じられた~~記念~~日に、この記事を書いています。 

さて、この記事では、Haskell と量子プログラミング[^1]との相性の良さと、現在利用できる QIO について軽く紹介して、その使い方や問題点を見ていきたいと思います。

## 量子コンピューター界隈の最新動向
2017年は、量子コンピューターの実現に大きく近づいた年となりました。特に、この年末にかけて、Google, IBM,  Microsoft という古典コンピューター[^2]に関わる巨人たちが揃って次のような大きな成果を目指して活動してきました。

+ Google
  Google は、2015年には、カナダの D-Wave 社のイジングマシン（アニーリング型量子コンピューター）をいち早く使って、「量子コンピューター[^3]が１億倍高速[^4]」という論文を NASA とともに発表し、世界の目を量子コンピューターに向けた先駆け的な成果を出しました。一方で、Google は、万能性のある量子コンピューターの研究開発にも独自で取り組み、2017年のうちに、49 量子ビットを実現するという発表しています。もしこれが今年中に実現すれば、今年最大のニュースとなるでしょう。しかし、噂によると、正式発表にはもう少し時間がかかりそうな気配です。果たして、Google からのクリスマスプレゼントは届くのでしょうか？


+ IBM
  2017年を振り返ると、量子コンピューター関連の最大のニュースといえば、2017年3月の「IBM Q」の登場でしょう。IBM により、量子コンピューターがクラウドで商用利用できるようになりました。利用できる量子ビット数が少ないとはいえ、この分野に関わる多くの人たちに刺激と希望を与えました。そして12月14日、20 量子ビットの最新のデバイスの構造も公開されました。かなり前から、IBM は量子コンピューターでは先駆者でしたが、現時点でも最先端を走っているのは、IBM でしょう。そして更には、現状のスパコン性能の評価値を高め、49 量子ビットでは、量子コンピューターは古典コンピューターを超えられない、という研究発表も行っています。おそらく、Google に先行されまいと、プライドをかけた真剣勝負の研究開発競争があるのでしょう。それを観客サイドに立ってみると非常に面白いです。


+ Microsoft
  Microsoft は、量子情報の専門家のなかでも、選りすぐりの研究者を自社に招聘して、先進的な研究をしています。その成果が、公けにリークされることは少なく、突然の進展があることもあり、今後もこの分野では期待されています。ソフトウェアでは、量子プログラミング言語「LIQi|>」（「リキッド」と読みます）を公開して、貢献していました。しかし、ハードウェアに関しては、少々、悲観的な状況のようです。彼らの目指す方式（マヨナラと呼ばれる）は、理論的には素晴らしい方式ですが、まだ実現段階ではないと見られています。特に今年の Google, IBM の活動から、焦りを感じているのでしょうか、今まであった「LIQi|>」を捨てて[^5]、12月12日に、新しい量子プログラミング言語「Q#」をリリースしました。ソフトウェア開発者を味方につける戦略として、Visual Studio で量子プログラミングができるような環境を整えようとしています。

## 量子コンピューターを扱うライブラリ

量子コンピューターを扱うライブラリや量子プログラミング言語は、python を使った実装が盛んに行われております。一部には、量子コンピューターをやるなら、python を勉強すればいいと言う人もいます。確かに、最新の量子コンピューターのためのライブラリは、次の通り、python 実装のものがほとんどです。

+ OpenFermion　：　Google謹製のライブラリ群。
+ QiSKit　：　IBM製、IBM Q とそのエミュレーターを使うためのライブラリ群。
+ pyQuil　：　Rigetti（量子コンピューター専業のベンチャー）製のライブラリ群。

そこに、Microsoft が F# を拡張した「Q#」を登場させました。
これだけあれば、プログラマーの皆さんが活躍するための環境が揃ってきているのではないでしょうか。

しかし、Haskell 好きの私としては、Haskell の状況に言及しないわけにはいきません。
そもそも、量子プログラミング言語が初めて登場したときには、C言語や関数型言語を元にしたものがほとんどした。その流れを汲む量子プログラミング言語に、Haskell をホスト言語とした埋め込み言語として実装された「Quipper」があります。Quipperは、2013年に公開されており、上のどの python よりも先に開発されてきました。しかし、2017年現在では、OSSとしてメンテナンスされておらず、最新のGHCや、stack環境への対応などがなく、少々時代遅れになってしまっています。（残念です）

## 量子プログラムの動作
ここまでで、量子コンピューターとそれを取り巻く量子プログラミングに関する状況をみてきました。ここでは、量子コンピューターの特性とふまえて、量子プログラムの周辺環境について考えてみましょう。

量子コンピューターの動作や仕組みは、様々なところで解説されていますが、次の図で示すような説明がされていることはありません。学術的な正確さはなく、一般的な解説でもありませんが、あながち間違えでもない概念を表しているつもりです。
<img src="https://qiita-image-store.s3.amazonaws.com/0/136950/373f8527-04dc-ff8e-2b7a-2f41a930f669.png" width="600" />
この図を簡単に解説しますと、この図の箱状になっている部分が量子コンピューターです。
量子コンピューターは、計算したい計算「関数$f(x)$」を入力として、量子計算して確率的に得られる値$x$とその値が得られる確率$Prob$を求め、「確率密度関数$Prob(x)$」として出力します。
量子コンピューターの中（図の箱の中）には、$n$個の量子ビットがあり、計算レジスタとして使います。また、演算する前に、入力として与えられた「関数$f(x)$」を、この量子ビットに作用（操作ともいう）するための$ U_{f(x)}^{(n)} $ （これを「ユニタリー変換（行列）」と呼びます）に翻訳します。このユニタリー変換 $ U_{f(x)}^{(n)} $ は、古典コンピューターでいう「マシン語」「アセンブリ言語」と呼ばれるレイアと似た仕組みで「量子アセンブリ言語」と呼んでも差し支えないものです。そして関数$f(x)$からユニタリー変換$ U_{f(x)}^{(n)} $への翻訳作業は「量子コンパイル」とも呼べる動作になります。
実際の量子計算は、$n$量子ビットにユニタリー変換を作用させることで計算されます。一言で表現すると、$2n$次の複素行列計算を繰り返して計算結果を導きます。この計算結果は、確率的に値が得られますので、確率付きの値が出力されます。
（偏見的ではありますが）この箱のような計算機が量子コンピューターです。

「箱の中にはいった計算のようなもの」
「確率的な振舞いが箱の中では行われている」...
「関数を入力として」「〇〇関数で出力される」...

Haskell を学ばれているエンジニアさんは、もうピンときますよね？[^6]
そうです。「量子コンピューターは、モナドで表現できるのです」
そして「関数型言語で記述する」のも良さそうです。


## Haskell には QIO あり
Haskell には、量子コンピューターを扱うための Hackage ライブラリ「QIO」が既にあります。QIO は、QuantumIO の略でしょう。IO と名前がつくだけあって、勿論、モナド構造で実装されています。
それでは、QIO を使いながら具体的にみてみましょう。

※以下では、Haskellの実行環境 stack が整備されていることを前提とします。

```bash
$ stack install QIO
```
と、サクッとインストールしておきましょう。
### QIO の概要
QIO では、Qdata 型クラスで、古典での情報（例えば、Bool）と、量子での情報（Qbit）を関連づけます。
具体的な例として、量子ビット（Qbit）の実装をみます。

```haskell:QioSyn.hs
newtype Qbit = Qbit Int deriving (Num, Enum, Eq, Ord)
applyU :: U -> QIO ()
```
```haskell:Qdata.hs
instance Qdata Bool Qbit where
  mkQ = mkQbit
  measQ = measQbit
  letU b xu = ulet b xu
  condQ q br = cond q br
```
それぞれに定義された関数をみてみましょう。

`applyU :: U -> QIO ()`は、与えられたユニタリ演算を現在の量子状態に適用します。
`mkQbit :: Bool -> QIO Qbit`は、与えられたBool値でQbitを初期化し、それを全体の量子状態に加えます。`ulet :: Bool -> (Qbit -> U) -> U`は、与えられたユニタリー変換に、与えられたBool値の付属的な量子ビットを導入したユニタリー変換です。`cond :: Qbit -> (Bool -> U) -> U`は、与えられたQbitの値に応じて条件付きユニタリー変換を作用する、ユニタリー変換です。そして、`measQbit :: Qbit -> QIO Bool`は、与えられたQbitを測定し、測定結果を返します。（測定が破壊的であるため、全体の量子状態に影響を及ぼす可能性がある操作です。）

つまり、量子ビット（Qbit）が Bool から作れて（mkQ）、様々なユニタリー変換を作る（letU,condQ）ことができ、これを適用(applyU)したり、観測（measQ）することができます。これが、QIO コンテキストの中（量子コンピューターの箱の中）で行われるという実装となっています。
次に、ユニタリー変換の型を調べておきます。

```haskell:QioSyn.hs
data U = UReturn | Rot Qbit Rotation U
       | Swap Qbit Qbit U | Cond Qbit (Bool -> U) U | Ulet Bool (Qbit -> U) 
```
回転変換`Rot`、スワップ変換`Swap`、制御付きユニタリー変換`Cond`（今は Control という）、サブユニタリー変換`Ulet`が定義されています。
あとは、プログラム実行のための関数があれば、使えそうです。

```haskell:Qio.hs
run :: QIO a -> IO a
```

量子計算を行うために必要な、ひと通りの部品は揃っているようです。

### QIO を使ってみる
#### 量子ビット（Qbit）の具体例

```haskell:QExamples.hs
-- | Initialise a qubit in the |0> state
q0 :: QIO Qbit
q0 = mkQ False

-- | Initialise a qubit in the |1> state
q1 :: QIO Qbit
q1  =  mkQ True

-- | Initialise a qubit in the |+> state. This is done by applying a Hadamard
-- gate to the |0> state.
qPlus :: QIO Qbit
qPlus  =  do  qa <- q0
              applyU (uhad qa)
              return qa

-- | Initialise a qubit in the |-> state. This is done by applying a Hadamard
-- gate to the |1> state.
qMinus :: QIO Qbit
qMinus  =  do  qa <- q1
               applyU (uhad qa)
               return qa
```
#### ユニタリー変換の具体例

基礎的な演算を定義して、パウリ演算とアダマール演算の定義を見てみます。

```haskell
-- | The phase rotation
rphase :: RR -> Rotation
rphase _ (False,False)  = 1
rphase r (True,True)    = exp(0:+r)
rphase _ (_,_)          = 0

-- | Apply the given rotation to the given qubit
rot :: Qbit -> Rotation -> U
rot x r = Rot x r UReturn

-- | Apply a phase rotation (of the given angle) to the given qubit
uphase :: Qbit -> RR -> U
uphase x r = rot x (rphase r)
```


+ パウリ（Pauli）演算

```haskell:QExapmles.hs,QIORandom.hs
-- | A definition of the Pauli-Z gate.
uZZ :: Qbit -> U
uZZ qb = (uphase qb pi)

-- | The exponentiated Pauli-X rotation
rX :: RR -> Rotation
rX r (x,y) = if x==y then (cos (r/2):+0) else (0:+ (-(sin (r/2))))

-- | The exponentiated Pauli-Y rotation
rY :: RR -> Rotation
rY r (x,y) = if x==y then (cos (r/2):+0) else (s * sin (r/2):+0) where s = if x then 1 else -1
```

+ アダマール（Hadamard）演算

```haskell:QioSyn.hs,QIORandom.hs
-- | The hadamard rotation
rhad :: Rotation
rhad (x,y) = if x && y then -h else h where h = (1/sqrt 2)

-- | Apply a hadamard rotation to the given qubit
uhad :: Qbit -> U
uhad x = rot x rhad

-- | Applies a Hadamard rotation to each qubit in the given list of qubits
hadamards :: [Qbit] -> U
hadamards [] = mempty
hadamards (q:qs) = uhad q `mappend` hadamards qs
```
Haskellでは、複数量子ビットのアダマール操作がこのように、非常に簡単に記述できます。

#### ショアのアルゴリズム

最後に、量子アプリケーションの例をみてみましょう。
QIO には、ショアのアルゴリズムを動作させる関数が含まれています[^7]。ショアのアルゴリズムは、量子コンピューターで因数分解を行うためのアルゴリズムで、古典コンピューターより高速に大きな数の因数が解かるとされているものです。詳しくは別記事「[量子コンピュータで因数分解が高速に解ける？〜 ショアのアルゴリズム 〜](https://qiita.com/kyamaz/items/eebd0f7734c8a33de2ad)」を参考にしてください。
それでは、`import QIO.Shor` した、数行のプログラム`shor.hs`で試してみましょう。引数を１つ指定して、その指定した自然数の因数を調べます。因数があれば停止し、因数がなければ候補を探し続けます。

！！注意事項！！
乱暴な作りです。候補が見つかるまで止まりません。止まらない場合は[Ctrl-C]で止めてください。

```haskell:shor.hs
import QIO.Shor
import System.Environment (getArgs)

main = do
  args <- getArgs
  factorV (read $ head args :: Int)
```
幾つか試してみましょう。


```bash:（例１）15の因数分解
$ stack runhaskell shor.hs 15

Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 1 15"
Shor took
period a = 0, giving xa = 1
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 4 15"
Shor took
period a = 6, giving xa = 64
Result: Factors of 15 include 5 and 3.
 The total time taken was
```
２回試行して、３回目で答えがでています。（この例ではたまたま２回でした。１回で答えを出すときもありますし、十数回繰り返したときもありました。）

```bash:（例２）11の因数分解（！注意！この実行例は停止しません。）
$ stack runhaskell shor.hs 11

Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 8 11"
Shor took
period a = 7, giving xa = 512
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 6 11"
Shor took
period a = 12, giving xa = 46656
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 3 11"
Shor took 1 sec
period a = 2, giving xa = 3
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 7 11"
Shor took
period a = 11, giving xa = 16807
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 4 11"
Shor took
period a = 0, giving xa = 1
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 2 11"
Shor took
period a = 7, giving xa = 8
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 8 11"
Shor took
period a = 4, giving xa = 64
Recalling factorV
Started at Sat Dec DD hh:mm:ss JST 2017
Calling "shor 10 11"
Shor took
period a = 0, giving xa = 1
Recalling factorV
:
[Ctrl-C]
```
素数の因数を探していますから、見つからないです。正しいことは正しいですが、プログラムをもう少し工夫しないとです。

次に、少し大きめの数を２つ試してみます。

```bash:（例３）65536,　65535の因数分解
$ stack runhaskell shor.hs 65536
Factors of 65536 include 2 and 2.
 The total time taken was

$ stack runhaskell shor.hs 65535
Started at Sat Dec DD hh:mm:ss JST 2017
shor.hs: int2bits: too large
CallStack (from HasCallStack):
  error, called at ./QIO/Qdata.hs:67:36 in QIO-1.3-A4P3Lp84s89rm1VQydBNq:QIO.Qdata
```

ん？2の倍数は、即座に判定してますが、5の倍数を得るのも、 int2bits で扱える値より大きすぎるというエラーがでて、実行できません。続いて、グロタンディーク素数（因数分解できます！）も試してみます。

```bash:（例４）57の因数分解
$ stack runhaskell shor.hs 57
Started at Sat Dec DD hh:mm:ss JST 2017
shor.hs: int2bits: too large
CallStack (from HasCallStack):
  error, called at ./QIO/Qdata.hs:67:36 in QIO-1.3-A4P3Lp84s89rm1VQydBNq:QIO.Qdata
```

あぁ〜あ、これほど簡単(？)な自然数の因数も見つけてくれませんでした。

これを見ると、QIOの実装は、さほど出来のよいものでは無さそうです。
折角存在している QIO なのですが、どうも今どきの利用用途としては、使え無さそうです。
そうとは言え、量子計算についてHaskellで試してみるための、ショーケースとしての役割は果たしているとは思います。


## あとがき
私には「量子の世界感はモナドで記述するのが良く似合う」という思いがあり、今回の記事を書かせて頂きました。結論的には、今どきの量子プログラミング[^1]に合う実装は Haskell には今のところ存在していません。これから先、この状況を打開するべく、活動していきたいと考えております。

「量子コンピューターをやるなら、Haskell を勉強すればいい」と言われる日がいつか来て欲しい。量子コンピューターの隆盛とともに、Haskell の利用が増えることをクリスマスのお願いとしたいと思います。

最後に、私はこのような場で発言することがほとんどなく不慣れで、量子情報の研究者でもありません。拙文、および論理的な裏付けの欠如は、平にご容赦ください。
さらに、Advent Calendar 2017 のイベントに、[Haskell](https://qiita.com/advent-calendar/2017/haskell2)のテーマで参加表明したのちに、[量子コンピュータ](https://qiita.com/advent-calendar/2017/quantum)のテーマが作られました。ただ、量子コンピュータの参加者は少なく、寂しい状況です。この記事は、Haskellカレンダー用に書きましたが、両方の領域に関わるため、量子コンピュータのカレンダへのエントリ記事ともさせて頂きます。


---
[^1]: 「量子プログラミング」という言葉そのものが新しい言葉です。現在、量子コンピューターが実用的なものではない状況で、量子コンピューター上で動作する「量子アプリケーション」がどのようなソフトウェアで、それを記述するためのプログラムがどういったものかは未成熟です。
[^2]: 量子コンピューター界隈では、従来型のコンピューターを敬意を持って「古典コンピューター」と呼びます。物理学で「量子力学」が登場した以降、ニュートン力学などのそれ以前の力学を「古典力学」と呼んでいるのと同じです。
[^3]: この記事では、ここ以外に「量子コンピューター」と記載する場合は、万能性のあるゲート型の量子コンピューターを指します。
[^4]: この１億倍速いという研究論文も、のちにD-Waveマシンが得意で差が顕著にでやすい問題を扱った比較評価だったと言われています。
[^5]: Microsoftの「Q#」は、実際は、それまでの「LIQUi|>」を元にして、新しい言語のような見せ方をしているだけです。言うなれば、F# の亜種でしょう。
[^6]: [箱で考えるFunctor、ApplicativeそしてMonad](https://qiita.com/suin/items/0255f0637921dcdfe83b)が参考になるでしょう。
[^7]: ショアのアルゴリズムのほかに、`QExamples.hs`では、量子テレポーテーションやドイチェのアルゴリズムの例があります。また、`Qft.hs`にショアのアルゴリズムでも使っている量子フーリエ変換の実装例もあります。
[^8]: (12/21追記)今年になって査読は進んでいるという状況でしたが、完了したというのは、あるメディアの勇み足による報道だったようです。12/21現在では、情報が混乱しておりますが、誤っている部分を消し線で削除しました。裏付けのない第一報のみを信じて、本記事に掲載してしまいましたことに関しまして、お詫び申し上げます。ただ、望月教授の理論が認められる日が来ることを祈りましょう。