量子審判ゲーム

量子情報処理における量子審判ゲームは、量子ゲームの一般理論におけるゲームの一種である。^{[1]このゲームはアリスとボブの2人のプレイヤー間でプレイされ、審判によって仲裁される。審判は}量子情報を交換しながら、一定数のラウンドでプレイヤーと対話した後、プレイヤーの報酬を出力する。

ターン量子審判は、プレイヤーのアリスとボブとラウンドのやり取りを行います。各やり取りでは、アリスとボブから量子状態を受け取り、その量子状態を前回のやり取りの「残り」の状態とともに処理し、出力状態を生成し、出力状態の一部をプレイヤーに送信します。ラウンドの終わりに、審判はプレイヤーから受け取った最終状態を処理し、アリスとボブの報酬を決定します。審判の役割は、プレイヤーのアリスとボブに量子ビットを渡すことです。量子ビットをエンタングルメントするのが審判の仕事であり、これは量子ゲームでは不可欠であると言われています。アリスとボブが審判に量子ビットを返すと、審判はそれらの最終状態を確認します。^[2]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

数学的には、nターン審判は入力空間と出力空間が次の形式である 測定共戦略である。${\displaystyle \{R_{a}:a\in \Sigma \}}$${\displaystyle {\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}}$${\displaystyle {\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}}$

${\displaystyle {\mathcal {X}}_{k}={\mathcal {A}}_{k}\otimes {\mathcal {B}}_{k}}$そして${\displaystyle {\mathcal {Y}}_{k}={\mathcal {C}}_{k}\otimes {\mathcal {D}}_{k}}$

複素 ユークリッド空間 およびの場合。 ${\displaystyle {\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}}$${\displaystyle {\mathcal {D}}_{k},\ 1\leq k\leq n}$

${\displaystyle {\mathcal {A}}_{k},{\mathcal {B}}_{k}}$は審判がターン中にアリスとボブに送ったメッセージを表し、彼らの応答に対応する。ターンの終わりに審判は出力を生成する。${\displaystyle k}$${\displaystyle {\mathcal {C}}_{k},{\mathcal {D}}_{k}}$${\displaystyle n}$${\displaystyle a\in \Sigma }$

ターン量子審判ゲームは、 n ターン審判と、各測定出力をアリスとボブの報酬にマッピングする関数で構成されます。 ${\displaystyle n}$${\displaystyle V_{A},V_{B}:\Sigma \mapsto \mathbb {R} }$${\displaystyle a}$

個々の量子審判ゲームは、アリスとボブが選択できる戦略に特定の制限を課す場合があります。たとえば、非局所ゲーム^[3]や疑似テレパシーゲーム^[4]では、 アリスとボブはエンタングルメントを共有することはできますが、通信することは禁止されています。一般に、このような制限は量子審判ゲームには適用されない可能性があります。

言語Lがエラーεの審判付きゲームを持つとみなされるのは、多項式時間検証器が以下の条件を満たす場合である：各文字列x∈Lに対してアリス（イエス証明者）はボブ（ノー証明者）の戦略に関係なく少なくとも1-εの確率で審判にxを受け入れるよう説得でき、各文字列x∉Lに対してボブはアリスの戦略に関係なく少なくとも1-εの確率で審判にxを拒否するよう説得できる。^[5]

古典的なゼロサムゲームと同様に、ゼロサム量子審判ゲーム^[1]は追加の制約を伴う量子審判ゲームである。 ${\displaystyle V_{A}(a)+V_{B}(a)=0}$

ゼロサム量子審判ゲームでは、アリスとボブが独立した戦略でプレイすると仮定するのが自然です。なぜなら、直接通信したり、最初にエンタングルメント状態を共有したりすることが、両方のプレイヤーにとって同時に有利になることはないからです。この場合、アリスとボブの戦略は次のように表すことができます。

