Idris2で量子計算 〜Qimaeraの紹介〜

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz :frog: です。
本稿は、[量子コンピューター Advent Calendar 2024](https://qiita.com/advent-calendar/2024/quantum) の 17日目の寄稿です。


## はじめに
今年も量子コンピューター関連の話題は多かったですが、初期に注目されたベンチャー Zapata Computing Holdings Inc. のネガティブな情報が10月にあった一方で、日本のベンチャーの先頭を走っている QunaSys が11月に追加の資金調達を行うという良い情報もあり、ビジネス面では業界全体として様々な見方がされているのが実状かと思います。
ただ、一時期あった過度な期待から現実に見合った期待と活用が進んでいる印象です。研究分野における成果も着実に進展していると感じております。様々な分野からの参画と多方面に渡る技術の進展が必要となります。特に、周辺ハードウェア、低レイアなデバイス制御系、ソフトウェアスタック開発の人材の参入が必要な状況だと推察しております。

:frog: は、量子プログラムのコンパイラに関わる取り組みを注目しており、高級プログラミング言語処理系のなかで関数型プログラミング言語への実装に興味をもっております。本稿では、Idris2 上での実装例である Qimaera について取り上げます。

### Idris について
Idris は依存型を扱える関数型プログラミング言語です。Idris の特徴と環境の構築については以前のエントリに簡単に紹介しておりますので参考にしてみてください。Idris には、バージョン１からバージョン２へ破壊的な仕様変更がされました。本稿では、曖昧さを避けるためにプログラミング言語の呼称としても、バージョン２系を明確にするため 2 を付けて Idris2 と表記することにします。

https://qiita.com/kyamaz/items/20dd334180a3225e5107

https://qiita.com/kyamaz/items/1e31a6abdf8dc320444d

## Qimaera の外観
Qimaera は、2021年にarXivに投稿された論文  [arXiv:2111.10867](https://arxiv.org/abs/2111.10867)  で提案されている Idris2 上で動作する量子プログラミングのためのライブラリ群です。GitHub でソースコードが公開されています。（ https://github.com/zamdzhiev/Qimaera ）
昨今、量子・古典ハイブリッドアルゴリズムとして変分量子アルゴリズムが有用な計算として研究されております。この論文でも、変分量子アルゴリズムである QAOA と VQE について検証されています。本稿では、そのような量子プログラミングの応用的な例示の前段階として、基本的な側面を取り上げてたいと思います。（応用例はいずれエントリにしようと思っています。）

量子プログラミングに、Idris2が都合のよい理由として次の２点が挙げられております。

(1) ユニタリな量子操作を実装しやすり依存型をもつ  
(2) 量子操作の実行をきめ細かく制御して量子力学の法則に準拠できるようにする線形性

## Qimaera を動かす
まずは、手元で動作させてみましょう。

#### レポジトリからソースコードを取得
前述のGithubのレポジトリから `git clone` します。以降は、そのフォルダで作業します。

```bash:
$ git clone https://github.com/zamdzhiev/Qimaera
$ cd Qimaera
```

#### プログラムを make して実行
単に、レポジトリTOPにある `makefile` をもとにしてサンプルプログラムを make します。

```bash:
$ make package
$ make
$ ./run
```

次に、レポジトリTOPにあるスクリプトファイル `run` を実行します。すると以下のように出力されて、サンプルコードが動作します。（出力は折りたたんでいます）

<details><summary>output</summary>

```bash:
Drawing ToBellBasis:
CNOT 0 1 (H 0 IdGate)
- H -- • -
------ Θ -

An example of circuit built with H, P and CNOT constructors :
 H 1 (P (pi/2) 2 (CNOT 2 0 IdGate))
- Θ -----------
--|-------- H -
- • -- S ------

Examples using composition
Example 1 : TGate . HGate
- H -- T -

Example 2 : (H 1 IdGate) . (P pi 0 IdGate) . toBellBasis
- H -- • -- Z ------
------ Θ ------- H -

Examples using tensor product
Example 1 : HGate # PGate pi # CNOTGate
- H -----------
------ Z ------
----------- • -
----------- Θ -

Example 2 : tensorn 3 HGate
- H -----------
------ H ------
----------- H -

Example 3 : tensorMapSimple [HGate, PGate pi, HGate]
- H -----------
------ Z ------
----------- H -

Example 4 : tensorMap [CNOTGate, toBellBasis, CNOTGate]
- • ----------------
- Θ ----------------
------ H -- • ------
----------- Θ ------
---------------- • -
---------------- Θ -


Another possibility for toBellBasis:
CNOTGate . (HGate # IdGate)
- H -- • -
------ Θ -

Examples using adjoint
Example 1 : adjoint toBellBasis
- • -- H -
- Θ ------

Example 2 : adjoint toffoli
- • -- T+ ------- • ------------------- • ------------------ • ----------------
- Θ -------- T -- Θ -- T+ --------------|-------- • ---------|-------- • ------
---------------------------- H -- T+ -- Θ -- T -- Θ -- T+ -- Θ -- T -- Θ -- H -


An example of usage of compose, tensor and adjoint:
(adjoint toBellBasis # IdGate) . (TGate # toBellBasis)
- T ------------ • -- H -
------ H -- • -- Θ ------
----------- Θ -----------


Apply Examples
U = HGate # IdGate {n = 1} # (PGate pi)

Example 1 : apply toBellBasis U [0,1]
- H ------- H -- • -
---------------- Θ -
------ Z -----------

Example 2 : apply toBellBasis U [0,2]
- H ------- H -- • -
-----------------|--
------ Z ------- Θ -

Example 3 : apply toBellBasis U [2,0]
- H ------------ Θ -
-----------------|--
------ Z -- H -- • -

Example 4 : apply toBellBasis U [2,1]
- H ----------------
---------------- Θ -
------ Z -- H -- • -

Example 5 : apply toffoli [2,0,1]
------ • ------------------ • ----------------------- T -- Θ -- T+ ------- Θ -
- H -- Θ -- T+ -- Θ -- T -- Θ -- T+ -- Θ -- T -- H --------|---------------|--
----------------- • ------------------ • ----------------- • -------- T -- • -

Examples of circuits parametrized by classical data
Example 1 : for b : bool , if b then HGate else PGate pi
For b = True :
- H -

For b = False :
- Z -

Example 2 : for b1, b2 : Bool and p : Double , CNOTGate . (if b1 then H 0 IdGate else IdGate) . (if b2 then IdGate else P p 1 IdGate)
For b1 = True, b2 = False, p = pi/2
------ H -- • -
- S ------- Θ -

Examples of depth computation
The depth of the following circuit
- • ------------ • -
--|--- H -- Θ -- Θ -
- Θ ------- • ------

is 3


The depth of the following circuit
------ H -----------
- H ------- H ------
---------------- H -

is 2


The depth of the following circuit
---------------- • -- • ------
- H -- Z -- H -- Θ ---|--- • -
--------------------- Θ -- Θ -

is 6


Executing an example of quantum operations : sequencing quantum operations using run
Create 2 qubits q1 and q2
Apply `toBellBasis` circuit on q1 and q2
Create one new qubit q3
Apply the toffoli gate on q1,q3 and q2
Measure q2 : result is False
Apply CNOT on q3 and q1
Measure q1 and q3 : results are False and False

Test coin toss by performing 1000 coin tosses.
Number of heads: 491

Test 'Repeat Until Success'. Probability to measure '1' is 2/3 for this example.
Number of '1' outcomes: 6678 out of 10000 measurements.

Small test with QAOA
result from QAOA : [True, True, False, False, True]
```

</details>

`makefile` もスクリプト`run` も単純な記述しかされていません。ビルドは `idris2 -p contrib -p linear Main.idr -o main` で idris2 コマンドが実行されており、その出力された実行形式のファイル `./build/exec/main` を `run` で実行しております。

サンプルとして実装されている内容は、`Main.idr` を見ると簡単に想像できます。

```idris:
main : IO ()
main = do
  -- Execute the example file and draw the circuit examples
  drawExamples

  -- Draw the Quantum Fourier Transform for n = 3
--  putStrLn "\n\n\nQuantum Fourier Transform for n = 3"
--  draw (qft 3)

  -- Execute the coin toss example
  putStrLn "\nTest coin toss by performing 1000 coin tosses."
  testCoins

  -- Repeat until success
  putStrLn "\nTest 'Repeat Until Success'. Probability to measure '1' is 2/3 for this example."
  testMultipleRUS 10000

  -- VQE
--  putStrLn "\nSmall test with VQE"
--  r <- testVQE
--  putStrLn $ "result from VQE : " ++ show r

  -- QAOA
  putStrLn "\nSmall test with QAOA"
  cut <- testQAOA
  putStrLn $ "result from QAOA : " ++ show cut

  pure ()
```

コメントアウトされている処理もありますが、別ファイルで定義されている `drawExamples`, `testCoins`, `testMultipleRUS`, `testQAOA` を呼び出しております。もう一段 `Examples.idr` まで追いかけると、次の通り幾つかの例を順番に呼び出しています。

```idris:
drawExamples : IO ()
drawExamples = do
  drawToBellBasis
  drawConstructorsExample
  drawComposeExamples
  drawTensorExamples
  drawToBellBasis2
  drawAdjointExamples
  exampleComposeTensor1
  drawApplyExamples
  drawParamExamples
  drawDepthExamples
  drawQuantumOp
```

量子プログラミングができそうな雰囲気は掴めました。これ以上のドリルダウンによる深掘りはしないで、フレームワークとしての実装を『量子計算の基本原理』に基づいてみてみましょう。

## 量子計算の基本原理
量子計算の概念を数学的な描像で説明するには、次の４つの公理系に集約することができます。言い換えるとこの４つの数学的な要素をもつようにできると、有限個の量子ビットで構成される量子コンピュータを抽象的に扱うことができます。

1. 量子状態の公理（量子ビットの重ね合わせ状態を定義する）
2. 合成の公理（量子状態の公理を複数の量子ビットに拡張して、もつれの性質を定義する）
3. 量子ゲートの公理（量子ビットの状態を変換するためのユニタリ操作を導入する）
4. 測定の公理（量子ビットの測定操作を導入し、読み出せる情報を記述できるようにする）

つまり、４つの公理に対応する実装がされていれば、量子プログラミング言語としての要素を満たしていると言えます。以下に、Qimaera の実装を確認します。


## Qimaera の内部実装
レポジトリTOPで次のように、idris2コマンドを実行すると、サンプルプログラムを読み込んだ状態で**REPL (Read-Eval-Print Loop) 環境**が整います。`makefile` にある記述と同様に、`contrib` `linear` のパッケージを読み込むようにします。

```bash:
$ idris -p contrib -p linear Main.idr
     ____    __     _         ___
    /  _/___/ /____(_)____   |__ \
    / // __  / ___/ / ___/   __/ /     Version 0.7.0-1a3df3fb6
  _/ // /_/ / /  / (__  )   / __/      https://www.idris-lang.org
 /___/\__,_/_/  /_/____/   /____/      Type :? for help

Welcome to Idris 2.  Enjoy yourself!
Main>
```

このREPL環境で実装を確認するには、`:t`, `:printdef` や `:browse` で調べるのが便利です。その出力を使いながら、量子計算の基本原理の４つの公理に対応する実装をみてみましょう。

#### 量子状態の公理（量子ビットの重ね合わせ状態を定義する）
量子ビット`Qubit`は次のように定義されております。

```idris: QuantumOp.idr にて実装
data Qubit : Type where
  MkQubit : (n : Nat) -> Qubit
```

引数は量子ビット数`n`をとるコンストラクタ`MkQubit`で量子ビットを使えるようになります。ただし、このコンストラクタはスコープがモジュール内のみですので、外部から呼べるのは `interface QuantumOp (0 t : Nat -> Type)`　に定義されている次の実装です。

```idris: QuantumOp.idr にて実装
newQubit : QuantumOp t => QStateT (t n) (t (S n)) Qubit
```

ここで、`Qubit`の状態を保持するためのモナド`QStateT`が導入されています。

#### 合成の公理（量子状態の公理を複数の量子ビットに拡張して、もつれの性質を定義する）
上記の量子ビットを複数もち、線型結合の性質も取り入れて複数の量子ビットを使えるようにする関数が以下のように定義されております。

```idris: QuantumOp.idr にて実装
newQubits : QuantumOp t => (p : Nat) -> QStateT (t n) (t (n + p)) (LVect p Qubit)
```

#### 量子ゲートの公理（量子ビットの状態を変換するためのユニタリ操作を導入する）
量子ゲートはユニタリ演算で表されればよいため、ユニタリ行列が定義できればよく、次のように実装されます。

```idris: Unitary.idr にて実装
data Unitary : Nat -> Type where
  IdGate : Unitary n
  H      : (j : Nat) -> {auto prf : (j < n) = True} -> Unitary n -> Unitary n
  P      : (p : Double) -> (j : Nat) -> {auto prf : (j < n) = True} -> Unitary n -> Unitary n
  CNOT   : (c : Nat) -> (t : Nat) ->
            {auto prf1 : (c < n) = True} -> {auto prf2 : (t < n) = True} -> {auto prf3 : (c /= t) = True} ->
            Unitary n -> Unitary n
```

このようにユニタリを定義して、代表的な１量子ビットに対する量子ゲートは `Unitary` を使って以下のように定義されます。

```idris: Unitary.idr にて実装
HGate : Unitary 1   -- アダマール(H)ゲート
XGate : Unitary 1   -- Xゲート
ZGate : Unitary 1   -- Zゲート
SGate : Unitary 1   -- Sゲート
SAdjGate : Unitary 1  -- S†ゲート
TGate : Unitary 1   -- Tゲート
TAdjGate : Unitary 1  -- T†ゲート
-- X,Y,Z軸まわりの回転ゲート
RxGate : Double -> Unitary 1
RyGate : Double -> Unitary 1
RzGate : Double -> Unitary 1
```

２量子ビットに対する `CNOTGate : Unitary 2`、トフォリゲート `toffoli : Unitary 3` などの定義も実装されています。

ユニタリの演算も定義されております。

```idris: Unitary.idr にて実装
---------------------------COMPOSE-----------------------------
|||Compose 2 circuits of the same size
public export
compose : Unitary n -> Unitary n -> Unitary n
compose IdGate g1 = g1
compose (H j g1) g2 = H j (compose g1 g2)
compose (P p j g1) g2 = P p j (compose g1 g2)
compose (CNOT c t g1) g2 = CNOT c t (compose g1 g2)

public export
(.) : Unitary n -> Unitary n -> Unitary n
(.) = compose

---------------------TENSOR PRODUCT----------------------------
|||Make the tensor product of two circuits
public export
tensor : {n : Nat} -> {p : Nat} -> Unitary n -> Unitary p -> Unitary (n + p)
tensor g1 g2 =
  let p1 = (allSmallerRangeVect 0 n)
      p2 = lemmaAnd (allSmallerRangeVect n p) (allDiffRangeVect n p)
      p3 = allSmallerPlus n p (rangeVect 0 n) p1
      p4 = lemmaAnd p3 (allDiffRangeVect 0 n)
      g' = apply {i=n} {n = n+p} g1 (IdGate {n = n+p}) (rangeVect 0 n) {prf = p4}
  in apply {i = p} {n = n + p} g2 g' (rangeVect n p) {prf = p2}

public export
(#) : {n : Nat} -> {p : Nat} -> Unitary n -> Unitary p -> Unitary (n + p)
(#) = tensor
```

さらに量子ビットに対する演算の適用については次の実装になります。

```idris: QuantumOp.idr にて実装
applyCNOT : QuantumOp t => (1 _ : Qubit) -> (1 _ : Qubit) -> QStateT (t n) (t n) (LPair Qubit Qubit)
applyH : QuantumOp t => (1 _ : Qubit) -> QStateT (t n) (t n) Qubit
applyP : QuantumOp t => Double -> (1 _ : Qubit) -> QStateT (t n) (t n) Qubit
applyUnitary : QuantumOp t => (1 _ : LVect i Qubit) -> Unitary i -> QStateT (t n) (t n) (LVect i Qubit)
```


#### 測定の公理（量子ビットの測定操作を導入し、読み出せる情報を記述できるようにする）
４つ目に必須となる測定の実装は次のようにされております。

```idris: QuantumOp.idr にて実装
measure : QuantumOp t => (1 _ : LVect i Qubit) -> QStateT (t (i + n)) (t n) (Vect i Bool)
measureAll : QuantumOp t => (1 _ : LVect n Qubit) -> QStateT (t n) (t 0) (Vect n Bool)
measureQubit : QuantumOp t => (1 _ : Qubit) -> QStateT (t (S n)) (t n) Bool
```

ここまで見てきたように、量子計算の基本原理が全て実装されておりますので、これらの関数を使えば、量子プログラムを実装できるようになります。応用例はまた別の機会にと思いますが、こういった数学的な描像に沿った実装ができているのも idris2 というプログラミング言語の特徴を上手く使えているからだと思います。


## おわりに

量子プログラムの関数型プログラミング言語への実装において、Haskell での QIO や Quipper での実装がこれまでありましたが、どちらもメンテナンスが停滞しており、最近の処理系に適合しづらかったり、量子計算の進展に対するアップデートがされていない印象です。
本稿でご紹介した Qimaera のような最近の量子計算の状況と新しい処理系を取り入れたフレームワークは、ほかではあまり見られないためユニークな取り組みだと考えております。

いかがでしたでしょうか。**ご一読いただきまして有り難うございます。**


（●）（●） Happy Hacking!
/""　＿＿""＼ 
@kyamazは、オープンソース・コミュニティを通じて、皆さんと共に新しい技術に挑戦していきたいと考えております。[^0]どうぞ宜しくお願いいたします。

May your Christmas wishes come true!
May happy Quantum Computer world has come!

[^0]: @kyamaz は、オープンソース・コミュニティ『OpenQL』プロジェクト[^99]を通じて、皆さんと共に量子情報・量子コンピューティングの分野で挑戦しております。
[^99]: OpenQLプロジェクトは、量子コンピューターを扱うためのライブラリを開発するためのオープンソースプロジェクトです。量子情報、量子コンピューターに興味のある人たちが集うコミュニティを運営しております。詳しくは[connpassのサイト](https://openql.connpass.com/)をご覧ください。