0000000001143866
AUTHOR
Madars Virza
Worst Case Analysis of Non-local Games
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input x i to the i th player who then responds by sending an answer a i to the referee. The players win if the answers a i satisfy a condition that may depend on the inputs x i .
Advantage of Quantum Strategies in Random Symmetric XOR Games
Non-local games are known as a simple but useful model which is widely used for displaying nonlocal properties of quantum mechanics. In this paper we concentrate on a simple subset of non-local games: multiplayer XOR games with 1-bit inputs and 1-bit outputs which are symmetric w.r.t. permutations of players.
Dažu kvantu spēļu analīze
Viens no veidiem, kā pamatot kvantu pasaules atšķirību no klasiskās ir kvantu spēles, kurās spēlētāju uzvaras varbūtība ir lielāka, ja tie lieto kopīgus kvantu stāvokļus. Darba mērķis ir atrast jaunus kvantu spēļu piemērus un metodes to analīzei. Šajā darbā ir veikta divu konkrētu spēļu analīze, kā arī pētīta nejaušo simetrisko spēļu klase. Tiek dots pilnīga Ardehali spēles klasiskā gadījuma analīze jebkuram spēlētāju skaitam. EQUAL-EQUAL spēle tiek analizēta novitārā ``worst-case'' modelī un pierādīts, ka tai ne ``worst-case'', ne ``average-case'' varbūtību sadalījumiem nav kvantu priekšrocības, bet tāda parādās nesimetriskiem sadalījumiem. Tiek pierādīti arī kvantu un klasiskie novērtējum…
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1−o(1) fraction of all 2-player XOR games.
On symmetric nonlocal games
Abstract Nonlocal games are used to display differences between the classical and quantum world. In this paper, we study symmetric XOR games, which form an important subset of nonlocal games. We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player. We illustrate those methods with two examples. One example is an N -player game (due to Ardehali (1992) [3] ) that provides the maximum quantum-over-classical advantage. The second example comes from generalization of CHSH game by letting the referee to choose arbitrary symmetric distribution of players’ inputs.
Galuā lauku realizācija, izmantojot vispārējās programmēšanas paradigmu
Darbs ``Galuā lauku realizācija, izmantojot vispārējās programmēšanas paradigmu'' apraksta bibliotēkas, kas ļauj darboties ar patvaļīgiem galīgajiem laukiem $GF(p^n)$, izstrādi. Tiek atbalstītas visas aritmētiskās operācijas ar lauka elementiem, kā arī kvadrātsaknes vilkšana un lauka parametru ģenerēšana. Bibliotēka dota C++ izejas tekstu veidā, ir strukturēta un savietojama ar vairākiem kompilatoriem vairākās arhitektūrās. Atslēgvārdi: Galuā lauki, galīgie lauki, galīga lauka ģenerēšana, C++
Sensitivity versus block sensitivity of Boolean functions
Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.
Worst case analysis of non-local games
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input $x_i$ to the $i^{th}$ player who then responds by sending an answer $a_i$ to the referee. The players win if the answers $a_i$ satisfy a condition that may depend on the inputs $x_i$. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study …
Quantum strategies are better than classical in almost any XOR game
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.