퀀텀 레퍼런스 게임

양자정보처리에서 퀀텀은 퀀텀게임의 일반 이론에서 퀀텀게임의 한 종류다.^[1] 그것은 앨리스와 밥이라는 두 명의 선수 사이에서 연주되며, 심판이 중재한다. 심판은 양자 정보를 교환하면서 일정 횟수의 라운드에서 선수들과 교류한 후 선수들에 대한 보답을 출력한다.

정의

$n$ $n$ 턴 $n$ 양자 심판이 플레이어 앨리스와 밥과 $n$ $n$ 회전을 $n$ 수행한다. 각각의 상호작용은 앨리스와 밥으로부터 양자 상태를 수신하고, 이전 상호작용에서 양자 상태를 "좌측" 상태와 함께 처리하며, 일부 출력 상태를 생성하고, 출력 상태의 일부를 플레이어에게 보내는 것을 포함한다. $n$ $n$ 라운드가 $n$ 끝나면 심판은 선수들로부터 받은 최종 상태를 처리하고 앨리스와 밥의 보답을 결정한다. 심판의 역할은 선수 앨리스와 밥에게 쿼트를 전달하는 것이다. 양자경기에 필수적이라고 주장되는 qubit을 얽는 것이 심판의 일이다. 앨리스와 밥이 심판에게 쿼트를 돌려주면, 심판은 그들의 마지막 상태를 점검한다.^[2]

Quantum Referred 게임

Mathematically, an n-turn referee is a measuring co-strategy $\{R_{a}:a\in \Sigma \}$ whose input spaces ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}$ and output spaces ${\displaystyle {\mathcal {Y}}_{1},\cdots ,{\mathc$ $al{Y}_{n}}$ 은 ${\mathcal Y}_{1},\cdots ,{\mathcal Y}_{n}$ (는) 형식이다.

{\mathcal {X}}_{k}={\mathcal {A}}_{k}\otimes {\mathcal {B}}_{k}

and

{\mathcal {Y}}_{k}={\mathcal {C}}_{k}\otimes {\mathcal {D}}_{k}

복합 유클리드 공간 ${\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}$ ${\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}$ B ${\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}$ C ${\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}$ ${\$ mathcal ${A}_$ {k $},{\mathcal {B}_$ {k $},{\mathcal$ { ${\mathcal {D}}_{k},\ 1\leq k\leq n$ $}$ ${\mathcal {D}}_{k},\ 1\leq k\leq n$ $k},$ D ${\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}$ k ${\mathcal {D}}_{k},\ 1\leq k\leq n$ 1 ≤ ${\mathcal {D}}_{k},\ 1\leq k\leq n$ ≤ ${\mathcal {D}}_{k},\ 1\leq k\leq n$ ${\mathstyle {{D}_{k}, 1\leq$ k $\n$

${\mathcal {A}}_{k},{\mathcal {B}}_{k}$ ${\mathcal {A}}_{k},{\mathcal {B}}_{k}$ , ${\mathcal {A}}_{k},{\mathcal {B}}_{k}$ ${\mathcal {A}}_{k},{\mathcal {B}}_{k}$ ${\$ 턴 $k$ ${\$ ${\mathcal {C}}_{k},{\mathcal {D}}_{k}$ $k$ C ${\mathcal {C}}_{k},{\mathcal {D}}_{k}$ , ${\mathcal {C}}_{k},{\mathcal {D}}_{k}$ k ${\displaystycal{C}}},$ {\ $mathcal{D}_{k}}}}}}}}}}}}}}}}{$ k ${\mathcal {C}}_{k},{\mathcal {D}}_{k}$ }}}}}}}}}}}}}{k}}}}}}}}}}}}}}}}}}}}}}}} $n$ $n$ 턴이 $n$ 끝나면 $a\in \Sigma$ 은 ∈ $a\in \Sigma$ ∈ ${[\displaystyle a\in \Sigma }$ 을(를) 출력한다.

An $n$ -turn quantum refereed game consists of an n-turn referee along with functions $V_{A},V_{B}:\Sigma \mapsto \mathbb {R}$ that maps each measurement output $a$ to Alice's and Bob's pay-off.

개별 퀀텀 리뷰 게임은 앨리스와 밥이 선택할 수 있는 전략에 특정한 제한을 둘 수 있다. 예를 들어, 비로컬 게임과 사이비 텔레파시 게임에서 앨리스와 밥은 얽힘을 공유하는 것은 허용되지만 의사소통은 금지된다.^[4] 일반적으로 이러한 제한은 양자 참조 게임에서는 적용되지 않을 수 있다.

언어 L은 이러한 조건을 만족하는 다항 시간 검증기가 있는 경우 오류 ε가 있는 레퍼런스 게임을 하는 것으로 간주된다: 각 문자열 xlL 앨리스(예스 프로베러)는 심판에게 Bob의 전략(프로베러 없음)과 관계없이 최소 1-13의 확률로 x를 받아들이도록 설득할 수 있고 각 문자열 xlL 밥은 심판에게 심판에게 거부하도록 설득할 수 있다. x는 앨리스의 전략과 상관없이 최소 1타수 이상의 확률로 구성된다.^[5]

제로섬 게임

기존의 제로섬 게임과 유사하게 제로섬 양자 참조 게임은 추가^[1] 제약 $V_{A}(a)+V_{B}(a)=0$ $V_{A}(a)+V_{B}(a)=0$ ( $V_{A}(a)+V_{B}(a)=0$ ) $V_{A}(a)+V_{B}(a)=0$ + V $V_{A}(a)+V_{B}(a)=0$ ( $V_{A}(a)+V_{B}(a)=0$ ) $V_{A}(a)+V_{B}(a)=0$ = $V_{A}(a)+V_{B}(a)=0$ ${\displaystyle V_{A}(a)+$ 가 있는 양자 참조 게임이다. $V_{B}(a)=0}$ .

서로 직접 의사소통하거나 초기에 관여된 상태 {참조}을(를) 공유하는 것은 동시에 두 플레이어가 유리할 수 없기 때문에 제로섬 양자 참조 게임에서 앨리스와 밥이 독자적인 전략을 구사한다고 가정하는 것은 당연하다. 이 경우 앨리스와 밥의 전략은 다음과 같이 나타낼 수 있다.

A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})