${\displaystyle A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$そして${\displaystyle B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$

ここで、は入力空間と出力空間を持つすべてのnターン戦略の集合です。 ${\displaystyle {\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})}$${\displaystyle {\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}}$${\displaystyle {\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}}$

組み合わせた戦略は次のようになります。 ${\displaystyle A\otimes B}$

、 と定義すると、アリスの期待利得は${\displaystyle V(a)=V_{A}(a)=-V_{B}(a)}$${\displaystyle R=\sum _{a\in \Sigma }V(a)R_{a}}$${\displaystyle \sum _{a\in \Sigma }V(a)\langle A\otimes B,R_{a}\rangle =\langle A\otimes B,R\rangle }$

アリスにとっての最適戦略は、最小最大問題にある。

${\displaystyle \max _{A}\min _{B}\langle A\otimes B,R\rangle =\min _{B}\max _{A}\langle A\otimes B,R\rangle }$。

上記の等式は、がコンパクト凸集合およびから抽出されているため成り立ちます。これは、ゼロ和量子ゲームの 最小最大定理と呼ばれます。${\displaystyle A,B}$${\displaystyle {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$${\displaystyle {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$

1 ターンの量子審判ゲームは、量子審判ゲーム (QRG) のサブセットで、2 人の無制限のプレイヤー (アリスとボブ) と計算的に制限された審判が存在します。ゲームごとに 1 ターンしかないため、1 ターン ゲームまたは QRG1 と呼ばれます。ゲームは、各プレイヤーが密度行列を審判に送信し、審判がそれらの状態を量子回路に差し込むことで機能します。ゲームの勝者は回路の結果によって決定されます。回路によって「はい」または |1> 状態が生成された場合は、アリスが大多数の時間で勝ち、回路によって「いいえ」または |0> 状態が生成された場合は、ボブが大多数の時間で勝ちます。^[6]  ターンは、審判が証明者 (アリスまたはボブ) にメッセージを送信し、アリスまたはボブが審判に応答を返すことで構成されます。^[5]ゲームの順序は次のようになります。アリスは審判に密度行列を送り、審判はアリスの状態を処理してボブに状態を送ります。ボブは状態を測定して審判に古典的な結果を送り返します。審判はボブの測定を確認し、アリスの勝利を意味する「はい」を生成するか、ボブの勝利を意味する「いいえ」を生成します。^[5]

ベル州立大学の量子審判ゲームには、アリス、ボブ、審判の 3 人の参加者がいます。ゲームは 3 つのドアで構成されています。各ドアの後ろには、x または o (スピンアップ状態またはスピンダウン状態) があります。審判は、アリスとボブに、各ドアの後ろにあるものに関する 3 つの条件を与えます。たとえば、条件は次のようになります。1) ドア 1 と 2 は同じです。2) ドア 2 と 3 は同じです。3) ドア 1 と 3 は異なります。

このゲームの目的は、アリスとボブがドアの後ろで一致するペアを見つけることです。量子的に言えば、これはアリスとボブが一致する密度状態を生成することを意味します。ゲーム中、アリスとボブは通信できませんが、ゲーム開始前に戦略を立てることはできます。彼らは、もつれた光子のペアを共有することでこれを行います。戦略を立てることで、アリスとボブは勝利の可能性を最大化できます。戦略を立てない場合、アリスとボブの勝利の確率は 2/3 です。戦略を立てることで、アリスとボブが一致する量子状態を生成する確率は 2/3 から 3/4 に増加します。^[7]

2 人の競合する証明者による量子インタラクティブ証明は、単一証明者による量子インタラクティブ証明システムの一般化です。^{[8] [9]}これは、アリスとボブが競合する証明者で、審判が検証者であるゼロサム審判ゲームによってモデル化できます。審判は計算量が制限されている (多項式サイズの量子回路) と想定されますが、アリスとボブは計算量が制限されない場合があります。アリス、ボブ、審判は共通の文字列を受け取り、一定回数の対話 (証明者と審判の間で量子情報を交換) を行った後、審判はアリスの勝者とボブの勝者を決定します。

古典的な設定では、RG は次の問題として考えることができます。アリス、ボブ、審判員に何らかの文が与えられます。アリスは審判員に文が真であると納得させようとし、ボブは審判員に文が偽であると納得させようとします。計算能力が限られている審判員は、アリスとボブが提供した証明を見て質問し、最終的にどちらのプレーヤーが正しいか (勝者か) を決定します。審判員の目標は、文が真である場合、アリスが 3/4 を超える確率で勝つ方法があり、文が偽である場合、ボブが 3/4 を超える確率で勝つ方法があるようなアルゴリズムを見つけることです。この確率は 1-ε に等しいです。^[5]

計算量理論の言語では、約束問題が 古典的な審判付きゲーム（古典的なRG）を持つとは、多項式時間ランダム計算で記述される審判が存在する場合であり、 ${\displaystyle L=(L_{\text{yes}},L_{\text{no}})}$

1. それぞれに対して、アリスが勝つための戦略が ≥ 3/4 の確率で存在し、${\displaystyle x\in L_{\text{yes}}}$

2. それぞれに対して、ボブが ≥ 3/4 の確率で勝つ戦略があります。${\displaystyle x\in L_{\text{no}}}$

RG = EXPであることが知られている。^{[10] [11]}

競合する証明者による量子インタラクティブ証明システムは、古典的な RG の一般化であり、審判は多項式時間で生成される量子回路に制限され、プレイヤーと量子情報を交換できます。^[1]したがって、QRG は次の問題として考えることができます。 アリス、ボブ、審判に何らかのステートメントが与えられます (量子状態が含まれる場合があります)。 アリスは審判にステートメントが真であると納得させようとし、ボブは審判にステートメントが偽であると納得させようとします。 審判は量子状態を介して証明者に質問し、量子状態で回答を受け取り、受信した量子状態を量子コンピューターを使用して分析できます。 アリスとボブとラウンドで通信した後、審判はステートメントが真か偽かを決定します。 審判が確率 ≥ 3/4 で正しい決定を下す方法がある場合、ゲームは QRG にあります。 この確率は ≥ 1-ε です。^[5]${\displaystyle n}$

より正式には、QRGは、以下のように定義される量子審判ゲームを持つすべての約束問題の複雑性クラスを表す。文字列が与えられたとき、多項式時間で生成される量子回路によって表現される審判が存在する場合 、約束問題はQRGに属する。${\displaystyle x}$${\displaystyle L=(L_{\text{yes}},L_{\text{no}})}$

1. ならば、アリスが勝つための戦略が確率 ≥ 3/4 で存在し、${\displaystyle x\in L_{\text{yes}}}$

2. の場合、ボブが ≥ 3/4 の確率で勝つ戦略が存在する。${\displaystyle x\in L_{\text{no}}}$

QRG = EXP であることが判明しました。審判が量子回路を使用して量子情報を送受信できるようにしても、審判に追加の権限が与えられるわけではありません。EXP ⊆ QRG は、EXP = RG ⊆ QRG という事実から生じます。半正定値プログラム(SDP) を使用して QRG を定式化することで、QRG ⊆ EXP を証明しました。

量子審判ゲームでは、すべてのやり取りの最後に、審判は 2 つの可能な結果のうちの 1 つを出力して、アリスが勝つかボブが勝つかを示します。 ${\displaystyle \{a,b\}}$${\displaystyle (a)}$${\displaystyle (b)}$

設定により、量子審判ゲームの結果となり、その値はアリスの最大勝利確率となります。 ${\displaystyle V(a)=1,V(b)=0}$

上記のゼロサム量子審判ゲームと同じ表記法を使用すると、審判は演算子 で表され、アリスは から戦略を選択し、ボブは から戦略を選択できます。定義 ${\displaystyle \{R_{a},R_{b}\}}$${\displaystyle A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$${\displaystyle B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$

${\displaystyle \Omega _{a}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{a})}$、 そして

${\displaystyle \Omega _{b}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{b})}$、

ここで、 は部分トレース演算子です。 ${\displaystyle \operatorname {Tr} _{\mathcal {X}}(Z)}$

審判は確率 でを出力し、確率 で を出力します。は、アリスの戦略と審判の戦略を融合した共同戦略と考えることができます。 ${\displaystyle a}$${\displaystyle \langle A\otimes B,R_{a}\rangle =\langle B,\Omega _{a}(A)\rangle }$${\displaystyle b}$${\displaystyle \langle A\otimes B,R_{b}\rangle =\langle B,\Omega _{b}(A)\rangle }$${\displaystyle \{\Omega _{a}(A),\Omega _{b}(A)\}}$

アリスが選択した戦略に対して、ボブが勝つ確率は最大で ${\displaystyle A}$

${\displaystyle \max _{B}\langle B,\Omega _{b}(A)\rangle }$、

これは戦略表現の性質により、

${\displaystyle \min\{p\geq 0:\Omega _{b}(A)\leq pQ,\ Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\}}$。

したがって、アリスの勝利確率を最大化するには、 ボブの最大勝利確率をすべての可能な戦略にわたって最小化する必要があります。目標は、 ${\displaystyle p}$

${\displaystyle {\begin{array}{rl}\min &p\\{\text{subject to}}&\Omega _{b}(A)\leq pQ,\\&A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n}),\\&Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\end{array}}}$。

