Posted at

量子零和ゲーム(令和改元記念)


はじめに

「令和⇒レイ和⇒零和⇒ゼロ和⇒ゼロサム」ということで、令和改元記念としまして、零和ゲーム(ゼロサムゲーム)の話しをしようと思います。


ゼロサムゲーム

ゲーム理論で扱うゲームの一種で、プレイヤー個々の得点と失点を全て足し合わせた合計が0になるゲームを指します。つまり、総和(サム)がゼロになるゲームで「ゼロサムゲーム」です。

例えば二国間の為替レートは、一方の換算レートがある額だけ上がれば、逆側の換算レートは同じ額だけ下がるため、為替取引はゼロサムゲームと考えられます。

ゲーム理論については、hatenablog にある yagami12 さんの 星の本棚:ゲーム理論が細かくまとめられいて分かり易く解説されています。ゼロサムゲームについても詳しく記載されています。さらに学びたい方は参考にしてみてください。(全てを理解するのにはそれなりの気合いが要るほどの大作で、私はほんの少ししか学べていません。)

"星の本棚"にもある通り、ゼロサムゲームだけをとっても、ナッシュ均衡や maxmin戦略、minmax戦略など数理的に素敵な話題が満載です。このエントリーでは欲張らずに1つの話題だけに絞ります。

ここではゼロサムゲームの1つである「ペニーフリップゲーム(Penny Flip Game)」をご紹介します。ペニーは1セント銅貨の通称ですし、フリップは“反転する、入れ替える”の意味ですから、コイン反転ゲームとでも訳せると思いますが、ここではそのまま"ペニーフリップゲーム"と呼びます。


ペニーフリップゲーム

それではゲームのルールを説明しましょう。

ペニーフリップゲームは2人で行います。そのプレイヤーをP,Q1とします。ルールは次の通りです。


ペニーフリップゲームのルール

0. コインを裏にしてはじめます。

1. QはPに分からないように、コインを裏返すか、裏返さないかを選び、コインを操作します。
2. PはQに分からないように、コインを裏返すか、裏返さないかを選び、コインを操作します。
3. QはPに分からないように、コインを裏返すか、裏返さないかを選び、コインを操作します。
4. コインを見て、裏ならQの勝ち、表ならPの勝ちです。

このゲームは両者が適切な戦略をとれば、どちらも勝つ確率が等しくなるゲームです。ゲーム理論の言葉で表現すると、これはゼロサム2人ゲームにおける混合戦略のナッシュ均衡に対応していると言えるそうです。

少し繰り返しになりますが、この後、話し易くするために、ゲームのルールを少し言い換えます。

コインの表を「1」、裏を「0」と表します。そしてコインを裏返す(0を1にして、1を0にする)操作を「Flip」と呼び、そのままの操作を「Stay」と呼びます。するとゲームのルールは次のように言い換えられます。


ペニーフリップゲームのルール(言い換え)

0. コインを「0」にしてはじめます。

1. QはPに分からないように、「Flip」か「Stay」を選び、コインを操作します。
2. PはQに分からないように、「Flip」か「Stay」を選び、コインを操作します。
3. QはPに分からないように、「Flip」か「Stay」を選び、コインを操作します。
4. コインを見て、「0」ならQの勝ち、「1」ならPの勝ちです。

Stayを選んだ場合を"S"、Flipを選んだ場合を"F"として、プレイヤーPから見た利得行列を表にすると次のようになります。(プレイヤーQから見た利得行列は表内のプラスとマイナスが逆転します。)

Qの手順1,3の組合せ→
Pの手順2↓
(S,S)
(S,F)
(F,S)
(F,F)

(S)
-1
1
1
-1

(F)
1
-1
-1
1

この利得行列を見ていると、P,Qのどちらとも勝つ確率が等しくなるゲームであることが想像できそうです。


量子版ペニーフリップゲーム

