Supercon

本選問題

月日

はじめに今年は東京工業大学のスーパーコンピュータ TSUBAME . を使って量子コンピュータのシミュレーションをしてもらう。量子コンピュータは素因数分解など従来のコンピュータでは効率的に解けないと信じられている問題を効率的に解くことができる。そのような理論的な事実は年代に分かっていたが、量子コンピュータを実際に作るためには技術的な困難が多く、実現するのは当分先のことだと考えられていた。しかし、この数年で劇的に量子コンピュータに関する技術が進展し、IBM や Google は去年から今年にかけて量子ビット程度のサイズの量子コンピュータを作ったと発表した。この本選問題では量子ビット以下の量子コンピュータの計算を TSUBAME . を使って、いかに高速にシミュレーションするかを競ってもらう。

量子ビット
私達が普段ビットの列を使って情報を表現しているように、量子コンピュータでは量子ビット (qubit) を使って情報を表現する。古典ビット 0 と 1 に対応する量子ビットは |0⟩ と |1⟩ である。量子ビットは直接「見る」ことはできず、量子ビットを「測定」することで初めて情報が得られる。|0⟩ を測定すると 0 が |1⟩ を測定すると 1 が確率[ ][ ] で得られる。しかし量子ビッ01というように 次元, |1⟩ =トはこの つだけではない。基本的な量子ビットを |0⟩ =10ベクトルと同一視することにしよう。一般の量子ビットは次のように表せる。
[ ]α.
|ψ⟩ = α |0⟩ + β |1⟩ =β
ここで α と β は α2 + β 2 = 1 を満たす実数である 。この量子状態 |ψ⟩ を「測定」すると測定結果 0 と 1 がそれぞれ確率 α2 と β 2 で得られる。
「なあんだ、量子ビットというのは確率的なビットのことか」と思うかもしれないが、その理解は正しくないことを付録 Aで説明する。
次に 量子ビットとして基本的なものは次の つである。
    00010010
|11⟩ = |10⟩ = |01⟩ = |00⟩ = 
0 .
1 ,
0 ,
0 ,
1000
本当は実数だけじゃなく複素数も許されているのだが、簡単のため実数としておく。

そして一般の量子ビットは次のように表せる。
 α
β 

|ψ⟩ = α |00⟩ + β |01⟩ + γ |10⟩ + δ |11⟩ = 
γ  .
δ

ここで、係数 α, β, γ, δ は α2 + β 2 + γ 2 + δ 2 = 1 を満たす実数である。この量子状態 |ψ⟩ を「測定」すると測定結果 00, 01, 10, 11 がそれぞれ確率 α2 , β 2 , γ 2 , δ 2 で得られる。 量子ビット以上も同様である。n 量子ビットは 2n 次元ベクトルで表される。この 2n 次元ベクトルの要素を上から順に 0 から 2n − 1 とインデックスをつけると都合がよい。ビット列b0 b1 · · · bn−1 に∑n−1 iついて、n 量子ビット状態 |bn−1 bn−2 · · · b0 ⟩ はインデックスが i=0 2 bi の成分が でそれ以外の成分が のベクトルと同一視できる。例えば、 量子ビットの状態 |110⟩ は 23 = 8 次元ベクトルで 0000
0 001 
0 010 
0 011
|110⟩ = 0 100 
0 101 
1 1101110というようにインデックスの二進数表現が 110 の成分がと見なせる。

でそれ以外の成分がのベクトル

