Let's Simulate a Quantum Computer with Pretty Scala

ScalaMatsuri 2018
http://2018.scalamatsuri.org/index_en.html

Transcript

1. Let's Simulate a Quantum Computer with Pretty Scala #ScalaMatsuri 2018 Torigoe Takatomo https://github.com/piyo7/qlione 量子コンピュータをScalaでかわいくシミュレーションしてみよう
 　鳥越貴智 (piyo7)

2. This Session’s Cake (Goal) Quantum Fourier Transform Circuit 　本セッションの目標は、量子フーリエ変換の回路を
 　Scalaでシミュレーションすること。

3. Don’t Let the Cake Lie 　回路を縦にしてみましょう。
 
 ↷
4. The Cake is Baked 　そして回路をコーディングしたものがこちらになります。
 
 (|("000").> + |("100").>).bits[_3] |> (H x I x I) |> (Rz(Pi/2) . C x I) |> (Rz(Pi/4) x I) . C |> (I x H x I) |> (I x Rz(Pi/2) . C) |> (I x I x H)
5. The Cake is Baked 　そして回路をコーディングしたものがこちらになります。
 　ね、簡単でしょ？
 (|("000").> + |("100").>).bits[_3] |> (H x I x I) |> (Rz(Pi/2) . C x I) |> (Rz(Pi/4) x I) . C |> (I x H x I) |> (I x Rz(Pi/2) . C) |> (I x I x H)
7. The End Is a Lie CyberAgent AdTech Studio Torigoe Takatomo https://qiita.com/piyo7 ScalaMatsuri & me • 2014: wireless simulation engineer (C++) • 2016: looking for a new job... • 2017: adtech data & ML engineer (Scala) 　鳥越貴智です。ScalaMatsuri に感化されて転職しました。
 　サイバーエージェントは今年も＼将軍スポンサー／

8. Quantum Computers Are Coming https://www.research.ibm.com/ibm-q/ https://www.microsoft.com/en-us/quantum/what-is-quantum-computing
9. Hello, Quantum Bit (Qubit) Classical 2 bits Quantum 2 bits A n-qubit state is “superposition” of 2^n bases. 　古典ビットと量子ビットの違いを見てみましょう。
 　n 量子ビットの状態は、 2^n 個の基底の「重ね合わせ」。

10. Hello, Quantum Bit (Qubit) A n-qubit is denoted by a complex column vector. Its size is 2^n. (ex. 2^50=1,125,899,906,842,624) 　n 量子ビットの状態は、 2^n 行の複素ベクトルで表せます。
 　50量子ビットなら、1,125,899,906,842,624。

11. Hello, Quantum Gate = A n-qubit gate is denoted by a complex matrix. Its column size & row size are 2^n. 　n 量子ゲートは、 2^n 行 2^n 列の複素行列で表せます。
 

12. Hello, Quantum Calculation Enter in The core of quantum calculation is matrix operation. 　量子計算の肝は、複素行列の演算です。
 

13. OK. We can calculate qubits. これで量子計算できるようになりました。
 すべて世は事も無し。

14. Handwriting Hell 　2^n 行 2^n 列の複素行列、手計算つらたん。
 　見るからに地獄　｡･ﾟ･（>﹏<）･ﾟ･｡

