エアWriteup “DEFCON 2021 Quals: QOO or OOO”

はじめに

DEFCON 2021 Quals: QOO or OOOは量子コンピュータ（量子力学？）では有名なCHSHゲームを題材としたCTFの問題である。この問題のことを友人に教えてもらい^[1]、筆者自身もCHSHゲーム（またはBell不等式）をきちんと追ったことがなかったこともあり、この記事ではこの問題とCHSHゲームについて、物理の知識や量子コンピュータの知識をなるべく必要としない形で、行列計算に基づいて具体的に計算しながら説明したい。
この記事を読んで改善するべきところや、不明な点を見つけた場合は気軽にコメントなどで教えてほしい。

問題の起動

DEFCON 2021 Quals: QOO or OOOのページへ行き、書いてあるとおりにDockerを起動すればOKである。macOSの問題なのか、筆者の環境では下記のようにポートをバインドしたらうまくいった。

$ docker run -p 127.0.0.1:5000:5000/tcp -d --name qoo-or-ooo archiveooo/pub:qoo-or-ooo

あとは次のようにncコマンドで問題サーバーへ接続できる。

$ nc localhost 5000
Matplotlib created a temporary config/cache directory at /tmp/matplotlib-r284hmrs because the default path (/root/.config/matplotlib) is not a writable directory; it is highly recommended to set the MPLCONFIGDIR environment variable to a writable directory, in particular to speed up the import of Matplotlib and to better support multiprocessing.
zardus: Hey hacker! Shall we play a game against QOO?
        There are two competitors here and they each will bet on 0 or 1.
        Let's put our numbers there so that the sum of ours is same as the multiplication of theirs

“QOO or OOO”の説明

この問題は自分も含めた次のような4人の参加者がいる。

• Hacker（自分）
• Zardus
• HackerのCompetitor
  • 便宜上こちらをCompetitor Aとする
• ZardusのCompetitor
  • 同様にこちらをCompetitor Bとする

そして、この4人は次のようなプロトコルを実行する。

1. Competitor Aがベット（Bet）と呼ばれる1ビットの値をHackerへ公開する
   • このベットを$a \in \{0, 1\}$とする
   • このベット$a$をZardusは知ることができない
2. Hackerが1ビットの値$h \in \{0, 1\}$またはmagic qoinを選ぶ
   • このmagic qoinについては後で説明する
3. Competitor Bが同様にベット$b \in \{0, 1\}$を選びZardusへ公開する
   • ただしこの値$b$がどちらなのかHackerは知ることができない
4. ZardusはCompetitor Bの選んだベット$h$によって、後述する適応的な行動にしたがって値$z \in \{0, 1\}$を選択する
5. $h \oplus z = a \times b$^[2]であればHackerの勝利となり、そうでなければ敗北となる
6. この（1）〜（5）を30回行って、勝率が 85% を越えればフラグが獲得できる

magic qoinのところで量子性を利用するが、とりあえずこのゲームをHackerやZardusが適当に$0, 1$を入力したとして、どれくらい勝てるのか考えてみる。まずHackerとZardusの値をXORした結果$h \oplus z$は$0, 1$になる確率がちょうど$\frac{1}{2}$となっている。次にCompetitor A, Bの値をかけ算した結果である$a \times b$は、両方が$1$である場合に限って$1$でありそれ以外の場合は$0$であることから、$\frac{3}{4}$の確率で$0$であり$\frac{1}{4}$の確率で$1$となる。したがってHackerとZardusが勝利する確率は次のようになる。

$$\frac{1}{2} \times \frac{3}{4} + \frac{1}{2} \times \frac{1}{4} = \frac{1}{2}$$

ただし問題設定としてZardusはHackerの仲間である。ここで彼は手順（4）で「Competitor Bの選んだ値$b$に限らず常に$0$を出す」という戦略を取るとして、Hacker（自分）も常に$0$を出せば$h \oplus z = 0 \oplus 0 = 0$となり、$\frac{3}{4} = 75\%$の確率で勝利することができる。ここまでの説明だけではこの$75\%$という確率を越えることができないが、ここでmagic qoinを利用することで無理やり解決していこうというのがこの問題の想定解となる。

量子ビットと量子計算

