Name
Abstract | ||
|---|---|---|
A two-player one-round binary game consists of two cooperative players who each repliesby one bit to a message that he receives privately; they win the game if both questions andanswers satisfy some predetermined property. A game is called entangled if the playersare allowed to share a priori entanglement. It is well-known that the maximum winningprobability (value) of entangled XOR-games (binary games in which the predeterminedproperty depends only on the XOR of the two output bits) can be computed by asemidefinite program. In this paper we extend this result in the following sense; if abinary game is uniform, meaning that in an optimal strategy the marginal distributionsof the output of each player are uniform, then its entangled value can be efficientlycomputed by a semidefinite program. We also introduce a lower bound on the entangledvalue of a general two-player one-round game; this bound depends on the size of theoutput set of each player and can be computed by a semidefinite program. In particular,we show that if the game is binary, ωq is its entangled value, and ωsdp is the optimumvalue of the corresponding semidefinite program, then 0.68 ωsdp q ≤ ωsdp. |
Year | Venue | Keywords |
|---|---|---|
2010 | Quantum Information & Computation | abinary game,binary game,entangled value,sdp q,semidefinite program,asemidefinite program,general two-player one-round game,corresponding semidefinite program,two-player one-round binary game,entangled binary game,entangled xor-games,satisfiability,quantum physics,lower bound |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Quantum entanglement,Upper and lower bounds,A priori and a posteriori,Quantum pseudo-telepathy,Example of a game without a value,Mathematics,Binary number | Journal | 10 |
Issue | ISSN | Citations |
11 | Quant. Inf. Comp. 10, 0911-0924 (2010) | 0 |
PageRank | References | Authors |
0.34 | 14 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salman Beigi | 1 | 56 | 11.43 |