さて、ペニーフリップゲームのルールが分かったところで、このゲームの量子版を考えてみましょう。

コインが出てくるケースでは、そのコインを「量子コイン」にして考えるのが量子版を考えるときの常套手段です。通常のコインは、0または1で表されるためコンピューターの「ビット」と対応しています。量子コインは、通常のコインの対応に習って「量子ビット」に対応していると考えます。天下り的ですが、$|\alpha|^2+|\beta|^2$を満たす$\alpha,\beta$を使って $\alpha \lvert 0 \rangle + \beta \lvert 1 \rangle$ という状態をもつコインを量子コインとします。

また、この量子コインの操作にはユニタリ変換を考えるのが、量子版の常套手段です。1量子ビットに対するユニタリ変換は、$UU^{\ast}=I$($U^{\ast}$は行列$U$の随伴行列、$I$は恒等行列)を満たす$2\times 2$の複素正方行列「ユニタリ行列」として表現します。

量子版を考えるための準備が整ったところで、量子版ペニーフリップゲームに戻りましょう。量子版ペニーフリップゲームは、1999年 David Meyer氏により提案2され、2009年に James CHAPPELL氏らも研究3しています。その量子版では、

Qは量子的なコイン操作ができ、Pは古典的なコイン操作しかできない(知らない)。

というケースを考えています。Qには非常に有利そうな雰囲気の漂った状況ではありますが、この前提のもとで量子版ペニーフリップゲームのルールを変更してみましょう。


量子版ペニーフリップゲームのルール

0. 量子コインを |0> にしてはじめます。

1. QはPに分からないように、ユニタリ演算を選び、量子コインを操作します。
2. PはQに分からないように、「Flip」か「Stay」を選び、量子コインを操作します。
3. QはPに分からないように、ユニタリ演算を選び、量子コインを操作します。
4. 量子コインをZ基底で測定して、 |0> ならQの勝ち、 |1> ならPの勝ちです。

ここで、手順2でPが操作するのは古典的な次の操作になります。

「Flip」はパウリX演算$\sigma_{x}=\Big(\matrix{0 & 1 \cr 1 & 0}\Big) $「Stay」は恒等演算$ I=\Big(\matrix{1 & 0 \cr 0 & 1}\Big)$です。

この量子版ゲームは、量子的なプレイヤーであるQにとって有利になるのでしょうか?

$$\begin{aligned}&\vdots \cr &\vdots\end{aligned}$$

結論からお伝えします。

Pの戦略に関わらず、Qには必ず勝つ戦略があります。

結論は想像通りですが、それがどのような戦略かを簡単に示します。

Qの戦略は、手順1($U_{1}$)と手順3($U_{3}$)でアダマール変換 $H=\frac{1}{\sqrt{2}}\Big(\matrix{1 & 1 \cr 1 & -1}\Big) $を行います。すると、Pの戦略によらず、必ず裏である $\lvert0\rangle$が得られます。この戦略を導き出す計算は、難しくはありませんが少し大変です。イメージだけでいうと、Qは手順1で量子コインを立てるように置きます。Pが手順2で操作しても、Qが縦置きにした量子コインを縦軸に回せるだけです。最後に手順3で立てた手順の逆に操作すれば、Qは必ず裏 $\lvert0\rangle$ にできるという戦略です。

正確には量子情報理論の基礎を学んで、混合状態で全て議論しなければなりませんが、その雰囲気を式で確認してみます。

Pの行う手順2の「Flip」を確率$p$で行うとすると、Pの操作$U_{2}$は、

$

U_{2}=p\sigma_{x}+(1-p)I = \Big(\matrix{1-p & p \cr p& 1-p} \Big)

$

と考えられます。そして、Qの手順1,3がアダマール変換としてたときに、順番に操作したとすると、

$\begin{aligned}

U_{3}U_{2}U_{1}&=H \cdot \{ p\sigma_{x}+(1-p)I \} \cdot H \cr