この章では量子ビットとそれの計算について説明する。基本的な行列に関する演算や用語（内積、複素共役など）そして量子計算で利用するディラック記法については過去に書いたガチャの記事にまとめたので、これからの説明のうち行列の計算などで不明な点があればこちらも参考にしてほしい。

1量子ビット

量子ビットと行列

まず1量子ビットは次のような行列で表現される。

$$\def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \ket{0} \equiv \left(\begin{array}{c} 1 \\ 0 \end{array}\right),\;\; \ket{1} \equiv \left(\begin{array}{c} 0 \\ 1 \end{array}\right)$$

このままだと古典コンピュータ^[3]と同様に2通りしか表現できないので、ここに確率振幅という複素数$\alpha, \beta$をあたえて次のような1量子ビットを考える。

$$\ket{\psi} \equiv \alpha\ket{0} + \beta\ket{1}$$

この確率振幅は$\ket{0}, \ket{1}$が発生する確率の素となる概念である。1量子ビット$\ket{\psi}$を測定したとき$|\alpha|^2$の確率で$\ket{0}$が観測され、$|\beta|^2$の確率で$\ket{1}$が観測される。したがって確率の要請から次のようになる。

$$\begin{align} |\alpha|^2 + |\beta|^2 = 1 \tag{1} \end{align}$$

このように1量子ビットは古典コンピュータの1ビットとはことなり次のような性質を持つ。

• 2つの確率振幅と呼ばれる複素数により、$\ket{0}, \ket{1}$のどちらが観測されるか曖昧な状態を持つことができる

また重要な性質として、我々は確率振幅を直接知ることはできない。あくまで量子ビットの測定によって生じる観測結果に確率振幅が寄与するのであって、この複素数を具体的に取り出す操作はできないことに注意が必要である。

1量子ビット計算

たとえば古典コンピュータにあるNOT演算子は次のような行列$X$で表現される。

$$X \equiv \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right)$$

さきほどの$\ket{0}, \ket{1}$に$X$を適用すると次のようにNOT演算子となっていることがわかる。

$$\begin{align*} X\ket{0} &= \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right)\left(\begin{array}{c} 1 \\ 0 \end{array}\right) &= \left(\begin{array}{c} 0 \times 1 + 1 \times 0 = 0 \\ 1 \times 1 + 0 \times 0 = 1 \end{array}\right) &= \ket{1} \\ X\ket{1} &= \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right)\left(\begin{array}{c} 0 \\ 1 \end{array}\right) &= \left(\begin{array}{c} 0 \times 0 + 1 \times 1 = 1 \\ 1 \times 0 + 0 \times 1 = 0 \end{array}\right) &= \ket{0} \\ \end{align*}$$

$X$ゲートとは別のゲートとして次のアダマールゲート$H$を紹介する。

$$H \equiv \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right)$$

たとえばこれを$\ket{0}$に適用すると次のようになる。

$$H\ket{0} = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right) \left(\begin{array}{c} 1 \\ 0 \end{array}\right) = \frac{1}{\sqrt{2}}\left(\begin{array}{c} 1 \\ 1 \end{array}\right) =\frac{1}{\sqrt{2}}\left(\ket{0} + \ket{1}\right)$$

量子ビットの測定

1量子ビットの測定にはまず基底^[4]と呼ばれる2つの行列を選ぶ必要がある。たとえば$\{\ket{0}, \ket{1}\}$を利用して$\ket{1}$を測定する場合を考える。このとき、あえて確率振幅を表記するとしたら$\ket{1} = 0\ket{0} + 1\ket{1}$となるため、100%の確率で$\ket{1}$が観測されることになる。それでは揺らぎのある次のような量子ビット$\ket{+}$の測定を考えてみる。

$$\ket{+} \equiv \frac{1}{\sqrt{2}}\left(\ket{0} + \ket{1}\right)$$

このとき$\ket{0}$が観測される確率は$\left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$であり、$\ket{1}$も同様である。シュレディンガーの猫などとして聞いたことがあるかもしれないが、測定後には$\ket{+}$のような量子ビットは揺らいだ状態が失なわれ、なにかしらの基底へと収束してしまう。このような現象も実は演算子$X$のような行列として表現できる。測定には次のような基底の外積である$\ket{0}\bra{0}, \ket{1}\bra{1}$という行列を利用する。

