Problem – C1 – Codeforces

問題概要

2つの量子状態\( |0\rangle,\ |+\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\)のどちらかがそれぞれ確率50%で与えられる。
どちらが与えられたか確率80%以上で(測定することで)判定せよ。

解法

コンテスト中は、Bloch球を描いてy軸周りに\(\frac{\pi}{4}\)回転すれば確率最大だろうと予想して解きました。条件の確率80%という数字をどう導出するのか気になったのでまとめます。

まず、内積\(\langle 0 | + \rangle\)は、

$$ \langle 0 | + \rangle = \begin{pmatrix}1 & 0\end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1\end{pmatrix} = \frac{1}{\sqrt{2}}\ $$

であり、これより、

$$ \cos\theta = \frac{1}{\sqrt{2}} \\ \theta = \frac{\pi}{4} $$

であるので、\( |0\rangle \)と\( |+\rangle \)は直交していません。一般に、区別したい状態が直交していないと完全に区別することはできません。

区別できる確率を最大にするには、Bloch球上でy軸周りに\( \frac{\pi}{4} \) 回転し、Pauli Z 基底での測定した結果が \( |0\rangle \)ならばもともと\( |0\rangle \)、\( |1\rangle\)ならばもともと\( |+\rangle\)だったと答えるようにすればよいことは想像がつきます。

なぜかというと下図のように\( |0\rangle,|+\rangle\)がそれぞれ緑色、オレンジ色のベクトルへと変化し、それぞれ\( |0\rangle,|1\rangle\)へのなりやすさが等しくなるからです。

Bloch球上でy軸周りに回転するゲート$$ R_y(\theta)=\begin{pmatrix}\cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ \sin\frac{\theta}{2} & \cos\frac{\theta}{2}\end{pmatrix}$$

を用いて、\( \theta\)回転させたときに、正解する確率\( P(\theta)\)がどのように変化していくか見ていきます。

条件付き確率\( P(B|A)\)を次のように定義します。

  • 最初の量子状態が\( |A\rangle\)で、その後ユニタリゲート\( U\)を作用させた後、測定した結果が\( |B\rangle\)である確率

例えば\( P(1|+)\)は、量子状態がもともと\( |+\rangle\)で、その後なんらかのユニタリゲート\( U\)を作用させた後に、測定した結果が\( |1\rangle\)である確率です。

今回作用させるユニタリゲート\( U\)は\( R_y(\theta)\)で、\( P(\theta)\)は条件付き確率を用いて、

$$ P(0)P(0|0)+P(+)P(1|+) $$

と表せます。問題の条件より、\( P(0)=P(+)=\frac{1}{2}\)なので、
$$ P(\theta)=\frac{1}{2}(P(0|0)+P(1|+)) $$

です。\(R_y(\theta)\)は、入力が\( |0\rangle\)のとき、

$$ R_y(\theta)(|0\rangle)=\cos\frac{\theta}{2}|0\rangle+\sin\frac{\theta}{2}|1\rangle $$

であり、入力が\( |+\rangle\)のとき、

$$ R_y(\theta)(|+\rangle)=\frac{1}{\sqrt{2}}(\cos\frac{\theta}{2}-\sin\frac{\theta}{2})|0\rangle+\frac{1}{\sqrt{2}}(\sin\frac{\theta}{2}+\cos\frac{\theta}{2})|1\rangle $$

であるので、

$$ P(0|0)=\cos^2\frac{\theta}{2} \\ P(1|+)=|\frac{1}{\sqrt{2}}(\sin\frac{\theta}{2}+\cos\frac{\theta}{2})|^2=\frac{1}{2}+\sin\frac{\theta}{2}\cos\frac{\theta}{2} $$

となります。以上のことから、

$$ P(\theta) = \frac{1}{2}(\cos^2\frac{\theta}{2}+\frac{1}{2}+\sin\frac{\theta}{2}\cos\frac{\theta}{2}) $$

となり、\( P(\theta)\)の臨界点を求めることで\( \theta=\frac{\pi}{4}\)のとき最大値\( \frac{1}{4}(2+\sqrt{2})=0.85355\cdots\)が求まります。

参考に、Wolfram Alpha で\(P(\theta)\)の最大化を解いてみると、Maximize{(1/2)(1/2+cos^2x+cosxsinx), 0<=x<=π/2},{x} – Wolfram|Alpha のようになります。

つまり、理想的には約85%の確率で\( |0\rangle\)と\( |+\rangle\)が区別できるので、誤差を考慮してこの問題では80%以上という条件にしたのだろうとわかります。

ソースコード

Ry(PI()/4.0, q);
if(M(q)==One){
  return 1;
}
return 0;

参考