and

B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})

where ${\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})$ is the set of all n-turn strategies having input space ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}$ and output space ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$ ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$ ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$ ${\$

이때 결합된 $A\otimes B$ 은 A $A\otimes B$ b $A\otimes B$ ${\displaystyle$ A\ $otimes$ B $}$ 이다 $A\otimes B$

미니맥스 정리

$V(a)=V_{A}(a)=-V_{B}(a)$ ( $V(a)=V_{A}(a)=-V_{B}(a)$ a ) $V(a)=V_{A}(a)=-V_{B}(a)$ = $V(a)=V_{A}(a)=-V_{B}(a)$ $V(a)=V_{A}(a)=-V_{B}(a)$ ( $V(a)=V_{A}(a)=-V_{B}(a)$ a ) $V(a)=V_{A}(a)=-V_{B}(a)$ = $V(a)=V_{A}(a)=-V_{B}(a)$ - $V(a)=V_{A}(a)=-V_{B}(a)$ $V(a)=V_{A}(a)=-V_{B}(a)$ ( $V(a)=V_{A}(a)=-V_{B}(a)$ ) ${\displaystyle V(a)=$ 정의 $V_{A}(a)=-V_{B}(a)}$ , and $R=\sum _{a\in \Sigma }V(a)R_{a}$ , then Alice's expected pay-off is $\sum _{a\in \Sigma }V(a)\langle A\otimes B,R_{a}\rangle =\langle A\otimes B,R\rangle$

앨리스에게 최적의 전략은 미니맥스 문제에 있다.

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

.

The above equality holds because $A,B$ are drawn from compact and convex sets ${\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})$ and ${\displaystyle {\mathcal {S}}_{n}({\$ $mathcal {B}_{1\cdots$ n $},{\mathcal {D}_{1\cdots$ n ${\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ 제로섬 양자 게임을 위한 min-max 정리라고 불린다.

원턴 게임

원턴 퀀텀 레퍼런스 게임은 퀀텀 레퍼런스 게임(QRG)의 하위 세트로서, 두 명의 언바운드 플레이어(앨리스와 밥)와 계산적으로 경계된 심판이 있다. 게임당 턴이 1개뿐이라 원턴 게임이나 QRG1로 불린다. 이 게임은 각 플레이어가 심판에게 밀도 매트릭스를 보내 자신의 양자 회로에 해당 주들을 연결하도록 하는 방식으로 진행된다. 경기의 승자는 회로의 결과에 의해 결정되는데, 회로에 의해 "예" 또는 "1" 상태가 생성될 때 앨리스가 대다수를 이기고, "아니오" 또는 "0" 상태가 생성될 때 밥이 대다수를 이긴다.^[6] 턴은 주심이 프로베라(앨리스 또는 밥)에게 메시지를 보낸 다음 앨리스 또는 밥이 심판에게 응답을 보내는 것으로 구성된다.^[5] 경기의 순서는 다음과 같다. 앨리스는 심판에게 자신의 밀도 매트릭스를 보내고, 그 다음 심판이 앨리스 주를 처리하고 밥에게 주를 보내고, 그 다음 밥은 주를 측정하고, 그 다음 클래식 결과를 심판에게 보내고, 그 심판은 밥의 측정을 체크하고, 앨리스가 승리하거나 "아니오"를 생산하고, 밥이 승리한다는 것을 의미하는 "예"를 생산한다.^[5]

벨 스테이트 게임

벨 스테이트 양자 참조 게임에는 앨리스, 밥, 심판의 세 명의 참가자가 있다. 그 경기는 세 개의 문으로 구성되어 있다. 각 도어 뒤에는 x 또는 o(스피닝 업 상태 또는 스핀 다운 상태)가 있다. 심판은 앨리스와 밥에게 문 뒤에 무엇이 있는지 세 가지 조건을 제시한다. 예를 들어, 조건은 다음과 같을 수 있다: 1) 문1과 2는 같다. 2) 2번 문과 3번 문이 같다. 3) 문 1과 3은 다르다.

이 게임의 목적은 앨리스와 밥이 문 뒤에서 짝을 찾는 것이다. 양자어로, 이것은 앨리스와 밥이 일치하는 밀도 상태를 생산한다는 것을 의미한다. 경기 중에는 앨리스와 밥이 의사소통을 할 수 없지만, 경기가 시작되기 전에 전략을 짜는 것이 허용된다. 그들은 얽힌 한 쌍의 광자를 공유함으로써 이것을 한다. 전략을 짜는 것은 앨리스와 밥이 그들의 승부의 변화를 최대화할 수 있도록 한다. 전략 수립 없이 앨리스와 밥은 2/3의 승산이 있다. 전략화에 의해 앨리스와 밥이 일치하는 양자 상태를 생산할 확률은 2/3에서 3/4로 증가한다.^[7]

경쟁 프로바이더와의 양자 대화형 증명

두 개의 경쟁 프로버가 있는 양자 쌍방향 증명서는 단일 프로베러 양자 쌍방향 증명 시스템의 일반화다.^[8]^[9] 그것은 앨리스와 밥이 경쟁하는 프로바이더인 제로섬 게임으로 모델링할 수 있고, 심판이 검증자인 것이다. 심판은 계산적으로 경계(다항식 크기 양자 회로)된 것으로 가정하는 반면, 앨리스와 밥은 계산적으로 제한되지 않은 것으로 간주된다. 앨리스와 밥, 주심은 공통의 끈을 받고, 일정한 교감(프로퍼와 심판의 양자 정보 교환)을 거쳐 주심이 앨리스의 승패를 결정한다.

클래식 게임

고전적 환경에서 RG는 다음과 같은 문제로 볼 수 있다. 앨리스, 밥, 그리고 심판은 진술서를 받는다. 앨리스는 밥이 심판에게 그 진술이 거짓이라는 것을 납득시키려 애쓰는 동안 그 진술이 사실이라는 것을 심판에게 납득시키려고 애쓰고 있다. 계산력이 제한된 심판은 앨리스와 밥이 제공한 교정쇄를 보고 질문을 한 뒤 마지막에 어느 선수가 맞는지(윙)를 결정한다. 심판은 진술이 사실일 경우 앨리스가 3/4 이상의 확률로 승리할 수 있는 방법이 있고, 진술이 거짓일 경우 밥이 3/4 이상의 확률로 승리할 수 있는 방법이 있다는 알고리즘을 찾는 것이 목표다. 이 확률은 1과 같다.^[5]

복잡성 이론의 언어에서 $L=(L_{\text{yes}},L_{\text{no}})$ 문제 L $L=(L_{\text{yes}},L_{\text{no}})$ = $L=(L_{\text{yes}},L_{\text{no}})$ ( $L=(L_{\text{yes}},L_{\text{no}})$ $L=(L_{\text{yes}},L_{\text{no}})$ $L=(L_{\text{yes}},L_{\text{no}})$ $L=(L_{\text{yes}},L_{\text{no}})$ ) ${\displaystyle$ L $=(L_{\text{yes}},$ $L_{\text{no}}}$ 은(는) 다항 시간 무작위 계산에 의해 설명되는 심판이 있는 경우 다음과 같은 고전적 레퍼런스 게임(클래식 RG)을 $L=(L_{\text{yes}},L_{\text{no}})$ 가지고 있다.

1. 각

x\in L_{\text{yes}}

x\in L_{\text{yes}}

x\in L_{\text{yes}}

x\in L_{\text{yes}}

{\

에 대해

x\in L_{\text{yes}}

확률 / 3/4로 앨리스가 승리하는 전략이 있다.

2. 각

x\in L_{\text{no}}

x\in L_{\text{no}}

x\in L_{\text{no}}

x\in L_{\text{no}}

{\

에 대해

x\in L_{\text{no}}

probability 3/4 확률로 밥이 승리하는 전략이 있다.

RG = EXP로 알려져 있다.^[10]^[11]

양자 게임

경쟁 프로버가 있는 양자 쌍방향 증명 시스템은 기존의 RG를 일반화한 것으로, 현재 심판이 다항 시간 생성 양자 회로로 제한되어 있고 선수들과 양자 정보를 교환할 수 있다.^[1] 따라서 QRG는 다음과 같은 문제로 볼 수 있다. 앨리스, 밥, 그리고 심판에게 어떤 진술이 주어진다. (양자 상태가 관련될 수도 있다.) 앨리스는 밥이 심판에게 그 진술이 거짓임을 납득시키려고 노력하는 동안 심판에게 그 진술이 진실이라고 설득하려고 애쓰고 있다. 심판은 양자 상태를 통해 찬성자에게 질문을 하고, 양자 상태에서 답변을 받으며, 양자 컴퓨터를 사용하여 수신된 양자 상태를 분석할 수 있다. 앨리스와 밥과 $n$ $n$ 라운드 $n$ 동안 의사소통을 한 후, 심판은 그 진술이 사실인지 거짓인지를 결정한다. 심판이 확률 probability 3/4로 정확한 판정을 내릴 수 있는 방법이 있다면 경기는 QRG에 들어간다. 이 확률은 ≥ 1 ε이다.^[5]

좀 더 공식적으로 QRG는 양자 참조 게임을 다음과 같이 정의한 모든 약속 문제에 대한 복잡도 등급을 나타낸다. $L=(L_{\text{yes}},L_{\text{no}})$ $x$ ${\displaystyle$ x $x$ 약속 문제 L $L=(L_{\text{yes}},L_{\text{no}})$ = $L=(L_{\text{yes}},L_{\text{no}})$ ( L $L=(L_{\text{yes}},L_{\text{no}})$ $L=(L_{\text{yes}},L_{\text{no}})$ $L=(L_{\text{yes}},L_{\text{no}})$ ) ${\displaystyle$ L $=(L_{\text{yes},$ $L_{\text{no}}}$ 은(는) 다항 시간 생성 양자 회로로 대표되는 심판이 있으면 QRG에 있다 $L=(L_{\text{yes}},L_{\text{no}})$ .

1.

x\in L_{\text{yes}}

x\in L_{\text{yes}}

x\in L_{\text{yes}}

x\in L_{\text{yes}}

{\

확률 ≥ 3/4로 앨리스가 승리하는 전략이 존재하며,

2.

x\in L_{\text{no}}

x\in L_{\text{no}}

x\in L_{\text{no}}

x\in L_{\text{no}}

{\

확률 ≥ 3/4로 밥이 승리하는 전략이 존재한다.

QRG = EXP — 심판이 양자 회로를 사용하고 양자 정보를 송수신할 수 있는 것은 심판에게 여분의 힘을 주지 않는 것으로 나타났다. EXP ⊆ QRG는 EXP = RG ⊆ QRG. Semidefinite 프로그램(SDP)을 활용한 QRG 제형으로 QRG ⊆ EXP를 입증한 데 따른 것이다.

세미데핀 프로그램 공식화

양자 참조 게임의 경우, 모든 상호작용이 끝날 때, 심판은 가능한 두 가지 결과 중 하나를 출력하여 앨리스가 $(b)$ 를 $(a)$ 표시한다 $\{a,b\}$ $(b)$ $\{a,b\}$ $,$ $\{a,b\}$ ${\$ $displaystyle$ $a$ $,$ $b\}$

$V(a)=1,V(b)=0$ ( $V(a)=1,V(b)=0$ ) $V(a)=1,V(b)=0$ = $V(a)=1,V(b)=0$ , $V(a)=1,V(b)=0$ V $V(a)=1,V(b)=0$ ( $V(a)=1,V(b)=0$ ) $V(a)=1,V(b)=0$ = $V(a)=1,V(b)=0$ $V(a)=1,V(b)=0$ 을 설정하면 앨리스의 최대 승리 확률인 양자 참조 게임이 발생한다 $V(a)=1,V(b)=0$ .

Using the same notation as the zero sum quantum refereed game as above, the referee is represented by operators $\{R_{a},R_{b}\}$ , Alice may pick a strategy from ${\displaystyle A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\$ $cdots n}$ , 및 $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ 1 $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$ )의 Bob은 ${\displaystyle B\in {\mathcal {S}_{n}({\mathcal {B}_{1\cdots n},{\mathcal {D}_{1\cdotsn}}}})$ 을 정의하십시오 $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}}

,

\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

여기서 $\operatorname {Tr} _{\mathcal {X}}(Z)$ $\operatorname {Tr} _{\mathcal {X}}(Z)$ $\operatorname {Tr} _{\mathcal {X}}(Z)$ ( $\operatorname {Tr} _{\mathcal {X}}(Z)$ ) $\operatorname {Tr} _{\mathcal{X}(Z)$ 은 $\operatorname {Tr}_{{{\mathcal X}}}(Z)$ 부분 트레이스 연산자다.

The referee outputs $a$ with probability $\langle A\otimes B,R_{a}\rangle =\langle B,\Omega _{a}(A)\rangle$ , and $b$ with probability ${\displaystyle \langle A\otimes B,R_{b}\rangle =\la$ $ngle B,\Oomega _{b}(A)\rangele$ $\langle A\otimes B,R_{b}\rangle =\langle B,\Omega _{b}(A)\rangle$ $\{\Omega _{a}(A),\Omega _{b}(A)\}$ { $\{\Omega _{a}(A),\Omega _{b}(A)\}$ $\{\Omega _{a}(A),\Omega _{b}(A)\}$ $\{\Omega _{a}(A),\Omega _{b}(A)\}$ ) $\{\Omega _{a}(A),\Omega _{b}(A)\}$ , $\{\Omega _{a}(A),\Omega _{b}(A)\}$ $\{\Omega _{a}(A),\Omega _{b}(A)\}$ ( $\{\Omega _{a}(A),\Omega _{b}(A)\}$ ${\디스플레이$ 스타일 $\{\Oomega _{a}(A),\Oomega _{b}(A)\}}}}}}}}}$ 는 앨리스의 전략을 심판의 전략과 병합한 공동 전략으로 볼 수 있다 $\{\Omega _{a}(A),\Omega _{b}(A)\}$ .

앨리스가 $A$ 선택한 어떤 주어진 전략 $A$ $A$ 의 경우, 밥의 최대 승산은 다음과 같다.

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

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

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

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

,

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

b

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

(

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

)

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

{\displaystyle \max _{B}\langle B,\Oomega _{B}(A)\angle

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

전략 대표성의 특성에 의해 다음과 같다.

\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})\}

.

따라서 앨리스의 우승 확률을 극대화하기 위해서는 가능한 모든 전략에 걸쳐 밥의 최대 우승 확률인 $p$ p {\ $displaystyle p}$ 을(를) 최소화할 필요가 있다 $.$ 그 다음 목표는 계산하는 것이다.

민 pΩ b(A)≤ pQA∈ Sn(1⋯, C1⋯ n), Sn(B1⋯, D1⋯ n){\displaystyle{\begin{배열}{rl}\min 및 co- Q∈, p\\{\text{대상}}및 대상을 말한다.\Omega _ᆩ(A)\leq pQ,\\&.A\in{{S\mathcal}}_{n}({{A\mathcal}}_{1\cdots n},{{C\mathcal}}_{1\cdots.

n}),\\&Q\in {\text{co-}{\mathcal

{

S}_{n}({\mathcal

{

B}_{1\cdots n},{\mathcal {D}_{1\cdots

n

}\end{array

이러한 최소화 문제는 다음과 같은 SDP 문제로 표현될 수 있다.^[1]

{\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}}

N), Ak∈ 포스 ⁡(C1⋯ k⊗는 1⋯ k)(1≤ k≤ n), Qkm그리고 4.9초 만 ∈ 포스 ⁡(D1⋯ k⊗ B1⋯ k)(1≤ k≤ n), Pkm그리고 4.9초 만 ∈ 포스 ⁡(D1⋯ k⊗ B1⋯ k)(1≤ k≤ n),{\displaystyle{\begin{배열}{rll}\min&\operatorname{Tr}(P_{1})\\{\text{대상}}&.Q,\\& _ᆩ(A_{n})\leq \Omega, \o

peratorname {Tr} _{\mathcal {C}_{k}}(A_{k})

=A_{k-1}\otimes I_{{\mathcal{A}_{k}_{k}&(2\leq k\leq n),\&\operatorname {Tr} _{{\mathc}_{1}(A_{1})=

I_{{\mathcal{A}_{1},\&Q_{k}=P_{k}\otimes I_{{{\mathcal {{D}_{k}}}&(1\leq k\leq n),\\\\\\\mathcal 이름 {Tr} _{{B}}{k}}}}}{k}(P_{k)

=Q_{k-1}&,(2\leqk\leq n),\\&.A_{k}\in\operatorname{포스}({\mathcal{C}}_{1\cdots k}\otimes A_{1\cdots k})&,(1\leqk\leq n),\\&amp을 말한다.Q_{k}\in\operatorname{포스}({{D}}_\mathcal{1\cdots k}\otimes B_{1\cdots k})&,(1\leqk\leq n),\\&amp을 말한다.P_{k}\in\operatorname{포스}({{D}}_\mathcal{1\cdots k}\otimes B_{1\cdots k})&,(1\leqk\leq n),\\\end{배열}}}.

이 SPD의 입력 및 출력 공간의 치수는 $n$ ${\displaystyle n$ 의 (텐서 제품 상태에서) 지수적이며, SDP는 입력 및 출력 공간의 치수에 크기 다항식을 가진다. 다항식 시간에 SDP를 해결할 수 있는 효율적인 알고리즘이 있기 때문에 그 QRG ⊆ EXP를 따른다.^[12]^[13]^[14]

참고 항목

참조

^ ^a ^b ^c ^d Gutoski, G; Watrous J (2007). Toward a general theory of quantum games. Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing. p. 565. arXiv:quant-ph/0611234. Bibcode:2006quant.ph.11234G. doi:10.1145/1250790.1250873. ISBN 9781595936318. S2CID 2329605.
^ "Let the quantum games begin". Physics World. 2002-10-02. Retrieved 2020-11-11.
^ Cleve, R; Hoyer P.; Toner B.; Watrous J. (2004). "Consequences and limits of nonlocal strategies". Proceedings of the 19th Annual IEEE Conference on Computational Complexity: 236–249. arXiv:quant-ph/0404076. Bibcode:2004quant.ph..4076C.
^ Brassard, G.; Broadbent A.; Tapp A. (2005). "Quantum pseudo-telepathy". Foundations of Physics. 35 (11): 1877–1907. arXiv:quant-ph/0407221. Bibcode:2005FoPh...35.1877B. doi:10.1007/s10701-005-7353-4. S2CID 7395322.
^ ^a ^b ^c ^d ^e Gutoski, Gus; Watrous, John (2005). "Quantum Interactive Proofs with Competing Provers". Stacs 2005. Lecture Notes in Computer Science. 3404. pp. 605–616. arXiv:cs/0412102. doi:10.1007/978-3-540-31856-9_50. ISBN 978-3-540-24998-6. S2CID 15662983.
^ Ghosh, Soumik (2020). "A study of one-turn quantum refereed games" (PDF). U Waterloo. Retrieved 2020-10-11.
^ 웹, 스탠포드Edu, 2020, http://web.stanford.edu/~oas/SI/QM/notes/SIQMWek3.pdf.
^ Kitaev, A; Watrous J (2000). "Parallelization, amplification, and exponential time simulation of quantum interactive proof system". Proceedings of the 32nd AMC Symposium on Theory of Computing: 608–617.
^ Watrous, J (2003). "PSPACE has constant-round quantum interactive proof systems". Theoretical Computer Science. 292 (3): 575–588. doi:10.1016/s0304-3975(01)00375-9.
^ Koller, D; Megiddo N (1992). "The complexity of two-person zero-sum games in extensive form". Games and Economic Behavior. 4 (4): 528–552. CiteSeerX 10.1.1.30.7625. doi:10.1016/0899-8256(92)90035-q.
^ Feige, U; Kilian J (1997). Making games short. Proceedings of the Twenty-Ninth Annual ACM Symbosium on Theory of Computing. pp. 506–516. CiteSeerX 10.1.1.5.1990. doi:10.1145/258533.258644. ISBN 978-0897918886. S2CID 15664449.
^ KHACHIYAN, L (1979). "A polynomial time algorithm in linear programming". Soviet Mathematics - Doklady. 20: 191–194.
^ Grötschel, M; Lovász L.; Schrijver, A. (1988). Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics. Springer. ISBN 978-3-642-97883-8.
^ Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior-Point Polynomial Algorithms in Convex Programming (PDF). SIAM Studies in Applied Mathematics. 13. doi:10.1137/1.9781611970791. ISBN 978-0-89871-319-0.

[general_qg-1] Gutoski, G; Watrous J (2007). Toward a general theory of quantum games. Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing. p. 565. arXiv:quant-ph/0611234. Bibcode:2006quant.ph.11234G. doi:10.1145/1250790.1250873. ISBN 9781595936318. S2CID 2329605.

[2] "Let the quantum games begin". Physics World. 2002-10-02. Retrieved 2020-11-11.

[3] Cleve, R; Hoyer P.; Toner B.; Watrous J. (2004). "Consequences and limits of nonlocal strategies". Proceedings of the 19th Annual IEEE Conference on Computational Complexity: 236–249. arXiv:quant-ph/0404076. Bibcode:2004quant.ph..4076C.

[4] Brassard, G.; Broadbent A.; Tapp A. (2005). "Quantum pseudo-telepathy". Foundations of Physics. 35 (11): 1877–1907. arXiv:quant-ph/0407221. Bibcode:2005FoPh...35.1877B. doi:10.1007/s10701-005-7353-4. S2CID 7395322.

[:0-5] Gutoski, Gus; Watrous, John (2005). "Quantum Interactive Proofs with Competing Provers". Stacs 2005. Lecture Notes in Computer Science. 3404. pp. 605–616. arXiv:cs/0412102. doi:10.1007/978-3-540-31856-9_50. ISBN 978-3-540-24998-6. S2CID 15662983.

[6] Ghosh, Soumik (2020). "A study of one-turn quantum refereed games" (PDF). U Waterloo. Retrieved 2020-10-11.

[:1-7] 웹, 스탠포드Edu, 2020, http://web.stanford.edu/~oas/SI/QM/notes/SIQMWek3.pdf.

[8] Kitaev, A; Watrous J (2000). "Parallelization, amplification, and exponential time simulation of quantum interactive proof system". Proceedings of the 32nd AMC Symposium on Theory of Computing: 608–617.

[9] Watrous, J (2003). "PSPACE has constant-round quantum interactive proof systems". Theoretical Computer Science. 292 (3): 575–588. doi:10.1016/s0304-3975(01)00375-9.

[10] Koller, D; Megiddo N (1992). "The complexity of two-person zero-sum games in extensive form". Games and Economic Behavior. 4 (4): 528–552. CiteSeerX 10.1.1.30.7625. doi:10.1016/0899-8256(92)90035-q.

[11] Feige, U; Kilian J (1997). Making games short. Proceedings of the Twenty-Ninth Annual ACM Symbosium on Theory of Computing. pp. 506–516. CiteSeerX 10.1.1.5.1990. doi:10.1145/258533.258644. ISBN 978-0897918886. S2CID 15664449.

[12] KHACHIYAN, L (1979). "A polynomial time algorithm in linear programming". Soviet Mathematics - Doklady. 20: 191–194.

[13] Grötschel, M; Lovász L.; Schrijver, A. (1988). Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics. Springer. ISBN 978-3-642-97883-8.

[14] Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior-Point Polynomial Algorithms in Convex Programming (PDF). SIAM Studies in Applied Mathematics. 13. doi:10.1137/1.9781611970791. ISBN 978-0-89871-319-0.

[1]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Search