$$P_0 \equiv \ket{0}\bra{0} = \left(\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}\right),\;\; P_1 \equiv \ket{1}\bra{1} = \left(\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}\right)$$

測定後の量子状態は観測結果によって次のように分岐する。

1. $\ket{+}$を基底$\{\ket{0}, \ket{1}\}$で測定した結果が$\ket{0}$となった場合^[5]

   $$\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} \ket{0}\bra{0}\ket{+} = \ket{0}\braket{0}{+} = \ket{0}\left(\frac{1}{\sqrt{2}}\braket{0}{0} + \frac{1}{\sqrt{2}}\braket{0}{0}\right) = \frac{1}{\sqrt{2}}\ket{0}$$

2. 同様に測定した結果が$\ket{1}$となった場合

   $$\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} \ket{1}\bra{1}\ket{+} = \ket{1}\braket{1}{+} = \ket{1}\left(\frac{1}{\sqrt{2}}\braket{1}{0} + \frac{1}{\sqrt{2}}\braket{1}{1}\right) = \frac{1}{\sqrt{2}}\ket{1}$$

このままでは確率振幅の満すべき式$(1)$を満さない。そのためこれらは$\sqrt{\bra{+}P_i\ket{+}}\; \left(i := \{1, 2\}\right)$で割って次のようにする整える（正規化する）必要がある。

$$\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} \begin{align*} \sqrt{\bra{+}P_0\ket{+}} &= \sqrt{\braket{+}{0}\braket{0}{+}} = \sqrt{\frac{1}{2}} = \frac{1}{\sqrt{2}} \\ \sqrt{\bra{+}P_1\ket{+}} &= \sqrt{\braket{+}{1}\braket{1}{+}} = \sqrt{\frac{1}{2}} = \frac{1}{\sqrt{2}} \end{align*}$$

このようにどちらも$\frac{1}{\sqrt{2}}$で割ることで確率振幅が$1$となって式$(1)$を満すようになる。
さて、ここまで基底として$\{\ket{0}, \ket{1}\}$を利用してきたが、基底は別にこれでなくてもよい。次に基底を変更して$\{\ket{+}, \ket{-}\}$を利用して測定することを考える。ただし$\ket{-}$は次のように定義されるものとする。

$$\ket{-} \equiv \frac{1}{\sqrt{2}}\left(\ket{0} - \ket{1}\right)$$

さきほどの$\ket{+}$をこの基底$\{\ket{0}, \ket{1}\}$で測定した場合、$\ket{+} = 1\ket{+} + 0\ket{-}$であるから100%の確率で$\ket{+}$が観測されることになる。次に$\ket{0}$を測定する場合を考える。

$$\ket{0} = \frac{\sqrt{2}}{{2}}\left(\ket{+} + \ket{-}\right)$$

$\ket{0}$はこのように表現できるため、$\left|\frac{\sqrt{2}}{{2}}\right|^2 = \frac{1}{2}$より$\ket{+}, \ket{-}$がそれぞれ$\frac{1}{2}$の確率で観測されるということになる。このように同じ量子ビットであっても測定する際の基底によって観測される結果が異なることがある。

2量子ビット

ここまでの議論は全て1量子ビットについて議論してきたが、問題で必要となるためさらにここで1量子ビット追加して2量子ビットの議論をしていく。

2量子ビットの表現

2量子ビットはテンソル積$\otimes$を利用する。具体的な行列表現として2量子ビット$\ket{0} \otimes \ket{1}$は次のようになる。

$$\ket{0} \otimes \ket{1} = \left(\begin{array}{c} 1 \left(\begin{array}{c} 0 \\ 1 \end{array}\right) \\ 0 \left(\begin{array}{c} 0 \\ 1 \end{array}\right) \end{array}\right) = \left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right)$$

なお、表記を短縮するため今後は$\ket{0} \otimes \ket{1}$を$\ket{01}$と書くことにする。

$CX$ゲート

実は複数量子ビットを組みあわせた場合、テンソル積では表現できない状態となることがある。まずは次のような行列で表現される$CX$ゲート（コントロールNOTゲート）を考える。

$$\begin{align*} CX &\equiv \ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes X \end{align*}$$

ただし$I$は次のような単位行列である。

$$I \equiv \left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right)$$