量子回路
古典計算の計算モデルの一つに古典回路がある。古典回路はビット列を入力にとり、NOT(否定)、AND(論理積)、OR(論理和) という 種類のゲートを適用することで出力を計算する。任意の二元関数はこれら 種類のゲートの組み合わせで書ける。量子計算の一番標準的な計算モデルである量子回路はこの古典回路を量子ビットと量子ゲートに置き換えたものである。
今回考える量子回路は X (パウリ X 変換), Z (パウリ Z 変換), H (アダマール変換)、CX (コントロール X 変換)、CZ (コントロール Z 変換)、CCX (トフォリ変換) という 種類の量子ゲートからなる。この 種類の量子ゲートを組み合わせれば任意の「量子状態の変換」が任意の精度で近似できることが知られている 。これらの量子ゲートを説明する。まず始めにこれらの量子ゲートは「線形変換」である。 量子ビットに対する量子ゲート A の場合、|0⟩ と|1⟩ の変換先を A |0⟩ と A |1⟩ と書くことにすると、任意の 量子ビット |ψ⟩ = α |0⟩ + β |1⟩ は
A |ψ⟩ = α(A |0⟩) + β(A |1⟩) に変換される。なので 量子ビットゲートの場合は |0⟩ と |1⟩ の変換先を決めれば、一般の量子状態の変換先は自動的に定まる。以下、|0⟩ と |1⟩ が各量子ゲートによって何に変換されるかを定義していく。
• パウリ X 変換
パウリ X 変換は |0⟩ を |1⟩ に |1⟩ を |0⟩ に変換する量子ゲートである。古典ゲートの NOTに対応するものである。回路図による表現は次のようになる。
|x⟩X|x⟩

ここで、x は 1 − x である。
今回複素数を導入しないので、「限定された量子状態の上の変換」と言った方が正しい。

• パウリ Z 変換
パウリ Z 変換は |0⟩ を |0⟩ に |1⟩ を − |1⟩ に変換する量子ゲートである。回路図による表
現は次のようになる。
|x⟩(−1)x |x⟩Z
• アダマール変換
アダマール変換は |0⟩ を √12 (|0⟩ + |1⟩) に |1⟩ を √12 (|0⟩ − |1⟩) に変換する量子ゲートである。回路図による表現は次のようになる。
|x⟩√1 (|0⟩ + (−1)x |1⟩)2H