この最小化問題は、次のSDP問題で表現できる。^[1]

${\displaystyle {\begin{array}{rll}\min &\operatorname {Tr} (P_{1})\\{\text{subject to}}&\Omega _{b}(A_{n})\leq Q,\\&\operatorname {Tr} _{{\mathcal {C}}_{k}}(A_{k})=A_{k-1}\otimes I_{{\mathcal {A}}_{k}}&(2\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {C}}_{1}}(A_{1})=I_{{\mathcal {A}}_{1}},\\&Q_{k}=P_{k}\otimes I_{{\mathcal {D}}_{k}}&(1\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {B}}_{k}}(P_{k})=Q_{k-1}&(2\leq k\leq n),\\&A_{k}\in \operatorname {Pos} ({\mathcal {C}}_{1\cdots k}\otimes A_{1\cdots k})&(1\leq k\leq n),\\&Q_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\&P_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\\end{array}}}$。

このSPDの入出力空間の次元は（テンソル積状態から）指数関数的であり、SDPは入出力空間の次元にサイズ多項式を持ちます。SDPを多項式時間で解くことができる効率的なアルゴリズムがあるため、^{[12] [13] [14]}、QRG ⊆ EXPとなります。 ${\displaystyle n}$

• 最小最大定理
• 半正定値計画法
• QIP (複雑さ)