$CX$ゲートは$2 \times 2$行列のテンソル積の足し算であることから、$4 \times 4$行列となり、これは2量子ビットに一度に作用する。コントロールNOT（CNOT）ゲートと言われるように、$CX$ゲートは次のように1量子ビット目の状態によって適応的に2量子ビット目に作用する。

• 1量子ビット目が$\ket{0}$のとき、2量子ビット目には何も作用させない
• 1量子ビット目が$\ket{1}$のとき、2量子ビット目に$X$ゲートを作用させる

たとえば$\ket{10}$に$CX$ゲートを適用してみると次のようになる。ただし、計算を分かりやすくするために$\ket{\alpha} \otimes \ket{\beta}$を$\ket{\alpha}_1\ket{\beta}_2$と、左から^[6]1量子ビット、2量子ビットがそれぞれ分かりやすくした表記を利用する。

$$\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} \begin{align*} CX\ket{1}_1\ket{0}_2 &= \ket{0}\braket{0}{1}_1 I\ket{0}_2 + \ket{1}\braket{1}{1}_1 X\ket{0}_2 \\ &= \ket{0}\braket{0}{1}_1 \ket{0}_2 + \ket{1}\braket{1}{1}_1 \ket{1}_2 \\ &= 0\ket{0}_1\ket{0}_2 + 1\ket{1}_1\ket{1}_2 \\ &= \ket{1}_1\ket{1}_2 \end{align*}$$

このように2量子ビット目に$X$ゲート（NOTゲート）が作用して判定しているのが分かる。しかし量子ビットには$\ket{0}, \ket{1}$の他に$\ket{+}$のような曖昧な状態があった。このような量子ビットを$CX$ゲートの1量子ビット目にした場合どうなるか計算してみたい。1量子ビット$\ket{+}$と$\ket{0}$に作用させると次のようになる。

$$\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} \begin{align*} CX\ket{+}_1\ket{0}_2 &= \ket{0}\braket{0}{+}_1 I\ket{0}_2 + \ket{1}\braket{1}{+}_1 X\ket{0}_2 \\ &= \ket{0}\braket{0}{+}_1 \ket{0}_2 + \ket{1}\braket{1}{+}_1 \ket{1}_2 \\ &= \frac{1}{\sqrt{2}}\ket{0}_1\ket{0}_2 + \frac{1}{\sqrt{2}}\ket{1}_1\ket{1}_2 \end{align*}$$

この結果は確率$\left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$で$\ket{00}$、そして同様に確率$\frac{1}{2}$で$\ket{11}$となることを意味している。つまり1量子ビット目が$\ket{0}$であり、一方で2量子ビット目が$\ket{1}$のような状態は生じない。片方を測定して結果が$\ket{0}, \ket{1}$のどちらに確定した場合は、もう片方の量子ビットも必ず同じ結果になるという状況を$CX$ゲートは生み出すことができる。
また、古典コンピュータとの直感が大きく異なる点として、このように片方が$\ket{1}$ならば残りも$\ket{1}$となるような、エンタングルメントした（もつれた）量子状態というのは2つの量子ビットがどれだけ離れていたりしていても影響し続ける。理想的には、たとえば$CX$ゲートを適用したあとの2量子ビットを片方は日本に設置して、もう片方はアメリカ合衆国に設置した場合であってもこの計算どおりになる。
最後に余談ではあるが、このような量子操作を量子回路という下記の図で表わすこともできる。

量子回路では2量子ビットを共に$\ket{0}$からはじめて、最初はアダマールゲート$H$を利用して$\ket{+}$を作成し$CX$ゲートをこのように表す。

magic qoin

ここからはこれまで説明した量子ビットに関する知識を利用して、この問題でプレイヤーが選択できるmagic qoinを使った想定解法がなぜそうなるのかを解説する。
Hackerの選択肢としてmagic qoinを選ぶと、次のように追加の選択肢が表示される。

[Round 0]: Your competitor bets on 0
0. Bet for 0
1. Bet for 1
2. Use your magic qoin
2
Do you want to rotate your qoin before flipping?
0. No, do not rotate my qoin
1. Yes, rotate left
2. Yes, rotate right