15. Complex Number case class Complex(re: Double, im: Double) { def +(that: Complex) = Complex(re + that.re, im + that.im) ... object Complex { implicit def toComplex(d: Double) = Complex(d, 0) implicit class ToComplex(val d: Double) extends AnyVal { def i = Complex(0, d) } ... 　まずは、複素数を実装します。
 

16. Complex Number DSL 　ケースクラス、暗黙のメソッド、暗黙の値クラス、を使うと
 　数式っぽく複素数を書けます。
 Numerical expression can be written with... • Case class • Implicit method • Implicit value class > 0.1 + 2.3.i // toComplex(0.1) + ToComplex(2.3).i // Complex(0.1, 0.0) + Complex(0.0, 2.3) res = Complex(0.1, 2.3)
17. Complex Matrix Multiplication 　はい、複素行列の掛け算です。
 　map と zip と reduce でサクッと実装できます。
 val in = Vector[Complex]( (1 + 1.i) / 4, (1 - 1.i) / 4, 1.0 / 2, 1.0 / math.sqrt(2)) val gate = Vector[Vector[Complex]]( Vector(1 , 0 , 0 , 0 ), Vector(0 , 1 , 0 , 0 ), Vector(0 , 0 , 0 , -1.i), Vector(0 , 0 , 1.i , 0 )) val out = gate.map(row => row.zip(in).map(pair => pair._1 * pair._2).reduce(_ + _))
18. OK.. We can write Scala code to calculate qubits? これで量子計算をScalaでプログラミングできますね。
 OK Google?
 the cake is a lie.
19. Out of Memory Hell 　16 量子ゲートを作ろうとした結果、メモリが溢れました。
 　どう考えても地獄　｡･ﾟ･（>﹏<）･ﾟ･｡
 scala> Vector.fill(65536)(Vector.fill(65536)(0 + 0.i)) java.lang.OutOfMemoryError: GC overhead limit exceeded at com.github.piyo7.qlione.Complex.$plus(Complex.scala:8) at .$anonfun$res31$2(<console>:15) at $$Lambda$2011/487012190.apply(Unknown Source) at scala.collection.generic.GenTraversableFactory.fill(GenTrave at .$anonfun$res31$1(<console>:15) at $$Lambda$2010/565550535.apply(Unknown Source) at scala.collection.generic.GenTraversableFactory.fill(GenTrave ... 25 elided
20. Sparse Matrix = Usually, most of elements in quantum gates are 0. 　量子ゲートの複素行列は、たいていの場合、
 　ほとんどの要素がゼロ、すなわち疎行列です。

21. Map Is Efficient for Sparse Matrix 　疎行列のデータ構造には、 Map が適しています。
 　12 量子単位ゲートのメモリ使用量を確認してみましょう。
 import com.twitter.common.objectsize.ObjectSizeCalculator._ val identity12a: Vector[Vector[Complex]] = (0 until 4096).map(a => (0 until 4096).map(b => if (a == b) 1 + 0.i else 0 + 0.i).toVector).toVector getObjectSize(identity12a) // == 615,566,088 bytes val identity12b: Map[(Int, Int), Complex] = (0 until 4096).map(a => (a, a) -> (1 + 0.i)).toMap getObjectSize(identity12b) // == 562,056 bytes
22. Bra–Ket Notation = |a> <b| denotes a sparse matrix whose a-th row and b-th column element is an only 1. |a> is a column vector called “ket”. <b| is a row vector called “bra”. 　量子計算では、しばしばブラケット記法を使います。
 　|a> <b| は、 a 行 b 列の要素のみが 1 の疎行列です。

23. Bra-Ket Case Classes 　ケースクラスを使うと、
 　ブラケット記法っぽく量子ゲートを書けます。
 case class QuMatrix(map: Map[(Int, Int), Complex]) { … } case class |(i: Int) extends AnyVal { def > = QuMatrix(Map((i, 0) -> 1)) // bra notation } case class <(i: Int) extends AnyVal { def | = QuMatrix(Map((0, i) -> 1)) // ket notation } val Y = -1.i * |(0).> * <(1).| + 1.i * |(1).> * <(0).|
24. OK... We can write Scala code to calculate qubits on classical memory? これで量子計算の古典メモリ使用量を抑えられますね。
 OK GO?
 the cake is a lie. the cake is a lie.
25. Unmatched Size Hell 　うっかり量子ビット数を間違えてしまい、無が生まれました。
 　控えめに言って地獄　｡･ﾟ･（>﹏<）･ﾟ･｡
 // 3-qubit state val in = QuMatrix (Map((7, 0) -> 1)) // 2-qubit gate val CY = QuMatrix (Map((0, 0) -> 1, (1, 1) -> 1, (2, 3) -> -1.i, (3, 2) -> 1.i)) // A 2-qubit gate acts on a 3-qubit state. val out = CY * in pritnln(out) // == QuMatrix(Map()) null state!
26. Type-Level Natural Number 　型レベル自然数です。 0 から再帰的に構築します。
 　足し算をすることもできます。
 sealed trait _Nat class _0 extends _Nat class _suc[A <: _Nat] extends _Nat // successor in Peano axioms // imitate shapeless library trait _plus[A <: _Nat, B <: _Nat] { type Out <: _Nat } object _Nat { type _1 = _suc[_0] type _2 = _suc[_1] // _suc[_suc[0]] type _3 = _suc[_2] // _suc[_suc[_suc[0]]] ...
27. Type-Level Sized Matrix 　行数と列数を型レベル自然数で表した行列クラスです。
 　量子ビットやゲートのため、 2 のベキの指数を保持します。
 // 2^A x 2^B matrix // N quantum bits: A = N, B = _0 // N quantum gate: A = N, B = N case class QuMatrix[A <: _Nat, B <: _Nat] (map: Map[(Int, Int), Complex]) { // (2^A x 2^B matrix) + (2^A x 2^B matrix) = 2^A x 2^B matrix def +(that: QuMatrix[A, B]): QuMatrix[A, B] = … // (2^A x 2^B matrix) * (2^B x 2^C matrix) = 2^A x 2^C matrix def *[C <: _Nat](that: QuMatrix[B, C]): QuMatrix[A, C] = …
28. Type-Level Size Check 　量子ビット数を型レベルで持つことで、
 　整合していないとコンパイルできないように。
 val in = QuMatrix[_3, _0] (Map((7, 0) -> 1)) val CY = QuMatrix[_2, _2] (Map((0, 0) -> 1, (1, 1) -> 1, (2, 3) -> -1.i, (3, 2) -> 1.i)) // This expression cannot be compiled! // val out = CY * in // Type mismatch, // expected: QuMatrix[_2, _0], actual: QuMatrix[_3, _0]
29. OK.... We can write Scala code to calculate type-level sized qubits on classical memory? これで量子ビット数を型レベルで保証できますね。
 OK 次に進もうぜ？
 the cake is a lie. the cake is a lie. the cake is a lie.
30. RedUNdaNt TyPe pARamETer HElL 　そこかしこで型パラメータを書かないといけないように。
 　フツーに地獄　｡･ﾟ･（>﹏<）･ﾟ･｡
 val Y: QuMatrix = -1.i * |(1).> * <(0).| + 1.i * |(0).> * <(1).| val b: QuMatrix = sqrt(0.5) * |(0).> + sqrt(0.5) * |(1).> val Y: QuMatrix[_1, _1] = - 1.i * |(1).>[_1, _0] * <(0).|[_0, _1] + 1.i * |(0).>[_1, _0] * <(1).|[_0, _1] val b: QuMatrix[_1, _0] = sqrt(0.5) * |(0).>[_1, _0] + sqrt(0.5) * |(1).>[_1, _0] ⇩
31. in 2-size context in 4-size context in ?-size context Addition & Multiplication allow unsized matrix. Unsized Sparse Matrix 　実のところ、疎行列はサイズが決まっていなくても、
 　足し算や掛け算を行えてしまうのです。

32. = = = Kronecker Product Needs Size 　ただし、量子ビットや量子回路を結合するために使う
 　クロネッカー積は、サイズが決まってないといけません。
 // (2^A x 2^B) (2^C x 2^D) = (2^(A + C) x 2^(B + D)) def x[C <: _Nat, D <: _Nat](that: QuMatrix[C, D]) (implicit pAC: _plus[A, C], pBD: _plus[B, D]) : QuMatrix[pAC.Out, pBD.Out] = …
33. Type-Level Optionally Sized Matrix 　型レベルのオプション自然数を実装して、
 　本当に必要なところのみサイズを宣言するようにしました。
 sealed trait _OptNat class _none extends _OptNat sealed trait _Nat extends _OptNat case class QuMatrix[A <: _OptNat, B <: _OptNat] (map: Map[(Int, Int), Complex]) { … } // Of course types of following values can be inferred. val Y: QuMatrix[_none, _none] = -1.i * |(1).> * <(0).| + 1.i * |(0).> * <(1).| val H: QuMatrix[_none, _none] = … val YH: QuMatrix[_2, _2] = Y.gate[_1] x H.gate[_1]
34. OK..... We can write Scala code without redundant type parameters to calculate type-level sized qubits on classical memory? これで冗長な型パラメータを書かずにすみますね。
 OK余裕？
 the cake is a lie. the cake is a lie. the cake is a lie. the cake is a lie.
35. The direction of data flow is opposite. Dataflow Direction Hell 　回路は左から右にデータが流れますが、掛け算は逆です。
 　これが意外と地獄　｡･ﾟ･（>﹏<）･ﾟ･｡　
 val out = Z * (Y * (X * |(0).>))
36. Pipeline Operator 　パイプライン演算子によって、関数適用を左右反転します。
 
 case class QuMatrix[A <: _OptNat, B <: _OptNat] (map: Map[(Int, Int), Complex]) { def |>[C <: _OptNat](that: QuMatrix[C, A]): QuMatrix[C, B] = that * this // flip horizontal ... } val out = |(0).> |> X |> Y |> Z
37. OK....... We can write intuitively directed Scala code without redundant type parameters to calculate type-level sized qubits on classical memory? これで直感的にデータフローを書けますね。
 もうOKしてもいいよね？
 cake is a lie. the cake is a lie. the cake is a lie. the cake is a lie. the cake is
38. The Cake is NOT a Lie 　Scalaのテクニックを駆使することで、かわいく
 　量子フーリエ変換の回路をコーディングできました。
 (|("000").> + |("100").>).bits[_3] |> (H x I x I) |> (Rz(Pi/2) . C x I) |> (Rz(Pi/4) x I) . C |> (I x H x I) |> (I x Rz(Pi/2) . C) |> (I x I x H)
39. Stay Pretty to Survive from Hells We are still alive through… • Handwriting Hell • Out of Memory Hell • Unmatched Size Hell • RedUNdaNt TyPe pARamETer HElL • Dataflow Direction Hell 　かわいいは正義の敵：手書き、メモリ不足、サイズ不整合、
 　冗長な型パラメータ、反転したデータフロー

40. Play Qlione! https://github.com/piyo7/qlione