例えば、アダマール変換してからパウリ X 変換してアダマール変換する操作は()111|0⟩ + |1⟩ |0⟩ − |1⟩√HXH |0⟩ = HX √ (|0⟩ + |1⟩) = H √ (|0⟩ + |1⟩) = √+ √= |0⟩22222()1
1|0⟩ − |1⟩ |0⟩ + |1⟩1√− √= − |1⟩
HXH |1⟩ = HX √ (|0⟩ − |1⟩) = H √ (|1⟩ − |0⟩) = √22222を満たす。よって HXH = Z という量子ゲートに関する等式が得られる。
一般に n 量子ビットの k 番目の量子ビットに上記の 量子ビット向けの量子ゲートを適用した場合は、「対応する量子ビットだけが変換される」。量子ゲート U を k 番目の量子ビットに適用する操作を U (k) と書くことにすると、X (k) |bn−1 · · · b0 ⟩ = |bn−1 · · · bk+1 bk bk−1 · · · b0 ⟩Z (k) |bn−1 · · · b0 ⟩ = (−1)bk |bn−1 · · · b0 ⟩)1 (H (k) |bn−1 · · · b0 ⟩ = √ |bn−1 · · · bk+1 0 bk−1 · · · b0 ⟩ + (−1)bk |bn−1 · · · bk+1 1 bk−1 · · · b0 ⟩2が成り立つ。
次に複数量子ビットに対する量子ゲートを定義する。 量子ビットの場合と同様に、 量子ビットゲートは |00⟩ から |11⟩ までの変換先を定義すればよい ( 量子ビットゲートは |000⟩から |111⟩ までの変換先を定義すればよい)。以下では、x, y ∈ {0, 1} について、|yx⟩ の変換先を定義していく ( 量子ビットゲートについては x, y, z ∈ {0, 1} について、|zyx⟩ の変換先を定義していく)。
• コントロール X 変換|x⟩ を「コントロール量子ビット」、|y⟩ を「ターゲット量子ビット」とするコントロー
ル X 変換は x が のときは何もせず、 のときは y を反転させる量子ゲートである。
量子ビット |yx⟩ は次のルールで変換される。
|00⟩ 7−→ |00⟩|01⟩ 7−→ |11⟩|10⟩ 7−→ |10⟩|11⟩ 7−→ |01⟩
回路図による表現は次のようになる。
|x⟩|y⟩•|x⟩|y ⊕ x⟩

ここで ⊕ は排他的論理和 (x ⊕ y = 0 ⇐⇒ x = y で定義される {0, 1} 上の二項演算) である。

• コントロール Z 変換
コントロール Z 変換は x と y がともに の時に - を掛ける量子ゲートである。x もし
くは y が の時は何もしない。 量子ビット |yx⟩ は次のルールで変換される。
|00⟩ 7−→ |00⟩|01⟩ 7−→ |01⟩|10⟩ 7−→ |10⟩|11⟩ 7−→ − |11⟩
回路図による表現は次のようになる。
|x⟩

•

|x⟩

|y⟩

•

(−1)xy |y⟩

コントロール Z 変換は x と y について対称であり、どちらがコントロール量子ビットでどちらがターゲット量子ビットであるという区別はない。
• トフォリ変換|x⟩ と |y⟩ を「コントロール量子ビット」、|z⟩ を「ターゲット量子ビット」とするトフォリ変換は x と y がともに の時に z を反転させる量子ゲートである。x もしくは y がの時は何もしない。 量子ビット |zyx⟩ は次のルールで変換される。
|000⟩ 7−→ |000⟩|001⟩ 7−→ |001⟩|010⟩ 7−→ |010⟩|011⟩ 7−→ |111⟩|100⟩ 7−→ |100⟩|101⟩ 7−→ |101⟩|110⟩ 7−→ |110⟩|111⟩ 7−→ |011⟩
回路図による表現は次のようになる。
|x⟩•

|x⟩

|y⟩

•

|y⟩

|z⟩

|z ⊕ (x ∧ y)⟩

ここで ∧ は論理積 (x ∧ y = 1 ⇐⇒ x = y = 1 で定義される {0, 1} 上の二項演算) である。
量子ビットに対する量子ゲートと同様に、n 量子ビットの一部に複数量子ビットのゲートを適用した場合は「それらの量子ビットだけが変換される」。例えば、n − 1 ≥ i > j > k ≥ 0について、i 番目と j 番目の量子ビットをコントロール量子ビットとして k 番目の量子ビットをターゲット量子ビットとするトフォリ変換は次のように作用する。
|bn−1 · · · bi · · · bj · · · bk · · · b0 ⟩ 7−→ |bn−1 · · · bi · · · bj · · · (bk ⊕ (bi ∧ bj )) · · · b0 ⟩

本選問題: 量子回路のシミュレーション.

概要

問題の入力として量子回路を与える。|00 · · · 0⟩ をその量子回路への入力とした場合の量子回路の出力を測定した時に、得られる確率が一番高い測定結果とその確率を問題の解とする。

.

問題の入力

入力は
N K
G1 O 1G2 O 2..
.
GK OKで与えられる。各変数の取り得る値は25 ≤ N ≤ 30
500 ≤ K ≤ 2000
Gi ∈ { X, Z, H, CX, CZ, CCX },∀i ∈ {1, 2, . . . , K},
ただし H の総数は以下

if Gi ∈ { X, Z, H }a,0 ≤ a, b, c ≤ N − 1,Oi = a b,∀i ∈ {1, 2, . . . , K}
if Gi ∈ { CX, CZ } ,a, b, c は相異なる
a b c, if Gi = CCXである。ここで N は量子ビットの数、K は量子ゲートの数である。その後の K 行に量子ゲー
トの内容が示されている。各 Gi は量子ゲートの種類を表しており、X, Z, H, CX, CZ, CCX のいずれかである。ここで、X, Z, H, CX, CZ, CCX はそれぞれ、パウリ X 変換、パウリ Z 変換、アダマール変換、コントロール X 変換、コントロール Z 変換、トフォリ変換を表す。各 Oi は量子ゲートが適用される量子ビットのインデックス ( 以上 N − 1 以下) の列である。複数の量子ビットにかかる量子ゲートについては、最後のインデックスがターゲット量子ビットである。例えばCX 4 3は 番目の量子ビットがコントロール量子ビットで 番目の量子ビットがターゲット量子ビットである。同様に
CCX 0 19 2
は 番目,番目の量子ビットがコントロール量子ビットで 番目の量子ビットがターゲット量子ビットである。これらの量子ゲートを G1 から GK まで順番に適用する量子回路を Cとおく。

.

問題の解

|00 · · · 0⟩ を量子回路 C の入力としたときに、量子回路 C から出力される量子状態を測定した際に得られる確率が一番高い測定結果とその確率を問題の解とする。ただし、測定結果∑N −1 i2 bi の十進数表現を出力する。確率は相対誤差 10−5 未満をbN −1 bN −2 · · · b0 について、 i=0正解とする。測定確率が等しいものが複数ある場合はどれを出力しても構わない。出力のフォーマットは

測定確率最大の測定結果の一つの十進数表現
その測定確率とする。測定確率の出力は printf("%e\n", max_probability); のようにすればよい。

.

入出力例

簡単のため、N や K が小さい場合の入出力例を示す。実際の評価では 25 ≤ N ≤ 30,500 ≤ K ≤ 2000 の範囲の場合だけを考える。
. .

入出力例
2 4X 1Z 0CX 1 0
X 1

回路図は次のようになる。
|0⟩Z|0⟩X•

X

量子ゲートを順に適用しておくと量子ビットは順に|00⟩ 7−→ |10⟩ 7−→ |10⟩ 7−→ |11⟩ 7−→ |01⟩と変換される。そのため量子回路の出力は |01⟩ となる。これを測定すると、01 が確率られる。そのため、問題の出力は11.0となる。
. .

入出力例
2 3H 0
CX 0 1X 1

回路図は次のようになる。
|0⟩|0⟩H•Xで得量子ゲートを順に適用しておくと量子ビットは順に111|00⟩ 7−→ √ (|00⟩ + |01⟩) 7−→ √ (|00⟩ + |11⟩) 7−→ √ (|10⟩ + |01⟩)
222と変換される。そのため量子回路の出力は √12 (|10⟩ + |01⟩) となる。これを測定すると、10 と01 がそれぞれ確率 / で得られる。そのため、問題の出力は10.5もしくは20.5となる。
. .

入出力例
3 11X 2
H 0H 1
H 2
CCX 0 1 2H 0
H 1
CCX 0 1 2
H 0
H 1
H 2

回路図は次のようになる。
|0⟩H•

H

•

H|0⟩H

•H

•

H|0⟩XHH

量子ゲートを順に適用しておくと量子ビットは順に11|000⟩ 7−→ |100⟩ 7−→ √ (|100⟩ + |101⟩) 7−→ (|100⟩ + |110⟩ + |101⟩ + |111⟩)
2217−→ √ (|000⟩ − |100⟩ + |010⟩ − |110⟩ + |001⟩ − |101⟩ + |011⟩ − |111⟩)
2 217−→ √ (|000⟩ − |100⟩ + |010⟩ − |110⟩ + |001⟩ − |101⟩ + |111⟩ − |011⟩)
2 217−→ (|000⟩ − |100⟩ + |011⟩ − |111⟩)
217−→ √ (|000⟩ + |010⟩ − |100⟩ − |110⟩ + |001⟩ − |011⟩ − |101⟩ + |111⟩)
2 217−→ √ (|000⟩ + |010⟩ − |100⟩ − |110⟩ + |001⟩ − |111⟩ − |101⟩ + |011⟩)
2 217−→ (|000⟩ + |010⟩ − |100⟩ − |110⟩)217−→ √ (|000⟩ − |100⟩)27−→ |100⟩と変換される。そのため量子回路の出力は |100⟩ となる。これを測定すると、100 が確率得られる。そのため、問題の出力はで41.0となる。

.

評価方法

プログラムのコンパイルは
nvcc program.cu -O2 -arch=sm_60で行う。速度を評価するための入力は配布の gen.cpp を用いて生成する。25 ≤ N ≤ 30,
500 ≤ K ≤ 2000 の範囲で入力を生成し、計算結果と実行時間を評価する。速度差が判別できるくらい十分多くの入力を用いて評価する。順位付けは• 計算結果が正しいものが多い方が上位• 計算結果が正しいものが同数の場合は実行時間の総和が小さい方が上位というルールに従って決める。上位は全問正解するものと期待している。結局のところ
N = 30 の場合が一番時間がかかるので、そこで一番差がつくと考えている。

A

ベルの不等式 (本選問題と直接は関係がない)

そもそも量子力学とは何なのか？古典力学とどう違うのか？最短距離で説明する。次のゲー
ムを考えよう。

CHSH ゲーム
遠く離れ通信ができないアリスとボブが次のようなゲームをする。アリスは x ∈ {0, 1} を受け取り、ボブは y ∈ {0, 1} を受け取る。アリスとボブはそれぞれ a ∈ {0, 1} と b ∈ {0, 1}を出力し、それらが a ⊕ b = x ∧ y を満たすとき、アリスとボブの勝ちとする。



さて、入力 x と y が一様な確率で選ばれるとしたときに、CHSH ゲームの最大勝率はいくつになるだろう？x から決まる a の値を ax 、y から決まる b の値を by と書くことにする。各 x,y について勝利条件を書き下すと次のようになる。
a0 ⊕ b0 = 0 ∧ 0 = 0,a0 ⊕ b1 = 0 ∧ 1 = 0,a1 ⊕ b0 = 1 ∧ 0 = 0,a1 ⊕ b1 = 1 ∧ 1 = 1.
この つの式のうち つが 1/4 の確率で選ばれ、それが満たされていれば勝ちということになる。この つの式を足すと 0 = 1 となるので、全ての式を満たすように (a0 , a1 , b0 , b1 ) を決めることは不可能である。一方で、a0 = a1 = b0 = b1 = 0 とおくと、 つの式は満たされる。
よって、最大の勝率は 3/4 = 0.75 となる。これは、アリスとボブがランダムビットを共有し√ていても変わらない。しかし、量子状態を共有していると最大の勝率は (2 + 2)/4 ≈ 0.854になる！この現象のことを「ベルの不等式の破れ (もしくは CHSH 不等式の破れ)」という。
実際にゲームの中で現れる値は ax と by だが、現れない値 ax と by も存在している、と考えるのが自然である。しかし、(a0 , a1 , b0 , b1 ) の同時確率分布が存在していると、CHSH ゲー
ムの最大勝率は 3/4 を超えない。よって、ベルの不等式の破れは a0 , a1 , b0 , b1 という つの値が同時に存在していないことを示している。観測するしないに関わらず、確率的にせよ観測値が存在しているという理解では量子力学を説明できないのである。このように、量子力学においては観測したときに観測値が定まると考えるほかない。
√
具体的に最大の勝率 (2 + 2)/4 を達成するためには、アリスとボブは次の 量子ビット状態を共有している必要がある。
1√ (|00⟩ + |11⟩)2
一つ目がアリスの持っている量子ビットで二つ目がボブが持っている量子ビットと考える。
アリスとボブがそれぞれx と y の値に応じて、量子ビットを操作してから測定することで勝√率 (2 + 2)/4 が達成できる。