そもそもこのmagic qoinとは何かについては実は問題の時点では公開されていない。終了後に公開されたソースコードsecret_coin.py^[7]において、このmagic qoinとは「ERPペアな2量子ビットをつくり、HackerとZardusがそれぞれ1量子ビットを持っている」状態であるということが分かる。ここでERPペアとはたとえば次のような2量子ビットである。

$$\frac{1}{\sqrt{2}}\left(\ket{0}_1\ket{0}_2 + \ket{1}_1\ket{1}_2\right) = CX\ket{+}_1\ket{0}_2$$

そして、このようなエンタングルメントした2量子ビットのうち、Zardusが1量子ビット目である$\ket{+}_1$を持ち、Hackerが2量子ビット目である$\ket{0}_2$を持った状態でゲームが開始される。

各プレイヤーの量子操作

Hacker

さて問題ではCompetitor Aのベットを知ったうえで、magic qoinを左右に回転（rotate）させるか、あるいは何もしないかを選ぶことができる。
準備として、「左右」のような空間的な表現が登場したため、説明を直感的にするためにブロッホ球という量子ビットの空間的な表現を導入する。

ブロッホ球の各軸

このように$x, y, z$の3つの軸があり、これまで説明してきた1量子ビットは実はこの球の表面の座標に対応する。たとえばこれまで紹介してきたいくつかの1量子ビットはブロッホ球において次のような位置に対応する。

このブロッホ球の表面座標$(x, y, z)$とすると、たとえば$\ket{0} = (0, 0, 1)$というような感じで量子ビットを空間的に表現することができる。また、量子ゲートに関してもブロッホ球上での空間的な意味を考えることができる。たとえば$X$ゲートは$X\ket{0} = \ket{1}, X\ket{1} = \ket{0}$なため、これは$x$軸を中心に$\pi\, (= 180^{\circ})$回転させる量子操作であると考えることもできる。
ブロッホ球による空間的な表現について補足したところで、この問題が述べている左右の回転とは何か？というと配布されているソースコードcoin.py^[8]から次のような操作であることがわかる^[9]。

$$\begin{align*} \text{rotate right} &\equiv R_y\left(\frac{\pi}{4}\right) \\ \text{rotate left} &\equiv R_y\left(-\frac{\pi}{4}\right) \\ &\text{where}\; R_y(\theta) \equiv \left(\begin{array}{cc} \cos{\frac{\theta}{2}} & -\sin{\frac{\theta}{2}} \\ \sin{\frac{\theta}{2}} & \cos{\frac{\theta}{2}} \end{array}\right) \end{align*}$$

この行列表現からは分かりにくいかもしれないが、$R_y(\theta)\ket{a}$は「1量子ビット$\ket{a}$を$y$軸中心に$\theta$回転させる」ことを意味している。したがってこの問題においてrotate rightは$y$軸中心に$\frac{\pi}{4}$回転させる操作であり、逆にrotate leftは$y$軸中心に$-\frac{\pi}{4}$回転させる操作となる。
最後にHackerは基底$\{\ket{0}, \ket{1}\}$で測定してその結果が$\ket{0}$ならば$0$、$\ket{1}$であれば$1$を出力する。

Zardus

ソースコードplayers.py^[10]からZardusはCompetitor Bの結果$b$に応じて次の量子操作を行う。

• $b = 0$であるとき
  • なにもせずにZardusが持つ量子ビットを基底$\{\ket{0}, \ket{1}\}$で測定する
• $b = 1$であるとき
  • Zardusが持つ量子ビットにアダマールゲート$H$を作用させたうえで基底$\{\ket{0}, \ket{1}\}$で測定する

CHSHゲーム中の量子ビット変化と観測確率

ここまでHackerとZardusの量子操作をまとめて1つの量子回路で書くと次のようになる。

今回の問題の量子操作に対応する量子回路図

先に問題（CHSHゲーム）の模範解答を述べてしまうと、Hackerは次のような操作を行えばよい。

• $a = 0$ならばrotate leftを行う
• $a = 1$ならばrotate rightを行う

なぜこのようになるのかについて、Competitorのベットである$a, b$の結果で場合分けしてHackerとZardusの測定結果にどのように影響するかを考えていく。

1. $b = 1$のとき

