Questions tagged [nonlocal-games]
The nonlocal-games tag has no usage guidance.
45 questions
1
vote
1
answer
95
views
What states are valid GHZ-game states?
The GHZ game involves three non-communicating players, Alice, Bob, and Carol. They each receive a bit, $r,s,t$ with the guarantee that $r\oplus s\oplus t=0$ (i.e. with the guarantee that there are an ...
- 161
1
vote
0
answers
47
views
CHSH rigidity for sharing mixed state
In the CHSH game the best winning rate $\omega^{*}=\frac{2+\sqrt{2}}{4}$ and if the players achieve the winning rate of $\omega^{*}-\epsilon$ by sharing a pure two-qubit state $|\psi\rangle$,then the ...
- 275
1
vote
0
answers
26
views
CHSH optimal winning strategy by matrix derivation for observables
For CHSH games if the players share EPR state then the maximal Bell violation is $2\sqrt{2}$ which can be proved by Tsireson's bound(here we consider the case where the shared state is fixed to be EPR)...
- 275
2
votes
0
answers
37
views
Accuracy of Instructions for a Student to Act as a Qubit for the CHSH Game
My goal
I am an educator attempting to demonstrate an optimal quantum strategy for the CHSH game in a math club meeting of students. Students will play the roles of Alice, Bob, the Referee, and Qubits....
- 121
1
vote
1
answer
44
views
Using group representation to prove the rigidity of CHSH, puzzled in one step
I am reading this lecture note: UCSD Summer school notes
Quantum multiplayer games, testing and rigidity. In the proof of the following theorem:
the group $H=\pm\{I,X,Z,XZ\}$ is considered. Let $$f(\...
- 275
1
vote
1
answer
93
views
The rationale for the payoff function of the CHSH game
The payoff of the CHSH game is the characteristic function $\mathbf 1(x\cdot y=(a+b \mod 2))$. What is the rationale for picking this particular payoff function? Is it a consequence of the CHSH ...
- 231
1
vote
0
answers
69
views
Super-dense coding by adding quantum correlations between classical bits
Consider the following non-local game between Alice, Bob (who are spatially separated but share a maximally entangled state) and a referee:
Referee samples two question bits "$x,y$" and ...
- 11
1
vote
1
answer
119
views
Finding the violating bound of CHSH using the first level of NPA hierarchy on MATLAB
I've been trying to implement the NPA hierarchy in MATLAB using CVX library. To start off with, I thought of finding the bound of CHSH using the first level of NPA hierarchy. I represented my gram ...
0
votes
0
answers
47
views
Non-local games: A game has a perfect local density if and only if it has a perfect deterministic strategy
This is about 'Two Players Cooperative Games':
Such a game is described by two input sets $I_A, I_B$, two output set $O_A, O_B$, and a function $V : I_A \times I_B \times O_A \times O_B \to \{0, 1\}$, ...
- 231
3
votes
1
answer
166
views
CHSH game sharing a general state
For the CHSH game if the players share a general two-qubit state $\rho = \frac{1}{4} \sum_{i,j = 0}^{3} M_{ij} (\sigma_i \otimes \sigma_j)$, then the maximal violation is $2 \sqrt{\lambda_1^2 + \...
- 275
1
vote
1
answer
74
views
Can a quantum state be certified using self-test?
I am reading the paper Certifying almost all quantum states with
few single-qubit measurements. The main result of the paper (Theorem 1) is that
given an $n$-qubit target pure state $|\psi\rangle$ and ...
- 275
2
votes
1
answer
238
views
Why are only projective measurements considered in nonlocal games to get optimal strategy?
In the CHSH game where Alice and Bob share one EPR the optimal strategy is to measure the following observables $A_0=Z,A_1=X,B_0=1/\sqrt{2}(X+Z),B_1=1/\sqrt{2}(X-Z)$ depending on their question. We ...
- 275
1
vote
1
answer
75
views
CHSH game sharing more general states
In the CHSH game, when the players share EPR states they can achieve best the winning rate of approximately 85% which can be proved through the Tsirelson's bound. I wonder what the best winning rate ...
- 275
4
votes
0
answers
194
views
Can Alice and Bob convince the cops that they don't share any entanglement?
Suppose Alice and Bob are arrested for killing Eve, and are taken to two different interrogation rooms. The police quiz Alice and separately Bob, asking them a bunch of different questions along the ...
- 14.4k
1
vote
0
answers
23
views
Magic square operator's measurement product
In the talk by Andrea Coladangelo (link) at 29:30, he claims that if $X_1X_2X_3 = I$, such that the operators commute. Then, the product of the measurement results on an EPR pair of the same dimension ...
- 391
2
votes
1
answer
85
views
Why are randomized strategies convex mixtures of deterministic ones?
I am looking for a proof of this fact regarding randomized strategies of the CHSH game:
"... allowing randomized strategies can not help them to get a better success probability. This is because ...
- 231
2
votes
0
answers
28
views
Spreading entanglement over multiple systems
Question: imagine that Alice and Bob share, say, one ebit $\lvert\Phi_+\rangle_\text{AB}$, and that they are only able to carry out local operations and classical communication. Is there an algorithm ...
7
votes
1
answer
617
views
Worst Bell inequality violation with non-maximally entangled state?
I'm familiar with CHSH game and the strategy that allows Alice and Bob to succeed with a probability of $$\frac{1+\tfrac{1}{\sqrt 2}}{2}\approx 85\%$$ if they share a maximally entangled state such as ...
-1
votes
1
answer
73
views
In the CHSH game, why do $a,b$ need to be the same unless $x=y=1$?
In this lecture, in the CHSH game section, it is claimed that a and b must be the same unless x and y are both 1. Can someone explain why? I see it the other way around.
2
votes
2
answers
393
views
Why is an X gate a quantum coin flip?
I am reading this page of Qiskit's textbook. I noticed that it extends coin games to quantum computers by defining an $X$ gate to be a classical coin flip. However, I do not understand this. For ...
- 433
1
vote
1
answer
93
views
XOR game quantum strategy expected payoff?
I am reading Thomas Vidick, Quantum multiplayer games, testing and rigidity. On top of p.4,
$$\text{E}[a\cdot b] = \sum_{i,j\in \{0,1\}}(-1)^{i+j}\text{Pr}\big((a,b)=(i,j)\big)$$
I do not understand ...
- 231
2
votes
1
answer
119
views
Local operation to change the maximally mixed 2 qubit state to $\frac{1}{2}(|01\rangle \langle01|+|10\rangle \langle10|)$?
A paper I read talked about local interactions on only a single subsystem, leaving the state of that subsystem invariant, and the observation of this requiring the whole state.
Here is the paper
Now ...
- 1,232
3
votes
1
answer
617
views
What is the quantum strategy required to win the Magic Squares game
This question is about the Magic Squares game. Links here, here and link here in which two players try to win a game. It's a cooperative game - either the team wins or the team loses. It is claimed ...
- 701
2
votes
2
answers
667
views
How can one show that Alice's and Bob's answers agree at the intersection cells of Mermin-Peres' "magic square"?
This question is along the lines of Problems in understanding the solution for "Mermin–Peres Magic Square Game"
How can one show that Alice's and Bob's answers agree at the intersection ...
- 29
5
votes
0
answers
69
views
Who first studied nonlocal games with probabilistic predicate?
For some background, a nonlocal game consists of questions $x,y\in X,Y$ and answers $a,b \in A,B$; the pair of questions $x,y$ is asked with probability $\mu(x,y)$, and a referee accepts the pair of ...
- 3,073
1
vote
0
answers
123
views
Modified CHSH game - Does entanglement help?
I'm thinking about a modified version of the CHSH game and I'm trying to convince myself that in this case, entanglement cannot be used to gain an advantage or else it would imply signalling is ...
- 155
3
votes
1
answer
212
views
How are Franson Interferometers used to prove security in Photonic QKD Experiments?
I am currently reading this paper about Quantum Key Distribution Protocols which use Franson Interferometers to secure against eavesdroppers. I am having trouble understanding how the interferometers ...
4
votes
2
answers
291
views
How does a classical computer simulate nonclassical correlations?
This may be a dumb question, if so please forgive me, it is late at night.
I have learned that a classical computer can simulate a quantum computer in exponential time and space, but classical ...
- 609
4
votes
1
answer
1k
views
Problems in understanding the solution for "Mermin–Peres Magic Square Game"
I am referring to the article Advanced Topics in Quantum Information Theory exercise 4 and to the MS Quantum Kata MS-Quantum-Kata which describes a solution for the Mermin–Peres Magic Square Game.
I ...
- 105
3
votes
1
answer
229
views
MS Quantum Katas - Measurements Task 2.3 - problems in understanding the solution
I am referring to the MS Quantum Katas, Measurements, 2.3 Peres/Wootters game
I have big problems to understand the solution.
The task is defined as:
--begin
Input: A qubit which is guaranteed to be ...
- 105
6
votes
1
answer
335
views
Is Connes' Embedding Problem akin to the word problem for finitely presented groups?
The complexity class $\mathrm{MIP^*}$ includes the set of languages that can be efficiently verified by a classical, polynomially-bounded verifier, engaging with two quantum provers that can share (...
- 14.4k
2
votes
2
answers
180
views
Using Qiskit with Blender
I want to use Blender and Blender Python Scripts working with Qiskit.
(want to make 3D creations) (www.blender.org)
How can I do this ?
(because when I try to install Qiskit inside Blender Python, it ...
- 21
6
votes
1
answer
246
views
Why is $P(1,2)_{\text{same}} = \frac{1}{4}$ and not $\frac{1}{2}$ in Preskill's Bell experiment?
Context:
Three coins on the table. Each is either heads or tails. You can
uncover any one of the three coins, revealing whether it is heads or
tails but then you choose two the other two coins ...
- 17.8k
9
votes
2
answers
2k
views
Optimal strategy to a quantum state game
Consider the following game:
I flip a fair coin, and depending on the outcome (either heads/tails), I'll give you one of the following states:
$$|0\rangle \text{ or } \cos(x)|0\rangle + \sin(x)|1\...
- 91
5
votes
1
answer
9k
views
How can quantum computing win 97% of times in coin flipping experiment?
I'm new to this field of science. I'm curious about how quantum computing can win 97% of times in a coin flipping experiment?
Refer this link: Ted Talk by Shohini Ghose
To give an idea about how ...
- 153
9
votes
3
answers
2k
views
Proof of optimality for CHSH game classical strategy
I'm aware that the optimality of the quantum strategy for the CHSH game is given by Tsirelson's bound, but presentations all skip over the (admittedly much less interesting) proof of the classical ...
- 4,228
3
votes
2
answers
331
views
How could a quantum computer perform nimber arithmetic?
I am interested in combinatorial game theory & was doing some research on quantum combinatorial games. This lead me to wondering how a quantum computer might be able to perform nimber arithmetic (...
- 3,342
3
votes
1
answer
196
views
How are nonlocal games used in device-independent quantum cryptography?
As I understand it, device-independent quantum cryptography enables you to safely perform cryptographic operations without necessarily trusting the quantum device on which they are performed. Nonlocal ...
- 4,228
3
votes
0
answers
95
views
13
votes
3
answers
633
views
Are correlations stronger than those allowed by quantum mechanics possible?
We know how a quantum correlation setup can help us with a better probability of winning games like the CHSH. But what is the upper bound that physics can allow? Is it the quantum correlation setup? ...
- 1,795
4
votes
1
answer
152
views
Using XOR games to benchmark quantum computers
In an answer to a previous question, What exactly are Quantum XOR Games?, ahelwer states:
One application of xor games is self-testing: when running algorithms on an untrusted quantum computer, you ...
- 3,342
7
votes
1
answer
456
views
In which paper was the CHSH game first presented?
The CHSH inequality was presented in the paper Proposed Experiment to Test Local Hidden-Variable Theories published in 1969 by J.F. Clauser, M.A. Horne, A. Shimony, and R.A. Holt. I'm interested in ...
- 4,228
5
votes
3
answers
332
views
Algorithm-based game project to introduce quantum computing
I am currently working on a quantum computing subject for my coding school, and I had some questions for you. My objective would be to introduce students to quantum computing with an algorithmic ...
- 51
16
votes
1
answer
1k
views
What exactly are Quantum XOR Games?
I have done some research & found a few different papers that discuss xor games (classic & quantum). I am curious if someone could give a concise introductory explanation as to what exactly ...
- 3,342
7
votes
1
answer
255
views
Has anyone analyzed multi-round nonlocal games?
The traditional definition of a nonlocal game is restricted to having two players and one round (e.g., here), but it is natural to consider a more general class of games that may have more than two ...
- 518