量子力学在奇偶游戏中的运用

假设你和你的朋友在外闲逛时,突然被邀请参加一个便于本文接着写下去的游戏——奇偶游戏。游戏的主持人告诉你们,两位参赛者,友人 A 和你(那么不妨称你为便于后文表示的友人 B 吧w),在正式开始比赛之后,处于相互隔离(即无法交换信息)的状态。游戏的主持者会随机选取两个二进制位 $x, y\in \{0,1\}$。然后 $x$ 会交给友人 A,$y$ 自然是交给你,即友人 A 知道 $x$ 是 0 还是 1,但不知道 $y$ 的值;类似的,你知道 $y$ 的值,但不知道友人 A 手上的 $x$ 的值。你们需要根据自己所知道的值,分别给出一个二进制位 $a, b\in \{0,1\}$ 作为回答。

在你们都给出了回答之后,主持者先计算 $a \oplus b$ 的值($\oplus$ 代表异或运算),然后计算 $x\wedge y$ 的值。如果有 $a \oplus b = x\wedge y$,那么你们就获胜。(会获得什么奖品呢~我想要小裙子!

假设在比赛开始前(或者说参赛前),你和友人 A 可以在一起商量策略,设计一个使你们最大可能获胜的方案。那么传统的策略有两种,一种是确定型的,另一种是随机的。下面进入你们的讨论过程吧。

“如果我们用固定的方案的话,每个人不外乎只有 4 种呢_(: 」∠)_”

友人 A:“嗯,要么是一直回答 0,要么一直回答 1,或者拿到什么就回答什么,最后就是回答和自己拿到的值相反的呢。”

“是的呢,用函数表示的话,就是下面这种样子呢\(//∇//)\”

\begin{equation}
\left\{
\begin{aligned}
f_1(x) &= 0\\
f_2(x) &= 1\\
f_3(x) &= x\\
f_4(x) &=
\left\{
\begin{aligned}
0 \text{ if }x=1\\
1 \text{ if }x=0
\end{aligned}
\right.
\end{aligned}
\right.
\end{equation}

友人 A:“来算算我们获胜的概率吧(=゚ω゚)ノ”

“假如说我选择了 $f_3(x) = x$ 吧,那么我们先把上面的判定条件调整一下。”

\begin{equation}
\begin{aligned}
a \oplus b &= x\wedge y\\
x \oplus b &= x\wedge y\\
x \oplus x \oplus b &= x \oplus (x\wedge y)\\
0 \oplus b &= x \oplus (x\wedge y)\\
b &= x \oplus (x\wedge y)
\end{aligned}
\end{equation}

友人 A:“这个我能明白,因为你的答案 $a \equiv x$,所以先将左边的 $a$ 替换为 $x$,接着在两边再次同时异或 $x$,根据异或计算的特点,我们知道这个是和原来的式子等价的w”

“那么现在就看你的回答了,当你拿到 $y$ 以后,你会怎么选(。・ω・。)”

友人 A:“如果 $y = 1$ 的话,显然有 $x\wedge y = x$,接着 $x \oplus x = 0$,那么这个时候我直接回答 0 就可以保证我们 100% 胜。如果 $y = 0$ 的话,就会有$x\wedge y = 0$,然后变成 $0 \oplus x = x$,而然我又不可能知道你的 $x$,不管我选哪个,甚至我用上概率型的方法——投骰子,我也只有 $\frac{1}{2}$ 的概率给出和你的 $x$ 相同的回答呢QAQ”

“那么我们总的胜率就该这么算,因为 $y$ 有一半可能是 0,一半可能是 1,所以 $y = 0$ 时,就看你那儿的一半对一半运气,即$\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$;当 $y = 1$ 时,我们总是可以保证获胜,则$\frac{1}{2}\times 1=\frac{1}{2}$。加起来就是$\frac{1}{4}+\frac{1}{2}=\frac{3}{4}$,看起来好像还不错呢(๑╹ω╹๑ )”

友人 A:“唔,但是奖品好像很不错呢~能不能找出一个更好的方案呢,75% 的概率似乎也不太高呢╮(╯▽╰)╭”

“要去图书馆才知道~”

友人 A:“图书馆?!”

“没错~不知道的时候就去图书馆找答案”

友人 A:“哪里还有时间去了啦(╯°□°)╯︵ ┻━┻”

“那还有别的东西吗┬─┬ ノ( ゜-゜ノ)”

友人 A:“我这里就还有一个祖传的便于作者编下去的 正好是处于 $|00\rangle + |11\rangle$ 叠加态的 2-量子位系统。”

“すーごいー!!”

友人 A:“我们要怎么用起来呢(⁎⁍̴̛ᴗ⁍̴̛⁎)”

“是这样的~我们先把这个 2-量子位系统 分裂为 2 个 1-量子位系统,你拿一个,我拿一个。不过在比赛开始之前都不要测量哦~”

友人 A:“这倒是没问题,不过我们的策略是什么喵?”

“我拿到 $x$ 之后,如果 $x = 1$,那么我会将我的量子位旋转 $\frac{\pi}{8}$。否则什么也不做。嘛~量子力学允许我这么做,并且不会破坏这个系统,不过解释起来过于繁杂,我们还是专注于这个游戏吧。”

友人 A:“可是你说的‘旋转’是什么意思呢(>﹏<)”

“我发现你拿到的恰好是具有实数振幅的、利于我们继续讲下去的量子,我们不妨将这样的一个量子态想像成在二维空间上的几何向量,$|0\rangle$ 我们可以想为 $(1, 0)$,对应的 $|1\rangle$ 则是 $(0, 1)$。”

友人 A:“到这里我觉得我还是能理解,$|0\rangle$ 是一种量子力学中的表示,不过此处我们可以看成 $R^2$ 平面上的基向量 $\vec{e_1}=(1, 0)$,$|1\rangle$ 也类似的,$\vec{e_2}=(0, 1)$,没错吧☆〜(ゝ。∂)”

“嗯嗯,那么我们表示量子力学中的叠加态就简单多了对吧,比如说叠加态的 $\alpha_0|0\rangle+\alpha_1|1\rangle$,经过我们这样的转化之后,可以等价的表示为 $R^2$ 中的向量 $\alpha_0\vec{e_1}+\alpha_1\vec{e_2}$。当然,这里我们要 $\alpha_0, \alpha_1$ 满足平方和等于一,即 $\alpha^2_0+\alpha^2_1=1$。我们拿到的 $|00\rangle + |11\rangle$ 这种叠加态实际上省去了前面的系数 $\alpha_0=\alpha_1=\frac{1}{\sqrt{2}}$,在均匀态的时候,系数,或者说归一化因子,是可以省略掉的。因此我们拿到的,即为 $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$,于是在你测量的时候,看到 $|00\rangle$ 的概率为 $(\frac{1}{\sqrt{2}})^2=\frac{1}{2}$,$|11\rangle$ 的概率也同样是 $\frac{1}{2}$。”

友人 A:“这样啊,不过看到这些,还有平方和相加等于一,总会不自觉的想到 $\sin^2 \theta+\cos^2 \theta=1$ 的说。”

“是的,我正要说呢,我们可以令 $\alpha_0=\cos \theta, \alpha_1=\sin \theta$,于是替换掉原来的 $\alpha_0, \alpha_1$,就可以更直观的表示出来了\(≧▽≦)/”

友人 A:“这样看起来的话,并不算难以理解~那么接下来呢?”

“接下来就是你在收到 $y$ 以后,如果 $y = 1$,就将你的量子位旋转 $-\frac{\pi}{8}$。否则就不用动。然后我们测量出自己的量子位,将结果作为自己的答案就行。”

友人 A:“策略我理解了,但是这样的方法真的能提高我们获胜的概率嘛∑(゚Д゚)”

“那不妨来演算一下吧,首先我们拿到的是原先处于 $|00\rangle + |11\rangle$ 叠加态分裂之后的 2 个 1-量子位系统。然后如果有 $x = y = 0$,那么 $x\wedge y$ 的结果也是 $0$,此时根据我们的策略,你和我都不会旋转自己的量子位,量子力学告诉我们,我们这个时候测量的话,虽然单看自己得到 0, 1 的概率都是 $\frac{1}{2}$,但结合两个人,一定会要么都是 $|0\rangle$,要么都是 $|1\rangle$,根据异或计算,我们的 $a\oplus b$ 也等于 $0$。”

友人 A:“也就是说在 $x = y = 0$ 这种情况下,我们是必胜的。也就有了 $\frac{1}{4}\times 1=\frac{1}{4}$ 的概率。接下来呢”

“接下来我们考虑 $x\not=y$ 的情况,因为这里两种情况是对称的,所以我只说说 $x=0, y=1$ 的推算。$x=0$ 时,我不会操作我的量子位,于是我测量得到 0 的概率是 $\frac{1}{2}$,在你将自己的量子位旋转 $-\frac{\pi}{8}$ 后,对应到上面的 $R^2$ 的表示的话,$\theta=-\frac{\pi}{8}$,需要注意的是,因为我得到 0 了,所以我知道我们的系统原先是 $|00\rangle$,于是用 $\cos^2 \theta$ 来算的话,就是算出你得到 0 的概率,即 $\cos^2 \theta=\cos^2 -\frac{\pi}{8}$。同样的,如果我测量得到的是 1,我们的系统原先则是 $|11\rangle$,于是用 $\cos^2 \theta$ 来算的话,就是算出你得到 1 的概率,也是 $\cos^2 -\frac{\pi}{8}$。”

友人 A:“呜……也就是说,在 $x\not=y$ 的情况下,因为 $x\wedge y = 0$,所以只需要考虑我们给出的答案相同的可能性,即 $a=b$ 的概率。根据你的推算,这个概率是 $\cos^2 -\frac{\pi}{8}$。如果我没算错的话,这个值大概是 $\frac{1}{4\sqrt{2}} + 0.5\approx 0.85$。因此,我们总的获胜几率又增加了 $\frac{1}{2}\times 0.85$ 呢(((o(*゚▽゚*)o)))”

“是的,现在就剩最后一个了,$x=y=1$,这是我们都进行了量子位旋转的那种情况。因为我们是先旋转,再测量,所以我们的这个 2-量子位系统进入的状态是这样的(・Д・)ノ”

\begin{equation}
    \begin{aligned}
        &(\cos(\frac{\pi}{8})|0\rangle + \sin(\frac{\pi}{8})|1\rangle)(\cos(\frac{\pi}{8})|0\rangle - \sin(\frac{\pi}{8})|1\rangle) + (-\sin(\frac{\pi}{8})|0\rangle + \cos(\frac{\pi}{8})|1\rangle)(\sin(\frac{\pi}{8})|0\rangle + \cos(\frac{\pi}{8})|1\rangle)\\
        =&(\cos^2(\frac{\pi}{8})-\sin^2(\frac{\pi}{8}))|00\rangle-2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|01\rangle+2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|10\rangle+(\cos^2(\frac{\pi}{8})-\sin^2(\frac{\pi}{8}))11\rangle\\
        =&\cos(\frac{\pi}{4})|00\rangle-2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|01\rangle+2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|10\rangle+\cos(\frac{\pi}{4})11\rangle\\
        =&\sin(\frac{\pi}{4})|00\rangle-2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|01\rangle+2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|10\rangle+\sin(\frac{\pi}{4})11\rangle\\
        =&2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|00\rangle-2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|01\rangle+2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})|10\rangle+2\sin(\frac{\pi}{8})\cos(\frac{\pi}{8})11\rangle\\
        =&|00\rangle+|10\rangle+|01\rangle+|11\rangle
    \end{aligned}
\end{equation}

友人 A:“我先走了(・◇・)/~~~”

“不要哇wwww其实只是根据旋转之后的概率写了一下,中间利用三角函数公式变换,最后得出此时我们又变成了一个均匀态,也就是说,量子力学告诉我们,我们可能给出的 4 种结果,$(a=0 \wedge b=0)$, $(a=0 \wedge b=1)$, $(a=1 \wedge b=0)$ 以及 $(a=1 \wedge b=1)$ 都具有相同的概率。因为主持人给我们的 $x=y=1$,所以 $x\wedge y = 1$,我们这边要让 $a\oplus b=1$ 的话,结果中有 2 种可以满足,又因为这 4 种是等概率的,因此 $a\oplus b=1$ 的概率为 $\frac{1}{2}$。即我们在这种情况下获胜的概率是 $\frac{1}{4}\times \frac{1}{2}=\frac{1}{8}$。”

友人 A:“那……来算算总的获胜概率_φ(・_・”

\begin{equation}
    \begin{aligned}
        &\frac{1}{4}\times 1+\frac{1}{2}\times (\frac{1}{4\sqrt{2}} + 0.5) + \frac{1}{4}\times\frac{1}{2}\\
        \approx &0.25+0.5\times 0.85 + 0.125\\
        =&0.25+0.425+0.125\\
        =&0.8
    \end{aligned}
\end{equation}

友人 A:“居然真的比传统策略的获胜率高耶☆*:.。. o(≧▽≦)o .。.:*☆”

“(=´∀`)人(´∀`=)”

Reference
  1. Computational Complexity A Modern Approach, Sanjeev Arora and Boaz Barak, p205-209
  2. 上帝不投骰子, CAPO
声明: 本文为0xBBC原创, 转载注明出处喵~

《量子力学在奇偶游戏中的运用》有10个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注