$b = 1$なのでZardusは彼が持つ量子ビットにアダマールゲートを適用して測定を行った。まずはZardusの測定後にHackerが持つ量子ビットがどのような状態となったかを確認する。ここでアダマールゲートをZardusの持つ1量子ビット目だけ適用するため$H \otimes I$として次のように計算する。

$$\begin{align*} (H \otimes I) CX\ket{+}_1\ket{0}_2 &= \frac{1}{\sqrt{2}}\left(\begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{array}\right) \frac{1}{\sqrt{2}}\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 1 \end{array}\right) \\ &= \frac{1}{2}\left(\begin{array}{c} 1 \\ 1 \\ 1 \\ -1 \end{array}\right) \\ &= \frac{1}{2}\left(\ket{0}_1\ket{0}_2 + \ket{0}_1\ket{1}_2 + \ket{1}_1\ket{0}_2 - \ket{1}_1\ket{1}_2 \right) \end{align*}$$

したがってこれは$\left|\pm\frac{1}{2}\right|^2 = \frac{1}{4}$で$00, 01, 10, 11$の全パターンが測定されうることを意味する。Zardusの測定結果$z$によって整理すると次のようになる。

• $z = 0\,(\ket{0})$のとき

  • Hackerの持つ量子ビットは$\frac{1}{2}$の確率で$\ket{0}, \ket{1}$のいずれかとなるため

    $$\frac{1}{\sqrt{2}}\left(\ket{0}_2 + \ket{1}_2\right) = \ket{+}_2$$
• $z = 1\,(\ket{1})$のとき

  • 同様に$\frac{1}{2}$の確率で$\ket{0}, -\ket{1}$いずれかとなるため

    $$\frac{1}{\sqrt{2}}\left(\ket{0}_2 - \ket{1}_2\right) = \ket{-}_2$$

ここまででZardusの測定後のHackerの持つ量子ビット（magic qoin）を調べ終わった。さて、ここに来たところでHackerのCompetitorのベット$a$によってどうすれば勝利するかについて確認してみる。$b = 1$なので次のようになる。

• $a = 0$ならばZardusの結果$z$と同じ結果となれば勝利する
• $a = 1$ならばZardusと異なる結果となれば勝利する

今の量子ビットをそのまま測定した場合、$\frac{1}{2}$の完全にランダムな運まかせで勝負となる。そこでまず$a = 0$のケースを考える。こちらはつまり次のようになる

• $\ket{+}_2\,(\Rightarrow z = 0)$ならば$\ket{0}$が出てほしい
• $\ket{-}_2\,(\Rightarrow z = 1)$ならば$\ket{1}$が出てほしい

このときrotate leftを行うと、次の図のように完全に$\frac{1}{2}$でランダムであった$\ket{0}, \ket{1}$へ傾いたことがわかる。

$y$軸から見たブロッホ球

そして次のように確率振幅を計算すれば、そこから勝率を求めることができる。

$$\begin{align*} R_y\left(-\frac{\pi}{4}\right)\ket{\pm}_2 &= \left(\begin{array}{cc} \cos{-\frac{\pi}{8}} & -\sin{-\frac{\pi}{8}} \\ \sin{-\frac{\pi}{8}} & \cos{-\frac{\pi}{8}} \end{array}\right) \frac{1}{\sqrt{2}}\left(\begin{array}{c} 1 \\ \pm 1 \\ \end{array}\right) = \frac{1}{\sqrt{2}}\left(\begin{array}{c} \cos{\frac{\pi}{8}} -\sin{-\frac{\pi}{8}} \\ \sin{-\frac{\pi}{8}} \pm \cos{\frac{\pi}{8}} \\ \end{array}\right) \\ &= \frac{1}{\sqrt{2}}\left( \left(\cos{\frac{\pi}{8}} + \sin{\frac{\pi}{8}}\right)\ket{0} + \left(-\sin{\frac{\pi}{8}} \pm \cos{\frac{\pi}{8}}\right)\ket{1} \right) \end{align*}$$

したがって次のようにこのゲームで勝利する確率が求まる。