&= p\sigma_{z}+(1-p)I =\Big(\matrix{1 & 0 \cr 0 & 1-2p} \Big)

\end{aligned}$

となります。初期状態 $\lvert0\rangle$ からの操作を考えてみると、

$

U_{3}U_{2}U_{1}\lvert0\rangle = \Big(\matrix{1 & 0 \cr 0 & 1-2p} \Big)

\Big(\matrix{1 \cr 0} \Big) = \Big(\matrix{1 \cr 0} \Big)

$

となり、Pの戦略に関する確率$p$によらず、必ず$\lvert0\rangle$が得られます。

ペニーフリップゲームの量子版は、数理的な証明は少し辛そうで本稿では示しませんが、単純な結果が得られる例でした。従来の(古典版)ペニーフリップゲームの数理と比べると、異なる結果になり、必勝法があるゲームになりました。

このように、従来あった数理モデルの量子版を考えることは、面白い現象が現れることが多いようです。ここではプレイヤーQを量子的な存在として考えましたが、プレイヤーPも量子的な存在として扱うのも面白いかもしれません。(投稿者の力量が足らないため、話しはここまでにしますが。)ほかにも、ニムゲームの量子版4を考察したものもあり、ゲーム理論の量子版を考えるのも楽しそうです。


終わりに

本稿で取り上げたペニーフリップゲームは、今から20年以上前の量子コンピューティングの第一次ブームと呼ばれる時代でもある1999年に David A. Mayer 氏から提案された論文をもとにしました。昨今、量子コンピューティングの第二次ブームと言われていますが、2000年前後の量子計算関連の論文には当時斬新だった理論がたくさんあります。今に使えそうなアイディアが20年も前に提案されていたりします。

量子情報分野のプロの研究者の方々 は、最新の研究で成果を上げることに重点をおいて、日進月歩で取り組んでいらっしゃいます。一方で、過去の才能ある研究者の提案を再評価することも良いのではないかと私は考えています。量子コンピューターの利用ができるようになった今だからこそ、過去の論文を見直して検証するのも有用かもしれません。

私のようなアマチュアには、最先端の研究には手を出せないことが多いですが、こういった過去の成果に対しても取り組めるのが、アマチュアならではの活動だと思って、日々の勉強に取り入れています。

令和改元の記念として、本稿を記しました。平成の時代には、30年かけてコンピューターやインターネットが進歩し、スマホやIoTという形で私たちの身近な存在になりました。令和の時代が長く続き、その期間に量子コンピューターや量子通信が進歩して、量子が身近な存在になることを祈って、本稿を締めくくりたいと思います。

拙文ではございますが、本稿が皆さまの量子計算に対する興味のきっかけになればと幸いです。最後までお読み頂きましてありがとうございました。

ご注意ください(免責事項)

投稿者は量子情報やゲーム理論の専門家ではございません。
科学的・技術的な内容は出典のある文献やプログラムを動作した結果をもとにして、可能な限り正確な情報を掲載できるように心がけておりますが、投稿者が調査できた狭い範囲での内容であり、網羅性のある情報や多角的な情報ではございません。誤情報が入り込んだり、情報が古くなったりすることもあり、必ずしも正確性を保証するものではありません。また、投稿者の主観的な発言も含まれております。
もし、誤りなどお気づきの点がございましたら、ご指摘ください。





  1. Meyerの論文では、スタートレックの「死のゲームHide and Q」を想像させる説明がされています。プレイヤーP,Qをその登場人物であるPicard艦長と高次元生命体として解説されています。 



  2. "Quantum strategies" David A Meyer, Physical Review Letters 82 (5), 1052 



  3. "An Analysis of the Quantum Penny Flip Game using Geometric Algebra" James M. CHAPPELL et al., Journal of the Physical Society of Japan 78(5):054801 



  4. "Toward Quantum Combinatorial Games" Paul Dorbec, Mehdi Mhalla, arXiv:1701.02193