• $\ket{+}_2$なら$\ket{0}$が観測されたときに勝利するため$\left|\frac{1}{\sqrt{2}}\left(\cos{\frac{\pi}{8}} + \sin{\frac{\pi}{8}}\right)\right|^2 = \frac{1}{2} + \frac{1}{2\sqrt{2}}$
• $\ket{-}_2$なら$\ket{1}$が観測されたときに勝利するため$\left|\frac{1}{\sqrt{2}}\left(-\sin{\frac{\pi}{8}} - \cos{\frac{\pi}{8}}\right)\right|^2 = \frac{1}{2} + \frac{1}{2\sqrt{2}}$

同様に$a = 1$のケースであればrotate rightすることによって次のように傾かせることができる。

確率振幅は次のようになる。

$$\begin{align*} R_y\left(\frac{\pi}{4}\right)\ket{\pm}_2 &= \left(\begin{array}{cc} \cos{\frac{\pi}{8}} & -\sin{\frac{\pi}{8}} \\ \sin{\frac{\pi}{8}} & \cos{\frac{\pi}{8}} \end{array}\right) \frac{1}{\sqrt{2}}\left(\begin{array}{c} 1 \\ \pm 1 \\ \end{array}\right) = \frac{1}{\sqrt{2}}\left(\begin{array}{c} \cos{\frac{\pi}{8}} -\sin{\frac{\pi}{8}} \\ \sin{\frac{\pi}{8}} \pm \cos{\frac{\pi}{8}} \\ \end{array}\right) \\ &= \frac{1}{\sqrt{2}}\left( \left(\cos{\frac{\pi}{8}} -\sin{\frac{\pi}{8}}\right)\ket{0} + \left(\sin{\frac{\pi}{8}} \pm \cos{\frac{\pi}{8}}\right)\ket{1} \right) \end{align*}$$

こちらの場合は先程とは勝利条件が異なり、XORの結果を$a = b = 1$にしなければならないため、Zardusとは異なる結果が求められる。したがって勝利条件は次のようになる。

• $\ket{+}_2\,(\Rightarrow z = 0)$ならば$\ket{1}$で勝利
  • したがって勝利する確率は$\left|\frac{1}{\sqrt{2}}\left(\sin{\frac{\pi}{8}} + \cos{\frac{\pi}{8}}\right)\right|^2 = \frac{1}{2} + \frac{1}{2\sqrt{2}}$となる
• $\ket{-}_2\,(\Rightarrow z = 1)$ならば$\ket{1}$で勝利
  • 同様に確率$\left|\frac{1}{\sqrt{2}}\left(\cos{\frac{\pi}{8}} -\sin{\frac{\pi}{8}}\right)\right|^2 = \frac{1}{2} + \frac{1}{2\sqrt{2}}$で勝利する

したがって合計で4パターンの場合分けしてそれぞれの勝率が全て$\frac{1}{2} + \frac{1}{2\sqrt{2}}$であったため、$b = 1$な場合は$\frac{1}{2} + \frac{1}{2\sqrt{2}}$で勝利する。

2. $b = 0$のとき

$b = 0$なので、この場合は$a$の値に関係なくHackerとZardusの結果を同じにすればよい。このときZardusはアダマールゲートを作用させることなく基底$\{\ket{0}, \ket{1}\}$で測定を行う。すでに述べたようにこの2量子ビット$CX\ket{+}_1\ket{0}_2$を測定すると$\ket{00}$か$\ket{11}$がそれぞれ$\frac{1}{2}$で観測されるため、このときHackerの持つ量子ビットを回転をせずに基底$\{\ket{0}, \ket{1}\}$で測定した場合は100%の確率で$h = z$となって$z \oplus h = 0$となりゲームに勝利する。
しかしHackerは$b = 0$であることを知っていないため、もし$b = 1$であるにも関わらずそのまま回転させずに測定してしまった場合は前に述べたとおり$\frac{1}{2}$でしか勝利できない。そこでこの場合でもHackerの持つ量子ビットを同じように回転させる。

• $z = 0$のケース

  • 

  • この場合の確率振幅は次のようになる

    $$\begin{align*} R_y\left(\pm\frac{\pi}{4}\right)\ket{0}_2 &= \left(\begin{array}{cc} \cos{\frac{\pi}{8}} & \mp\sin{\frac{\pi}{8}} \\ \pm\sin{\frac{\pi}{8}} & \cos{\frac{\pi}{8}} \end{array}\right) \left(\begin{array}{c} 1 \\ 0 \end{array}\right) = \left(\begin{array}{c} \cos{\frac{\pi}{8}} \\ \pm\sin{\frac{\pi}{8}} \end{array}\right) \\ &= \cos{\frac{\pi}{8}}\ket{0} \pm\sin{\frac{\pi}{8}}\ket{1} \end{align*}$$
  $z = 0$なので$h = 0\,(\ket{0})$のとき勝利するため、勝率は$\left|\cos{\frac{\pi}{8}}\right|^2 = \frac{1}{2} + \frac{1}{2\sqrt{2}}$となる
• $z = 1$のケース

  • 

  • 同様に確率振幅は次のようになる

    $$\begin{align*} R_y\left(\pm\frac{\pi}{4}\right)\ket{1}_2 &= \left(\begin{array}{cc} \cos{\frac{\pi}{8}} & \mp\sin{\frac{\pi}{8}} \\ \pm\sin{\frac{\pi}{8}} & \cos{\frac{\pi}{8}} \end{array}\right) \left(\begin{array}{c} 0 \\ 1 \end{array}\right) = \left(\begin{array}{c} \mp\sin{\frac{\pi}{8}} \\ \cos{\frac{\pi}{8}} \end{array}\right) \\ &= \mp\sin{\frac{\pi}{8}}\ket{0} + \cos{\frac{\pi}{8}}\ket{1} \end{align*}$$

  • よって$h = 1\,(\ket{1})$が観測される確率$\left|\cos{\frac{\pi}{8}}\right|^2 = \frac{1}{2} + \frac{1}{2\sqrt{2}}$が勝率となる

最終的な勝率

このように全パターンの確率を求めると全て$\frac{1}{2} + \frac{1}{2\sqrt{2}}$となるため、この節の冒頭で述べたように$a = 0$ならばrotate leftを行い、$a = 1$ならばrotate rightを行うという操作で$\frac{1}{2} + \frac{1}{2\sqrt{2}} = 85.35\%$で勝利することができる。よってもともとの問題で要請されていた勝率85%を越えることができる。

まとめ

CHSHゲームやBell不等式については以前から知っていたが、量子計算として詳しく数式で追ったことはなく、筆者としてもとても勉強になったと思う。

参考文献

• Quantum Native Dojo: コラム1：量子複製不可能 (No-Cloning) 定理
• 量子計算理論 量子コンピュータの原理
• 量子コンピューティング: 基本アルゴリズムから量子機械学習まで

脚注

1. なお、この友人は非想定解でクリアしたらしい。

2. $\oplus$はXOR演算を意味する。

3. 量子コンピュータと区別して従来のコンピュータをこのように呼ぶ。

4. 基底の定義のため本当はここで線形空間や1次独立などの定義を述べるべきではあるが、この記事は完全に厳密性な数学的背景を明らかにしていくというよりは、CTFの問題を通して量子コンピュータなどに関する知識を少し深める手助けになればよいというスタンスであるため、いったんこれらの定義は記事が巨大になってしまうのを避けるためにあえて解説しない。

5. このように内積の分配法則などを利用して、量子計算では具体的な行列表現を使って計算するというよりは、このようにブラケット記法のまま計算を進めていくことも多いと思う。

6. 通常の（古典）コンピュータでは右端から左側へ1ビット、2ビットとなるため、この表記に違和感があるかもしれないが、数学や日常の表現では$1, 2, \dots$などと左から右へ大きくなっていくため、ここでは自分が普段参照している教科書の都合もあってこの表記とした。したがって、古典コンピュータの表現と統一するために右端を1量子ビットとしても問題はないと思う。

7. https://github.com/o-o-overflow/dc2021q-qoo-or-ooo-public/blob/64164c2315395390b9a8f6cae970841ad777c401/service/src/secret_coin.py#L8

8. https://github.com/o-o-overflow/dc2021q-qoo-or-ooo-public/blob/64164c2315395390b9a8f6cae970841ad777c401/service/src/coin.py#L15-L19

9. $R_y(\theta)$については量子計算ライブラリーが提供している関数を利用していたため、ここでは筆者の所有する教科書から行列表現を用意してきた。

10. https://github.com/o-o-overflow/dc2021q-qoo-or-ooo-public/blob/64164c2315395390b9a8f6cae970841ad777c401/service/src/players.py#L47-L52